Il capitolo precedente ha costruito il linguaggio dei Processi Decisionali di Markov e lo ha portato fino alle equazioni di Bellman: quelle di aspettativa, che caratterizzano la value function di una policy data e formano un sistema lineare, e quelle di ottimalità, che caratterizzano la value function ottima ma, a causa dell’operatore di massimo, non ammettono soluzione in forma chiusa. Questo capitolo affronta la domanda naturale che ne segue: assumendo di conoscere completamente il modello dell’MDP, cioè la dinamica one-step $p(s' \mid s, a)$ e la funzione di reward $r(s, a)$, come si calcolano concretamente $V^{\pi}$, $V^{*}$ e $\pi^{*}$? La risposta è la famiglia degli algoritmi di programmazione dinamica (Dynamic Programming, DP): iterative policy evaluation per il problema di valutazione, policy improvement e policy iteration per il problema di controllo, la cornice unificante della generalized policy iteration (GPI) e la sua istanza più celebre, value iteration, fino alle varianti asincrone. Il capitolo si chiude con l’analisi dei costi computazionali e con i due limiti strutturali della DP, la maledizione della dimensionalità e la necessità del modello, che motivano il passaggio ai metodi model-free dei capitoli successivi. Un esempio numerico svolto passo-passo, sia su un gridworld sia su un piccolo MDP a due stati, accompagna ogni algoritmo.

Riferimenti sul testo: Sutton e Barto, Reinforcement Learning: An Introduction, capitolo 4. Materiale complementare consigliato: il corso online Fundamentals of Reinforcement Learning (Coursera).

1. Se conosco il modello, posso pianificare#

1.1 I due problemi: prediction e control#

Tutto il capitolo si svolge sotto un’ipotesi forte: l’MDP è noto per intero. Sono dati gli insiemi $\mathcal{S}$ e $\mathcal{A}$, la dinamica di transizione $p(s' \mid s, a)$, il reward atteso $r(s, a)$ e il discount factor $\gamma$. In queste condizioni non c’è nulla da “imparare” dall’esperienza: si tratta di pianificare, cioè di estrarre dal modello, con puro calcolo, le quantità di interesse. I problemi da risolvere sono due, in ordine crescente di difficoltà.

I due problemi non sono indipendenti: la prediction è il mattone del control. Come si vedrà, gli algoritmi di controllo funzionano alternando una fase in cui si valuta la policy corrente (prediction) e una fase in cui la si migliora sfruttando la valutazione appena ottenuta. Gli strumenti matematici sono sempre le equazioni di Bellman: quelle di aspettativa per $V^{\pi}$ e $Q^{\pi}$ nel caso della prediction, quelle di ottimalità per $V^{*}$ e $Q^{*}$ nel caso del control.

In parole semplici: prediction risponde a “quanto rende questa strategia?”; control risponde a “qual è la strategia migliore?”. La seconda domanda si affronta rispondendo ripetutamente alla prima: valuto la strategia che ho, scopro dove sbaglia, la correggo, e ricomincio.

1.2 Perché la forza bruta non funziona#

Il capitolo precedente ha già fornito, in linea di principio, una soluzione per entrambi i problemi. Per la prediction c’è la forma chiusa $V^{\pi} = (I - \gamma P^{\pi})^{-1} R^{\pi}$, che costa $O(|\mathcal{S}|^3)$. Per il control c’è la ricerca esaustiva: il teorema di esistenza garantisce una policy ottima deterministica, quindi basterebbe enumerare tutte le policy deterministiche, valutare ciascuna e tenere la dominante. Il conteggio però condanna questo approccio: le policy deterministiche sono

$$|\mathcal{A}|^{|\mathcal{S}|}$$

perché in ogni stato si sceglie indipendentemente una tra $|\mathcal{A}|$ azioni, e per ciascuna di esse andrebbe risolto un sistema di $|\mathcal{S}|$ equazioni lineari. Anche un gridworld modesto, $5 \times 5$ con 4 azioni, produce $4^{25} \approx 10^{15}$ policy candidate: la ricerca brute-force è fuori scala già sui problemi giocattolo. Serve un metodo che sfrutti la struttura del problema invece di enumerarne le soluzioni.

1.3 Che cos’è la programmazione dinamica e perché si applica agli MDP#

La programmazione dinamica non è nata per gli MDP: è un paradigma algoritmico generale (lo stesso, per esempio, degli algoritmi di cammino minimo). Perché sia applicabile, un problema deve possedere due proprietà strutturali:

• sottostruttura ottima: la soluzione ottima del problema si può comporre a partire dalle soluzioni ottime dei sottoproblemi; il principio di ottimalità deve valere, cioè “comportarsi in modo ottimo da qui in poi” deve decomporsi in “prima mossa ottima, poi comportamento ottimo dal punto d’arrivo”;
• sottoproblemi ricorrenti (overlapping): gli stessi sottoproblemi si ripresentano molte volte, così che la loro soluzione possa essere calcolata una volta, memorizzata e riutilizzata.

Gli MDP soddisfano entrambe le proprietà, ed è esattamente ciò che le equazioni di Bellman esprimono. La sottostruttura ottima è la ricorsione di Bellman: il valore di uno stato si decompone in reward immediato più valore scontato dello stato successivo, quindi “quanto rende partire da $s$” si risolve conoscendo “quanto rende partire da ciascun possibile $s'$”. I sottoproblemi ricorrenti sono gli stati stessi: il valore di uno stato $s'$ serve nel calcolo del valore di tutti gli stati che possono transitare in $s'$, e la value function è precisamente la cache che memorizza le soluzioni dei sottoproblemi per riutilizzarle.

Idea chiave: le equazioni di Bellman sono la ricetta di decomposizione della programmazione dinamica applicata agli MDP: ogni stato è un sottoproblema, la value function è la tabella delle soluzioni parziali, e l’aggiornamento di Bellman è l’operazione che propaga le soluzioni da uno stato ai suoi predecessori.

La strategia che la DP mette in campo per il control è già visibile in filigrana: produrre una successione di policy via via migliori, ciascuna valutata con le equazioni di aspettativa e corretta con quelle di ottimalità, finché la successione non si stabilizza sulla policy dominante.

In parole semplici: invece di provare tutte le strategie una per una, si compila una tabella con il valore di ogni situazione, sfruttando il fatto che il valore di una situazione dipende solo dal valore delle situazioni in cui si può finire. Si aggiorna la tabella finché i numeri non tornano coerenti tra loro: a quel punto la tabella contiene la risposta.

2. Valutare una policy: iterative policy evaluation#

2.1 Dall’equazione di Bellman all’aggiornamento iterativo#

Il punto di partenza è l’equazione di aspettativa di Bellman, che $V^{\pi}$ soddisfa in ogni stato:

$$V^{\pi}(s) = \sum_{a} \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V^{\pi}(s') \right]$$

Risolvere direttamente il sistema lineare costa $O(|\mathcal{S}|^3)$ ed è impraticabile su spazi di stati grandi. La programmazione dinamica segue un’altra strada: trasforma l’identità in una regola di aggiornamento. Si parte da una stima iniziale arbitraria $V_0$ (per esempio $V_0(s) = 0$ per ogni $s$, con l’unico vincolo che gli eventuali stati terminali abbiano valore 0) e si genera una successione di approssimazioni applicando a ogni passo il membro destro dell’equazione alla stima corrente:

$$V_{k+1}(s) = \sum_{a} \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V_k(s') \right] \qquad \forall s \in \mathcal{S}$$

Un’applicazione dell’aggiornamento a tutti gli stati si chiama sweep (spazzata) dello spazio degli stati. Ogni singolo aggiornamento è un backup completo (full-width backup): per calcolare il nuovo valore di $s$ si considerano tutte le azioni possibili in $s$ e, per ciascuna, tutti i possibili stati successori con le rispettive probabilità; è qui che la conoscenza del modello ($r$ e $p$) viene usata in modo essenziale.

In forma compatta, usando l’operatore di Bellman di aspettativa introdotto nel capitolo precedente, la successione è $V_{k+1} = T^{\pi} V_k$. La convergenza è allora immediata dalle proprietà già dimostrate: $V^{\pi}$ è l’unico punto fisso di $T^{\pi}$ e, per $\gamma < 1$, $T^{\pi}$ è una $\gamma$-contrazione in norma del massimo. Ne segue che

$$\left\lVert V_k - V^{\pi} \right\rVert_{\infty} \leq \gamma^k \left\lVert V_0 - V^{\pi} \right\rVert_{\infty} \longrightarrow 0$$

quindi $V_k \to V^{\pi}$ per $k \to \infty$, qualunque sia l’inizializzazione $V_0$, con errore che si riduce almeno di un fattore $\gamma$ a ogni sweep. Nei task episodici la convergenza è garantita anche con $\gamma = 1$, purché ogni policy considerata raggiunga prima o poi uno stato terminale.

Idea chiave: l’equazione di Bellman viene usata non come vincolo da risolvere ma come operazione da ripetere: si “gira la manovella” del backup finché i valori smettono di cambiare. Quando l’aggiornamento non modifica più nulla, la stima soddisfa l’equazione di Bellman, e quindi è $V^{\pi}$.

In parole semplici: si parte con una tabella di valori tutti a zero e la si corregge a ogni giro: il nuovo valore di ogni stato è “premio medio immediato più valore scontato medio di dove si finisce”, calcolato con i valori del giro precedente. Ogni giro avvicina la tabella alla verità di un fattore $\gamma$, quindi dopo abbastanza giri la tabella è (quasi) esatta.

2.2 Pseudocodice e criterio d’arresto#

In pratica l’iterazione si arresta quando i valori si sono stabilizzati: si monitora la variazione massima su tutti gli stati in uno sweep e ci si ferma quando scende sotto una soglia $\theta > 0$ scelta piccola.

Iterative Policy Evaluation
Input: policy π da valutare, modello (p, r), discount γ, soglia θ > 0

Inizializza V(s) arbitrariamente per ogni s ∈ S (V = 0 sugli stati terminali)
ripeti
    Δ ← 0
    per ogni s ∈ S:
        v ← V(s)
        V(s) ← Σ_a π(a|s) [ r(s,a) + γ Σ_{s'} p(s'|s,a) V(s') ]
        Δ ← max(Δ, |v − V(s)|)
finché Δ < θ
Output: V ≈ V^π

Il criterio d’arresto ha una lettura precisa: se dopo uno sweep la variazione massima è $\Delta < \theta$, significa che la stima corrente soddisfa l’equazione di Bellman a meno di $\theta$; grazie alla contrazione si può anche limitare la distanza residua dalla soluzione vera, che è dell’ordine di $\theta \gamma / (1 - \gamma)$ in norma del massimo. Più $\theta$ è piccolo, più la valutazione è accurata, al prezzo di più sweep.

2.3 Versione a due array e versione in place#

La formula $V_{k+1} = T^{\pi} V_k$ descrive un aggiornamento sincrono: tutti i nuovi valori sono calcolati usando esclusivamente i valori del passo precedente, il che richiede due array, uno per $V_k$ e uno per $V_{k+1}$. Lo pseudocodice sopra implementa invece la variante in place: un solo array, in cui ogni valore appena aggiornato è immediatamente disponibile per gli aggiornamenti successivi all’interno dello stesso sweep. Le due versioni convergono entrambe a $V^{\pi}$; quella in place di solito converge più in fretta, perché l’informazione nuova si propaga già durante lo sweep invece di aspettare il successivo, ma il risultato intermedio dipende dall’ordine in cui gli stati vengono visitati. Questa osservazione, apparentemente un dettaglio implementativo, è il seme della programmazione dinamica asincrona della sezione 7.

In parole semplici: nella versione “pulita” si calcolano tutti i nuovi valori guardando solo la fotografia del giro precedente; nella versione in place si sovrascrive man mano, così chi viene aggiornato dopo sfrutta già i valori freschi dei vicini aggiornati prima. La seconda risparmia memoria e tipicamente accelera la convergenza.

2.4 Esempio numerico: il piccolo gridworld#

L’esempio classico su cui vedere l’algoritmo in azione è un gridworld $4 \times 4$ con queste regole:

• le due celle d’angolo opposte (in alto a sinistra e in basso a destra) sono terminali: raggiungerle conclude l’episodio; formalmente costituiscono un unico stato terminale con valore 0;
• gli altri 14 stati sono le celle non terminali; le azioni sono le quattro direzioni $\{\text{nord}, \text{sud}, \text{est}, \text{ovest}\}$, con effetto deterministico; un’azione che porterebbe fuori dalla griglia lascia l’agente fermo nella cella corrente;
• ogni transizione produce reward $-1$, finché non si raggiunge uno stato terminale; il task è episodico e non scontato, $\gamma = 1$;
• la policy da valutare è quella casuale uniforme: $\pi(a \mid s) = 0{,}25$ per ogni azione in ogni stato.

Poiché reward e transizioni sono deterministici data l’azione, l’aggiornamento si semplifica in

$$V_{k+1}(s) = \frac{1}{4} \sum_{a} \left[ -1 + V_k\big(\mathrm{succ}(s, a)\big) \right] = -1 + \frac{1}{4} \sum_{a} V_k\big(\mathrm{succ}(s, a)\big)$$

dove $\mathrm{succ}(s,a)$ è la cella in cui l’azione $a$ conduce da $s$. Partendo da $V_0 = 0$ ovunque:

Sweep 1. Per ogni cella non terminale, tutti i successori hanno valore $V_0 = 0$, quindi $V_1(s) = -1 + 0 = -1$ ovunque (0 sui terminali).

Sweep 2. Ora i valori dei vicini non sono più tutti uguali. Per una cella adiacente a un terminale, per esempio quella in prima riga, seconda colonna: andando a ovest si entra nel terminale ($V_1 = 0$), andando a est, a sud o sbattendo verso nord si finisce in celle con $V_1 = -1$. Quindi

$$V_2 = -1 + \frac{0 + (-1) + (-1) + (-1)}{4} = -1{,}75 \approx -1{,}7$$

Per una cella interna lontana dai terminali tutti e quattro i successori valgono $-1$, quindi $V_2 = -2{,}0$.

Sweep 3. Di nuovo per la cella in prima riga, seconda colonna, usando i valori esatti di $V_2$: ovest porta al terminale ($0$), est e sud portano in celle con $V_2 = -2$, nord fa sbattere e restare sul posto ($V_2 = -1{,}75$):

$$V_3 = -1 + \frac{0 + (-2) + (-2) + (-1{,}75)}{4} = -1 - \frac{5{,}75}{4} \approx -2{,}4$$

La successione dei valori, arrotondati alla prima cifra decimale, sulle sei istantanee più significative (le celle d’angolo in alto a sinistra e in basso a destra sono i terminali, sempre a 0):

$V_1$ (dopo il primo sweep):

$0{,}0$	$-1{,}0$	$-1{,}0$	$-1{,}0$
$-1{,}0$	$-1{,}0$	$-1{,}0$	$-1{,}0$
$-1{,}0$	$-1{,}0$	$-1{,}0$	$-1{,}0$
$-1{,}0$	$-1{,}0$	$-1{,}0$	$0{,}0$

$V_2$:

$0{,}0$	$-1{,}7$	$-2{,}0$	$-2{,}0$
$-1{,}7$	$-2{,}0$	$-2{,}0$	$-2{,}0$
$-2{,}0$	$-2{,}0$	$-2{,}0$	$-1{,}7$
$-2{,}0$	$-2{,}0$	$-1{,}7$	$0{,}0$

$V_3$:

$0{,}0$	$-2{,}4$	$-2{,}9$	$-3{,}0$
$-2{,}4$	$-2{,}9$	$-3{,}0$	$-2{,}9$
$-2{,}9$	$-3{,}0$	$-2{,}9$	$-2{,}4$
$-3{,}0$	$-2{,}9$	$-2{,}4$	$0{,}0$

$V_{10}$:

$0{,}0$	$-6{,}1$	$-8{,}4$	$-9{,}0$
$-6{,}1$	$-7{,}7$	$-8{,}4$	$-8{,}4$
$-8{,}4$	$-8{,}4$	$-7{,}7$	$-6{,}1$
$-9{,}0$	$-8{,}4$	$-6{,}1$	$0{,}0$

$V_{\infty} = V^{\pi}$ (limite della successione):

I valori limite hanno un’interpretazione trasparente: con reward $-1$ a ogni passo e $\gamma = 1$, $V^{\pi}(s)$ è l’opposto del numero atteso di passi che una passeggiata casuale impiega, partendo da $s$, per raggiungere un terminale. Dalla cella più sfavorita (l’angolo opposto diagonale rispetto a ciascun terminale) servono in media 22 passi; dalle celle adiacenti a un terminale ne servono in media 14: la policy casuale è molto inefficiente, e la value function lo quantifica esattamente.

In parole semplici: a ogni giro i valori negativi “si propagano” dai terminali verso l’interno, come un’onda: prima si sistemano le celle vicine alle uscite, poi via via quelle più lontane. Al limite ogni cella riporta quanti passi (in media, cambiati di segno) mancano all’uscita muovendosi a caso.

3. Migliorare una policy: policy improvement#

3.1 Agire greedy rispetto a una value function#

Il calcolo di $V^{\pi}$ non è fine a se stesso: serve per capire se e dove la policy $\pi$ può essere migliorata. Dal capitolo precedente è noto che, se si conoscessero le value function ottime, la policy ottima si otterrebbe agendo in modo greedy: $\pi^{*}(s) = \arg\max_a Q^{*}(s,a)$. La domanda naturale è: che cosa succede applicando la stessa ricetta a una value function non ottima? Data $V^{\pi}$, si costruisce la policy deterministica

$$\pi'(s) = \arg\max_{a \in \mathcal{A}(s)} Q^{\pi}(s, a) = \arg\max_{a \in \mathcal{A}(s)} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V^{\pi}(s') \right]$$

che in ogni stato sceglie l’azione con il miglior compromesso tra reward immediato e valore (secondo $\pi$) dello stato d’arrivo. Il calcolo dell’$\arg\max$ richiede di nuovo il modello: per ogni azione si esegue un lookahead a un passo attraverso $r$ e $p$. Due esiti sono possibili:

• $\pi' = \pi$: la scelta greedy non cambia nulla in nessuno stato. Allora $\pi$ soddisfa $V^{\pi}(s) = \max_a Q^{\pi}(s,a)$ per ogni $s$, cioè la sua value function soddisfa l’equazione di ottimalità di Bellman: $\pi$ è già la policy ottima $\pi^{*}$;
• $\pi' \neq \pi$: in almeno uno stato esiste un’azione con $Q^{\pi}$ strettamente maggiore di $V^{\pi}$. In tal caso, come garantisce il teorema seguente, $\pi'$ è una policy migliore.

3.2 Il teorema di policy improvement#

L’ipotesi va letta così: deviare da $\pi$ per un solo passo (eseguendo $\pi'(s)$ invece di $\pi(s)$) e poi tornare a seguire $\pi$ non peggiora mai le cose. La tesi afferma qualcosa di più forte: allora anche seguire $\pi'$ per sempre non peggiora mai le cose. La dimostrazione trasforma la deviazione di un passo in una deviazione permanente, espandendo la value function un passo alla volta.

Dimostrazione. Si parte dall’ipotesi nello stato $s$ e si espande $Q^{\pi}$ con la sua definizione a un passo:

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

L’ultima uguaglianza vale perché condizionare all’azione $A_t = \pi'(s)$ equivale a dire che il primo passo è compiuto secondo $\pi'$. Ora, dentro il valore atteso compare $V^{\pi}(S_{t+1})$; applicando l’ipotesi del teorema nello stato $S_{t+1}$ si ottiene $V^{\pi}(S_{t+1}) \leq Q^{\pi}(S_{t+1}, \pi'(S_{t+1}))$, e quindi

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

dove il secondo passaggio espande di nuovo $Q^{\pi}$ a un passo: ora anche la seconda azione è scelta da $\pi'$. Iterando lo stesso argomento (applicare l’ipotesi in $S_{t+2}$, espandere, e così via) si sostituisce $\pi$ con $\pi'$ un passo alla volta:

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

Al limite, il termine residuo $\gamma^k V^{\pi}(S_{t+k})$ svanisce (perché $\gamma^k \to 0$ se $\gamma < 1$, oppure perché l’episodio termina), e resta l’intero return generato seguendo $\pi'$:

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

che è la tesi. Se in qualche stato l’ipotesi vale con disuguaglianza stretta, la stessa catena parte con un $<$ e produce un miglioramento stretto in quello stato. $\blacksquare$

La policy greedy $\pi'$ della sezione 3.1 soddisfa automaticamente l’ipotesi del teorema: per ogni $s$,

$$Q^{\pi}\big(s, \pi'(s)\big) = \max_{a} Q^{\pi}(s, a) \geq \sum_{a} \pi(a \mid s) \, Q^{\pi}(s, a) = V^{\pi}(s)$$

perché il massimo di un insieme di valori non è mai inferiore a una loro media pesata. Quindi il miglioramento greedy non può mai peggiorare la policy; e se non la cambia, la policy era già ottima.

Idea chiave: il teorema di policy improvement trasforma un vantaggio locale in un vantaggio globale: se in ogni stato la deviazione di un solo passo verso $\pi'$ non è dannosa, allora adottare $\pi'$ ovunque e per sempre non è dannoso. È questa amplificazione dal singolo passo all’intera traiettoria che rende il miglioramento greedy uno strumento sicuro.

In parole semplici: se cambiare una sola mossa qua e là non fa mai danno, cambiare tutte le mosse insieme non fa danno: i piccoli vantaggi si accumulano lungo la traiettoria invece di annullarsi. Per questo scegliere sempre l’azione col $Q$ più alto della vecchia strategia produce una strategia nuova che è almeno altrettanto buona.

3.3 Il gridworld rivisitato: greedy su una value function non ottima#

Si torni al piccolo gridworld e alla value function $V^{\pi}$ della policy casuale. Poiché il reward è $-1$ per ogni mossa e le transizioni sono deterministiche con $\gamma = 1$, l’azione greedy in una cella è semplicemente quella che porta nel vicino con il valore più alto.

Applicando il miglioramento greedy alle istantanee della sezione 2.4 si osserva un fatto notevole:

• rispetto a $V_1$ (tutti $-1$ tranne i terminali) le uniche celle in cui la scelta greedy è determinata sono quelle adiacenti a un terminale: lì l’azione che entra nel terminale (valore 0) batte le altre (valore $-1$); altrove tutte le azioni sono in pareggio;
• rispetto a $V_2$ e $V_3$ il fronte delle scelte determinate avanza verso l’interno della griglia, seguendo la propagazione dei valori;
• rispetto a $V_3$, e a maggior ragione rispetto a $V_{\infty} = V^{\pi}$, la policy greedy risultante è già la policy ottima del gridworld: da ogni cella punta al terminale più vicino lungo un cammino di lunghezza minima.

Ci sono due lezioni. La prima: agire greedy rispetto alla value function di una policy mediocre (quella casuale) può produrre direttamente una policy eccellente; in questo piccolo esempio, addirittura ottima al primo miglioramento. La seconda, ancora più utile in pratica: la policy greedy si è stabilizzata già a $V_3$, molto prima che la valutazione converga ($V_3$ dista ancora parecchio da $V_{\infty}$). Valutare con precisione assoluta una policy destinata a essere subito rimpiazzata è uno spreco: questa osservazione motiverà la generalized policy iteration e value iteration.

In parole semplici: per capire da che parte andare non serve conoscere i valori esatti, basta che l’ordinamento tra i vicini sia giusto. E l’ordinamento giusto emerge dopo pochi giri di valutazione, molto prima dei valori esatti: quindi si può migliorare la strategia in anticipo, senza aspettare la fine dei conti.

4. Alternare valutazione e miglioramento: policy iteration#

4.1 L’algoritmo e la sua convergenza#

I due strumenti costruiti finora si compongono naturalmente in un algoritmo per il problema di control. Si parte da una policy arbitraria $\pi_0$ (per esempio quella casuale) e si alternano i due passi:

• valutazione (E): si calcola $V^{\pi_i}$ con la iterative policy evaluation (fino alla soglia $\theta$);
• miglioramento (I): si costruisce $\pi_{i+1}$ greedy rispetto a $V^{\pi_i}$.

La successione generata è

$$\pi_0 \xrightarrow{E} V^{\pi_0} \xrightarrow{I} \pi_1 \xrightarrow{E} V^{\pi_1} \xrightarrow{I} \pi_2 \xrightarrow{E} \cdots \xrightarrow{I} \pi^{*} \xrightarrow{E} V^{*}$$

e l’algoritmo termina quando il passo di miglioramento non modifica più la policy. La convergenza è garantita da un argomento in tre mosse:

• per il teorema di policy improvement ogni $\pi_{i+1}$ è migliore o uguale a $\pi_i$: la successione delle value function è monotona non decrescente in ogni stato;
• finché la policy non è ottima, il miglioramento è stretto in almeno uno stato: nessuna policy può ripresentarsi due volte nella successione;
• in un MDP finito le policy deterministiche sono in numero finito ($|\mathcal{A}|^{|\mathcal{S}|}$), quindi la successione deve arrestarsi dopo un numero finito di iterazioni; e si arresta soltanto quando la policy è greedy rispetto alla propria value function, cioè quando soddisfa l’equazione di ottimalità di Bellman: la policy finale è $\pi^{*}$.

Lo pseudocodice completo:

Policy Iteration
Input: modello (p, r), discount γ, soglia θ > 0

1. Inizializzazione:
   V(s) arbitraria e π(s) ∈ A(s) arbitraria, per ogni s ∈ S

2. Policy Evaluation:
   ripeti
       Δ ← 0
       per ogni s ∈ S:
           v ← V(s)
           V(s) ← r(s, π(s)) + γ Σ_{s'} p(s'|s, π(s)) V(s')
           Δ ← max(Δ, |v − V(s)|)
   finché Δ < θ

3. Policy Improvement:
   policy_stabile ← vero
   per ogni s ∈ S:
       a_old ← π(s)
       π(s) ← argmax_a [ r(s,a) + γ Σ_{s'} p(s'|s,a) V(s') ]
       se a_old ≠ π(s): policy_stabile ← falso
   se policy_stabile: restituisci V ≈ V* e π ≈ π*
   altrimenti: vai al passo 2

Un accorgimento pratico importante: al ritorno al passo 2 la valutazione della nuova policy non riparte da zero, ma dalla value function della policy precedente. Poiché policy consecutive sono simili, le loro value function lo sono altrettanto, e il “warm start” riduce drasticamente il numero di sweep necessari.

Idea chiave: policy iteration è una scalata monotona nello spazio (finito) delle policy deterministiche: ogni giro produce una policy non peggiore, nessuna policy viene mai rivisitata, e l’unica condizione di arresto possibile è l’ottimalità. La convergenza non è asintotica ma esatta e in un numero finito di passi.

In parole semplici: valuto la strategia che ho, poi in ogni situazione sostituisco la mossa prescritta con la migliore secondo i valori appena calcolati, e ricomincio. A ogni giro la strategia migliora davvero da qualche parte; siccome le strategie possibili sono in numero finito, prima o poi il giro non cambia più nulla, e a quel punto ho in mano la strategia ottima certificata.

4.2 Un esempio più ricco: gridworld con celle penalizzanti#

Per vedere la dinamica di policy iteration su qualche iterazione in più conviene un gridworld meno banale. L’ambiente è una griglia $4 \times 4$ con lo stato terminale nell’angolo in alto a sinistra e un gruppo di celle penalizzanti disposte su due file: ogni passo ordinario costa $-1$, ma entrare in una cella penalizzante costa $-10$; il task è episodico e non scontato ($\gamma = 1$). La struttura del problema rende sconveniente qualunque cammino che attraversi l’area penalizzante: anche quando il terminale è “in linea d’aria” oltre le celle cattive, il percorso ottimo le aggira, perché un solo ingresso nell’area costa quanto una decina di passi normali. L’esecuzione di policy iteration partendo dalla policy casuale uniforme procede così.

Prima valutazione e primo miglioramento. La value function della policy casuale è molto negativa ovunque (fino a $-242$ nell’angolo più lontano), perché una passeggiata casuale vaga a lungo e attraversa ripetutamente l’area penalizzante. Ciononostante i valori sono già informativi: contengono l’ordinamento giusto tra i vicini in gran parte della griglia. Per esempio, dalla cella con valore $-181$ il vicino “in alto” vale $-137{,}5$ e il vicino “a sinistra” $-129{,}5$: il miglioramento greedy sceglie di andare a sinistra, non perché $-129{,}5$ sia un buon valore, ma perché è meno peggio degli altri. La policy greedy risultante è già ragionevole, ma non ovunque: le celle della prima riga puntano ancora a sinistra attraverso l’area penalizzante, perché i valori della policy casuale non distinguono ancora bene il cammino diretto da quello che aggira le celle blu.

Seconda valutazione e correzioni successive. Valutando la nuova policy i valori cambiano radicalmente (molto meno negativi, perché ora la policy “ha senso”) e rendono visibili gli errori residui. Un esempio concreto: la cella d’angolo in alto a destra vale $-21$ perché la sua policy passa per la cella penalizzante adiacente (valore $-11$); il confronto tra i $Q$ al miglioramento successivo rende evidente che conviene invece scendere e aggirare l’area. Lo stesso accade nell’ultima riga: il cammino corretto esce a destra e risale lungo la colonna libera, e la correzione si propaga all’indietro una cella per giro (prima $-14 \to -7$, poi $-13 \to -8$, infine $-12 \to -9$), perché a ogni giro l’informazione buona arretra di un passo lungo il percorso. Gli stati vicini al terminale si sistemano per primi; quelli più lontani richiedono più iterazioni. Dopo pochi giri il miglioramento non modifica più alcuna azione: la policy è ottima e la value function corrente è $V^{*}$.

In parole semplici: anche i valori di una strategia pessima insegnano qualcosa, perché dicono quale mossa è “meno peggio” delle altre. Il primo giro sistema le scelte vicino all’obiettivo, i giri successivi propagano la correzione alle zone lontane, come un’onda che torna indietro dal traguardo. Quando l’onda ha raggiunto tutto, nessuna mossa cambia più: si è arrivati all’ottimo.

4.3 Il collo di bottiglia#

Il costo di policy iteration è dominato dal passo di valutazione: ogni iterazione esterna richiede molti sweep completi dello spazio degli stati solo per valutare, con precisione $\theta$, una policy che con ogni probabilità verrà scartata subito dopo. L’esempio del gridworld ha già suggerito che si tratta di uno spreco: la policy greedy si stabilizza ben prima che la valutazione converga. La domanda diventa: quanto si può troncare la valutazione senza perdere la convergenza all’ottimo? La cornice concettuale che risponde “quanto si vuole” è la generalized policy iteration della prossima sezione; la realizzazione estrema, un solo sweep di valutazione per miglioramento, è value iteration.

5. Generalized policy iteration#

L’idea che valutazione e miglioramento possano essere interlacciati a qualunque granularità ha un nome: generalized policy iteration (GPI). Il termine indica ogni schema in cui due processi interagiscono:

• un processo di valutazione, che spinge la value function corrente verso la coerenza con la policy corrente (verso $V^{\pi}$);
• un processo di miglioramento, che spinge la policy corrente verso la scelta greedy rispetto alla value function corrente.

Policy iteration è il caso estremo in cui la valutazione arriva a convergenza prima di ogni miglioramento; value iteration, oggetto della prossima sezione, è il caso estremo opposto, con un solo sweep di valutazione per miglioramento; la DP asincrona della sezione 7 interlaccia i due processi a grana ancora più fine, aggiornando singoli stati. In tutti i casi il comportamento qualitativo è lo stesso della scalata a zigzag di policy iteration: una traiettoria che rimbalza tra due “bersagli” mobili, con la valutazione che tira la value function verso il vincolo “$V$ coerente con $\pi$” e il miglioramento che tira la policy verso il vincolo “$\pi$ greedy rispetto a $V$”. I due processi in parte competono, perché ogni miglioramento rende la value function corrente obsoleta e ogni valutazione rende la policy corrente non più greedy; ma nel complesso cooperano, e la traiettoria converge verso l’unico punto in cui entrambi i vincoli sono soddisfatti simultaneamente.

Quel punto è caratterizzato con precisione: se la value function è coerente con la policy ($V = V^{\pi}$) e la policy è greedy rispetto alla value function, allora

$$V^{\pi}(s) = \max_{a \in \mathcal{A}(s)} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V^{\pi}(s') \right] \qquad \forall s$$

cioè vale l’equazione di ottimalità di Bellman: $V = V^{*}$ e $\pi = \pi^{*}$. La stabilità congiunta dei due processi implica l’ottimalità, e viceversa; per questo qualunque interlacciamento che continui a far progredire entrambi i processi finisce nell’ottimo.

La portata della GPI va molto oltre questo capitolo: quasi tutti i metodi di reinforcement learning che si incontreranno, compresi quelli model-free, sono istanze di GPI in cui cambia soltanto come viene realizzato il processo di valutazione (per esempio con stime campionarie invece che con backup esatti sul modello) e quanto spesso si migliora.

Idea chiave: valutazione e miglioramento sono due forze che si tirano a vicenda: qualunque modo di alternarle, anche parziale, sbilanciato o asincrono, converge allo stesso punto di equilibrio, l’unico in cui la policy è greedy rispetto alla propria value function. Quel punto è l’ottimo di Bellman.

In parole semplici: non importa se si misura tanto e si corregge poco, o si misura poco e si corregge subito: finché si continua sia a misurare sia a correggere, si finisce sempre nello stesso posto, dove misura e strategia non si contraddicono più. Quel posto è la soluzione ottima, e quasi tutto il reinforcement learning è una variazione su questo schema.

6. La scorciatoia: value iteration#

6.1 Fondere valutazione e miglioramento in un unico aggiornamento#

Si consideri l’istanza di GPI in cui il passo di valutazione esegue un solo sweep e si ferma. La sequenza delle operazioni per uno stato $s$ diventa: un backup di valutazione con la policy corrente $\pi$,

$$V_{k+1}(s) = r\big(s, \pi(s)\big) + \gamma \sum_{s'} p\big(s' \mid s, \pi(s)\big) \, V_k(s')$$

seguito subito dal miglioramento greedy, che ridefinisce $\pi(s) = \arg\max_a [\, r(s,a) + \gamma \sum_{s'} p(s' \mid s,a) V(s') \,]$. Ma se il miglioramento viene comunque eseguito subito dopo, tanto vale usare direttamente l’azione massimizzante dentro il backup di valutazione: i due passi si fondono in un unico aggiornamento che non fa più riferimento ad alcuna policy esplicita,

$$V_{k+1}(s) = \max_{a \in \mathcal{A}(s)} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V_k(s') \right] \qquad \forall s \in \mathcal{S}$$

Questo è l’aggiornamento di value iteration, e la sua forma è inconfondibile: è l’equazione di ottimalità di Bellman trasformata in regola di aggiornamento, esattamente come la iterative policy evaluation era l’equazione di aspettativa trasformata in regola di aggiornamento. In forma compatta, $V_{k+1} = T^{*} V_k$ con $T^{*}$ operatore di ottimalità di Bellman.

Idea chiave: value iteration elimina la policy dal ciclo: a ogni sweep ogni stato prende direttamente il valore della sua azione migliore rispetto alla stima corrente. Valutazione e miglioramento avvengono simultaneamente dentro il $\max$, e l’informazione fluisce verso l’ottimo a ogni sweep, senza sprecare sweep per valutare con precisione policy intermedie.

In parole semplici: invece di “prima misuro bene quanto rende la mia strategia, poi la correggo”, si fa tutto in un colpo: ogni situazione assume subito il valore della sua mossa migliore, ricalcolato a ogni giro. Non esiste più una strategia esplicita durante l’esecuzione; la strategia “implicita” cambia da sola a ogni giro, e alla fine si estrae quella ottima dai valori.

6.2 Convergenza e proprietà#

La convergenza di value iteration discende dalle proprietà di $T^{*}$ stabilite nel capitolo precedente: per $\gamma < 1$, $T^{*}$ è una $\gamma$-contrazione in norma del massimo e il suo unico punto fisso è $V^{*}$. Quindi, per qualunque inizializzazione $V_0$,

$$\left\lVert V_k - V^{*} \right\rVert_{\infty} \leq \gamma^k \left\lVert V_0 - V^{*} \right\rVert_{\infty} \qquad \Longrightarrow \qquad \lim_{k \to \infty} V_k = V^{*}$$

La convergenza è geometrica di fattore $\gamma$ ma, a differenza di policy iteration, asintotica: in generale nessuna iterata finita coincide esattamente con $V^{*}$, e ci si arresta quando la variazione massima di uno sweep scende sotto una soglia $\theta$ (con la stessa garanzia sulla distanza residua vista per la policy evaluation). Due osservazioni caratterizzano l’algoritmo:

• le iterate intermedie $V_k$ in generale non sono la value function di nessuna policy: sono oggetti intermedi che interpolano tra la stima iniziale e $V^{*}$; questo non è un problema, perché interessa solo il limite;
• durante l’esecuzione non viene mai costruita né memorizzata una policy; al termine, la policy ottima (approssimata) si estrae dai valori con un ultimo passo greedy:

$$\pi(s) = \arg\max_{a \in \mathcal{A}(s)} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V(s') \right]$$

Questo passo finale è legittimo proprio perché applicato a (un’approssimazione di) $V^{*}$: come stabilito nel capitolo precedente, la policy greedy rispetto alla value function ottima è la policy ottima.

Lo pseudocodice, sensibilmente più semplice di quello di policy iteration (un solo loop invece di due annidati):

Value Iteration
Input: modello (p, r), discount γ, soglia θ > 0

Inizializza V(s) arbitrariamente per ogni s ∈ S (V = 0 sugli stati terminali)
ripeti
    Δ ← 0
    per ogni s ∈ S:
        v ← V(s)
        V(s) ← max_a [ r(s,a) + γ Σ_{s'} p(s'|s,a) V(s') ]
        Δ ← max(Δ, |v − V(s)|)
finché Δ < θ
Output: policy deterministica π(s) = argmax_a [ r(s,a) + γ Σ_{s'} p(s'|s,a) V(s') ]

6.3 Policy iteration e value iteration a confronto#

Nessuno dei due domina l’altro in assoluto: policy iteration fa poche iterazioni costose, value iteration molte iterazioni economiche; quale sia più veloce dipende dal problema. Value iteration ha però il pregio della semplicità e propaga informazione verso l’ottimo a ogni singolo sweep, senza mai “fermarsi a rifinire” la valutazione di una policy provvisoria. Concettualmente, i due algoritmi restano gli estremi dello spettro della generalized policy iteration: valutazione completa a ogni giro da un lato, valutazione troncata a un solo sweep dall’altro, con tutte le vie di mezzo ugualmente legittime.

7. Programmazione dinamica asincrona#

Gli algoritmi visti finora sono sincroni: ogni iterazione esegue uno sweep esaustivo, aggiornando tutti gli stati uno dopo l’altro in un ordine fissato. Su spazi di stati molto grandi questo è un vincolo pesante: un singolo sweep può essere proibitivo, e molti aggiornamenti sono sprecati su stati i cui valori sono già accurati o irrilevanti. La DP asincrona rimuove il vincolo dello sweep: gli stati vengono aggiornati singolarmente, in qualunque ordine, usando ogni volta i valori correnti (aggiornamento in place) degli altri stati. Lo schema generale è:

• si sceglie uno stato $s$ (con una qualche strategia di selezione);
• si applica a $s$ il backup appropriato (di aspettativa, se si sta valutando una policy; di ottimalità, se si sta facendo value iteration);
• si ripete finché un criterio di convergenza non è soddisfatto.

La convergenza ai valori corretti resta garantita a una condizione: nessuno stato deve essere abbandonato per sempre, cioè ogni stato deve continuare a essere selezionato (tutti gli stati devono essere aggiornati infinite volte, nel limite). All’interno di questo vincolo, la libertà nell’ordine di aggiornamento apre tre opportunità concrete:

• selezione casuale e parallelismo: invece di uno sweep sequenziale si estraggono stati a caso e li si aggiorna; poiché non c’è più un ordine obbligato, più unità di calcolo possono aggiornare in parallelo regioni diverse dello spazio degli stati, il che sposa bene le architetture di calcolo moderne;
• prioritized sweeping: la selezione può essere resa intelligente dando priorità agli stati “più bisognosi”, per esempio quelli con il maggiore errore di Bellman corrente, $\big| \max_a [\, r(s,a) + \gamma \sum_{s'} p(s' \mid s,a) V(s') \,] - V(s) \big|$: si aggiorna lo stato in cima alla coda di priorità, si ricalcola la priorità dei suoi predecessori (che sono quelli il cui valore dipende dal suo) e si procede; l’informazione si propaga così all’indietro lungo le direzioni in cui serve davvero. Anche una conoscenza parziale del problema, come una policy quasi buona già disponibile, può guidare la scelta delle zone da cui partire;
• real-time DP: la guida più naturale per la selezione è l’esperienza dell’agente stesso: si eseguono i backup sugli stati che l’agente visita realmente interagendo con l’ambiente secondo la policy corrente. Il calcolo si concentra così sulle parti dello spazio degli stati che sono effettivamente rilevanti per il comportamento, ignorando a lungo (legittimamente) le regioni mai raggiunte.

La DP asincrona non riduce il costo teorico del problema, ma permette spesso di trovare policy buone con molto meno calcolo di quello richiesto da sweep esaustivi, e di applicare la DP a problemi più grandi di quelli trattabili in forma sincrona.

In parole semplici: non serve rifare tutti i conti su tutta la mappa a ogni giro: si possono aggiornare le caselle una alla volta, in qualsiasi ordine, magari partendo da quelle più sbagliate o da quelle che l’agente incontra davvero. Basta non dimenticarsi per sempre di nessuna casella, e il risultato finale è lo stesso, spesso con molta meno fatica.

8. Efficienza e limiti della programmazione dinamica#

8.1 Complessità computazionale#

Quanto costa la DP? La buona notizia è che trovare una policy ottima con la programmazione dinamica ha costo polinomiale nel numero di stati e di azioni, laddove la ricerca diretta nello spazio delle policy dovrebbe esaminarne $|\mathcal{A}|^{|\mathcal{S}|}$, un numero esponenziale: rispetto alla forza bruta, la DP è esponenzialmente più efficiente. Le stime di riferimento:

• value iteration: ogni sweep costa $O(|\mathcal{S}|^2 |\mathcal{A}|)$, perché per ciascuno degli $|\mathcal{S}|$ stati si valutano $|\mathcal{A}|$ azioni, ognuna con una somma su fino a $|\mathcal{S}|$ successori;
• policy iteration: la valutazione iterativa di una policy fino a precisione $\epsilon$ costa dell’ordine di $O\!\left( |\mathcal{S}|^2 \, \frac{\log(1/\epsilon)}{\log(1/\gamma)} \right)$ (ogni sweep costa $O(|\mathcal{S}|^2)$ a policy fissata, e il numero di sweep segue dalla contrazione di fattore $\gamma$); per la fase di miglioramento, il numero di iterazioni necessarie è limitato da una quantità dell’ordine di $O\!\left( \frac{|\mathcal{A}|}{1 - \gamma} \, \log \frac{|\mathcal{S}|}{1 - \gamma} \right)$.

In entrambi i casi il fattore $1/(1-\gamma)$ segnala che problemi molto lungimiranti (con $\gamma$ vicino a 1) sono intrinsecamente più costosi: la contrazione è più lenta e l’informazione deve propagarsi su orizzonti effettivi più lunghi. Esistono anche approcci alternativi alla DP basati sulla programmazione lineare, che riformulano la ricerca di $V^{*}$ come problema di ottimizzazione lineare; in teoria sono eleganti, ma in pratica scalano peggio della DP al crescere del problema.

8.2 La maledizione della dimensionalità#

La cattiva notizia è che “polinomiale in $|\mathcal{S}|$” è una consolazione solo apparente, perché $|\mathcal{S}|$ stesso è spesso astronomico. Il fenomeno ha un nome: curse of dimensionality (maledizione della dimensionalità). Se lo stato è descritto da $n$ variabili, ciascuna con $d$ valori possibili, allora $|\mathcal{S}| = d^n$: il numero di stati cresce esponenzialmente con il numero di variabili di stato, non con la loro dimensione fisica. Una scacchiera ha 64 caselle ma circa $10^{44}$ configurazioni; un robot con una decina di sensori continui discretizzati ha uno spazio di stati che nessuna tabella può contenere.

In pratica:

• la DP classica (sincrona, tabellare) è applicabile fino a qualche milione di stati;
• la DP asincrona, concentrando il calcolo dove serve e prestandosi al parallelismo, arriva a problemi più grandi;
• ma è facile costruire MDP perfettamente ragionevoli per i quali qualunque metodo di DP tabellare è impraticabile.

In parole semplici: il costo della DP cresce “solo” come una potenza del numero di stati, ma il numero di stati esplode come una potenza del numero di variabili che descrivono la situazione. Basta aggiungere qualche sensore o qualche caratteristica allo stato e la tabella dei valori diventa più grande di qualunque memoria: è questo, non l’algoritmo, il vero muro.

8.3 Il limite fondamentale: serve il modello#

C’è però un limite ancora più radicale del costo computazionale, ed è visibile in ogni singola formula di questo capitolo: ogni backup di DP richiede $r(s, a)$ e $p(s' \mid s, a)$, cioè la dinamica one-step completa dell’MDP. La DP non è un metodo di apprendimento ma di pianificazione: calcola la soluzione a partire dalla descrizione perfetta del problema. Nei problemi reali questa descrizione spesso non c’è:

• la dinamica può essere ignota: nessuno fornisce la tabella delle probabilità di transizione di un mercato finanziario o di un utente che interagisce con un sistema;
• oppure può essere nota in linea di principio ma proibitiva da modellare: costruire un modello accurato può essere più difficile che risolvere il problema, e un modello sbagliato produce una “soluzione ottima” del problema sbagliato.

Ciò che invece è quasi sempre disponibile, o generabile con un simulatore, è l’esperienza: traiettorie di stati, azioni e reward osservate interagendo con l’ambiente. I metodi dei prossimi capitoli, detti model-free, ripartono esattamente da qui: mantengono l’architettura concettuale costruita in questo capitolo, la generalized policy iteration, ma sostituiscono i backup esatti sul modello con stime ottenute dai campioni. Il primo rappresentante della famiglia, i metodi Monte Carlo, stima le value function mediando i return effettivamente osservati; questa sostituzione, come si vedrà, porta con sé un problema nuovo e centrale, quello dell’esplorazione. Le equazioni di Bellman e lo schema valutazione-miglioramento restano il filo conduttore: cambia solo il modo di calcolare le aspettative quando il modello non c’è.

Idea chiave: la DP risolve gli MDP alla perfezione, ma a due condizioni che il mondo reale raramente concede: uno spazio di stati abbastanza piccolo da essere spazzato, e un modello completo della dinamica. Il reinforcement learning propriamente detto nasce rinunciando alla seconda condizione: stessi obiettivi, stesse equazioni, ma aspettative stimate dall’esperienza invece che calcolate dal modello.

9. Esempio svolto: value iteration sul robot riciclatore#

Per chiudere il cerchio si applica value iteration, passo per passo, al piccolo MDP del robot riciclatore già risolto analiticamente nel capitolo precedente, di cui si conoscono quindi in anticipo la soluzione ottima e la value function ottima: un banco di prova ideale.

9.1 Il modello e le equazioni di aggiornamento#

Richiamo dei dati: stati $\{A, B\}$ (batteria alta e bassa), $\gamma = 0{,}9$. Nello stato $A$ le azioni sono cerca (reward $2$; resta in $A$ con probabilità $0{,}9$, scende in $B$ con probabilità $0{,}1$) e attendi (reward $1$; resta in $A$). Nello stato $B$ le azioni sono cerca (reward atteso $0$, perché $0{,}6 \cdot 2 + 0{,}4 \cdot (-3) = 0$; resta in $B$ con probabilità $0{,}6$, con probabilità $0{,}4$ la batteria si esaurisce e il robot viene soccorso e riportato in $A$), attendi (reward $1$; resta in $B$) e ricarica (reward $0$; va in $A$). La soluzione nota: la policy ottima è $\pi^{*} = (\text{cerca in } A,\ \text{ricarica in } B)$, con $V^{*}(A) \approx 18{,}35$ e $V^{*}(B) \approx 16{,}51$.

L’aggiornamento di value iteration, scritto esplicitamente per i due stati:

$$V_{k+1}(A) = \max \Big\{ \underbrace{2 + 0{,}9 \big( 0{,}9 \, V_k(A) + 0{,}1 \, V_k(B) \big)}_{\text{cerca}}, \ \underbrace{1 + 0{,}9 \, V_k(A)}_{\text{attendi}} \Big\}$$

$$V_{k+1}(B) = \max \Big\{ \underbrace{0{,}9 \big( 0{,}6 \, V_k(B) + 0{,}4 \, V_k(A) \big)}_{\text{cerca}}, \ \underbrace{1 + 0{,}9 \, V_k(B)}_{\text{attendi}}, \ \underbrace{0{,}9 \, V_k(A)}_{\text{ricarica}} \Big\}$$

9.2 Le prime iterazioni a mano#

Si parte da $V_0 = (0, 0)$.

Iterazione 1. In $A$: cerca dà $2 + 0{,}9 \cdot 0 = 2$, attendi dà $1$: vince cerca, $V_1(A) = 2$. In $B$: cerca dà $0$, attendi dà $1$, ricarica dà $0$: vince attendi, $V_1(B) = 1$.

Iterazione 2. In $A$: cerca dà $2 + 0{,}9 (0{,}9 \cdot 2 + 0{,}1 \cdot 1) = 2 + 0{,}9 \cdot 1{,}9 = 3{,}71$; attendi dà $1 + 1{,}8 = 2{,}8$: vince cerca, $V_2(A) = 3{,}71$. In $B$: cerca dà $0{,}9 (0{,}6 \cdot 1 + 0{,}4 \cdot 2) = 1{,}26$; attendi dà $1 + 0{,}9 = 1{,}9$; ricarica dà $0{,}9 \cdot 2 = 1{,}8$: vince ancora attendi, per un soffio, $V_2(B) = 1{,}9$.

Iterazione 3. In $A$: cerca dà $2 + 0{,}9 (0{,}9 \cdot 3{,}71 + 0{,}1 \cdot 1{,}9) = 2 + 0{,}9 \cdot 3{,}529 \approx 5{,}18$; attendi dà $4{,}34$: $V_3(A) \approx 5{,}18$. In $B$: cerca dà $0{,}9 (0{,}6 \cdot 1{,}9 + 0{,}4 \cdot 3{,}71) \approx 2{,}36$; attendi dà $1 + 1{,}71 = 2{,}71$; ricarica dà $0{,}9 \cdot 3{,}71 \approx 3{,}34$: qui avviene il sorpasso, vince ricarica, $V_3(B) \approx 3{,}34$. Il motivo è leggibile: man mano che $V_k(A)$ cresce, il valore di “tornare in $A$” cresce con lui, finché il guadagno immediato di attendi ($+1$) non basta più a compensare la rinuncia a trovarsi in $A$.

La tabella riassume le prime iterazioni e, per ciascuna $V_k$, la policy greedy che se ne estrarrebbe:

9.3 Che cosa insegna l’esempio#

Tre osservazioni condensano i messaggi del capitolo:

• la policy converge molto prima dei valori: la policy greedy estratta da $V_k$ è già quella ottima da $k = 2$ in poi, quando i valori ($3{,}71$ e $1{,}90$) distano ancora enormemente da quelli ottimi ($18{,}35$ e $16{,}51$). Come nel gridworld, per decidere bene serve l’ordinamento corretto tra le alternative, non i valori esatti;
• la velocità di convergenza dei valori è dettata da $\gamma$: la garanzia di contrazione dà $\lVert V_k - V^{*} \rVert_{\infty} \leq 0{,}9^k \lVert V_0 - V^{*} \rVert_{\infty} = 0{,}9^k \cdot 18{,}35$. Per portare l’errore sotto $0{,}1$ servono circa $k \approx 50$ sweep: la coda della convergenza è lunga, coerentemente con il fattore $1/(1-\gamma) = 10$ di questo problema;
• il limite coincide con la soluzione analitica: la successione converge esattamente alla $V^{*}$ calcolata nel capitolo precedente risolvendo le equazioni di ottimalità, e la policy estratta è la $\pi^{*}$ certificata allora. Value iteration è a tutti gli effetti un solutore iterativo di quelle equazioni non lineari che non ammettevano forma chiusa.

In parole semplici: l’algoritmo scopre quasi subito “che cosa” conviene fare (cercare con batteria alta, ricaricare con batteria bassa) e impiega molto più tempo a stabilire con precisione “quanto vale” farlo. Se l’obiettivo è la strategia, ci si può fermare presto; se servono i valori esatti, si paga la lentezza della contrazione, tanto più cara quanto più $\gamma$ è vicino a 1.

Glossario#

Dispensa Machine Learning · Politecnico di Milano