Questo capitolo chiude il percorso del corso sul reinforcement learning e presenta la famiglia di metodi più importante dell’intera area: il temporal-difference learning (TD). I capitoli precedenti hanno messo a disposizione due strumenti agli estremi opposti dello spettro. Da un lato la programmazione dinamica (DP), che risolve esattamente le equazioni di Bellman ma richiede la conoscenza completa della dinamica dell’MDP; dall’altro i metodi Monte Carlo (MC), che imparano dall’esperienza pura senza alcun modello, ma possono aggiornare le stime solo alla fine di un episodio completo. Il TD learning combina il meglio dei due mondi: come MC impara da campioni di interazione, senza modello; come DP aggiorna una stima usando un’altra stima, cioè fa bootstrapping, e per questo può imparare a ogni singolo passo, anche in problemi che non terminano mai. Il percorso del capitolo: prima il difetto strutturale di Monte Carlo che motiva il cambio di approccio, poi l’idea di bootstrapping e l’algoritmo di prediction TD(0) con l’esempio del random walk, quindi il confronto sistematico MC vs TD vs DP lungo gli assi bias/varianza e sampling/bootstrapping. Dalla prediction si passa al control: SARSA (on-policy) e Q-learning (off-policy), con il confronto sul cliff walking che ne rivela la differenza di carattere. Seguono le estensioni a più passi (n-step TD, $\lambda$-return, eligibility traces), il quadro riassuntivo finale DP vs MC vs TD e una sezione di esercizi d’esame interamente svolti, con la procedura meccanica per eseguire a mano gli update di TD(0), SARSA e Q-learning su un episodio dato: una tipologia d’esame molto frequente.

Riferimenti sul testo: Sutton e Barto, Reinforcement Learning: An Introduction, capitoli 6 e 7. Materiale complementare consigliato: il corso online Sample-based Learning Methods (Coursera).

1. Il difetto di Monte Carlo: aspettare la fine dell’episodio#

1.1 Dove siamo: modelli, campioni ed episodi#

Conviene richiamare in una riga che cosa sanno fare i metodi visti finora e a quale prezzo:

