L'equazione di Bellman: l'operatore che fa convergere il reinforcement learning

Una sola identità ricorsiva, applicata in loop, calcola il valore di ogni decisione. Tutti gli algoritmi di RL ne sono campioni più o meno fortunati.

Perché questo capitolo

Il capitolo precedente ha introdotto l’MDP come grammatica del decidere nel tempo, ed entro quella grammatica ha scritto, quasi di passaggio, due equazioni: Bellman expectation, Bellman optimality. Il presente capitolo le prende sul serio. Non come identità che caratterizzano un valore, ma come operatori — funzioni che mangiano una stima di valore e ne restituiscono una migliore. È questa lettura, dovuta a Bellman e poi formalizzata nei classici di Puterman e Bertsekas, a rendere il reinforcement learning calcolabile.

La promessa è grossa. Tutto ciò che il libro tratterà nei prossimi capitoli — Value Iteration, Policy Iteration, TD-learning, Q-learning, DQN, AlphaZero, RLHF, DPO — è un modo di applicare in pratica un’unica idea: contrarre verso un punto fisso. Capire l’operatore di Bellman come contrazione $\gamma$ in norma del massimo significa capire, in un colpo solo, perché tutti questi algoritmi convergono dove convergono, e perché divergono dove divergono.

C’è anche una ragione operativa al presente. Quando un LLM viene allineato con RLHF, l’objective ottimo ha la forma $\pi^*(a|s) \propto \pi_\text{ref}(a|s) \exp(Q^*(s,a)/\beta)$. Quella formula non cade dal cielo: è la soluzione di un’equazione di Bellman soft, regolarizzata in KL. Senza l’equazione di Bellman, l’algebra di RLHF resta una collezione di trucchi; con l’equazione, è una conseguenza ovvia di un teorema di punto fisso.

Infine, l’equazione di Bellman è la lente con cui si vedono i fallimenti. La deadly triad — function approximation, bootstrapping, off-policy — non è un avvertimento folkloristico: è l’enunciato preciso delle condizioni che rompono la garanzia di contrazione. Se non sai cosa è la garanzia, non puoi sapere quando è infranta. Per questo il capitolo arriva ora, prima di Value Iteration e Q-learning: il lettore deve saper riconoscere quale operatore stanno simulando, e in che senso.

Contesto

Richard Bellman (matematico americano, 1920-1984, RAND Corporation) inventa il dynamic programming fra il 1953 e il 1957. Nome scelto, racconterà nell’autobiografia Eye of the Hurricane del 1984, per ragioni politiche: il segretario alla Difesa Charles Wilson detestava la parola “research”, e Bellman doveva camuffare il suo lavoro alla RAND. «Try thinking of some combination that will possibly give it a pejorative meaning» — scriverà Bellman a proposito del termine. Aneddoto che vale per cogliere il colore dell’epoca: un campo intero porta un nome scelto come maschera.

Il libro Dynamic Programming (Princeton University Press, 1957) fissa due cose. Primo, il principio di ottimalità: «An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision». Secondo, l’equazione funzionale che oggi porta il suo nome.

Tre anni dopo Ronald Howard (ingegnere operations research, MIT poi Stanford) pubblica Dynamic Programming and Markov Processes (MIT Press, 1960). Vi introduce Policy Iteration e dimostra che converge in numero finito di passi su MDP finito. È il pendant operativo al lavoro di Bellman.

Sul versante apprendimento, Richard Sutton (informatico canadese, allora all’Università del Massachusetts) pubblica nel 1988 Learning to Predict by the Methods of Temporal Differences (Machine Learning, 3). Identifica per la prima volta l’errore TD come residuo di Bellman, fondando la famiglia TD-learning. L’anno dopo Chris Watkins difende la sua tesi a Cambridge (Learning from Delayed Rewards, 1989) e introduce Q-learning: un algoritmo che impara $Q^*$ senza conoscere transizioni e ricompense. Watkins e Peter Dayan dimostrano la convergenza tabular nel 1992 (Q-learning, Machine Learning 8).

Negli anni Novanta arrivano i guasti. Leemon Baird nel 1995 esibisce un controesempio minimo (sette stati) in cui TD off-policy con linear function approximation diverge esponenzialmente. John Tsitsiklis e Benjamin Van Roy nel 1997 (An Analysis of Temporal-Difference Learning with Function Approximation, IEEE TAC) chiariscono il quadro: convergenza on-policy, divergenza possibile off-policy. È la base teorica della deadly triad canonizzata da Sutton e Barto.

L’esplosione moderna è del 2015. Volodymyr Mnih e colleghi DeepMind (Human-level control through deep reinforcement learning, Nature 518) sostituiscono la tabella $Q$ con una rete convoluzionale: nasce DQN. Domano la deadly triad con due trucchi — target network e replay buffer — entrambi giustificati come modi di rallentare il bootstrapping.

Tre filiazioni recenti chiudono il quadro. Hado van Hasselt (2010, NeurIPS) identifica e corregge la maximization bias nel Bellman optimality update — Double Q-learning. Marc Bellemare, Will Dabney e Rémi Munos (2017, ICML) ridefiniscono l’operatore su distribuzioni invece che su valori attesi: nasce il distributional RL. Tuomas Haarnoja e colleghi (2018, ICML) introducono SAC con un soft Bellman operator in cui il massimo è sostituito da log-sum-exp. Quest’ultimo è il ponte verso RLHF: la formula della policy ottima KL-regularized è esattamente la stessa.

