Value Iteration e Policy Iteration: i due scheletri del reinforcement learning

Due algoritmi degli anni Cinquanta, scritti su MDP noto e finito, contengono già l’ossatura di Q-learning, DQN e AlphaZero. Capirli puri è il modo più rapido per riconoscerli sotto travestimento.

Perché questo capitolo

Il capitolo precedente ha trattato l’equazione di Bellman come operatore: una funzione $T^*$ che mangia una stima di valore e ne restituisce una migliore, contraendo verso $V^*$ a rate $\gamma$ . Questo è un teorema di esistenza e di geometria. Resta da rispondere a una domanda operativa: dato un MDP completamente noto — transizioni $P(s'|s,a)$ e ricompense $R(s,a)$ in chiaro — come si calcola in pratica $V^*$ e una policy ottima $\pi^*$ ?

Le due risposte canoniche sono Value Iteration e Policy Iteration. Sono datate, semplici, tabular, e sembrano lontane dai modelli moderni. Sono invece il vocabolario con cui leggere quasi tutto il reinforcement learning successivo. Q-learning estrae VI dal regime “modello noto” e lo trasforma in stimatore campionario. DQN aggiunge una rete neurale a quello stimatore e ottiene Approximate Value Iteration. Actor-critic alterna policy improvement e policy evaluation parziali, cioè è un’istanza di Generalized Policy Iteration. AlphaZero, nel paper Nature del 2017, dichiara esplicitamente di addestrarsi tramite policy iteration, dove l’improvement è un MCTS e l’evaluation è il risultato delle partite di self-play.

Capire VI e PI nella loro forma pulita, su MDP finiti e noti, ha quindi un valore doppio. Primo, sono utili in sé: i problemi di planning con modello noto esistono — controllo di inventario, code, pianificazione robotica con world model, gridworld didattici, AlphaZero stesso che gioca contro un modello deterministico delle regole del Go. Secondo, ogni algoritmo RL successivo si capisce più in fretta se si vede subito quale operatore sta simulando con i campioni e quali garanzie sta perdendo per strada. Quando un sistema RL diverge, la diagnosi di solito comincia chiedendosi: “Chi è T*, qui? E chi è $\pi$ ? E perché la contrazione è infranta?”.

Contesto

Richard Bellman (matematico americano, 1920-1984, RAND Corporation) introduce VI nel libro Dynamic Programming del 1957 sotto il nome di “successive approximations method”. L’idea è elementare: applichi $T^*$ a una stima iniziale qualsiasi, ottieni una stima migliore, ripeti. La convergenza segue dal fatto che $T^*$ è una contrazione $\gamma$ in norma del massimo, come dimostrato in equazione-bellman (123).

Tre anni dopo Ronald Howard (ingegnere operations research, MIT poi Stanford), nella tesi di dottorato pubblicata come Dynamic Programming and Markov Processes (MIT Press, 1960), introduce Policy Iteration in forma matura e dimostra il policy improvement theorem: rendendo una policy greedy rispetto al proprio valore, si ottiene una policy strettamente migliore — a meno di essere già ottimi, nel qual caso si è all’arresto. Combinato con la finitezza dello spazio delle policy deterministiche su un MDP finito, questo dà un teorema di terminazione finita: PI termina in al più $|A|^{|S|}$ passi. In pratica termina in molti meno — cinque, dieci, raramente venti, anche su problemi con migliaia di stati.

Le due varianti convivono per quindici anni. Poi, nel 1978, Martin Puterman (operations researcher canadese, University of British Columbia) e Moon Chil Shin pubblicano su Operations Research “Modified Policy Iteration Algorithms for Discounted Markov Decision Problems”: un’interpolazione fra VI e PI in cui la fase di evaluation viene troncata a $m$ passi. Per $m=1$ si recupera VI; per $m=\infty$ si recupera PI. Il vantaggio computazionale è netto su problemi medi: ci si ferma a $m$ piccolo (cinque o dieci) e si ottengono policy iteration veloci, con costo per iterazione paragonabile a quello di VI.

Dimitri Bertsekas (informatico greco, MIT) sistematizza negli anni Ottanta in Dynamic Programming and Optimal Control la versione asincrona: aggiorni un solo stato alla volta, in qualsiasi ordine, basta che ogni stato venga visitato infinitamente spesso. Andrew Moore e Christopher Atkeson (Carnegie Mellon, Machine Learning 1993) raffinano questa idea con prioritized sweeping: aggiorna prima gli stati con il backup error più alto, mantenuti in una priority queue. È la prima volta che VI diventa praticamente competitivo su problemi sparsi grandi.

Sul versante della formulazione, F. d’Epenoux già nel 1963 (Management Science 10) aveva dimostrato che $V^*$ è soluzione di un programma lineare, con duale interpretabile come state-action visitation. È l’altra faccia matematica del problema, oggi meno usata ma teoricamente importante perché collega RL e ottimizzazione convessa.

L’impatto di VI/PI sull’apprendimento — quando l’MDP non è noto — viene molto dopo. Watkins introduce Q-learning nel 1989 come VI sample-based: si vedrà nel capitolo q-learning (in preparazione). Damien Ernst, Pierre Geurts, Louis Wehenkel (JMLR 2005) pubblicano Fitted Q-Iteration, l’estensione batch di VI con regressore generico. Michail Lagoudakis e Ronald Parr (JMLR 2003) introducono LSPI, l’estensione di PI con least-squares TD per la policy evaluation sotto rappresentazione lineare. Sono i due punti di riferimento di approximate dynamic programming su cui si appoggiano DQN e i suoi derivati.

Una nota di differenziazione rispetto ai due capitoli precedenti, importante per non avere doppioni. In markov-decision-process (122) si è introdotto l’MDP come framework e si è citato VI/PI di passaggio. In equazione-bellman (123) si è trattato l’operatore $T^*$ come contrazione e si è dato il framework di Generalized Policy Iteration. Qui ci si concentra sui due algoritmi nella loro forma operativa: pseudocodice eseguibile, criteri di stopping, esempi numerici, pattern di chiamata. Il “perché funzionano” è in 123; il “come si scrive il codice” è qui.

L’intuizione

Due angoli, distinti, da percorrere prima della formula. Uno descrive VI; l’altro descrive PI. Un terzo angolo cattura entrambi sotto un’unica narrazione.

Angolo 1 — VI: applicare T* finché smette di cambiare

Hai una stima iniziale $V_0$ qualsiasi. Costante zero va benissimo, anche un valore casuale funziona. La regola di aggiornamento dice: per ogni stato, sostituisci la stima corrente con il massimo, su tutte le azioni, della ricompensa immediata più $\gamma$ volte la media pesata della stima nei prossimi stati. È esattamente $T^* V$ . Ripeti. Smetti quando due iterazioni successive differiscono di meno di una soglia $\varepsilon$ scelta in funzione del bound di sub-ottimalità che vuoi garantire. La policy ottenuta facendo greedy sull’ultima stima è quasi ottima, con bound esplicito.

Visivamente: sopra $S$ c’è una mappa di altimetria. A ogni passo lisci la mappa applicando una volta la dinamica al rovescio. La mappa converge a un’unica forma che non si modifica più — il fixed point $V^*$ . Il numero di passi necessari è geometrico in $\gamma$ : se $\gamma=0.9$ servono circa $\log(\varepsilon) / \log(0.9) \approx 22$ passi per ridurre l’errore di un fattore $10$ , indipendentemente dalla dimensione di $S$ .

Angolo 2 — PI: alterna calcolare bene una policy e migliorarla un po’

Hai una policy $\pi_0$ qualsiasi (anche random uniforme). Due passi che si alternano:

Policy evaluation: dato $\pi$ , calcola $V^\pi$ — il valore esatto di seguire $\pi$ per sempre. Si fa risolvendo un sistema lineare $|S| \times |S|$ , oppure iterando $T^\pi$ fino a convergenza.
Policy improvement: rendi $\pi$ greedy rispetto a $V^\pi$ . Cioè, per ogni stato, scegli l’azione che massimizza $R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^\pi(s')$ .

Ripeti finché la policy non cambia più. Howard ha dimostrato che ogni iterazione produce una policy strettamente migliore (o uguale, e in tal caso siamo all’ottimo). Poiché le policy deterministiche sono finite, ci si ferma in un numero finito di passi.

L’analogia mentale: affilare una lama. La policy evaluation è l’olio sulla pietra — lavora bene su ciò che c’è. Il policy improvement è la passata che corregge l’angolo. Una passata su cinque l’angolo è già giusto, ma per saperlo devi prima oliare bene. Marchiamo questa come analogia: somiglianza didattica, niente di più.

Angolo 3 — Generalized Policy Iteration: lo scheletro comune

Sutton e Barto, nella seconda edizione di Reinforcement Learning: An Introduction del 2018, propongono uno scheletro che inquadra VI, PI, modified PI e ogni algoritmo successivo: Generalized Policy Iteration (GPI). L’idea è che qualsiasi alternanza di evaluation parziale e improvement parziale, purché entrambi i processi siano “freschi” — cioè non si fermino prima dell’ottimo — converge alla coppia ottima $(V^*, \pi^*)$ .

VI è GPI con improvement implicito a ogni passo (il massimo nell’aggiornamento) e evaluation di un solo passo. PI è GPI con improvement raro e evaluation completa. Modified PI è GPI con improvement raro e evaluation troncata. Actor-critic è GPI con improvement via gradient e evaluation via TD. AlphaZero è GPI con improvement via MCTS e evaluation via outcome di self-play. Una volta vista questa forma, la maggior parte degli algoritmi RL si riconosce a colpo d’occhio.

GPI cycle: two arrows between policy and value spaces, evaluation and improvement, converging to optimal pair

La meccanica

Setup

Sia $\mathcal{M} = (S, A, P, R, \gamma)$ un MDP finito con $\gamma \in [0,1)$ . La value function ottima $V^*$ è il punto fisso dell’operatore di Bellman ottimale:

(T^* V)(s) = \max_{a \in A} \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V(s') \right].

La policy ottima è greedy rispetto a $V^*$ :

\pi^*(s) = \arg\max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s') \right].

Per una policy data $\pi$ , l’operatore di expectation è

(T^\pi V)(s) = \sum_{a} \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V(s') \right],

e $V^\pi$ è il suo unico punto fisso.

Value Iteration: pseudocodice

function VALUE_ITERATION(MDP, gamma, eps):
    V = array of zeros, length |S|
    while True:
        delta = 0
        V_new = empty array
        for s in S:
            V_new[s] = max over a of [R(s,a) + gamma * sum over s' of P(s'|s,a) * V[s']]
            delta = max(delta, |V_new[s] - V[s]|)
        V = V_new
        if delta < eps * (1 - gamma) / (2 * gamma):
            break
    pi(s) = argmax over a of [R(s,a) + gamma * sum over s' of P(s'|s,a) * V[s']]
    return V, pi

Riga per riga. La condizione di stopping $delta < eps * (1-gamma) / (2*gamma)$ deriva da un teorema che marchiamo come TEOREMA: se $\|V_{k+1} - V_k\|_\infty < \delta$ , allora $\|V_{k+1} - V^*\|_\infty < \delta \gamma / (1-\gamma)$ , e la policy greedy $\pi$ derivata da $V_{k+1}$ è $\delta \cdot 2\gamma/(1-\gamma)$ -ottima. Scegliendo $\delta = \varepsilon (1-\gamma)/(2\gamma)$ si garantisce sub-ottimalità $\varepsilon$ .

Costo per iterazione: $O(|S|^2 |A|)$ . Numero di iterazioni necessarie per scendere sotto soglia $\varepsilon$ partendo da $V_0=0$ : circa $\log_{1/\gamma}(R_{\max}/(\varepsilon (1-\gamma)))$ , dove $R_{\max}$ è il reward massimo.

Implementazione vettorizzata in numpy:

import numpy as np

def value_iteration(P, R, gamma=0.9, eps=1e-6):
    """
    P: array (|S|, |A|, |S|) — P[s, a, s'] = transition prob
    R: array (|S|, |A|) — reward when taking a in s
    Returns V (|S|,) and pi (|S|,).
    """
    nS, nA, _ = P.shape
    V = np.zeros(nS)
    threshold = eps * (1 - gamma) / (2 * gamma)
    while True:
        # Q[s, a] = R[s, a] + gamma * sum_{s'} P[s, a, s'] * V[s']
        Q = R + gamma * P @ V  # shape (|S|, |A|)
        V_new = Q.max(axis=1)
        if np.max(np.abs(V_new - V)) < threshold:
            V = V_new
            break
        V = V_new
    pi = (R + gamma * P @ V).argmax(axis=1)
    return V, pi

Policy Iteration: pseudocodice

function POLICY_ITERATION(MDP, gamma):
    pi = arbitrary policy (e.g., random)
    while True:
        # Policy evaluation: solve V = R^pi + gamma * P^pi V
        V = solve_linear_system(I - gamma * P_pi, R_pi)
        # Policy improvement
        pi_new(s) = argmax over a of [R(s,a) + gamma * sum over s' of P(s'|s,a) * V[s']]
        if pi_new == pi:
            return V, pi
        pi = pi_new

Riga per riga. $P_\pi$ è la matrice $|S| \times |S|$ con $P_\pi[s, s'] = P(s' \mid s, \pi(s))$ ; analogamente $R_\pi[s] = R(s, \pi(s))$ . La policy evaluation esatta richiede di risolvere un sistema lineare di dimensione $|S|$ , costo $O(|S|^3)$ con Gaussian elimination. In alternativa si itera $T^\pi$ fino a convergenza, costo $O(|S|^2)$ per iterazione. Il policy improvement è $O(|S|^2 |A|)$ .

TEOREMA (Howard 1960): PI termina in al più $|A|^{|S|}$ passi su MDP finito; ogni iterazione produce $V^{\pi_{k+1}} \ge V^{\pi_k}$ componente-wise, con disuguaglianza stretta in almeno uno stato a meno che $\pi_k$ non sia già ottima.

Implementazione numpy:

def policy_iteration(P, R, gamma=0.9):
    nS, nA, _ = P.shape
    pi = np.zeros(nS, dtype=int)
    while True:
        # Policy evaluation: exact linear solve
        P_pi = P[np.arange(nS), pi]      # shape (|S|, |S|)
        R_pi = R[np.arange(nS), pi]      # shape (|S|,)
        V = np.linalg.solve(np.eye(nS) - gamma * P_pi, R_pi)
        # Policy improvement
        Q = R + gamma * P @ V             # shape (|S|, |A|)
        pi_new = Q.argmax(axis=1)
        if np.array_equal(pi_new, pi):
            return V, pi
        pi = pi_new

Modified Policy Iteration

Sostituisci la policy evaluation esatta con $m$ applicazioni di $T^\pi$ :

def modified_policy_iteration(P, R, gamma=0.9, m=10, eps=1e-6):
    nS, nA, _ = P.shape
    pi = np.zeros(nS, dtype=int)
    V = np.zeros(nS)
    while True:
        # Partial policy evaluation: m steps of T^pi
        for _ in range(m):
            P_pi = P[np.arange(nS), pi]
            R_pi = R[np.arange(nS), pi]
            V = R_pi + gamma * P_pi @ V
        # Policy improvement
        Q = R + gamma * P @ V
        pi_new = Q.argmax(axis=1)
        if np.array_equal(pi_new, pi):
            return V, pi
        pi = pi_new

Per $m=1$ è (essenzialmente) VI con policy esplicita; per $m \to \infty$ è PI. Tipicamente $m \in [5, 50]$ dà il miglior compromesso.

Asynchronous DP

L’aggiornamento sincrono — calcolare $V_{\text{new}}[s]$ per tutti gli $s$ e poi sostituire — non è necessario. Bertsekas dimostra che VI converge anche se aggiorni un solo stato alla volta, in qualsiasi ordine, purché ogni stato venga visitato infinitamente spesso. Gauss-Seidel è il caso particolare in cui aggiorni in-place: dopo aver calcolato il nuovo $V[s]$ , le successive valutazioni nello stesso giro usano il valore aggiornato. Spesso accelera la convergenza di un fattore 2-3.

Prioritized sweeping (Moore-Atkeson 1993): mantieni una priority queue di stati ordinati per Bellman error stimato $|V_{\text{new}}[s] - V[s]|$ . Aggiorna prima gli stati con error più alto. Quando aggiorni $s$ , propaga indietro: ricalcola l’error stimato per tutti i predecessori di $s$ e reinseriscili nella queue. Su problemi sparsi con molti stati “morti” è ordini di grandezza più veloce di VI sincrono.

flowchart LR
    V0["V_0 (init qualsiasi)"] -- "T*" --> V1["V_1"]
    V1 -- "T*, contrazione di γ" --> V2["V_2"]
    V2 -- "..." --> Vk["V_k"]
    Vk -- "T*" --> Vk1["V_{k+1}"]
    Vk1 --> Stop{"||V_{k+1} - V_k||∞ < ε(1-γ)/(2γ)?"}
    Stop -- "no" --> Vk1
    Stop -- "sì" --> Vstar["V* (ε-ottimo)"]
    Vstar --> Pi["π = greedy(V*)"]

Figura 2 — VI step-by-step pipeline: V_0 → T → V_1 → T* → V_2 → … → V*; arrows labelled with contraction factor gamma*

Esempi

Esempio 1 — MDP a 3 stati, calcolo a mano

Tre stati $\{s_1, s_2, s_3\}$ , due azioni $\{a_1, a_2\}$ , $\gamma=0.9$ . $s_3$ è assorbente con reward 0. Da $s_1$ : $a_1$ porta in $s_2$ con reward 1; $a_2$ porta in $s_3$ con reward 5. Da $s_2$ : $a_1$ porta in $s_1$ con reward 0; $a_2$ porta in $s_3$ con reward 10. Tutte le transizioni deterministiche.

VI partendo da $V_0 = (0, 0, 0)$ :

Iterazione 1: $V_1(s_1) = \max(1 + 0.9 \cdot 0,\; 5 + 0.9 \cdot 0) = 5$ ; $V_1(s_2) = \max(0 + 0.9 \cdot 0,\; 10 + 0.9 \cdot 0) = 10$ ; $V_1(s_3) = 0$ .

Iterazione 2: $V_2(s_1) = \max(1 + 0.9 \cdot 10,\; 5 + 0.9 \cdot 0) = \max(10, 5) = 10$ ; $V_2(s_2) = \max(0 + 0.9 \cdot 5,\; 10 + 0.9 \cdot 0) = \max(4.5, 10) = 10$ ; $V_2(s_3) = 0$ .

Iterazione 3: $V_3(s_1) = \max(1 + 0.9 \cdot 10, 5) = 10$ ; $V_3(s_2) = \max(0.9 \cdot 10, 10) = 10$ . Convergenza.

Policy ottima: $\pi^*(s_1) = a_1$ (andare in $s_2$ ), $\pi^*(s_2) = a_2$ (terminare). Notare che il primo passo di VI dava $\pi^*(s_1) = a_2$ , sbagliato; serve il secondo passo per propagare il valore di $s_2$ indietro a $s_1$ .

PI partendo da $\pi_0(s_1) = \pi_0(s_2) = a_1$ . Policy evaluation: $V^{\pi_0}(s_1) = 1 + 0.9 V^{\pi_0}(s_2)$ , $V^{\pi_0}(s_2) = 0 + 0.9 V^{\pi_0}(s_1)$ . Sistema $V^{\pi_0}(s_1) = 1/(1 - 0.81) = 5.26$ , $V^{\pi_0}(s_2) = 4.74$ . Policy improvement: in $s_1$ , $a_1$ vale $1 + 0.9 \cdot 4.74 = 5.27$ , $a_2$ vale $5$ → $a_1$ . In $s_2$ , $a_1$ vale $0.9 \cdot 5.26 = 4.74$ , $a_2$ vale $10$ → $a_2$ . Nuova policy $\pi_1(s_1) = a_1$ , $\pi_1(s_2) = a_2$ . Iterazione successiva: la policy non cambia → ottimo. PI in due passi; VI in tre.

Esempio 2 — Gridworld 4x4 in numpy

Griglia $4 \times 4$ , $|S| = 16$ . Stato terminale assorbente in $(0,0)$ con reward $0$ ; reward $-1$ per ogni passo in stati non terminali. Quattro azioni: su, giù, sinistra, destra. Movimento bloccato dai bordi (lo stato resta lo stesso). Discount $\gamma = 1$ (problema episodico, ma per semplicità di analisi tabular usiamo $\gamma = 0.99$ ).

import numpy as np

def build_gridworld(n=4, gamma=0.99, step_reward=-1.0):
    nS = n * n
    nA = 4  # up, down, left, right
    P = np.zeros((nS, nA, nS))
    R = np.full((nS, nA), step_reward)
    # action deltas: up, down, left, right
    deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    terminal = 0  # state (0, 0)
    for s in range(nS):
        r, c = divmod(s, n)
        for a, (dr, dc) in enumerate(deltas):
            if s == terminal:
                P[s, a, s] = 1.0
                R[s, a] = 0.0
                continue
            nr = max(0, min(n - 1, r + dr))
            nc = max(0, min(n - 1, c + dc))
            ns = nr * n + nc
            P[s, a, ns] = 1.0
    return P, R, gamma

P, R, gamma = build_gridworld()
V_vi, pi_vi = value_iteration(P, R, gamma)
V_pi, pi_pi = policy_iteration(P, R, gamma)

print("VI value function (4x4):")
print(V_vi.reshape(4, 4))
print("PI value function (4x4):")
print(V_pi.reshape(4, 4))
print("Identical policies:", np.array_equal(pi_vi, pi_pi))

VI converge in circa 200 iterazioni con $\varepsilon=10^{-6}$ , $\gamma=0.99$ . PI converge in 4 iterazioni: random → “tendenzialmente verso il bordo sbagliato” → directional → near-optimal → optimal. Le policy finali sono identiche. Le value function differiscono di meno di $10^{-6}$ .

flowchart LR
    V0["V_0 (init qualsiasi)"] -- "T*" --> V1["V_1"]
    V1 -- "T*, contrazione di γ" --> V2["V_2"]
    V2 -- "..." --> Vk["V_k"]
    Vk -- "T*" --> Vk1["V_{k+1}"]
    Vk1 --> Stop{"||V_{k+1} - V_k||∞ < ε(1-γ)/(2γ)?"}
    Stop -- "no" --> Vk1
    Stop -- "sì" --> Vstar["V* (ε-ottimo)"]
    Vstar --> Pi["π = greedy(V*)"]

Figura 2 — gridworld 4x4 value heatmap dopo 0, 5, 20, 100 iterazioni di VI; e policy arrows dopo iterazione 1, 2, 4 di PI

Lettura del grafico: in VI il valore “scorre” lentamente dal goal verso gli stati lontani, propagandosi un passo per iterazione. In PI il valore è già consistente con la policy corrente dopo la prima evaluation, e l’improvement riorienta tutta la mappa in un colpo solo.

Esempio 3 — AlphaZero come Policy Iteration

David Silver e colleghi DeepMind (Nature 2017, “Mastering the game of Go without human knowledge”) dichiarano esplicitamente di addestrare AlphaZero in stile policy iteration. EQUIVALENZA argomentabile, non analogia.

Schema. Una rete neurale $f_\theta$ produce, dato uno stato di gioco $s$ , due output: una policy $p_\theta(\cdot|s)$ (distribuzione su mosse) e un valore $v_\theta(s)$ (stima del risultato finale dal punto di vista del giocatore di turno).

Policy evaluation: si gioca una partita di self-play usando MCTS con $f_\theta$ come euristica. Il risultato finale $z \in \{-1, 0, +1\}$ (perdita, patta, vittoria) è un Monte Carlo rollout esatto, $z \approx V^{\pi_\theta}(s)$ per ogni stato $s$ visitato nella partita.
Policy improvement: a ogni stato $s$ visitato, MCTS produce una distribuzione di visita $\pi_{\text{MCTS}}(\cdot|s)$ che è strettamente migliore della policy diretta $p_\theta(\cdot|s)$ — perché MCTS espande l’albero a profondità multiple. È un policy improvement operator analogo (qui sì) al greedy improvement classico.
Aggiornamento di $\theta$ : si addestra $f_\theta$ a far combaciare $p_\theta$ con $\pi_{\text{MCTS}}$ (cross-entropy) e $v_\theta$ con $z$ (MSE). La loss è $L(\theta) = -\pi_{\text{MCTS}}^T \log p_\theta + (z - v_\theta)^2 + \lambda \|\theta\|^2$ .

Le due fasi di GPI sono tutte presenti. Il paper le nomina esplicitamente. La differenza con PI tabular è che la rappresentazione è una rete neurale, non una tabella, e la policy evaluation è approssimata con singoli rollout di self-play. Le garanzie di Howard non valgono direttamente — siamo in regime di Approximate PI con tutti i caveat che ne derivano (vedi sezione “Dove si rompe”) — ma lo schema è fedele.

flowchart LR
    V0["V_0 (init qualsiasi)"] -- "T*" --> V1["V_1"]
    V1 -- "T*, contrazione di γ" --> V2["V_2"]
    V2 -- "..." --> Vk["V_k"]
    Vk -- "T*" --> Vk1["V_{k+1}"]
    Vk1 --> Stop{"||V_{k+1} - V_k||∞ < ε(1-γ)/(2γ)?"}
    Stop -- "no" --> Vk1
    Stop -- "sì" --> Vstar["V* (ε-ottimo)"]
    Vstar --> Pi["π = greedy(V*)"]

Figura 2 — AlphaZero PI loop: state → MCTS (improvement) → played game (evaluation) → train net → new policy net

Applicazioni pratiche

Planning con modello noto. Se hai $P$ e $R$ in chiaro, VI/PI sono il primo approccio. Inventory control, scheduling, code, controllo classico. La letteratura operations research è piena di applicazioni.
Robotics planning. Quando un robot ha un world model — ad esempio una mappa probabilistica costruita con SLAM — VI tabular su discretizzazione dello spazio degli stati è ancora competitiva per problemi piccoli.
AlphaZero e successori (MuZero, EfficientZero). Sono Approximate Policy Iteration con rete neurale. Equivalenza dichiarata in era-agenti-2024 (in preparazione) sezione AlphaZero.
DQN e varianti. Approximate Value Iteration sample-based, vedi q-learning (in preparazione).
Fitted Q-Iteration in offline / batch RL. Ernst et al. 2005. Si raccoglie un dataset offline $\{(s, a, r, s')\}$ e si itera VI sul batch, fittando un regressore (random forest, neural net) ai target $r + \gamma \max_{a'} Q_\theta(s', a')$ . Punto di riferimento per offline RL moderno (Conservative Q-Learning, IQL e altri ne sono derivati).
Prioritized sweeping in simulator-based agents. Quando un agente ha accesso a un simulatore del mondo, prioritized sweeping permette di propagare aggiornamenti di valore in modo selettivo, evitando di ricalcolare stati “morti”.
Agent planning con world model. Quando un LLM agent costruisce un world model interno (ad esempio una checklist di stati di un workflow), VI tabular su quel grafo discreto può guidare la pianificazione. Va trattata come pianificazione classica più che reinforcement learning.

Dove si rompe

Sezione ampia, perché qui sta il valore diagnostico del capitolo.

Curse of dimensionality

Il primo limite è ovvio. VI/PI tabular hanno costo $O(|S|^2 |A|)$ per iterazione e memoria $O(|S|)$ . In MDP reali $|S|$ esplode: una posizione di scacchi è uno stato, e ce ne sono $\sim 10^{43}$ . Una schermata Atari $84 \times 84$ in 8 colori è uno stato, e ce ne sono $2^{84 \cdot 84 \cdot 3 \cdot 8}$ . Tabular è infattibile. Vedi curse-dimensionalita (110) per la trattazione generale.

La cura ovvia è function approximation: rappresenta $V$ o $Q$ con una rete neurale parametrica $V_\theta$ . Costo memoria $O(|\theta|)$ , non $O(|S|)$ . Ma si paga: le garanzie di contrazione cadono.

Function approximation: la garanzia muore

Con tabular, $T^*$ è una contrazione $\gamma$ in norma del massimo. Con FA, l’iterazione vera è $V_\theta \leftarrow \Pi_\Theta T^* V_\theta$ , dove $\Pi_\Theta$ è la proiezione sullo spazio dei valori rappresentabili dai parametri. La composizione $\Pi_\Theta T^*$ in generale non è una contrazione. Munos (2007, “Performance Bounds in Lp-norm for Approximate Value Iteration”, SIAM J. Control Opt.) dà bound della forma:

\|V^* - V^{\pi_K}\|_p \le \frac{2\gamma}{(1-\gamma)^2} \cdot \sup_k \|T^* V_k - V_{k+1}\|_p,

ma il supremo a destra può esplodere se la classe di FA non è abbastanza ricca o la distribuzione di campionamento è male coperta. Il fattore $1/(1-\gamma)^2$ è una bomba: per $\gamma=0.99$ amplifica di un fattore $10^4$ .

Pratica corrente: si usano trucchi — target network in DQN, policy regularization in actor-critic, conservative bounds in offline RL — per tenere a bada questa instabilità. Sono cure euristiche, non teoremi.

Distribution shift offline

In FQI batch (Ernst 2005), si addestra $Q_\theta$ su un dataset fisso $\mathcal{D}$ . Il problema: il target $r + \gamma \max_{a'} Q_\theta(s', a')$ richiede di valutare $Q_\theta$ su azioni $a'$ che la policy comportamentale del dataset potrebbe non aver mai preso. L’approssimazione lì è non vincolata, e il massimo amplifica gli errori. È il distribution shift dell’offline RL (Fujimoto et al. 2019, “Off-Policy Deep Reinforcement Learning without Exploration”). La policy appresa esce dal supporto del dataset e l’estimazione esplode. Le cure (BCQ, CQL, IQL, BRAC) sono tutte tentativi di vincolare il massimo a stare nel supporto del dataset.

Stopping criterion conservativo

La soglia $\varepsilon (1-\gamma) / (2\gamma)$ deriva da un bound peggior caso. In pratica VI converge molto prima della soglia formale, ma se $\gamma$ è vicino a 1 il bound diventa molto stretto e si rischia di iterare a lungo per garantire una qualità che probabilmente è già raggiunta. Tecniche come span seminorm (Puterman 1994) danno stopping criteria più aggressivi.

Modified PI: scelta di m

Non c’è teoria pulita per scegliere $m$ . Empirico: $m=5$ dà qualcosa di simile a VI; $m=50$ dà qualcosa di simile a PI. La curva convergenza-totale-iterazioni vs costo-per-iterazione ha in genere un minimo a metà strada, ma dipende dal problema.

Approximate PI: oscillazioni e chattering

In API, il policy improvement greedy può oscillare. Bertsekas e Tsitsiklis (Neuro-Dynamic Programming, 1996) dimostrano un esempio dove API alterna fra due policy sub-ottime indefinitamente, perché ciascuna è greedy rispetto a una stima imperfetta dell’altra. Le cure pratiche: soft-greedy improvement (Boltzmann su $Q$ con temperatura), policy regularization (KL verso policy precedente), conservative policy iteration (Kakade-Langford 2002).

Modello noto: assunzione forte

VI/PI presuppongono $P, R$ noti. Nei problemi reali questo richiede un modello esatto (regole del Go, simulatore di inventario) o un world model appreso. Quest’ultimo introduce model error che si compone con $T^*$ e può accumulare.

LLM “policy iteration”: solo analogia

Tree-of-Thoughts (Yao et al. NeurIPS 2023) esplora un albero di reasoning steps con valutazione interna del modello come euristica. Qualcuno ha proposto di leggerlo come VI tronca su un albero di stati di reasoning. Va marcato come ANALOGIA, non equivalenza, per motivi precisi: non c’è MDP ben definito (lo “stato” è il prompt+contesto corrente, ma le transizioni non sono Markov rispetto a esso); non c’è operatore $T^*$ esplicito; il “valore” è una self-eval del modello, non una somma scontata di reward; non c’è garanzia di contrazione.

Stessa cautela per pattern come “self-refine” o “constitutional AI”: somigliano a GPI nella forma — alterna evaluation interna e improvement della risposta — ma non implementano l’algoritmo. Trattarli come PI vero porta a aspettative di convergenza che il sistema non dà.

Reward hacking

Se il reward design è imperfetto, $\pi^*$ esatto è una policy che massimizza il reward sbagliato. VI/PI non riconoscono il problema: lo amplificano, perché trovano l’ottimo. È un problema di specifica, non di algoritmo. Ne riparla superallineamento-concetto (in preparazione).

Markov assumption

Tutto poggia su $P(s'|s,a)$ — Markov rispetto allo stato. Se lo stato non cattura la storia rilevante, la policy ottima sull’MDP collassato non è ottima sul vero processo. POMDP è un capitolo a parte; qui basta segnalare l’ipotesi.

Discount $\gamma$ vicino a 1: tre patologie

Il regime $\gamma \to 1^-$ è quello più realistico per problemi a orizzonte lungo, ma è anche quello dove più cose si rompono. Tre patologie da tenere a mente.

Primo, la velocità di convergenza di VI degenera. Il bound $\gamma^k \|V_0 - V^*\|_\infty$ con $\gamma=0.999$ richiede circa $7000$ iterazioni per ridurre l’errore di un fattore $10^3$ . Se $|S|$ è grande, il costo totale esplode. Modified PI con $m$ alto rimedia in parte.

Secondo, il fattore di amplificazione $1/(1-\gamma)$ nei bound di approximate VI/PI diventa enorme. Errori di approssimazione del 10% si amplificano a errori del 10000% nel bound peggior caso per $\gamma=0.99$ . La pratica è migliore del bound, ma non sempre molto migliore.

Terzo, il sistema lineare $(I - \gamma P^\pi) V = R^\pi$ in PI esatta diventa mal condizionato. Numericamente conviene risolverlo iterativamente con $T^\pi$ (cioè Modified PI con $m$ grande) invece che con un solver diretto.

Comparazione con altre formulazioni

VI/PI risolvono il problema del controllo ottimo via iterazione di operatore. Tre alternative classiche meritano cenno.

La formulazione LP di d’Epenoux (1963) calcola $V^*$ come soluzione di un programma lineare con $|S|$ variabili e $|S| \cdot |A|$ vincoli. Vantaggio: dà accesso ai solver LP industriali e al duale. Svantaggio: scala male.

La programmazione dinamica deterministica backward (per problemi a orizzonte finito) calcola $V_t$ all’indietro da $V_T = R_T$ . È più semplice di VI e termina esattamente in $T$ passi, ma richiede orizzonte finito noto.

Il policy search diretto (CMA-ES, evolutionary strategies, REINFORCE puro) ottimizza direttamente $\theta$ per massimizzare la return, senza passare attraverso una value function. Vantaggio: aggira il bootstrapping e la deadly triad. Svantaggio: varianza alta, sample efficiency bassa.

Collegamenti

probabilita-base: valore atteso e varianza — il backup di Bellman è un valore atteso pesato.
bayes-base: condizionamento — $V^\pi(s) = \mathbb{E}[\sum_t \gamma^t r_t \mid s_0=s, \pi]$ è un’aspettativa condizionata.
discesa-gradiente: policy improvement via gradient è la versione “soft” del greedy classico in actor-critic.
curse-dimensionalita: perché VI/PI tabular muoiono e serve FA.
bias-varianza: trade-off in policy evaluation iterativa (più iterazioni = bias ridotto, varianza ai limiti se sample-based).
multi-armed-bandits: MDP a un solo stato — VI/PI degenerano a stima di reward medio e greedy.
ucb-thompson: exploration bonus si innesta su VI/PI in versione Bayesian (Bayesian DP).
markov-decision-process: framework MDP, prerequisito.
equazione-bellman: operatore $T^*$ come contrazione, prerequisito teorico.
q-learning (in preparazione): VI sample-based.
DQN (in preparazione): Approximate VI con rete neurale.
actor-critic (in preparazione): GPI con due reti.
ppo-trpo (in preparazione): policy iteration con vincoli di trust region.
AlphaGo (in preparazione): MCTS + PI in pratica su Go.

Confronto operativo VI vs PI

Dopo aver visto entrambi gli algoritmi all’opera, mette conto fissare i termini del confronto. Le due strategie convergono allo stesso ottimo, ma con profili computazionali diversi.

Numero di iterazioni. VI è geometrico in $\gamma$ : per scendere sotto soglia $\varepsilon$ servono circa $\log(1/\varepsilon) / \log(1/\gamma)$ iterazioni. Per $\gamma=0.9$ e $\varepsilon=10^{-6}$ sono circa 130; per $\gamma=0.99$ sono circa 1370. PI termina molto prima, tipicamente in 5-20 iterazioni anche su problemi grandi, indipendentemente da $\gamma$ . Il bound peggior caso $|A|^{|S|}$ è teorico e mai osservato in pratica.

Costo per iterazione. VI è $O(|S|^2 |A|)$ per iterazione. PI con policy evaluation esatta è $O(|S|^3)$ per la risoluzione del sistema lineare, più $O(|S|^2 |A|)$ per l’improvement. PI con policy evaluation iterativa è $O(k \cdot |S|^2)$ con $k$ iterazioni di $T^\pi$ . Quando $|A|$ è piccolo e $|S|$ grande, il fattore $|S|^3$ di PI esatto può essere proibitivo; conviene Modified PI.

Memoria. VI tiene solo $V$ . PI tiene $V$ e $\pi$ esplicita. Entrambi $O(|S|)$ + $O(|S| \cdot |A|)$ per il modello.

Anytime behaviour. VI è naturalmente anytime: a qualsiasi iterazione $k$ la policy greedy su $V_k$ è una policy ragionevole, con bound di sub-ottimalità che migliora monotonicamente. PI è anytime solo a fine iterazione: durante la policy evaluation la policy non cambia, quindi la qualità è fissa fino alla fine del passo.

Stabilità numerica. VI è molto stabile: ogni passo è una semplice presa di massimo. PI esatta richiede una decomposizione di $(I - \gamma P^\pi)$ , che può essere mal condizionata per $\gamma$ vicino a 1 (autovalori di $P^\pi$ vicino a 1 → $1 - \gamma \lambda$ vicino a zero). Modified PI evita il sistema lineare e ha la stabilità di VI.

Quando preferire l’uno o l’altro. Regola pratica:

$\gamma$ vicino a 1 e $|S|$ medio → PI o Modified PI ( $m=20$ ), per evitare la lentezza di VI.
$|S|$ grande e modello sparso → VI con prioritized sweeping.
$|A|$ molto grande → VI, perché il costo di PI lineare-solve non dipende da $|A|$ ma il policy improvement sì, e l’improvement va fatto comunque.
Problema online / anytime → VI, perché ogni iterazione dà una policy usabile.
Problema offline / batch → PI (o Modified PI con $m$ grande), perché si possono permettere iterazioni costose ma poche.

Sviluppi successivi: una mappa veloce. Q-learning (in preparazione) prende VI e ne fa una versione campionaria su $Q(s,a)$ invece che $V(s)$ , eliminando la necessità di conoscere $P, R$ . DQN (in preparazione) sostituisce la tabella $Q$ con una rete neurale e aggiunge target network e replay per stabilizzarla — è Approximate Value Iteration con due cure per la deadly triad. SARSA è VI on-policy con TD(0) come backup invece del massimo. Actor-critic (in preparazione) è GPI con actor che fa improvement via gradient e critic che fa evaluation via TD. Soft actor-critic è actor-critic dove l’improvement è soft-greedy (Boltzmann) e l’evaluation usa il soft Bellman operator. PPO e TRPO (in preparazione) sono policy iteration con vincoli di trust region per evitare le oscillazioni di API. Tutti, sotto la lente di GPI, sono lo stesso schema con due fasi e diverse implementazioni dei due passi.

Per andare oltre

Richard S. Sutton, Andrew G. Barto, Reinforcement Learning: An Introduction, MIT Press, 2nd ed., 2018, capitolo 4 “Dynamic Programming”. Il riferimento didattico standard, esempi e pseudocodice puliti.
Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994. Trattazione operations research definitiva: convergenza, complessità, varianti, average-reward.
Ronald A. Howard, Dynamic Programming and Markov Processes, MIT Press, 1960. La fonte primaria di Policy Iteration. Lettura storica ancora pulita e leggibile.
Damien Ernst, Pierre Geurts, Louis Wehenkel, “Tree-Based Batch Mode Reinforcement Learning”, JMLR 6, 2005. FQI come ponte fra DP classica e RL moderno con FA.
David Silver et al., “Mastering the game of Go without human knowledge”, Nature 550, 2017. Esempio paradigmatico di policy iteration con FA neurale; la lettura PI è dichiarata nel paper.
Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, vol. I-II, Athena Scientific. Trattazione rigorosa di asynchronous DP, Gauss-Seidel, prioritized sweeping, modified PI, average-reward.
Rémi Munos, “Performance Bounds in Lp-norm for Approximate Value Iteration”, SIAM Journal on Control and Optimization 46(2), 2007. Bound stretti per AVI con FA, fondamentali per leggere DQN e successori in chiave teorica.

Note di lettura per l’autodidatta

Se si vuole sviluppare intuizione operativa sui due algoritmi, una sequenza efficace è la seguente. Implementare VI tabular su un gridworld 4x4 in numpy e plottare la value function dopo 1, 5, 20, 100 iterazioni: si vede l’onda di valore propagarsi dal goal indietro. Implementare PI sullo stesso gridworld e plottare la policy dopo ogni iterazione: si vede una riorientazione brusca a ogni step. Implementare Modified PI con $m \in \{1, 5, 20, \infty\}$ e contare iterazioni totali e tempo: si vede il compromesso. Infine implementare prioritized sweeping su un gridworld 20x20 sparso e confrontarlo con VI sincrono: la differenza in tempo è di ordini di grandezza.

A quel punto si è pronti per leggere il capitolo Q-learning come “VI dove non hai $P, R$ ma campioni” e DQN come “Q-learning con rete neurale e due trucchi per non divergere”. L’eredità di Bellman e Howard sui modelli moderni diventa allora una riconoscibilità immediata, non una nozione astratta.