• la programmazione dinamica (policy iteration, value iteration) applica le equazioni di Bellman calcolando valori attesi esatti su tutti i successori; per farlo richiede la conoscenza della dinamica one-step $p(s', r \mid s, a)$, che nei problemi reali quasi mai è disponibile;
• i metodi Monte Carlo eliminano il modello: stimano le value function come medie empiriche dei return osservati interagendo con l’ambiente. Il prezzo è che il return $G_t$ si conosce solo quando l’episodio è finito.

Il vincolo di Monte Carlo ha due conseguenze immediate. Primo, MC si applica solo a task episodici: se l’interazione non termina mai, il return completo non è mai osservabile e non c’è nulla da mediare. Secondo, anche nei task episodici l’apprendimento avviene solo a fine episodio: durante l’episodio l’agente accumula esperienza ma non aggiorna nulla.

C’è poi una terza conseguenza, più sottile e in pratica spesso decisiva: se raggiungere lo stato terminale è difficile per la policy iniziale, Monte Carlo può restare a lungo senza imparare niente del tutto. All’inizio dell’apprendimento la policy è tipicamente casuale, perché non si sa nulla del problema; finché la policy casuale non inciampa per caso nello stato terminale, nessun episodio si completa, nessun return viene osservato, nessun aggiornamento viene eseguito. Su problemi in cui il goal richiede una sequenza di azioni lunga e specifica, la probabilità di completare il primo episodio per puro caso può essere minuscola.

In parole semplici: Monte Carlo è uno studente che si rifiuta di trarre conclusioni finché la partita non è finita. Se la partita è lunghissima, o se con mosse a caso non si arriva mai alla fine, lo studente non impara mai nulla. Serve un metodo capace di imparare qualcosa da ogni singola mossa, senza aspettare il fischio finale.

1.2 L’esempio del windy gridworld#

Il problema che esemplifica perfettamente questa difficoltà è il windy gridworld. Si tratta di una griglia di 7 righe e 10 colonne: l’agente parte da uno stato iniziale $S$ a metà del lato sinistro e deve raggiungere un goal $G$ a metà griglia, verso destra. Le azioni sono i quattro movimenti (su, giù, destra, sinistra), ogni passo costa reward $R_t = -1$ e il discount è $\gamma = 1$: massimizzare il return equivale a minimizzare il numero di passi per arrivare al goal. La particolarità è il vento: in ogni colonna centrale della griglia soffia un vento verso l’alto la cui intensità è indicata sotto la colonna stessa (nella versione classica le intensità sono $0,0,0,1,1,1,2,2,1,0$). Quando l’agente esegue un movimento partendo da una colonna ventosa, oltre allo spostamento scelto subisce uno spostamento aggiuntivo verso l’alto pari all’intensità del vento.

Il vento cambia radicalmente la geometria del problema. Le colonne immediatamente adiacenti al goal hanno vento forte: avvicinandosi al goal da sinistra, l’agente viene sistematicamente spinto sopra il goal e non riesce a centrarlo. L’unica strategia vincente è un lungo giro: attraversare tutta la zona ventosa lasciandosi trasportare verso l’alto, superare il goal, raggiungere le colonne di destra dove il vento è debole o assente, scendere, e rientrare sul goal da destra. Il cammino ottimo richiede una quindicina di passi ed è una sequenza tutt’altro che ovvia.

Ecco il problema per Monte Carlo: partendo con una policy casuale, la probabilità di completare per caso questa lunga manovra e raggiungere il goal è estremamente bassa. Finché ciò non accade, l’episodio non termina e MC non esegue nemmeno un aggiornamento: l’agente vaga per la griglia accumulando esperienza che non viene sfruttata. Un metodo che imparasse durante l’episodio, passo dopo passo, potrebbe invece iniziare subito a costruire conoscenza, per esempio su quali celle sono lontane dal goal, ancora prima di averlo mai raggiunto.

Idea chiave: la motivazione del temporal-difference learning è imparare dall’interazione a ogni passo, senza attendere il return completo: imparare durante la partita di scacchi invece che solo al termine, imparare da sequenze di interazione anche incomplete, imparare persino in problemi che non terminano mai.

2. Bootstrapping e TD(0)#

2.1 Dall’update Monte Carlo al target TD#

Il punto di partenza è la forma incrementale dell’update Monte Carlo per la state-value function. Dopo ogni episodio, per ogni stato visitato $s_t$, MC aggiorna la stima verso il return osservato:

$$V(s_t) \leftarrow V(s_t) + \alpha \left( G_t - V(s_t) \right)$$

dove $\alpha$ può essere il fattore $1/N(s_t)$ che realizza esattamente la media incrementale dei return, oppure un learning rate costante che produce una media pesata verso le osservazioni recenti. In entrambi i casi l’ingrediente indispensabile è $G_t$, il return osservato, disponibile solo a episodio concluso.

La via d’uscita viene dall’equazione di Bellman. Il return si decompone ricorsivamente come $G_t = R_{t+1} + \gamma G_{t+1}$, e prendendo il valore atteso si ottiene l’equazione di aspettativa

$$V^{\pi}(s) = \mathbb{E}_{\pi}\left[ R_{t+1} + \gamma V^{\pi}(S_{t+1}) \mid S_t = s \right]$$

La programmazione dinamica calcola questo valore atteso esattamente, usando la dinamica one-step per mediare su tutti i possibili successori. Senza modello quel valore atteso non si può calcolare, ma si può campionare: una singola transizione osservata $(s_t, a_t, r_{t+1}, s_{t+1})$ fornisce un campione del reward immediato, $r_{t+1}$, e per la parte futura si può usare la stima corrente del valore dello stato d’arrivo, $V(s_{t+1})$. La quantità $r_{t+1} + \gamma V(s_{t+1})$ diventa così una nuova stima del return da $s_t$, costruita con un solo passo di esperienza reale, e può sostituire $G_t$ nell’update di Monte Carlo.

La lettura intuitiva dell’update: $V(s_t)$ è “quanto mi aspettavo di guadagnare da $s_t$”; dopo un passo reale ho in mano un’informazione fresca, il reward $r_{t+1}$ effettivamente incassato e lo stato $s_{t+1}$ in cui sono davvero finito; la somma $r_{t+1} + \gamma V(s_{t+1})$ è “quanto sembra valere $s_t$ alla luce di quello che è appena successo”. Se le due stime non coincidono, la differenza $\delta_t$ è un errore, e la stima viene corretta di una frazione $\alpha$ di quell’errore, esattamente come nella discesa del gradiente stocastica si corregge un peso di una frazione dell’errore di predizione.

Idea chiave: il meccanismo si chiama bootstrapping: aggiornare una stima usando un’altra stima. Il TD target contiene $V(s_{t+1})$, che non è il valore vero ma la stima corrente, cioè proprio l’oggetto che si sta imparando: l’algoritmo si “tira su da solo” usando la propria conoscenza parziale come bersaglio. DP fa bootstrapping con il modello; TD fa bootstrapping con un campione.

In parole semplici: invece di aspettare la fine dell’episodio per sapere quanto ha reso uno stato, TD fa un solo passo, guarda il premio incassato e quanto pensa che valga il nuovo stato, e usa questa somma come “verità provvisoria” per correggere la stima dello stato di partenza. È come aggiornare la stima della durata di un viaggio a ogni tappa, usando la previsione residua dal punto in cui ci si trova, invece che solo all’arrivo.

2.2 L’algoritmo TD(0) per la policy evaluation#

L’update si traduce in un algoritmo di policy evaluation di semplicità estrema: non serve memorizzare episodi, non serve calcolare return, non servono medie; a ogni passo si osserva la transizione e si aggiorna un singolo valore.

TD(0) policy evaluation
Input: policy pi da valutare, learning rate alpha, discount gamma
Inizializza V(s) arbitrariamente per ogni s (V(terminale) = 0)
Ripeti per ogni episodio:
    inizializza lo stato s
    Ripeti per ogni passo dell'episodio:
        a  <- azione scelta da pi in s
        esegui a; osserva il reward r e il nuovo stato s'
        V(s) <- V(s) + alpha * ( r + gamma * V(s') - V(s) )
        s <- s'
    finché s è terminale

L’aggiornamento consuma la sequenza di interazione $s, a, r, s', a', r'', \dots$ una transizione alla volta: appena il passo si conclude, il valore dello stato appena lasciato viene corretto e si prosegue. Tre osservazioni:

• l’apprendimento è online: avviene durante l’episodio, a ogni passo, e non richiede che l’episodio si concluda;
• l’algoritmo funziona anche su sequenze incomplete (dati troncati, interazioni interrotte) e su task continui, dove uno stato terminale non esiste affatto: basta togliere il ciclo esterno sugli episodi;
• l’algoritmo è model-free: della dinamica dell’ambiente non usa nulla, solo le transizioni osservate.

2.3 Il ruolo del learning rate e la convergenza#

In Monte Carlo, con $\alpha = 1/N(s)$ l’update realizza la media aritmetica esatta dei return. In TD la scelta di $\alpha$ è più delicata, perché il target stesso cambia nel tempo (il bootstrapping usa stime che si stanno aggiornando). Le regole pratiche:

• un $\alpha$ troppo piccolo rende l’apprendimento lento: ogni osservazione sposta pochissimo le stime;
• un $\alpha$ troppo grande rende l’apprendimento inizialmente rapido ma impedisce la convergenza fine: le stime continuano a oscillare intorno al valore vero e l’errore asintotico resta più alto;
• il valore migliore è dipendente dal problema, e una strategia comune è far decrescere $\alpha$ nel tempo.

La teoria conferma l’intuizione: con la rappresentazione tabellare, TD(0) converge a $V^{\pi}$ purché tutti gli stati continuino a essere visitati e i learning rate soddisfino le condizioni classiche dell’approssimazione stocastica (condizioni di Robbins-Monro), cioè $\sum_t \alpha_t = \infty$ e $\sum_t \alpha_t^2 < \infty$: passi complessivamente infiniti, ma di ampiezza che si spegne abbastanza in fretta. La sequenza $\alpha_t = 1/t$ le soddisfa; un $\alpha$ costante no, e infatti con $\alpha$ costante le stime fluttuano in un intorno del valore vero senza fissarsi.

3. TD(0) all’opera: il random walk#

3.1 Il problema#

Un esempio minimale permette di osservare TD(0) e Monte Carlo fianco a fianco. Il random walk è una catena di cinque stati disposti in linea, $A, B, C, D, E$, con due stati terminali agli estremi: $T_1$ a sinistra di $A$ e $T_2$ a destra di $E$. Lo stato iniziale è $C$, quello centrale. La policy da valutare è quella casuale: in ogni stato, sinistra o destra con probabilità $1/2$. Il reward è $0$ su ogni transizione, tranne quella che entra nel terminale destro $T_2$, che vale $+1$; il discount è $\gamma = 1$.

Con questa struttura la value function ha un’interpretazione trasparente: $V^{\pi}(s)$ è la probabilità di terminare a destra partendo da $s$, perché il return è $1$ se e solo se l’episodio finisce in $T_2$. La dinamica è nota (è un problema giocattolo) e i valori veri si calcolano esattamente:

$$V^{\pi}(A) = \tfrac{1}{6}, \quad V^{\pi}(B) = \tfrac{2}{6}, \quad V^{\pi}(C) = \tfrac{3}{6}, \quad V^{\pi}(D) = \tfrac{4}{6}, \quad V^{\pi}(E) = \tfrac{5}{6}$$

crescenti da sinistra a destra, com’è naturale: più si è vicini a $T_2$, più è probabile finirci.

3.2 La dinamica dell’apprendimento: propagazione contro attesa#

Si inizializzano tutte le stime a $V(s) = 0{,}5$ (una scelta che rende leggibile l’evoluzione, ma nulla cambierebbe partendo da zero) e si fanno girare in parallelo TD(0) e Monte Carlo sugli stessi episodi. L’evoluzione rivela le differenze di carattere dei due metodi.

Fase iniziale. Finché tutte le stime interne valgono $0{,}5$, le transizioni tra stati non terminali non producono alcun aggiornamento TD: il TD error è $\delta_t = 0 + 1 \cdot 0{,}5 - 0{,}5 = 0$ (reward nullo, $\gamma = 1$, valori uguali). Gli unici errori non nulli compaiono sulle transizioni verso i terminali, il cui valore è zero per convenzione: entrare in $T_2$ produce $\delta = 1 + 0 - 0{,}5 = +0{,}5$, entrare in $T_1$ produce $\delta = 0 + 0 - 0{,}5 = -0{,}5$. All’inizio, quindi, sia TD sia MC imparano soltanto in coda all’episodio, ma con una differenza cruciale: al termine dell’episodio Monte Carlo aggiorna tutti gli stati visitati lungo la traiettoria (ognuno verso il return osservato), mentre TD aggiorna solo l’ultimo stato, quello adiacente al terminale. Sul primissimo episodio MC sembra quindi più veloce.

Regime di propagazione. Il vantaggio si ribalta subito dopo. Appena le stime non sono più tutte uguali, ogni transizione tra stati interni genera un TD error non nullo e quindi un aggiornamento: se $V(E)$ si è alzato, la prossima volta che l’agente passa da $D$ a $E$ il target $0 + V(E)$ supera $V(D)$ e anche $V(D)$ si alza. L’informazione portata dal reward finale si propaga all’indietro di stato in stato, un passo per ogni transizione, a ogni visita, senza bisogno di raggiungere il terminale. Monte Carlo, al contrario, tocca i valori solo una volta per episodio, e ogni stato impara esclusivamente dai return dei propri episodi. Sul medio periodo TD riduce l’errore molto più in fretta.

In parole semplici: TD sparge la conoscenza come un passaparola: appena uno stato “sa qualcosa” (il suo valore si è mosso), lo comunica a ogni vicino che lo attraversa. Monte Carlo invece consegna la notizia per posta solo a fine episodio, a ciascuno stato separatamente. All’inizio la posta sembra più efficiente, ma a regime il passaparola continuo vince.

3.3 Curve d’errore ed effetto di α#

Misurando l’errore quadratico medio delle stime rispetto ai valori veri, mediato sui cinque stati, in funzione del numero di episodi, si osserva che:

• le curve di TD stanno sistematicamente sotto quelle di MC a parità di episodi: su questo problema TD impara più in fretta;
• per TD, il valore di $\alpha$ regola il compromesso già discusso: con $\alpha$ grande (per esempio $0{,}15$) la discesa iniziale è ripidissima ma la curva si assesta su un errore residuo più alto; con $\alpha$ piccolo la discesa è lenta ma l’errore finale è migliore; nell’esperimento il compromesso migliore risulta intorno ad $\alpha = 0{,}05$;
• Monte Carlo, pur partendo con l’apparente vantaggio del primo episodio, riduce l’errore molto lentamente, perché ogni episodio fornisce un solo aggiornamento per stato e i return della policy casuale sono rumorosi.

Il valore ottimale di $\alpha$ è dipendente dal problema, e come anticipato una schedule decrescente di $\alpha$ permette di avere sia la rapidità iniziale sia la precisione asintotica.

4. MC vs TD vs DP: un confronto sistematico#

4.1 Quando e dove si può imparare#

Il primo asse di confronto tra TD e MC riguarda i vincoli operativi, ed è tutto a favore di TD:

• TD impara prima di conoscere l’esito finale: aggiorna a ogni passo; MC deve attendere la fine dell’episodio, quando il return diventa noto;
• TD impara anche senza l’esito finale: funziona su sequenze incomplete (dati troncati, esperienza interrotta); MC richiede sequenze complete;
• TD funziona in ambienti continui (senza terminazione); MC funziona solo in ambienti episodici.

4.2 Bias e varianza dei target#

Il secondo asse è statistico e riguarda la qualità del target usato nell’update. I due metodi correggono $V(S_t)$ verso bersagli diversi, e i bersagli hanno proprietà opposte.

Il target MC ha bias più basso. Il return osservato $G_t = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T$ è per definizione una realizzazione della variabile casuale di cui $V^{\pi}(S_t)$ è il valore atteso: è quindi uno stimatore non distorto (unbiased) di $V^{\pi}(S_t)$. Il TD target $R_{t+1} + \gamma V(S_{t+1})$ sarebbe anch’esso non distorto se al posto di $V$ ci fosse il valore vero $V^{\pi}$; ma $V$ è la stima corrente, in generale sbagliata ($V(S_{t+1}) \neq V^{\pi}(S_{t+1})$), e quindi il TD target è uno stimatore distorto (biased). È il prezzo del bootstrapping: usare come bersaglio qualcosa che si sta ancora imparando introduce un errore sistematico, che si riduce solo man mano che le stime migliorano.

Il target TD ha varianza più bassa. Il return $G_t$ dipende dall’intera coda della traiettoria: molte azioni casuali, molte transizioni casuali, molti reward casuali, i cui effetti si accumulano; la sua varianza può essere molto grande, e con pochi campioni la media empirica può essere lontanissima dal valore vero. Il TD target dipende da una sola azione casuale, una sola transizione e un solo reward: la quantità di casualità che entra in ogni singolo aggiornamento è minima, e le stime evolvono in modo molto più stabile.

Idea chiave: MC e TD occupano i due estremi di un compromesso bias-varianza sul target dell’update: MC è non distorto ma rumoroso, TD è distorto ma stabile. Nessuno dei due domina l’altro in assoluto; quale funzioni meglio dipende dal problema, dalla lunghezza degli episodi e dalla qualità dell’inizializzazione.

In parole semplici: il target di Monte Carlo è una testimonianza diretta (“ecco quanto ho davvero guadagnato fino alla fine”), sincera ma soggetta a enormi colpi di fortuna e sfortuna. Il target di TD è una stima ragionata (“ecco il premio di oggi più quanto credo valga il domani”), molto meno ballerina ma inquinata dagli errori delle credenze attuali.

4.3 Conseguenze pratiche: inizializzazione e function approximation#

Dal compromesso bias-varianza discendono due differenze pratiche importanti.

Sensibilità ai valori iniziali. Poiché la stima corrente entra nel target, TD è più sensibile all’inizializzazione: valori iniziali fuorvianti contaminano i target e rallentano (o distorcono) l’apprendimento. In MC i valori iniziali vengono semplicemente diluiti dalle medie dei return osservati, e la sensibilità è molto minore.

Function approximation. Tutto il capitolo assume una rappresentazione tabellare: una tabella con una cella per ogni stato (o coppia stato-azione), aggiornata cella per cella. Quando lo spazio degli stati è enorme o continuo la tabella non è praticabile, e inoltre la tabella non generalizza: ciò che si impara su uno stato non dice nulla sugli stati simili. La soluzione è rappresentare la value function con un modello di supervised learning (una regressione lineare, una rete neurale) addestrato sui target degli update. Qui la differenza tra i due metodi diventa critica: con MC il modello riceve come target stime non distorte del valore vero, e l’addestramento si comporta come un normale problema supervisionato; con TD il target contiene l’output del modello stesso (il bootstrapping usa $V(S_{t+1})$ prodotto dalla rete che si sta addestrando), e questo circolo può, in certi scenari, rendere l’addestramento instabile fino alla divergenza. In sintesi: MC convive bene con la function approximation, TD richiede maggiori cautele.

4.4 La mappa dei metodi: sampling e bootstrapping#

Le tre famiglie viste nel corso (DP, MC, TD) si lasciano classificare con due proprietà indipendenti, che rispondono a due domande diverse sull’update.

La classificazione:

La lettura per righe: DP fa bootstrapping (il backup di Bellman usa $V$ dei successori) ma non campiona, perché usa il modello per calcolare il valore atteso esatto su tutti i successori; MC campiona (usa traiettorie osservate) ma non fa bootstrapping, perché il suo target è il return reale, senza stime dentro; TD fa entrambe le cose: applica la decomposizione di Bellman come DP, ma su una singola transizione osservata come MC. È esattamente questa combinazione, campionare e fare bootstrapping insieme, a rendere TD model-free e al tempo stesso capace di imparare a ogni passo.

In parole semplici: ci sono due domande da fare a un algoritmo di questo tipo: “il tuo bersaglio contiene stime tue?” (bootstrapping) e “usi quello che è successo davvero invece di tutte le possibilità pesate?” (sampling). DP risponde sì/no, MC risponde no/sì, TD risponde sì/sì: prende da DP l’idea di appoggiarsi alle proprie stime e da MC l’idea di accontentarsi dell’esperienza osservata.

5. Dal prediction al control: SARSA#

5.1 Policy iteration model-free con TD#

Finora TD(0) risolve il problema di prediction: valutare una policy fissata. Il passo verso il control (trovare la policy ottima) ricalca lo schema già usato per Monte Carlo control: la generalized policy iteration, cioè l’alternanza tra un passo di valutazione e un passo di miglioramento, adattata al caso model-free. I due ingredienti ereditati dal capitolo su Monte Carlo restano validi:

• si lavora sulla action-value function $Q(s,a)$ e non su $V(s)$: il miglioramento greedy a partire da $V$ richiederebbe il modello (per fare il lookahead a un passo sulle transizioni), mentre a partire da $Q$ basta un $\arg\max$ sulle azioni, senza conoscere la dinamica;
• il miglioramento è $\varepsilon$-greedy e non greedy puro: con probabilità $1-\varepsilon$ si sceglie l’azione con $Q$ massimo, con probabilità $\varepsilon$ un’azione casuale, così da garantire per costruzione l’esplorazione continua di tutte le coppie stato-azione, senza la quale un metodo basato su campioni non può valutare le alternative.

La novità è tutta nel passo di valutazione: al posto della valutazione Monte Carlo (medie dei return a fine episodio) si usa la valutazione TD di $Q$, che aggiorna dopo ogni singola transizione. Lo schema che ne risulta è ancora più incrementale della policy iteration classica: non si aspetta nemmeno di aver completato la valutazione della policy corrente; a ogni passo si aggiorna una cella di $Q$ e, implicitamente, la policy $\varepsilon$-greedy rispetto a $Q$ è già migliorata.

5.2 L’update SARSA#

L’equazione di riferimento è l’equazione di aspettativa di Bellman per $Q^{\pi}$, campionata su una singola esperienza. Servono cinque elementi consecutivi della traiettoria: lo stato corrente $s_t$, l’azione eseguita $a_t$, il reward ottenuto $r_{t+1}$, lo stato d’arrivo $s_{t+1}$ e l’azione effettivamente scelta nello stato d’arrivo, $a_{t+1}$. La sequenza $(S, A, R, S', A')$ dà il nome all’algoritmo: SARSA.

SARSA è un metodo on-policy: la policy che genera i dati e la policy che si sta valutando e migliorando sono la stessa, la $\varepsilon$-greedy corrente. Nel target compare $Q(s_{t+1}, a_{t+1})$ con l’azione che l’agente ha davvero deciso di eseguire, comprese le eventuali azioni esplorative: la $Q$ appresa è quindi la value function della policy effettivamente seguita, esplorazione inclusa. Questo dettaglio, apparentemente innocuo, sarà la chiave del confronto con Q-learning.

5.3 Pseudocodice#

SARSA (on-policy TD control)
Inizializza Q(s,a) arbitrariamente per ogni s,a; Q(terminale, .) = 0
Ripeti per ogni episodio:
    inizializza lo stato s
    scegli a in s con la policy derivata da Q (es. epsilon-greedy)
    Ripeti per ogni passo dell'episodio:
        esegui a; osserva il reward r e il nuovo stato s'
        scegli a' in s' con la policy derivata da Q (es. epsilon-greedy)
        Q(s,a) <- Q(s,a) + alpha * ( r + gamma * Q(s',a') - Q(s,a) )
        s <- s';  a <- a'
    finché s è terminale

Si noti la struttura: l’azione successiva $a'$ viene scelta prima dell’update, perché serve dentro il target, e viene poi effettivamente eseguita al passo successivo. Non c’è un passo di improvement esplicito: la policy è definita implicitamente da $Q$ (è la $\varepsilon$-greedy rispetto a $Q$), quindi ogni update di $Q$ è già, allo stesso tempo, un piccolo miglioramento della policy.

5.4 Convergenza#

Le condizioni di convergenza combinano quelle viste per Monte Carlo control (sull’esplorazione) e quelle dell’approssimazione stocastica (sul learning rate).

La condizione GLIE risolve il dilemma esplorazione-sfruttamento nel limite: all’inizio si esplora abbastanza da vedere tutto, alla fine si sfrutta ciò che si è imparato, e la policy appresa tende alla greedy ottima. In pratica, con $\varepsilon$ e $\alpha$ costanti e piccoli, SARSA non converge in senso stretto ma si stabilizza in un intorno della soluzione, il che è spesso sufficiente.

In parole semplici: SARSA è la ricetta “prova, osserva un passo, correggi la tabella $Q$, ripeti”, condita con un pizzico di scelte casuali per non smettere mai di esplorare. Se il pizzico di casualità si riduce col tempo e le correzioni diventano via via più delicate, la tabella converge a quella ottima.

5.5 SARSA sul windy gridworld#

Tornando al problema della sezione 1.2, SARSA con policy $\varepsilon$-greedy ($\varepsilon = 0{,}1$), learning rate $\alpha = 0{,}5$ e $Q$ inizializzata a zero mostra esattamente il comportamento sperato. Il primo episodio è lunghissimo (migliaia di passi di esplorazione quasi casuale), ma a differenza di Monte Carlo l’algoritmo impara durante quell’episodio: ogni passo aggiorna una cella di $Q$, e le celle vicine al goal cominciano a differenziarsi ben prima che l’episodio finisca. Tracciando il numero di episodi completati in funzione del numero totale di passi di interazione si osserva una curva con pendenza crescente: gli episodi diventano via via più corti, segno che la policy sta migliorando, e dopo qualche migliaio di passi complessivi l’agente raggiunge il goal in modo affidabile con traiettorie vicine all’ottima (una quindicina di passi). La policy greedy rispetto alla $Q$ appresa realizza il giro largo descritto nella sezione 1.2: attraversare la zona ventosa, superare il goal, scendere nelle colonne senza vento e rientrare da destra. Su questo problema Monte Carlo con policy casuale iniziale sarebbe rimasto bloccato al primo episodio.

6. Imparare una policy diversa da quella eseguita: Q-learning#

6.1 On-policy e off-policy#

Nel capitolo su Monte Carlo è stata introdotta la distinzione tra due ruoli che una policy può giocare durante l’apprendimento:

• la behavior policy è la policy usata per interagire con l’ambiente e generare i dati;
• la target policy è la policy di cui si vuole apprendere la value function (o che si vuole rendere ottima).

Nei metodi on-policy, come SARSA, le due coincidono: si impara la policy che si sta eseguendo. Nei metodi off-policy sono diverse: si può esplorare con una policy molto casuale e nel frattempo imparare la policy greedy, ottenendo il meglio dei due mondi sul fronte esplorazione-sfruttamento. In Monte Carlo l’off-policy richiedeva il macchinario dell’importance sampling, con i suoi coefficienti di correzione e i problemi di varianza. La sorpresa del TD learning è che l’off-policy control si può ottenere senza importance sampling, con una modifica di un solo simbolo nell’update: è l’algoritmo più celebre del reinforcement learning, il Q-learning.

6.2 L’update Q-learning#

Il parallelo con la programmazione dinamica illumina la costruzione. SARSA campiona l’equazione di aspettativa di Bellman per $Q^{\pi}$, ed è quindi l’analogo model-free della policy iteration:

$$Q^{\pi}(s, a) = \mathbb{E}\left[ R_{t+1} + \gamma \, Q^{\pi}(S_{t+1}, A_{t+1}) \mid S_t = s, A_t = a \right]$$

Q-learning campiona invece l’equazione di ottimalità di Bellman per $Q^{*}$, ed è l’analogo model-free della value iteration:

$$Q^{*}(s, a) = \mathbb{E}\left[ R_{t+1} + \gamma \max_{a'} Q^{*}(S_{t+1}, a') \mid S_t = s, A_t = a \right]$$

Nell’equazione di ottimalità non compare alcuna policy: il futuro è valutato assumendo che dallo stato successivo in poi si giochi sempre l’azione migliore. La versione campionata di questo backup dà l’update.

La differenza rispetto a SARSA è tutta nel target: al posto di $Q(s_{t+1}, a_{t+1})$, con l’azione realmente scelta, c’è $\max_{a'} Q(s_{t+1}, a')$. Le conseguenze sono profonde:

• Q-learning è off-policy: la behavior policy può essere qualunque policy sufficientemente esplorativa (tipicamente la $\varepsilon$-greedy rispetto alla $Q$ corrente, ma andrebbe bene anche una policy casuale), mentre la target policy è la greedy rispetto a $Q$, che compare nel target attraverso il $\max$;
• l’azione esplorativa eventualmente eseguita in $s_{t+1}$ non entra nell’update: l’esplorazione serve solo a visitare le coppie stato-azione, non contamina i valori appresi;
• ciò che l’algoritmo stima è direttamente $Q^{*}$, la value function della policy ottima, anche se l’agente non la sta seguendo;
• non serve alcun coefficiente di importance sampling: il target dipende dalla transizione $(s_t, a_t, r_{t+1}, s_{t+1})$, che ha la stessa distribuzione qualunque sia la policy che ha scelto $a_t$, e dal $\max$, che non richiede di sapere come si comporterà l’agente.

Idea chiave: SARSA risponde alla domanda “quanto vale questa azione se poi continuo a comportarmi come mi sto comportando, esplorazione compresa?”; Q-learning risponde a “quanto vale questa azione se poi giocherò sempre al meglio?”. Il primo impara la policy che esegue; il secondo esegue una policy esplorativa ma impara la policy ottima.

In parole semplici: Q-learning è uno studente che frequenta le lezioni facendo anche esperimenti strampalati, ma quando aggiorna i suoi appunti scrive sempre “e da qui in poi farò la cosa migliore che conosco”, ignorando gli esperimenti futuri. SARSA invece scrive negli appunti la verità sul proprio comportamento reale, pasticci esplorativi inclusi.

6.3 Pseudocodice#

Q-learning (off-policy TD control)
Inizializza Q(s,a) arbitrariamente per ogni s,a; Q(terminale, .) = 0
Ripeti per ogni episodio:
    inizializza lo stato s
    Ripeti per ogni passo dell'episodio:
        scegli a in s con la behavior policy (es. epsilon-greedy da Q)
        esegui a; osserva il reward r e il nuovo stato s'
        Q(s,a) <- Q(s,a) + alpha * ( r + gamma * max_a' Q(s',a') - Q(s,a) )
        s <- s'
    finché s è terminale

Rispetto a SARSA cambia anche la struttura del ciclo: l’azione successiva non serve prima dell’update (nel target c’è il $\max$, non l’azione scelta), quindi si sceglie un’azione per volta, all’inizio di ogni passo.

6.4 Convergenza#

Per Q-learning la convergenza a $Q^{*}$ richiede condizioni più deboli che per SARSA: basta che la behavior policy continui a visitare tutte le coppie stato-azione (esplorazione sufficiente, per esempio una qualunque $\varepsilon$-greedy o $\varepsilon$-soft con $\varepsilon$ anche costante) e che i learning rate soddisfino le condizioni di Robbins-Monro. Non serve che la behavior policy diventi greedy nel limite: è la natura off-policy dell’algoritmo, la target policy è greedy per costruzione, dentro il $\max$ del target, qualunque cosa faccia l’agente. Una volta appresa $Q^{*}$ (o una sua buona approssimazione), la policy ottima si legge direttamente: $\pi^{*}(s) = \arg\max_a Q^{*}(s, a)$.

6.5 SARSA vs Q-learning: windy gridworld e cliff walking#

Sul windy gridworld con $\varepsilon = 0{,}1$ i due algoritmi si comportano in modo simile: entrambi imparano rapidamente a completare episodi sempre più corti, con curve di apprendimento confrontabili. In quel problema sbagliare una mossa costa solo qualche passo in più: la differenza tra imparare la policy eseguita e imparare la policy greedy non ha conseguenze drammatiche.

La differenza esplode nel cliff walking, l’esempio costruito apposta per rivelarla. L’ambiente è una griglia: partenza nell’angolo in basso a sinistra, goal nell’angolo in basso a destra, e lungo tutto il bordo inferiore, tra partenza e goal, un burrone (cliff). Ogni passo costa reward $-1$; cadere nel burrone costa $-100$ e riporta alla partenza. Le policy vengono eseguite in modo $\varepsilon$-greedy con $\varepsilon = 0{,}1$ fisso. Ci sono due cammini sensati: quello ottimo, che rasenta il bordo del burrone (il più corto possibile), e quello sicuro, che sale di qualche riga e viaggia lontano dal precipizio, più lungo ma senza rischi.

I due algoritmi imparano cammini diversi:

• Q-learning impara il cammino ottimo, lungo il bordo: i suoi valori sono quelli della policy greedy, che non commette mai errori, e per la policy greedy rasentare il burrone è perfettamente sicuro e massimamente efficiente;
• SARSA impara il cammino sicuro, lontano dal bordo: i suoi valori sono quelli della policy $\varepsilon$-greedy realmente eseguita, che ogni tanto fa un’azione casuale; vicino al burrone un’azione casuale ogni dieci significa cadute frequenti, e questo rischio entra nei valori $Q$ appresi, che risultano bassi per le celle a ridosso del precipizio e spingono la policy verso l’alto.

Il paradosso è nella performance online, cioè nel reward accumulato per episodio durante l’apprendimento: SARSA fa meglio di Q-learning. Q-learning conosce il cammino ottimo ma lo esegue con la $\varepsilon$-greedy, e camminando sul bordo con una probabilità $\varepsilon$ di mossa casuale ogni tanto precipita, pagando $-100$; SARSA percorre un cammino più lungo ma quasi mai cade, e in media incassa di più. Se però si fa decrescere $\varepsilon$ verso zero (condizione GLIE), entrambi convergono alla policy ottima e la differenza svanisce.

In parole semplici: Q-learning impara la strada perfetta per un guidatore perfetto, ma la fa percorrere a un guidatore che ogni tanto sterza a caso: sul ciglio del burrone è una pessima combinazione. SARSA sa di essere un guidatore imperfetto e impara la strada giusta per sé, più prudente. Chi dei due sia “migliore” dipende da cosa conta: la policy finale (Q-learning) o il punteggio raccolto mentre si impara (SARSA).

7. Oltre il passo singolo: n-step TD, λ-return ed eligibility traces#

TD(0) e Monte Carlo sono i due estremi di uno spettro continuo: TD(0) guarda avanti di un solo passo prima di appoggiarsi a una stima; MC guarda avanti fino alla fine dell’episodio e non si appoggia a stime. In mezzo c’è tutta una famiglia di metodi che guardano avanti di $n$ passi, o combinano più orizzonti insieme. L’esempio del random walk ha mostrato il costo del passo singolo: l’informazione si propaga all’indietro di uno stato per volta, e in catene lunghe la propagazione è lenta. Le estensioni di questa sezione servono esattamente ad accelerare quella propagazione mantenendo l’apprendimento online.

7.1 Il return a n passi#

I casi estremi recuperano i metodi noti:

• $n = 1$: $G_t^{(1)} = R_{t+1} + \gamma V(S_{t+1})$ è esattamente il TD target di TD(0);
• $n \to \infty$ (fino a fine episodio): $G_t^{(\infty)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{T-t-1} R_T$ è il return completo di Monte Carlo.

L’update di n-step TD corregge la stima verso il return a $n$ passi:

$$V(S_t) \leftarrow V(S_t) + \alpha \left( G_t^{(n)} - V(S_t) \right)$$

Al crescere di $n$ il target contiene più reward reali e meno bootstrapping: il bias diminuisce (la stima $V$ pesa $\gamma^n$, sempre meno) e la varianza aumenta (più passi casuali accumulati). Empiricamente, valori intermedi di $n$ battono spesso entrambi gli estremi: qualche passo di reward reale abbatte gran parte del bias, senza pagare tutta la varianza del return completo. Gli svantaggi: bisogna attendere $n$ passi prima di poter aggiornare (l’algoritmo resta online ma con un ritardo), e $n$ è un iperparametro in più da scegliere, con l’ottimo dipendente dal problema.

7.2 n-step SARSA: la versione per il control#

La stessa idea si applica al control sostituendo $V$ con $Q$: il return a $n$ passi per le coppie stato-azione è

$$G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n \, Q(S_{t+n}, A_{t+n})$$

e l’update di n-step SARSA è

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left( G_t^{(n)} - Q(S_t, A_t) \right)$$

con la policy $\varepsilon$-greedy rispetto a $Q$ nel ruolo consueto, on-policy come SARSA.

7.3 Il λ-return: tutte le lunghezze insieme#

Invece di scegliere un singolo $n$, si possono combinare tutti gli $n$-step return in un’unica media pesata, con pesi che decadono geometricamente.

Il fattore $(1-\lambda)$ normalizza i pesi: $(1-\lambda) \sum_{n \geq 1} \lambda^{n-1} = 1$. In un task episodico che termina al tempo $T$, tutti i return con $n \geq T - t$ coincidono con il return completo $G_t$, che riceve quindi il peso residuo $\lambda^{T-t-1}$. Il parametro $\lambda$ interpola con continuità tra i due estremi:

• $\lambda = 0$: sopravvive solo il termine $n = 1$ e si ritrova il target di TD(0) (da cui il nome TD(0) usato fin dall’inizio del capitolo);
• $\lambda = 1$: tutto il peso finisce sul return completo e si ritrova Monte Carlo.

Il $\lambda$-return così definito ha però un difetto pratico: per calcolarlo servono tutti i return futuri, quindi bisogna attendere la fine dell’episodio, esattamente come in Monte Carlo. Questa formulazione è detta vista forward: dallo stato $S_t$ si guarda in avanti nel tempo. Perde il vantaggio dell’apprendimento online, ed è per questo che serve una riformulazione.

7.4 Eligibility traces: la vista backward#

L’idea che rende il $\lambda$-return calcolabile online capovolge la prospettiva: invece di chiedersi “quali reward futuri concorrono al target di questo stato?”, ci si chiede a ogni passo “a quali stati passati va attribuito il TD error appena osservato?”. La risposta è codificata da una variabile di memoria per ogni stato, la eligibility trace, che misura quanto ogni stato è “eleggibile” a ricevere credito o colpa per ciò che sta accadendo adesso.

La trace combina due euristiche naturali di credit assignment: l’euristica di frequenza (più credito agli stati visitati spesso: ogni visita somma 1) e l’euristica di recenza (più credito agli stati visitati di recente: il decadimento $\gamma\lambda$ spegne progressivamente le trace degli stati visitati da tempo). L’algoritmo TD($\lambda$) in vista backward usa le trace per distribuire ogni TD error su tutti gli stati:

$$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t), \qquad V(s) \leftarrow V(s) + \alpha \, \delta_t \, e_t(s) \quad \text{per ogni } s$$

A ogni passo si calcola il consueto TD error a un passo, ma invece di correggerne solo lo stato corrente si correggono tutti gli stati, ciascuno in proporzione alla propria trace.

I casi limite tornano ancora una volta:

• con $\lambda = 0$ la trace vale 1 solo sullo stato corrente e 0 altrove: l’update coincide con TD(0), un solo stato aggiornato per passo;
• con $\lambda = 1$ (e aggiornamenti accumulati a fine episodio) il metodo è equivalente a Monte Carlo every-visit;
• per $\lambda$ intermedi, la vista backward realizza online lo stesso apprendimento complessivo della vista forward con il $\lambda$-return (l’equivalenza è esatta nel regime di aggiornamenti offline, cioè accumulati e applicati a fine episodio, e approssimata in quello online).

Il guadagno pratico è evidente ripensando al random walk: con TD(0) l’informazione del reward finale risale la catena di uno stato per episodio di visita; con TD($\lambda$) un singolo TD error alla fine dell’episodio aggiorna in un colpo solo tutti gli stati recentemente visitati, con intensità decrescente all’indietro. Lo stesso meccanismo si estende al control tenendo una trace per ogni coppia stato-azione $e_t(s,a)$ e aggiornando l’intera tabella $Q$ con il TD error di SARSA: è la variante SARSA($\lambda$).

In parole semplici: ogni stato porta al polso un braccialetto luminoso che si accende quando lo stato viene visitato e si spegne piano piano. Quando succede qualcosa di sorprendente (un TD error), la correzione viene distribuita a tutti gli stati in proporzione a quanto è ancora acceso il loro braccialetto: molto agli stati appena visitati, poco a quelli di tanto tempo fa. Così una scoperta fatta ora aggiorna in un colpo solo tutto il recente passato.

8. Quadro riassuntivo: DP, MC e TD a confronto#

La tabella raccoglie i tre approcci alla soluzione degli MDP visti nella parte di reinforcement learning del corso.

I criteri di scelta in sintesi. Se il modello è disponibile e lo spazio degli stati è trattabile, la DP dà soluzioni esatte. Se il modello non c’è, e gli episodi sono brevi e facili da completare, Monte Carlo è semplice, poco distorto e robusto. Se gli episodi sono lunghi, difficili da completare o inesistenti (task continui), o se conta imparare rapidamente durante l’interazione, il TD learning è la scelta naturale, con l’avvertenza della sensibilità all’inizializzazione e delle cautele con la function approximation. All’interno del TD control: SARSA se conta la performance durante l’apprendimento (l’agente opera nel mondo reale mentre impara, e gli errori costano); Q-learning se conta la policy finale e l’esplorazione è a buon mercato (simulatori), o se si vuole imparare da dati generati da un’altra policy. Si chiude osservando che il parallelismo con la DP è completo: SARSA sta alla policy iteration come Q-learning sta alla value iteration, con i backup esatti di Bellman sostituiti da campioni di esperienza; e proprio Q-learning, combinato con le reti neurali come function approximator, è il punto di partenza del deep reinforcement learning moderno.

9. Esercizi d’esame svolti: update a mano#

Una tipologia d’esame ricorrente fornisce una tabella di valori iniziali ($V$ o $Q$), un episodio osservato (sequenza di stati, azioni e reward) e i parametri $\alpha$ e $\gamma$, e chiede di eseguire a mano gli update di TD(0), SARSA o Q-learning. La procedura è puramente meccanica, ma gli errori di distrazione sono frequenti: questa sezione fissa il metodo e lo applica a tre esercizi completi.

9.1 La procedura meccanica#

1. Riscrivere l’episodio come lista di transizioni, nell’ordine temporale: per TD(0) triple $(s_t, r_{t+1}, s_{t+1})$; per SARSA quintuple $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$; per Q-learning quadruple $(s_t, a_t, r_{t+1}, s_{t+1})$.
2. Per ogni transizione, in ordine: calcolare il target (TD(0): $r + \gamma V(s')$; SARSA: $r + \gamma Q(s', a')$ con l’azione $a'$ realmente eseguita al passo dopo; Q-learning: $r + \gamma \max_{a'} Q(s', a')$), poi l’errore $\delta = \text{target} - \text{stima corrente}$, poi il nuovo valore $\text{stima} + \alpha \delta$.
3. Usare sempre i valori più aggiornati: se uno stato (o una coppia stato-azione) è già stato aggiornato in un passo precedente dello stesso episodio, nei target successivi va usato il valore nuovo, non quello iniziale.
4. Il valore del terminale è zero: $V(T) = 0$ e $Q(T, \cdot) = 0$ sempre, qualunque cosa dica la tabella.
5. A ogni passo cambia una sola cella: quella dello stato (o coppia) di partenza della transizione; tutte le altre restano invariate.

9.2 Esercizio 1: TD(0) prediction#

Testo. Un agente segue una policy fissata in un MDP con stati $s_1, s_2, s_3$ e uno stato terminale $T$. Valori iniziali: $V(s_1) = 1$, $V(s_2) = 2$, $V(s_3) = 0$. Parametri: $\gamma = 0{,}5$, $\alpha = 0{,}1$. Viene osservato l’episodio:

$$s_1 \xrightarrow{\;r=2\;} s_2 \xrightarrow{\;r=1\;} s_3 \xrightarrow{\;r=4\;} T$$

Calcolare i valori dopo l’applicazione di TD(0) lungo l’episodio.

Svolgimento

Le transizioni sono $(s_1, 2, s_2)$, $(s_2, 1, s_3)$, $(s_3, 4, T)$, da processare in quest’ordine, aggiornando dopo ogni passo.

Passo 1, transizione $(s_1, 2, s_2)$: il target è $2 + 0{,}5 \cdot V(s_2) = 2 + 0{,}5 \cdot 2 = 3$; l’errore è $\delta = 3 - V(s_1) = 3 - 1 = 2$;

$$V(s_1) \leftarrow 1 + 0{,}1 \cdot 2 = 1{,}2$$

Passo 2, transizione $(s_2, 1, s_3)$: il target è $1 + 0{,}5 \cdot V(s_3) = 1 + 0 = 1$; l’errore è $\delta = 1 - 2 = -1$;

$$V(s_2) \leftarrow 2 + 0{,}1 \cdot (-1) = 1{,}9$$

Passo 3, transizione $(s_3, 4, T)$: il target è $4 + 0{,}5 \cdot V(T) = 4 + 0 = 4$; l’errore è $\delta = 4 - 0 = 4$;

$$V(s_3) \leftarrow 0 + 0{,}1 \cdot 4 = 0{,}4$$

Risultato: $V(s_1) = 1{,}2$, $V(s_2) = 1{,}9$, $V(s_3) = 0{,}4$.

Confronto istruttivo con Monte Carlo. Sullo stesso episodio, MC (first-visit) userebbe come target i return osservati: $G(s_3) = 4$; $G(s_2) = 1 + 0{,}5 \cdot 4 = 3$; $G(s_1) = 2 + 0{,}5 \cdot 1 + 0{,}25 \cdot 4 = 3{,}5$. Gli update con lo stesso $\alpha$: $V(s_1) = 1 + 0{,}1(3{,}5 - 1) = 1{,}25$; $V(s_2) = 2 + 0{,}1(3 - 2) = 2{,}1$; $V(s_3) = 0{,}4$ (identico, perché per l’ultimo stato return e TD target coincidono). Si noti che i due metodi muovono $V(s_2)$ in direzioni opposte: MC lo alza verso il return realmente osservato (3), TD lo abbassa perché il suo target usa la stima corrente $V(s_3) = 0$, ancora pessimistica. È il bias del bootstrapping visto in azione: finché $V(s_3)$ è sottostimato, i target che lo contengono sono sottostimati a loro volta.

9.3 Esercizio 2: SARSA#

Testo. MDP con stati $s_1, s_2$, terminale $T$, azioni $a_1, a_2$ in ogni stato. Tabella iniziale:

	$a_1$	$a_2$
$s_1$	$1$	$0$
$s_2$	$2$	$0$

Parametri: $\alpha = 0{,}5$, $\gamma = 0{,}5$. L’agente, seguendo una policy $\varepsilon$-greedy, genera l’episodio:

$$s_1 \xrightarrow{\;a_1,\; r=2\;} s_2 \xrightarrow{\;a_2,\; r=-1\;} s_1 \xrightarrow{\;a_1,\; r=3\;} T$$

Applicare gli update SARSA nell’ordine e riportare la tabella finale.

Svolgimento

Le quintuple $(s, a, r, s', a')$ sono, in ordine: $(s_1, a_1, 2, s_2, a_2)$, $(s_2, a_2, -1, s_1, a_1)$, $(s_1, a_1, 3, T, \cdot)$.

Passo 1, quintupla $(s_1, a_1, 2, s_2, a_2)$: il target usa l’azione effettivamente eseguita in $s_2$, cioè $a_2$ (una mossa esplorativa: non è la greedy, visto che $Q(s_2, a_1) = 2 > 0$); target $= 2 + 0{,}5 \cdot Q(s_2, a_2) = 2 + 0{,}5 \cdot 0 = 2$; errore $\delta = 2 - Q(s_1, a_1) = 2 - 1 = 1$;

$$Q(s_1, a_1) \leftarrow 1 + 0{,}5 \cdot 1 = 1{,}5$$

Passo 2, quintupla $(s_2, a_2, -1, s_1, a_1)$: nel target serve $Q(s_1, a_1)$, che è appena stato aggiornato: si usa $1{,}5$, non il valore iniziale $1$; target $= -1 + 0{,}5 \cdot 1{,}5 = -0{,}25$; errore $\delta = -0{,}25 - Q(s_2, a_2) = -0{,}25 - 0 = -0{,}25$;

$$Q(s_2, a_2) \leftarrow 0 + 0{,}5 \cdot (-0{,}25) = -0{,}125$$

Passo 3, quintupla $(s_1, a_1, 3, T, \cdot)$: lo stato d’arrivo è terminale, quindi il termine futuro è zero qualunque azione si consideri; target $= 3 + 0 = 3$; errore $\delta = 3 - 1{,}5 = 1{,}5$ (di nuovo: si usa il valore corrente $1{,}5$);

$$Q(s_1, a_1) \leftarrow 1{,}5 + 0{,}5 \cdot 1{,}5 = 2{,}25$$

Risultato:

	$a_1$	$a_2$
$s_1$	$2{,}25$	$0$
$s_2$	$2$	$-0{,}125$

Le celle $Q(s_1, a_2)$ e $Q(s_2, a_1)$ non vengono mai toccate: le loro coppie stato-azione non compaiono come partenza di alcuna transizione dell’episodio.

9.4 Esercizio 3: Q-learning sullo stesso episodio#

Testo. Stessa tabella iniziale, stessi parametri e stesso episodio dell’esercizio 2, ma con gli update di Q-learning.

Svolgimento

Per Q-learning servono solo le quadruple $(s, a, r, s')$: $(s_1, a_1, 2, s_2)$, $(s_2, a_2, -1, s_1)$, $(s_1, a_1, 3, T)$. Il target usa il massimo sulla riga dello stato d’arrivo, non l’azione eseguita. Si riparte dalla tabella iniziale.

Passo 1, quadrupla $(s_1, a_1, 2, s_2)$: $\max_{a'} Q(s_2, a') = \max(2, 0) = 2$; target $= 2 + 0{,}5 \cdot 2 = 3$; errore $\delta = 3 - 1 = 2$;

$$Q(s_1, a_1) \leftarrow 1 + 0{,}5 \cdot 2 = 2$$

Il confronto con SARSA è già eloquente: SARSA aveva usato $Q(s_2, a_2) = 0$, perché l’agente ha davvero eseguito la mossa esplorativa $a_2$; Q-learning usa $Q(s_2, a_1) = 2$, il valore della mossa migliore, anche se $a_1$ non è stata eseguita. L’esplorazione futura non contamina il valore.

Passo 2, quadrupla $(s_2, a_2, -1, s_1)$: $\max_{a'} Q(s_1, a') = \max(2, 0) = 2$ (attenzione: $Q(s_1, a_1)$ vale ora $2$, il valore aggiornato al passo 1); target $= -1 + 0{,}5 \cdot 2 = 0$; errore $\delta = 0 - 0 = 0$;

$$Q(s_2, a_2) \leftarrow 0 + 0{,}5 \cdot 0 = 0$$

Passo 3, quadrupla $(s_1, a_1, 3, T)$: il massimo sul terminale è zero; target $= 3$; errore $\delta = 3 - 2 = 1$;

$$Q(s_1, a_1) \leftarrow 2 + 0{,}5 \cdot 1 = 2{,}5$$

Risultato:

	$a_1$	$a_2$
$s_1$	$2{,}5$	$0$
$s_2$	$2$	$0$

Confronto finale. Sullo stesso identico episodio, SARSA produce $Q(s_1, a_1) = 2{,}25$ e $Q(s_2, a_2) = -0{,}125$, Q-learning produce $Q(s_1, a_1) = 2{,}5$ e $Q(s_2, a_2) = 0$. Le stime di Q-learning sono sistematicamente più ottimistiche: valutano ogni stato futuro con la sua azione migliore, mentre SARSA sconta il fatto che l’agente in $s_2$ ha davvero giocato l’azione debole $a_2$, e in generale sconta il costo dell’esplorazione. È la stessa divergenza di carattere che nel cliff walking porta SARSA sul cammino sicuro e Q-learning sul bordo del burrone. Se l’esercizio chiedesse anche la policy greedy risultante, in questo caso i due metodi concordano: in $s_1$ l’azione greedy è $a_1$ ($2{,}25$ oppure $2{,}5$ contro $0$) e in $s_2$ è $a_1$ ($2$ contro $-0{,}125$ oppure $0$).

9.5 Errori tipici da evitare#

• Usare il $\max$ in SARSA o l’azione eseguita in Q-learning: è l’errore più frequente; SARSA usa $Q(s', a')$ con l’azione che compare nell’episodio, Q-learning usa $\max_{a'} Q(s', a')$ ignorando l’azione successiva dell’episodio.
• Non usare i valori già aggiornati: se lo stato (o la coppia) riappare più avanti nell’episodio, i target successivi devono usare il valore nuovo; processare gli update “tutti sulla tabella iniziale” è sbagliato.
• Dimenticare che il terminale vale zero: nel target dell’ultima transizione il termine $\gamma \cdot (\cdot)$ sparisce, qualunque valore fantasioso si sia tentati di usare.
• Dimenticare $\gamma$ nel target o $\alpha$ nella correzione: il nuovo valore è $\text{vecchio} + \alpha(\text{target} - \text{vecchio})$, non il target stesso (a meno che $\alpha = 1$).
• Aggiornare la cella sbagliata: l’update modifica la cella dello stato/coppia di partenza della transizione, mai quella d’arrivo.
• Processare le transizioni fuori ordine: l’ordine temporale conta, proprio perché i valori aggiornati rientrano nei target successivi.

Glossario#

Termine	Definizione
Temporal-Difference (TD) learning	Famiglia di metodi model-free che aggiornano le value function a ogni passo, usando come target il reward osservato più la stima scontata dello stato successivo.
Bootstrapping	Aggiornare una stima usando un’altra stima: il target contiene la value function corrente. Lo fanno DP e TD, non MC.
Sampling	Costruire l’update su una transizione campionata invece che su un valore atteso esatto. Lo fanno MC e TD, non DP.
TD(0)	Algoritmo di policy evaluation con update $V(s_t) \leftarrow V(s_t) + \alpha(r_{t+1} + \gamma V(s_{t+1}) - V(s_t))$ dopo ogni transizione.
TD target	La quantità $r_{t+1} + \gamma V(s_{t+1})$ (o l’analoga con $Q$): la nuova stima del return verso cui si corregge il valore.
TD error ($\delta_t$)	Differenza tra TD target e stima corrente: $\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)$.
Learning rate ($\alpha$)	Frazione dell’errore usata per la correzione; per la convergenza deve soddisfare $\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$ (Robbins-Monro).
On-policy / off-policy	On-policy: si impara la stessa policy usata per generare i dati (SARSA); off-policy: behavior policy e target policy sono diverse (Q-learning).
Behavior / target policy	La policy che interagisce con l’ambiente e genera i dati / la policy che si sta valutando o ottimizzando.
SARSA	TD control on-policy: $Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha(r_{t+1} + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t))$, con policy $\varepsilon$-greedy; campiona l’equazione di aspettativa di Bellman.
Q-learning	TD control off-policy: $Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha(r_{t+1} + \gamma \max_{a'} Q(s_{t+1},a') - Q(s_t,a_t))$; campiona l’equazione di ottimalità di Bellman e stima direttamente $Q^{*}$.
GLIE	Greedy in the Limit with Infinite Exploration: ogni coppia stato-azione visitata infinite volte e policy che converge alla greedy; condizione di convergenza di SARSA.
$\varepsilon$-greedy	Policy che sceglie l’azione con $Q$ massimo con probabilità $1-\varepsilon$ e un’azione casuale con probabilità $\varepsilon$; garantisce esplorazione.
Windy gridworld	Gridworld con vento verso l’alto di intensità variabile per colonna; esempio dei limiti di MC e banco di prova di SARSA.
Cliff walking	Gridworld con burrone (reward $-100$) tra partenza e goal; rivela la differenza SARSA (cammino sicuro) vs Q-learning (cammino ottimo ma rischioso durante l’apprendimento).
n-step return ($G_t^{(n)}$)	Somma dei primi $n$ reward più $\gamma^n V(S_{t+n})$; interpola tra TD(0) ($n=1$) e MC ($n \to \infty$).
$\lambda$-return ($G_t^{\lambda}$)	Media geometrica pesata di tutti gli n-step return, $G_t^{\lambda} = (1-\lambda)\sum_n \lambda^{n-1} G_t^{(n)}$; $\lambda=0$ dà TD(0), $\lambda=1$ dà MC.
Eligibility trace ($e_t(s)$)	Memoria per stato: $e_t(s) = \gamma\lambda\, e_{t-1}(s) + \mathbf{1}(S_t = s)$; combina le euristiche di recenza e frequenza per il credit assignment.
TD($\lambda$)	Algoritmo in vista backward che distribuisce ogni TD error su tutti gli stati in proporzione alle trace: $V(s) \leftarrow V(s) + \alpha\, \delta_t\, e_t(s)$.
Vista forward / backward	Formulazione del $\lambda$-return che guarda ai return futuri (richiede l’episodio completo) / formulazione online equivalente basata sulle eligibility traces.
Random walk	Catena di 5 stati con terminali agli estremi e reward $+1$ a destra; esempio classico di confronto tra TD(0) e MC nella prediction.

Dispensa Machine Learning · Politecnico di Milano