Una nota di differenziazione rispetto a markov-decision-process (122). Là l’equazione di Bellman compariva come identità che caratterizza $V^\pi$ e $V^*$ dentro l’MDP. Qui la trattiamo come operatore $T^\pi$ e $T^*$, oggetto matematico con proprietà sue. La distinzione è sostanziale: identità e operatore vivono in spazi diversi. L’identità sta nello spazio dei valori; l’operatore sta nello spazio delle funzioni dai valori ai valori. Tutti i metodi computazionali nascono da questa seconda lettura.

L’intuizione

Due angoli, da percorrere prima di scrivere una formula. Uno coglie l’idea di Bellman come ricetta locale che diventa soluzione globale. L’altro coglie l’idea di operatore come motore di calcolo.

Angolo 1: la regola locale che risolve il problema globale

Se sai dirmi quanto vale ogni stato, sai anche cosa fare in ognuno: in ogni stato prendi l’azione che massimizza la somma “ricompensa immediata + valore atteso del prossimo stato, scontato di $\gamma$”. Il problema è che il valore di uno stato dipende dal valore degli stati raggiungibili, che dipende dal valore di altri stati, che a tornano a dipendere dal primo. Sembra un cane che si morde la coda.

Bellman lo risolve con un colpo di teoria dei punti fissi. Scrive una regola locale ovvia — il valore di qui = ricompensa di qui + discount per il valore atteso del prossimo passo — la legge come funzione che trasforma l’intera tabella di valori in una nuova tabella, e si chiede quando l’iterazione converge. La risposta è limpida: converge sempre, esponenzialmente, perché ogni applicazione della regola avvicina due stime qualunque di un fattore $\gamma < 1$. L’eco del problema globale si attenua, l’intuizione locale vince. Il principio di ottimalità è l’enunciato non tecnico di questo fatto.

Angolo 2: l’operatore come “applicare una volta la dinamica”

Pensa $V$ come una mappa di altimetria sopra $S$: ogni stato ha un’altezza. L’operatore $T^\pi$ prende questa mappa e la modifica così: per ogni stato, sostituisci l’altezza con la ricompensa locale più $\gamma$ volte la media pesata delle altezze dei vicini, dove i pesi sono le probabilità di transizione sotto $\pi$. Hai applicato una volta la dinamica del sistema, alla rovescia, dal futuro al presente.

Adesso la metafora utile, che marchiamo come analogia (somiglianza didattica, niente di più). Pensare $T^\pi V$ come un passaggio di livellamento: mappa irregolare → mappa più liscia → mappa ancora più liscia. Ogni passo riduce la “rugosità” rispetto al fixed point — non in senso geometrico, ma nel senso preciso che vedremo: $\|T V - T W\|_\infty \le \gamma \|V - W\|_\infty$.

Il fixed point è la mappa di altimetria che, applicata a sé stessa, non si modifica più: $V^\pi = T^\pi V^\pi$. È la value function vera della policy $\pi$. L’operatore non è qualcosa di esotico: è solo l’equazione di Bellman, scritta come funzione invece che come uguaglianza.

La meccanica

Definizioni

Sia $S$ finito (per ora). Lo spazio delle value function è $\mathbb{R}^{|S|}$, dotato della norma del massimo (sup-norm) $\|V\|_\infty = \max_{s} |V(s)|$. Su questo spazio definiamo due operatori $T^\pi, T^*: \mathbb{R}^{|S|} \to \mathbb{R}^{|S|}$.

Bellman expectation operator sotto policy $\pi$:

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

In forma matriciale, definito $P^\pi$ come matrice $|S| \times |S|$ con entrata $(s, s') = \sum_a \pi(a|s) P(s'|s,a)$ e $R^\pi$ vettore degli expected reward sotto $\pi$:

$$T^\pi V = R^\pi + \gamma P^\pi V.$$

È un operatore affine, lineare in $V$.

Bellman optimality operator:

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

Il max introduce una non-linearità essenziale. $T^*$ non è lineare, ma resta una contrazione. Vediamolo.

Il teorema di contrazione (TEOREMA, prova in 4 righe)

Asserto: per $\gamma \in [0, 1)$, sia $T^\pi$ sia $T^*$ sono $\gamma$-contrazioni in sup-norm:

$$\|T V - T W\|_\infty \le \gamma \|V - W\|_\infty.$$

Prova per $T^*$ (per $T^\pi$ è strettamente più semplice). Per ogni $s$:

\begin{align*} |(T^* V)(s) - (T^* W)(s)| &= \left| \max_a [R(s,a) + \gamma \textstyle\sum_{s’} P(s’|s,a) V(s’)] - \max_a [R(s,a) + \gamma \textstyle\sum_{s’} P(s’|s,a) W(s’)] \right| \ &\le \max_a \left| \gamma \textstyle\sum_{s’} P(s’|s,a) [V(s’) - W(s’)] \right| \ &\le \gamma \max_a \textstyle\sum_{s’} P(s’|s,a) , |V(s’) - W(s’)| \ &\le \gamma |V - W|_\infty. \end{align*}

La prima disuguaglianza usa $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$. La seconda è la disuguaglianza triangolare con probabilità non negative. La terza è $\sum_{s'} P(s'|s,a) \le 1$ e $|V(s') - W(s')| \le \|V - W\|_\infty$. Vale per ogni $s$, quindi vale per il massimo: tesi.

Banach: punto fisso unico, convergenza geometrica (TEOREMA)

Il teorema di Banach del punto fisso (Stefan Banach, matematico polacco, 1922) afferma che ogni contrazione su uno spazio metrico completo ha uno e un solo punto fisso, e che iterando da qualunque punto si converge geometricamente.

Lo spazio $\mathbb{R}^{|S|}$ con la sup-norm è completo (lo è ogni spazio finito-dimensionale). Quindi:

• Esiste un unico $V^\pi$ con $T^\pi V^\pi = V^\pi$.
• Esiste un unico $V^*$ con $T^* V^* = V^*$.
• Per ogni $V_0$, ponendo $V_{k+1} = T^\pi V_k$ (rispettivamente $T^*$), si ha $\|V_k - V^\pi\|_\infty \le \gamma^k \|V_0 - V^\pi\|_\infty$.

L’ultima disuguaglianza è il punto operativo: dopo $k$ iterazioni l’errore è ridotto di $\gamma^k$. Con $\gamma = 0.9$ e $k = 100$, errore residuo $\sim 2.7 \times 10^{-5}$ volte l’errore iniziale. Con $\gamma = 0.99$, $k$ deve essere dell’ordine delle migliaia. Il discount factor non è un parametro estetico: governa la velocità di convergenza.

Questo è Value Iteration in nuce. Il capitolo value-iteration-policy-iteration (in preparazione) lo svolgerà.

Backup diagrams

Sutton e Barto disegnano l’operatore così. Un cerchio bianco rappresenta un nodo stato; un cerchio pieno un nodo (stato, azione). Le frecce in giù sono “espansioni”: dallo stato, le azioni possibili; dall’azione, gli stati successori, pesati per $P$. Le frecce in su sono “backup”: prendi i valori dei nodi sotto, li combini con expectation o max, li scrivi sul nodo sopra.

Quattro backup canonici, uno per ogni combinazione di expectation/optimality e $V$/$Q$:

• $V^\pi$: in giù due livelli (azione poi stato), in su con expectation su entrambi.
• $V^*$: stesso scheletro, ma il livello azione si combina con max invece che expectation.
• $Q^\pi$: in giù tre livelli (stato, azione’, stato), in su con expectation.
• $Q^*$: idem, ma all’ultimo livello azione si combina con max.

Ogni algoritmo RL si descrive scegliendo: quale dei quattro backup, esatto (full) o campionato (sample), profondità uno o $n$ o Monte Carlo. Tutto qui. È il dispositivo grafico per vedere l’operatore.

TD error come Bellman residual stocastico

L’aggiornamento TD(0) di Sutton 1988:

$$V(s_t) \leftarrow V(s_t) + \alpha \left[\, r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \,\right].$$

Il termine in parentesi è il TD error $\delta_t$. Calcoliamo il suo valore atteso condizionale a $s_t$:

$$E[\delta_t \mid s_t] = E[r_{t+1} + \gamma V(s_{t+1}) \mid s_t] - V(s_t) = (T^\pi V)(s_t) - V(s_t).$$

Questa è una equivalenza argomentata, non un’analogia: il TD error è il Bellman residual $T^\pi V - V$ valutato in $s_t$, sotto la policy che ha generato i dati. TD(0) è quindi un’iterazione stocastica di Robbins-Monro per il fixed point $V \leftarrow T^\pi V$. Sotto step-size $\alpha_t$ con $\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$, e ogni stato visitato infinitamente spesso, $V_t \to V^\pi$ con probabilità 1 — sempre nel caso tabular.

Q-learning come campione di $T^*$

Watkins 1989, oggetto $Q: S \times A \to \mathbb{R}$:

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[\, r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) \,\right].$$

Il target $r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')$ è un campione di $(T^* Q)(s_t, a_t)$, dove $T^*$ qui è ridefinito sullo spazio delle action-value:

$$(T^* Q)(s, a) = R(s, a) + \gamma \sum_{s'} P(s'|s, a) \max_{a'} Q(s', a').$$

Ancora una equivalenza: Q-learning è iterazione stocastica di Robbins-Monro su $T^*$ per le action-value. Watkins-Dayan 1992 prova: tabular, ogni $(s,a)$ visitato infinitamente spesso, condizioni Robbins-Monro su $\alpha_t$, allora $Q_t \to Q^*$ con probabilità 1. La policy comportamentale può essere $\varepsilon$-greedy o qualunque altra, purché copra tutti $(s,a)$: è off-policy perché il bersaglio è $T^*$ indipendentemente dalla distribuzione comportamentale. Il capitolo q-learning (in preparazione) ne svolgerà i dettagli.

Soft Bellman: il max diventa log-sum-exp

In maximum entropy reinforcement learning (Haarnoja 2018) si aggiunge all’objective un bonus di entropia: l’agente ottimale è quello che massimizza il return e resta diversificato sulle azioni. L’operatore corrispondente, sostituendo il max con un log-sum-exp pesato da una temperatura $\alpha > 0$:

$$(T^*_\text{soft} V)(s) = \alpha \log \sum_a \exp\left(\frac{R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s')}{\alpha}\right).$$

Continua a essere $\gamma$-contrazione in sup-norm (la prova è la stessa, sostituendo l’inegualianza per il max con quella per log-sum-exp). Limite $\alpha \to 0$: torna $T^*$ standard. Limite $\alpha \to \infty$: tutte le azioni equivalenti, policy uniforme. La policy ottima associata ha forma di Gibbs:

$$\pi^*(a \mid s) = \frac{\exp(Q^*(s, a) / \alpha)}{\sum_{a'} \exp(Q^*(s, a') / \alpha)}.$$

Tipo SAC. Il capitolo maximum-entropy-rl (in preparazione) ne darà la forma completa.

flowchart LR
  A[SFT policy<br/>π_ref] --> B[Reward model r_φ<br/>addestrato su preferenze umane]
  B --> C{Reward modificato<br/>r̃ = r_φ − β·log π_θ/π_ref}
  C --> D[Aggiornamento PPO<br/>policy π_θ]
  D --> E[Forma della policy ottima:<br/>π* ∝ π_ref · exp(Q*/β)]
  E --> F[Soft Bellman fixed point<br/>Q* = r_φ + γ·E[β·log Σ π_ref·exp(Q*/β)]]
  F -.feedback.-> D

Figura 3 — flusso RLHF come ottimizzazione di un Bellman regolarizzato in KL contro la reference policy, con la forma del soft fixed point della policy ottima

Distributional Bellman: l’operatore sale a un livello

Bellemare, Dabney e Munos (2017) cambiano lo spazio su cui agisce l’operatore. Invece di tenere $V(s) = E[G_t \mid s]$, modellano la distribuzione completa $Z(s)$ di $G_t$. L’operatore di Bellman distributional è definito da uguaglianza in distribuzione:

$$(T^\pi Z)(s, a) \stackrel{D}{=} R(s, a) + \gamma\, Z(s', A'),$$

con $s' \sim P(\cdot \mid s, a)$, $A' \sim \pi(\cdot \mid s')$, e $\stackrel{D}{=}$ uguaglianza in distribuzione. È una contrazione nella distanza di Wasserstein massima fra distribuzioni di return. Algoritmi: C51 (parametrizza $Z$ come categorica su 51 atomi fissi), QR-DQN (parametrizza i quantili). Empiricamente più stabili e più performanti su Atari rispetto a DQN classico. Il messaggio teorico è semplice: l’operatore di Bellman è una struttura, non una specifica formula. Si trasporta a qualunque spazio in cui si possa definire monotonia e contrazione.

Generalized Policy Iteration

Sutton e Barto chiamano GPI lo schema astratto comune a quasi tutti gli algoritmi RL: alternare policy evaluation (avvicinare $V$ al fixed point di $T^\pi$) e policy improvement (rendere $\pi$ greedy rispetto a $V$). Convergono a $\pi^*$ entrambi i lati. Value Iteration è il caso degenere “una sola iterazione di evaluation per ogni improvement”. Q-learning è “evaluation e improvement collassati in un singolo update”. DQN è “evaluation con SGD su rete profonda, improvement greedy implicita”. RLHF con PPO è “evaluation via critic, improvement via policy gradient”. Riconoscere GPI è riconoscere il tema.

Pseudocodice: applicare $T^*$ su MDP tabular

import numpy as np

def value_iteration(P, R, gamma, tol=1e-8, max_iter=10_000):
    """
    P: array (S, A, S) con P[s, a, s'] = Pr(s' | s, a)
    R: array (S, A) con R[s, a] = expected reward
    gamma: discount factor in [0, 1)
    Returns: V* (S,), pi* (S,)
    """
    nS, nA = R.shape
    V = np.zeros(nS)
    for k in range(max_iter):
        # (T* V)(s) = max_a [R(s,a) + gamma * sum_s' P(s,a,s') V(s')]
        Q = R + gamma * P.dot(V)         # shape (S, A)
        V_new = Q.max(axis=1)
        if np.max(np.abs(V_new - V)) < tol:
            V = V_new
            break
        V = V_new
    pi = Q.argmax(axis=1)
    return V, pi

Tre cose da notare. Primo: l’unica operazione costosa è il prodotto P.dot(V), $O(|S|^2 |A|)$. Secondo: la convergenza in $max_iter$ è garantita dal teorema di Banach, ma il numero effettivo dipende da $\gamma$ — più vicino a 1, più lento. Terzo: l’algoritmo non “sa” cosa sta calcolando; sta solo iterando una contrazione. La teoria gli garantisce di trovare $V^*$.

Pseudocodice: Q-learning agent

def q_learning(env, episodes, gamma=0.95, alpha=0.1, eps=0.1):
    nS, nA = env.nS, env.nA
    Q = np.zeros((nS, nA))
    for ep in range(episodes):
        s = env.reset()
        done = False
        while not done:
            # epsilon-greedy
            if np.random.rand() < eps:
                a = np.random.randint(nA)
            else:
                a = int(np.argmax(Q[s]))
            s2, r, done, _ = env.step(a)
            target = r + (0.0 if done else gamma * np.max(Q[s2]))
            Q[s, a] += alpha * (target - Q[s, a])
            s = s2
    return Q

Il termine target - Q[s, a] è il TD error / Bellman residual stocastico. Tutto il resto è strumentazione.

flowchart TD
  S[Osserva stato s_t] --> EG{epsilon-greedy<br/>su Q s_t,·}
  EG -->|esplora| RA[Azione casuale]
  EG -->|sfrutta| GA[argmax_a Q s_t,a]
  RA --> EX[Esegui azione a_t]
  GA --> EX
  EX --> NS[Riceve r_t+1, osserva s_t+1]
  NS --> TG[Calcola target<br/>y = r_t+1 + gamma · max_a' Q s_t+1,a']
  TG --> UP[Aggiorna<br/>Q s_t,a_t += alpha · y − Q s_t,a_t]
  UP --> S

Figura 6 — pipeline di update Q-learning: osserva stato, epsilon-greedy, esegue azione, calcola target Bellman, aggiorna Q incrementalmente

Backup come matrice (tabular) vs come rete (deep)

In tabular finito, $T^\pi V = R^\pi + \gamma P^\pi V$ è letteralmente un prodotto matrice-vettore. Si può anche calcolare $V^\pi$ in forma chiusa risolvendo un sistema lineare: $(I - \gamma P^\pi) V^\pi = R^\pi$, da cui $V^\pi = (I - \gamma P^\pi)^{-1} R^\pi$. La matrice $(I - \gamma P^\pi)$ è invertibile perché $\gamma P^\pi$ ha raggio spettrale $\le \gamma < 1$. Per $T^*$ non c’è forma chiusa per via del max non-lineare, ma resta la stessa struttura algebrica.

Quando $V$ è una rete neurale $V_\theta$, l’aggiornamento "$V \leftarrow T V$" non è applicabile: lo spazio dei $V_\theta$ rappresentabili non è chiuso sotto $T$. Si proietta. Il proxy è un passo di SGD con loss $(y - V_\theta(s))^2$ dove $y$ è il target Bellman calcolato con $V_\theta$ corrente. Tre conseguenze: (i) si campiona sui dati, non su tutti gli stati; (ii) il target si muove a ogni step; (iii) la garanzia di contrazione svanisce. Il capitolo dqn-tecnica (in preparazione) discuterà i trucchi DQN come tentativi di restaurare condizioni vicine alla contrazione: target network congela $\theta_\text{target}$ per $N$ step (target fermo, non si muove), replay buffer rende la distribuzione dei sample meno “on-policy istantaneo” e più “off-policy uniforme”. Sono palliativi efficaci perché aggrediscono i punti precisi della deadly triad.

Avvertenza: deadly triad

Tre ingredienti che, insieme, possono rompere la garanzia di convergenza:

1. Function approximation: $V$ o $Q$ rappresentati da una rete neurale o da feature lineari, non più tabella.
2. Bootstrapping: il target dell’aggiornamento usa la stima corrente — TD/Q-learning, non Monte Carlo.
3. Off-policy: la distribuzione dei dati non coincide con la distribuzione indotta dalla policy target.

Due su tre: di solito tutto bene. Tre su tre: rischio di divergenza (Baird 1995, Tsitsiklis-Van Roy 1997). DQN li usa tutti e tre, e infatti ha bisogno di trucchi (target network, replay buffer) per non divergere. Discutiamo questa zona in §8.

Cenno: HJB in continuous time

Per completezza, l’equazione di Bellman in tempo continuo è la Hamilton-Jacobi-Bellman:

$$\rho V(s) = \max_a \left[\, r(s, a) + \nabla V(s) \cdot f(s, a) \,\right],$$

dove $\dot{s} = f(s, a)$ è la dinamica continua e $\rho > 0$ il discount continuo. È una PDE non lineare. La teoria delle viscosity solutions (Crandall-Lions, anni ‘80) garantisce esistenza e unicità sotto condizioni opportune. Lo strumento è diverso, l’idea è la stessa: il valore in un punto è ricomposto da ricompensa locale e dalla derivata direzionale del valore lungo la traiettoria ottima. Lo lasciamo qui — il dettaglio è fuori scope per un libro orientato all’agent coding — ma è utile sapere che la versione continuous-time esiste e che la struttura è preservata.

Esempi

Tre esempi eterogenei: numerico, codice, scenario reale.

Esempio 1 — Convergenza geometrica su un MDP a due stati

Sia $S = \{0, 1\}$, $A = \{a, b\}$. Transizioni deterministiche: l’azione $a$ porta in 0, l’azione $b$ porta in 1, da qualunque stato. Ricompense: $R(0, a) = 1, R(0, b) = 0, R(1, a) = 0, R(1, b) = 2$. Discount $\gamma = 0.9$.

Si nota a vista che la policy ottima è “in 0 fai $b$, in 1 fai $b$”: loop in 1 con reward 2, valore $V^*(1) = 2/(1-0.9) = 20$, e $V^*(0) = 0 + 0.9 \cdot 20 = 18$. Verifica numerica iterando $T^*$ da $V_0 = (0, 0)$:

$k$	$V_k(0)$	$V_k(1)$	$\|V_k - V^*\|_\infty$
0	0.000	0.000	20.000
1	1.000	2.000	18.000
2	1.900	3.800	16.200
3	2.620	5.420	14.580
5	3.951	8.219	11.781
10	6.926	13.288	6.712
20	11.464	18.067	1.933
50	17.106	19.889	0.111
100	17.999	19.999	0.0006

Il rapporto $\|V_{k+1} - V^*\|_\infty / \|V_k - V^*\|_\infty$ tende a $0.9 = \gamma$. La contrazione non è una metafora: è un fatto numerico osservabile.

Esempio 2 — Q-learning su gridworld 4x4

Ambiente: griglia $4 \times 4$, partenza in $(0, 0)$, obiettivo in $(3, 3)$ con ricompensa $+1$ all’arrivo. Quattro azioni N, S, E, W deterministiche (i bordi tengono fermo l’agente). Costo per passo $-0.04$ per spingere a finire in fretta. $\gamma = 0.95$, $\alpha = 0.1$, $\varepsilon = 0.1$ con decadimento lineare.

Lanciato l’algoritmo dello pseudocodice precedente per $5\,000$ episodi, la $Q$-table converge alla soluzione tabular ottima. Tre osservazioni qualitative:

• Le prime $\sim 200$ episodi: l’agente cammina quasi a caso; $Q$ è dominata dal rumore.
• Episodi $200$-$1\,500$: l’agente trova spesso il goal; $Q$ degli stati vicini al goal si stabilizza prima.
• Episodi $1\,500$-$5\,000$: l’informazione si propaga indietro lungo gli stati; $Q$ degli stati lontani converge per ultima.

Questo è il cammino dell’informazione lungo il backup: dal goal indietro. È esattamente come Value Iteration, ma campionato. La differenza con Value Iteration è che qui si paga in episodi e in $\varepsilon$-esplorazione; il guadagno è non aver bisogno di conoscere $P$ né $R$.

Esempio 3 — RLHF KL-regularized: dove arriva il soft Bellman

Nel pipeline RLHF (Ziegler 2019, Stiennon 2020, Ouyang 2022) la fase RL ottimizza, con PPO, un reward modificato:

$$\tilde{r}(s, a) = r_\phi(s, a) - \beta \log \frac{\pi_\theta(a \mid s)}{\pi_\text{ref}(a \mid s)},$$

dove $r_\phi$ è il reward model addestrato sulle preferenze umane, $\pi_\text{ref}$ è la policy SFT di partenza e $\beta > 0$ è il coefficiente KL. La motivazione editoriale è ovvia: non vogliamo che la policy si scosti troppo dalla zona “grammaticale” che SFT ha già conquistato. La motivazione matematica è più profonda.

Si dimostra (formula classica del calcolo variazionale, oppure conseguenza diretta del soft Bellman) che la policy ottima che massimizza $E_\pi[\sum_t r_\phi - \beta \text{KL}(\pi(\cdot|s_t) \| \pi_\text{ref}(\cdot|s_t))]$ ha forma chiusa:

$$\pi^*(a \mid s) = \frac{1}{Z(s)} \pi_\text{ref}(a \mid s) \exp\!\left(\frac{Q^*(s, a)}{\beta}\right),$$

dove $Q^*$ soddisfa un’equazione di Bellman soft in cui il prior $\pi_\text{ref}$ rimpiazza l’uniforme:

$$Q^*(s, a) = r_\phi(s, a) + \gamma\, E_{s'}\!\left[ \beta \log \sum_{a'} \pi_\text{ref}(a' \mid s') \exp(Q^*(s', a') / \beta) \right].$$

Tre conseguenze pratiche, immediate.

Primo, DPO (Rafailov 2023, capitolo dpo-family in preparazione) si basa esattamente su questa forma chiusa: invertendola si ricava $r_\phi$ dalla policy, e si elimina il bisogno del reward model esplicito. È un caso libro di “se conosci la struttura del fixed point, ottimizzi senza simularlo”.

Secondo, $\beta$ è il termostato. $\beta \to 0$: scompare il vincolo KL, $\pi^* \to \arg\max_a Q^*$, cioè policy hard greedy come Q-learning. $\beta \to \infty$: $\pi^* \to \pi_\text{ref}$, cioè la SFT non si muove. Il “coefficiente KL” in produzione non è un magic number da tunare: è la temperatura di un soft Bellman.

Terzo, perché stabilizza? L’operatore soft-Bellman regolarizzato in KL su un prior non degenere è strettamente una contrazione, e il suo punto fisso è una policy stocastica. Niente azioni con probabilità zero, niente collasso del support. Il KL impedisce all’agente di dimenticare ciò che aveva imparato.

flowchart LR
  A[SFT policy<br/>π_ref] --> B[Reward model r_φ<br/>addestrato su preferenze umane]
  B --> C{Reward modificato<br/>r̃ = r_φ − β·log π_θ/π_ref}
  C --> D[Aggiornamento PPO<br/>policy π_θ]
  D --> E[Forma della policy ottima:<br/>π* ∝ π_ref · exp(Q*/β)]
  E --> F[Soft Bellman fixed point<br/>Q* = r_φ + γ·E[β·log Σ π_ref·exp(Q*/β)]]
  F -.feedback.-> D

Figura 3 — -rlhf-kl-regularized-soft-bellman-flow

Applicazioni pratiche

Mappa rapida, da scorrere come orientamento al resto del libro.

• Value Iteration / Policy Iteration: applicazione diretta di $T^*$ e $T^\pi$ in tabular. Capitolo value-iteration-policy-iteration (in preparazione).
• TD-learning (Sutton 1988): iterazione Robbins-Monro su $T^\pi$, on-policy, model-free.
• Q-learning (Watkins 1989, Watkins-Dayan 1992): iterazione Robbins-Monro su $T^*$, off-policy, model-free, tabular convergente.
• DQN (Mnih 2015): Q-learning con rete neurale; target network (clone congelato di $Q$ aggiornato ogni $N$ step) per ridurre il bootstrapping istantaneo; replay buffer per smussare la distribuzione off-policy. Capitolo dqn-tecnica (in preparazione; il capitolo storico è DQN su Atari, 2013).
• Double Q-learning (van Hasselt 2010, 2016): due stime alternate per ridurre la maximization bias del max in $T^*$.
• AlphaZero (Silver 2017): MCTS produce stime di $Q$ dei nodi via simulazione; queste stime sono target di una rete che viene addestrata come critic. Il backup dell’albero è un Bellman backup esplicito sui figli. Capitolo alphazero (in preparazione).
• Distributional RL (Bellemare-Dabney-Munos 2017): operatore di Bellman ridefinito su distribuzioni di return. Algoritmi C51 e QR-DQN. Capitolo distributional-rl (in preparazione).
• SAC (Haarnoja 2018): soft Bellman + actor-critic + replay. Stato dell’arte continuous control quando esce.
• RLHF (Christiano 2017, Ziegler 2019, Stiennon 2020, Ouyang 2022): policy gradient con reward $\tilde{r} = r_\phi - \beta \log(\pi/\pi_\text{ref})$. La forma chiusa della policy ottima è soft-Bellman con prior. Capitolo rlhf-ppo (in preparazione).
• DPO (Rafailov 2023): inversione della forma chiusa RLHF, evita PPO. Capitolo dpo-family (in preparazione).
• Agent planning in deep agent: l’expansion di un albero di tool-call con stima di valore alle foglie e backup verso la radice è, formalmente, backward induction Bellman su un MDP latente. La maggior parte dei pianificatori di tool use, anche quando non lo dichiarano, sono Bellman.

Dove si rompe

L’eleganza dell’operatore di Bellman si paga. Le condizioni che lo fanno funzionare sono molte, e in produzione cadono spesso. Vale la pena enumerarle perché ogni capitolo successivo del libro affronterà uno di questi modi di rottura.

Discount $\gamma = 1$ e horizon infinito

Senza $\gamma < 1$ la dimostrazione di contrazione non passa. Tre toppe possibili: (a) horizon finito $T$ noto, e si usa backward induction senza fixed point, esistono sempre soluzioni in $T$ passi; (b) average reward formulation (Puterman 1994), con teoria sua; (c) condizione di “proper policy” che termina con probabilità 1, alla Bertsekas. Nel primo, niente fixed point. Negli altri due, fixed point sì, ma con strumenti diversi e condizioni più sottili. Il “RL infinito-orizzonte con $\gamma$” è il caso comodo, non quello generale.

Function approximation rompe la garanzia

L’operatore composto $\Pi T$ — Bellman seguito da proiezione sullo spazio rappresentabile — può non essere una contrazione. Tsitsiklis e Van Roy (1997) costruiscono il quadro: con feature lineari e dati on-policy, $\Pi T^\pi$ resta una contrazione in una norma pesata dalla distribuzione stazionaria, quindi convergenza al miglior approssimante $V^\pi_\text{proj}$, non a $V^\pi$. Off-policy, niente garanzia. Con reti neurali, niente garanzia in generale. La pratica funziona spesso; la teoria spiega perché a volte non funziona.

Baird’s counterexample (1995)

Sette stati, due azioni, dinamica strutturata, feature lineari scelte ad arte. TD(0) off-policy con queste feature diverge esponenzialmente: i pesi $\theta$ esplodono. È un controesempio costruttivo, riproducibile in dieci righe di numpy. Non patologia, ma il caso minimale.

Deadly triad

Sutton e Barto canonizzano la formula: function approximation + bootstrapping + off-policy = potenziale divergenza. Due su tre, vivibile. Tutti e tre, serve mitigazione: target network, replay buffer, gradient clipping, importance sampling con cap, varianti GTD/ETD che proiettano sull’errore di Bellman quadrato. DQN funziona perché Mnih e colleghi neutralizzano due dei tre con i due trucchi citati.

Maximization bias

$E[\max_a X_a] \ge \max_a E[X_a]$ (disuguaglianza di Jensen, $\max$ convesso). Q-learning prende il $\max_{a'} Q(s', a')$ come stima di $\max_{a'} E[Q^*(s', a')]$, ma con $Q$ rumoroso il max sovrastima sistematicamente. È bias strutturale dell’operatore $T^*$ stimato, non bug del codice. Doppia stima alternata (Hasselt 2010, 2016) la riduce. Sopravvive comunque nei thinking models con value heads stimati: chi addestra deep agent osserva regolarmente Q overestimati e politiche overconfident.

Reward sparsi

Se $R$ è zero quasi ovunque e diverso da zero solo all’arrivo, il Bellman backup propaga informazione di un passo per iterazione. Su orizzonti lunghi servono iterazioni che scalano linearmente nel cammino fino al goal. L’esplorazione diventa il collo di bottiglia: senza visitare il goal, il backup non parte. Ricetta moderna: reward shaping (con cura, vedi agent-coding-anti-pattern in preparazione), HER (hindsight experience replay, Andrychowicz 2017), curriculum learning, intrinsic motivation. Tutte tecniche che non risolvono il problema dell’operatore: lo aggirano cambiando $R$ o la distribuzione di esplorazione.

Distribution shift in offline RL

In offline RL il dataset è fisso, raccolto da una policy $\mu$ ignota. Il Bellman backup richiede $\max_{a'}$ su $Q(s', a')$, ma $a'$ può non essere coperto da $\mu$: $Q(s', a')$ è una estrapolazione della rete, non una stima. Bias di overestimation amplificato. Soluzioni: BCQ, CQL, IQL (capitolo offline-rl non ancora previsto). La fragilità è di nuovo dell’operatore: se non puoi campionare il successore, l’operatore non è ben definito empiricamente.

Reward hacking

Krakovna et al. (2020, Specification gaming examples in AI) raccolgono casi in cui l’agente massimizza $R$ in modi non previsti dal designer. È un fallimento del sistema $R$, non dell’operatore. Ma l’operatore è amplificatore: se $R$ è specificato male, il fixed point del Bellman è il comportamento patologico, e il Bellman lo trova bene. Capitolo reward-hacking non ancora previsto.

LLM agent state non veramente Markov

Quando un LLM agisce in un harness, lo “stato” è il contesto in finestra. La Markov property tiene solo se la finestra contiene tutto ciò che serve a predire il futuro. Spesso non è così: roba uscita per compaction, side-effect filesystem, stato del provider remoto, stato umano del supervisore. Tutto il framework Bellman si applica a un MDP che non è davvero un MDP. Il fixed point esiste matematicamente, ma è il fixed point di un modello che ignora ciò che l’ambiente non ha incapsulato. È una delle ragioni per cui l’RL puro su LLM agent è ancora lontano dal funzionare bene fuori da contesti circoscritti.

Norma sbagliata, prove perse

Le prove di contrazione girano in sup-norm. È la scelta giusta in tabular finito: ogni stato è “uguale agli altri” come oggetto computazionale. Cambiare norma può rompere la garanzia. In particolare, l’operatore composto $\Pi T^\pi$ con una proiezione $\Pi$ in norma euclidea non è una contrazione in sup-norm; è una contrazione solo in una norma pesata dalla distribuzione stazionaria della Markov chain on-policy. Off-policy, niente norma in cui sia contrazione: ed è esattamente il varco da cui passa la divergenza. Questo è il cuore del risultato di Tsitsiklis e Van Roy. Vale la pena ricordare che la “norma” non è un dettaglio tecnico: è la cornice in cui esiste il teorema. Cambiare norma, o cambiare distribuzione di esempi, sposta il teorema o lo elimina.

RLHF: il reward model è approssimato e il Bellman propaga il bias

In RLHF $r_\phi$ è una rete addestrata su preferenze umane finite. Quando il PPO ottimizza il return scontato di $r_\phi$, il Bellman backpropaga gli errori di $r_\phi$ lungo l’orizzonte. Errori piccoli sui singoli reward diventano errori grandi sulle value function di stati lontani dal “fondo” di $r_\phi$. È un meccanismo strutturale, indipendente dalla qualità del reward model. Mitigazioni: KL-regularization sopra (riduce la distanza percorribile), reward clipping, conservatismo. La forma chiusa soft-Bellman con prior $\pi_\text{ref}$ è una risposta diretta a questo problema.

Collegamenti

• Probabilità di base: expectation, varianza e distribuzioni sono il vocabolario del lato destro di ogni Bellman backup.
• Discesa del gradiente: SGD è il motore di Q-learning con FA; il problema del target che si muove è esattamente quello che target network e replay risolvono.
• Curse of dimensionality: perché il tabular muore presto e perché la function approximation è obbligata, con tutte le conseguenze sulla deadly triad.
• Bias-varianza: TD vs Monte Carlo è un trade-off bias-varianza puro; TD ha bias più alto (bootstrapping) ma varianza più bassa.
• Giochi: definizione: MDP è un gioco a un agente contro la natura; il backup Bellman è l’analogo del minimax in giochi a due.
• Minimax: in giochi a due, $T^*$ diventa “minimax operator” e mantiene la struttura di contrazione (per giochi finiti, con discount).
• Multi-armed bandits: caso degenere a uno stato; non c’è transizione, niente backup, niente fixed point. L’esplorazione resta.
• UCB e Thompson sampling: meccanismi di esplorazione che si trasferiscono pari pari nel mondo MDP.
• Markov Decision Process: la grammatica entro cui vivono i due operatori che abbiamo studiato qui.
• value-iteration-policy-iteration (in preparazione): le applicazioni dirette dell’operatore in modalità planning.
• q-learning (in preparazione): il sample-based di $T^*$.
• policy-gradient (in preparazione): l’altra grande famiglia, complementare a Q-learning.
• ppo-trpo (in preparazione): il PPO che ottimizza l’objective KL-regularized in RLHF.
• rlhf-ppo (in preparazione): RLHF dove il soft Bellman appare come forma chiusa della policy ottima.
• dpo-family (in preparazione): l’inversione della forma chiusa RLHF.

Una nota sulle classi di affermazioni

Per chiarezza, a chiusura del capitolo, mappiamo le classi delle affermazioni che il capitolo ha fatto.

Teoremi (formalmente provabili, citati con prova in 4 righe o riferimento): $T^\pi$ e $T^*$ sono $\gamma$-contrazioni in sup-norm; Banach garantisce esistenza/unicità del fixed point e convergenza geometrica; Q-learning tabular converge a $Q^*$ sotto Robbins-Monro (Watkins-Dayan 1992); l’operatore distributional è contrazione in Wasserstein massima (Bellemare-Dabney-Munos 2017).

Equivalenze argomentate: TD error ↔ Bellman residual stocastico (calcolo dell’expectation condizionale); Q-learning update ↔ campione di $T^*$ applicato a $Q$; policy ottima KL-regularized ↔ forma chiusa Gibbs del soft Bellman.

Filiazioni documentate: Watkins 1989 cita esplicitamente Bellman 1957 e Sutton 1988; DQN cita Q-learning; soft Bellman cita Bellman classico; RLHF KL-regularized si appoggia su MaxEnt RL.

Analogie: l’operatore come “applicare una volta la dinamica”, il fixed point come “mappa di altimetria che non si modifica più”. Sono dispositivi didattici, non teoremi.

Tenere queste classi distinte aiuta a non confondere “il TD error è il Bellman residual” (vero, equivalenza calcolabile) con “Q-learning è Value Iteration” (analogia utile ma non equivalenza: Q-learning campiona, Value Iteration no).

Per andare oltre

• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Capitoli 3-7 e 11. Riferimento didattico universale; in particolare per backup diagrams e per la formulazione “deadly triad”.
• Bellman, R. (1957). Dynamic Programming. Princeton University Press. Il libro originale: il capitolo 3, sul principio di ottimalità, vale ancora la lettura.
• Watkins, C. J. C. H., & Dayan, P. (1992). “Q-learning.” Machine Learning, 8(3-4), 279-292. La prova originale di convergenza tabular.
• Puterman, M. L. (1994/2005). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley. Riferimento formale per le prove di contrazione, monotonia, esistenza/unicità del fixed point.
• Bellemare, M. G., Dabney, W., & Rowland, M. (2023). Distributional Reinforcement Learning. MIT Press. Trattazione moderna dell’operatore distributional, con prove e algoritmi.