Q-learning e DQN: imparare a decidere senza modello

Un algoritmo di tre righe scritto da Christopher Watkins nel 1989 ha fondato il reinforcement learning model-free; venticinque anni dopo, gli stessi tre passi infilati in una rete convoluzionale hanno fatto giocare un computer a quarantanove videogiochi Atari a livello umano. Capire quelle tre righe è capire come si impara una policy partendo solo da campioni.

Perché questo capitolo

I tre capitoli precedenti hanno costruito l’impianto teorico del decision making in regime markoviano: l’MDP come framework (122), l’equazione di Bellman come operatore di contrazione (123), Value Iteration e Policy Iteration come algoritmi che lo applicano quando il modello è completamente noto (124). Ma quasi nessun problema interessante arriva con il modello in chiaro. Non si conosce la dinamica esatta di un braccio robotico, né la distribuzione delle mosse di un avversario al Go, né la probabilità che un utente clicchi su un articolo dopo averne visti altri tre. In tutti questi casi si ha solo accesso all’ambiente: si agisce, si osserva il prossimo stato e il reward, e si deve imparare da quello.

Q-learning è la risposta canonica a questa domanda. Inventato da Christopher Watkins nella tesi di dottorato del 1989 e dimostrato convergente da Watkins e Dayan nel 1992, è un algoritmo di poche righe che applica Value Iteration a colpi di campioni stocastici, senza richiedere niente più del trace $(s, a, r, s')$. È model-free (non costruisce un modello di $P$ o $R$), off-policy (impara la policy ottima mentre ne segue una diversa, esplorativa), e TD(0) (bootstrappa su un solo passo). Per quasi vent’anni resta un algoritmo accademico, applicato a problemi di taglia tabulare o a giochi giocattolo. Poi, nel 2013-2015, Volodymyr Mnih e colleghi a DeepMind lo combinano con una rete convoluzionale e due trucchi di stabilizzazione, e ottengono DQN (Deep Q-Network): il sistema che impara a giocare a quarantanove giochi Atari leggendo i pixel grezzi, raggiungendo o superando il livello umano in ventinove di essi. Quello è il momento in cui il deep reinforcement learning entra nella mappa pubblica del campo.

Questo capitolo conta per tre ragioni. La prima è di filiazione: ogni algoritmo successivo in cui compaiono le sigle Double DQN, Dueling DQN, Rainbow, C51, soft Q, BCQ, CQL, IQL discende per linea diretta da Q-learning. Senza la base di Q-learning queste varianti sono nomi senza spina dorsale. La seconda è operativa: in molte applicazioni industriali, dalla recommendation alla robotica al controllo di sistemi, Q-learning con qualche estensione è ancora la prima cosa da provare prima di scomodare actor-critic o policy gradient. La terza è di collegamento: il legame tra Q-learning e RLHF moderno, in particolare Direct Preference Optimization (DPO), si capisce solo se si è internalizzato cosa significa “soluzione in forma chiusa di un Q-update sotto KL-reg”. Senza questo capitolo, la frase resta opaca.

La promessa esecutiva: alla fine si saprà scrivere Q-learning tabular in dieci righe di numpy, DQN minimale in cento righe di PyTorch, e si saprà diagnosticare i tre modi tipici in cui entrambi falliscono.

Contesto

Il grafo concettuale è denso. A monte di Q-learning ci sono tre filoni che convergono.

Programmazione dinamica e iterazione del valore. Richard Bellman (matematico americano, 1920-1984, RAND Corporation) introduce l’equazione che porta il suo nome nel libro Dynamic Programming del 1957 e VI come algoritmo nel medesimo testo. Ronald Howard (ingegnere operations research, MIT, poi Stanford) formalizza Policy Iteration nella tesi del 1960. Entrambi presuppongono modello noto. Vedi value-iteration-policy-iteration (124) per il dettaglio.

Temporal Difference learning. Richard Sutton (informatico canadese, allora a UMass Amherst, oggi DeepMind/University of Alberta) introduce TD(0) nel 1988 in “Learning to Predict by the Methods of Temporal Differences” su Machine Learning. L’idea: aggiornare una stima di valore $V(s)$ verso $r + \gamma V(s')$, senza aspettare la fine dell’episodio. È bootstrap: si usa una stima per migliorare un’altra stima. È il salto che rende possibile imparare on-line, da traiettorie incomplete.

Stochastic approximation. Herbert Robbins (statistico americano, Columbia) e Sutton Monro (statistico americano), nel 1951, in “A Stochastic Approximation Method” su Annals of Mathematical Statistics, dimostrano che si può risolvere $f(x)=0$ con osservazioni rumorose di $f$, sotto due condizioni sui learning rate $\alpha_t$: $\sum_t \alpha_t = \infty$ e $\sum_t \alpha_t^2 < \infty$. È l’attrezzo matematico che lega tutto.

Christopher Watkins (informatico britannico, Cambridge) nel 1989, nella tesi Learning from Delayed Rewards, mette insieme i tre filoni. Definisce la action-value function $Q^\pi(s,a)$ — il valore atteso del return se in $s$ si fa $a$ e poi si segue $\pi$ — e formula la regola che oggi chiamiamo Q-learning. Watkins e Peter Dayan (informatico britannico, allora a Edimburgo, poi UCL e Max Planck Tübingen) pubblicano nel 1992 su Machine Learning “Q-learning” con la prima dimostrazione di convergenza nel caso tabulare. John Tsitsiklis (operations researcher canadese-greco, MIT) generalizza nel 1994 in “Asynchronous Stochastic Approximation and Q-Learning” su Machine Learning alla versione asincrona, in cui non tutte le coppie $(s,a)$ vengono aggiornate ad ogni passo.

Sul lato del deep learning, due ingredienti maturano in parallelo. Gerald Tesauro (informatico statunitense, IBM Research) dimostra con TD-Gammon nel 1992 che TD learning su una rete neurale può arrivare a livello expert in un dominio complesso (backgammon). Vedi td-gammon-1992 (17). Damien Ernst, Pierre Geurts, Louis Wehenkel (Université de Liège) pubblicano nel 2005 su JMLR “Tree-based batch mode reinforcement learning”, introducendo Fitted Q-Iteration (FQI): batch RL in cui ad ogni iterazione si fitta un regressore generico (alberi, foreste) sui target Q. Martin Riedmiller (informatico tedesco, allora Friburgo) propone nel 2005 Neural Fitted Q-Iteration (NFQ), versione di FQI con rete neurale.

Il salto a DQN avviene nel 2013. Volodymyr Mnih (informatico ucraino-canadese, ex postdoc di Geoffrey Hinton, da pochi mesi a DeepMind) e colleghi caricano su arXiv “Playing Atari with Deep Reinforcement Learning”. Sette giochi, sei migliorati rispetto allo stato dell’arte. Quattordici mesi dopo, nel febbraio 2015, lo stesso gruppo pubblica su Nature vol. 518 pp. 529-533 “Human-level control through deep reinforcement learning”: quarantanove giochi, ventinove a livello umano, una sola architettura. Vedi dqn-atari-2013 (20) per la cornice storica.

Da DQN nasce una proliferazione di varianti. Hado van Hasselt (informatico olandese, allora UAlberta poi DeepMind) introduce Double Q-learning nel tabular nel 2010, e con Arthur Guez e David Silver Double DQN nel 2015. Ziyu Wang e colleghi propongono Dueling DQN nel 2016. Tom Schaul e altri Prioritized Experience Replay nel 2016. Marc Bellemare, Will Dabney, Rémi Munos introducono il Distributional RL con C51 nel 2017. Matteo Hessel e colleghi combinano sei estensioni in Rainbow nel 2018. Tuomas Haarnoja introduce Soft Q-learning nel 2017, base teorica di Soft Actor-Critic.

Sul versante offline, Scott Fujimoto, David Meger, Doina Precup (McGill) documentano in “Off-Policy Deep Reinforcement Learning without Exploration” (ICML 2019) il fenomeno dell’extrapolation error che fa esplodere DQN naive applicato a dataset fissi, e propongono BCQ. Aviral Kumar e Sergey Levine (Berkeley) introducono CQL (Conservative Q-Learning) nel 2020. Ilya Kostrikov e colleghi IQL (Implicit Q-Learning) nel 2021. Sono i tre algoritmi di riferimento per offline RL.

Sul versante LLM, Rafael Rafailov, Archit Sharma e colleghi (Stanford) pubblicano nel 2023 “Direct Preference Optimization: Your Language Model is Secretly a Reward Model” (NeurIPS), mostrando che sotto reward modellato e KL-regularization l’optimal policy ha forma chiusa, e l’addestramento si riduce a una BCE su preferenze pairwise. La connessione con Q-learning è argomentabile sotto ipotesi (equivalenza in setting bandit con KL-reg) ma non identica nel caso multi-step.

Una nota di differenziazione rispetto ai capitoli vicini, importante per evitare doppioni. In 122 si è introdotto l’MDP. In 123 si è dato Bellman come operatore $T^*$ contrattivo, e si è citato Q-learning come “campione stocastico” di $T^*$. In 124 si è dato VI/PI con modello noto. Qui Q-learning è il protagonista: derivazione completa, condizioni di convergenza, codice, estensioni, limiti. Quando in 124 il modello sparisce e i campioni prendono il suo posto, si finisce qui.

L’intuizione

Tre angoli prima del formalismo. Due descrivono Q-learning standalone; il terzo lega tutto ai capitoli precedenti.

Angolo 1 — Imparare quanto vale fare $a$ in $s$, contando solo i sample

Pensa a un giocatore di scacchi alle prime armi. Non conosce la teoria, non ha studiato aperture. Gioca, vince qualche partita, perde altre. Dopo cento partite ha un’intuizione vaga: “in questa posizione, muovere il cavallo qui sembra darmi buone chance, mentre spingere il pedone laterale finisce male”. Non sa perché, non ha un modello del gioco; ha solo accumulato statistica empirica.

Q-learning formalizza esattamente questa intuizione. Per ogni stato $s$ e azione $a$ tieni un numero $Q(s,a)$ — la stima corrente del return atteso se da $s$ fai $a$ e poi giochi al meglio. Ogni volta che osservi una transizione $(s, a, r, s')$, aggiorna $Q(s,a)$ tirandolo verso il TD-target $r + \gamma \max_{a'} Q(s', a')$, di un passo $\alpha$. Ripeti tante volte. Sotto condizioni precise — ne riparliamo — $Q(s,a)$ converge al valore vero $Q^*(s,a)$, e la policy “scegli $\arg\max_a Q(s,a)$” diventa ottima.

Quel max interno è la chiave. Dice: “non importa quale azione io abbia preso davvero al passo successivo, voglio fittarmi sul best possible prossimo passo”. È quello che rende Q-learning off-policy: il bersaglio è la policy ottima, non quella che sto seguendo per esplorare.

Angolo 2 — VI con il modello sostituito da un singolo sample

L’aggiornamento di Value Iteration per la action-value function (vedi 124) è

$$Q_{k+1}(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \max_{a'} Q_k(s', a').$$

Quel termine $\sum_{s'} P(s'|s,a) \max_{a'} Q_k(s',a')$ è un’aspettazione su tutti i prossimi stati possibili. Per calcolarla servono $P$ e $R$.

Se non li hai ma puoi interagire con l’ambiente, ottieni un singolo sample $s' \sim P(\cdot|s,a)$ e un singolo $r$. Sostituisci l’aspettazione con quel sample:

$$\hat T = r + \gamma \max_{a'} Q_k(s', a').$$

Questo $\hat T$ è uno stimatore unbiased di $T^*_Q Q_k(s,a)$, ma rumoroso. Per aggregare il rumore non sostituisci $Q$ con $\hat T$ direttamente, ma fai una media mobile esponenziale:

$$Q(s,a) \leftarrow Q(s,a) + \alpha (\hat T - Q(s,a)).$$

Questo è Q-learning. Letteralmente: VI in cui l’expectation è approssimata dal sample corrente, e l’aggiornamento è smussato da $\alpha$. È equivalenza argomentabile con VI sample-based — nel limite $\alpha_t \to 0$ con $\sum \alpha_t = \infty$ e visite infinite, si recupera VI esatta. Lo dice Watkins-Dayan 1992.

Angolo 3 — Off-policy come superpotere

C’è una proprietà sottile che vale la pena distillare separatamente. La policy che genera i dati (ε-greedy, random, una vecchia policy congelata) è diversa dalla policy che Q-learning sta cercando di imparare (la greedy ottima). Questo perché il target usa $\max_{a'}$, non $Q(s', a'_{\text{actually taken}})$. Conseguenza: posso esplorare in modo arbitrariamente strano e Q-learning continua a stimare $Q^*$.

Il fratello on-policy, SARSA, fa il contrario: $Q(s,a) \leftarrow Q(s,a) + \alpha[r + \gamma Q(s', a'_{\text{actually taken}}) - Q(s,a)]$. SARSA stima $Q^\pi$ per la $\pi$ comportamentale, quindi una ε-greedy converge a $Q^{\varepsilon\text{-greedy}}$, che non è $Q^*$.

L’esempio canonico (Sutton-Barto, Cliff Walking): un agente cammina in una griglia con un dirupo. Q-learning impara la policy ottima — cammina sul bordo del dirupo perché è la via più breve — ma se ε è alto cade spesso nel dirupo durante il training. SARSA impara una policy più conservativa che si tiene lontana dal bordo, perché tiene conto del comportamento ε-greedy che continua a generare i dati. Greedy a fine training, Q-learning vince. Cumulative reward durante il training, SARSA vince. È una distinzione, non una gerarchia.

La meccanica

Setup formale

Sia $\mathcal{M} = (S, A, P, R, \gamma)$ un MDP finito con $\gamma \in [0, 1)$. La action-value function ottima soddisfa l’equazione di Bellman ottimale per Q:

$$Q^*(s,a) = \mathbb{E}_{s' \sim P(\cdot|s,a)} \left[ R(s,a) + \gamma \max_{a'} Q^*(s', a') \right].$$

Definiamo l’operatore di Bellman ottimale per Q:

$$(T^*_Q Q)(s,a) := \mathbb{E}_{s' \sim P(\cdot|s,a)} \left[ R(s,a) + \gamma \max_{a'} Q(s', a') \right].$$

Si dimostra (analoga di 123 per $V$) che $T^*_Q$ è una contrazione $\gamma$ in norma $\ell_\infty$, quindi ha unico punto fisso $Q^*$ e iterando $T^*_Q$ partendo da qualsiasi $Q_0$ si converge a $Q^*$ a rate geometrico.

La regola Q-learning

Osservata la transizione $(s_t, a_t, r_{t+1}, s_{t+1})$:

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

Il termine $\delta_t := r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t)$ è il TD-error. Letto in pezzi:

• $r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')$: il TD-target. È la stima corrente del return atteso da $(s_t, a_t)$, costruita come reward immediato osservato più stima scontata del prossimo passo, sotto l’assunzione che da $s_{t+1}$ in poi si giochi greedy. Notare che è uno stimatore stocastico di $T^*_Q Q(s_t, a_t)$ — campionato su $s_{t+1}$ e $r_{t+1}$, deterministico nel resto.
• $- Q(s_t, a_t)$: la stima corrente, sottratta. La differenza misura quanto il target rompe la stima.
• $\alpha_t \delta_t$: passo di correzione, learning rate $\alpha_t \in (0, 1]$.

Derivazione come Robbins-Monro

Robbins e Monro (1951) considerano il problema di trovare $x^*$ tale che $\mathbb{E}[Y(x^*)] = 0$ per una variabile aleatoria $Y$ funzione di $x$. L’algoritmo è $x_{t+1} = x_t + \alpha_t Y_t(x_t)$. Sotto $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$, e ipotesi di regolarità (Lipschitz, momenti finiti), $x_t \to x^*$ a.s.

Applicato a Q-learning: $x = Q$, $Y(Q) = r + \gamma \max_{a'} Q(s',a') - Q(s,a)$ con $s'$, $r$ campionati. $\mathbb{E}[Y(Q) | s,a] = T^*_Q Q(s,a) - Q(s,a)$, che è zero esattamente in $Q = Q^*$. L’update di Q-learning è quindi R-M sull’operatore $T^*_Q - I$.

Teorema (Watkins-Dayan 1992; Tsitsiklis 1994). Sia $\mathcal{M}$ MDP finito con $\gamma < 1$. Se per ogni $(s,a)$ vale $\sum_t \mathbb{1}[(s_t,a_t)=(s,a)] = \infty$ a.s., $\sum_t \alpha_t(s,a) = \infty$, $\sum_t \alpha_t^2(s,a) < \infty$, allora $Q_t \to Q^*$ a.s.

In parole: ogni coppia stato-azione visitata infinite volte, learning rate che decresce ma non troppo in fretta. Sotto queste ipotesi la convergenza è garantita. È un teorema, con prova matematica completa nel paper originale (e in versione più moderna in Bertsekas-Tsitsiklis 1996 Neuro-Dynamic Programming).

La condizione “ogni $(s,a)$ visitata infinite volte” è la ragione per cui Q-learning richiede esplorazione. Una policy puramente greedy può ignorare per sempre azioni con stima iniziale bassa che però sarebbero ottime. Servono ε-greedy, Boltzmann, optimistic initialization, UCB, intrinsic motivation, o altre forme di esplorazione attiva.

Esplorazione: ε-greedy

La scelta più semplice. Con probabilità $1-\varepsilon$ scegli $\arg\max_a Q(s,a)$, con probabilità $\varepsilon$ scegli un’azione uniforme. Schedule tipico: $\varepsilon$ decresce nel tempo, partendo da 1.0 e arrivando a un floor $\varepsilon_{\min}$ (tipicamente 0.05 o 0.01). Decay lineare in $T_{\text{decay}}$ step:

$$\varepsilon_t = \max\left( \varepsilon_{\min}, 1 - \frac{t}{T_{\text{decay}}} (1 - \varepsilon_{\min}) \right).$$

In DQN su Atari: $\varepsilon$ da 1.0 a 0.1 lineare in $10^6$ frame, poi 0.05 fino a fine training. Numeri non scelti dal nulla; sono il risultato di tuning empirico riportato in Mnih 2015.

Tabular vs function approximation

Nel caso tabulare, $Q$ è una matrice $|S| \times |A|$. Aggiornamento di una cella alla volta. Convergenza dimostrata.

Con function approximation, $Q_\theta(s,a)$ è parametrizzato (lineare o NN). L’analogo dell’update è un gradient step semi-gradiente:

$$\theta \leftarrow \theta - \alpha \nabla_\theta \frac{1}{2} \left[ r + \gamma \max_{a'} Q_{\bar\theta}(s', a') - Q_\theta(s,a) \right]^2,$$

dove $\bar\theta$ è una copia congelata di $\theta$ (gradient non si propaga attraverso il target). Quel “semi” è cruciale: se si propagasse il gradient anche nel target, la dinamica non sarebbe più una contrazione e potrebbe divergere.

Deadly triad (Sutton-Barto 2018, §11.3): function approximation + bootstrapping + off-policy. Tre ingredienti che, presi insieme, possono far divergere Q-learning anche con learning rate corretto. Q-learning con NN soffre tutti e tre. Leemon Baird (1995) costruì un counterexample esplicito di sette stati in cui Q-learning lineare diverge. Per anni il deadly triad ha frenato l’applicazione di NN a RL. DQN aggira il problema con due trucchi.

DQN: target network e replay buffer

Mnih 2013/2015. Due ingredienti chiave a cui si aggiunge un terzo cosmetico.

Target network. Tieni due copie della rete: la online network $Q_\theta$ che si aggiorna ad ogni step, e la target network $Q_{\theta^-}$ che è una copia di $\theta$ aggiornata ogni $C$ step (in DQN Atari, $C = 10000$). Il TD-target usa $\theta^-$:

$$y = r + \gamma \max_{a'} Q_{\theta^-}(s', a').$$

Senza target network il bootstrap insegue se stesso: ogni gradient step modifica anche il target che il prossimo step vorrebbe colpire. Con target network il target è un bersaglio fisso per $C$ step.

Experience replay buffer. Salva ogni transizione $(s,a,r,s',d)$ in una coda di $10^6$ elementi. Durante il training, samplea minibatch da 32 elementi i.i.d. dal buffer. Due benefici. Primo, decorrela: i sample di un rollout sono correlati (frame consecutivi di un episodio sono quasi identici), e gradient steps su sample correlati sono biased. Sampling i.i.d. dal buffer rompe la correlazione. Secondo, riusa: ogni transizione contribuisce a più gradient step, migliorando la sample efficiency.

Reward clipping. In Atari, $r$ è clippato a $\{-1, 0, +1\}$, per uniformare scale fra giochi. Dettaglio pratico, non necessario in problemi a scala fissa.

L’architettura: 4 frame impilati 84×84 grayscale → conv (8×8, stride 4, 32 ch) → conv (4×4, stride 2, 64 ch) → conv (3×3, stride 1, 64 ch) → FC 512 → FC $|A|$. Output: un valore Q per ogni azione disponibile. Loss: Huber (smooth L1) sul TD-error, robusta a outlier.

Maximization bias e Double DQN

Hado van Hasselt (2010) osserva che $\mathbb{E}[\max_a \hat Q(s,a)] \geq \max_a \mathbb{E}[\hat Q(s,a)]$, per disuguaglianza di Jensen applicata al $\max$. Conseguenza: se $Q$ è stimato rumoroso (early training, FA imprecisa), il $\max$ seleziona sistematicamente azioni la cui stima è alta per fortuna, non per merito. Q-target è inflazionato. Bias positivo, persistente.

Double Q-learning (tabular, Hasselt 2010): tieni due tabelle $Q^A, Q^B$. Update alterna: con prob 0.5,

$$Q^A(s,a) \leftarrow Q^A(s,a) + \alpha[r + \gamma Q^B(s', \arg\max_{a'} Q^A(s',a')) - Q^A(s,a)],$$

e con prob 0.5 lo specchio (scambia $A$ e $B$). Una tabella seleziona l’azione, l’altra la valuta. Le due stime sono indipendenti, il bias scompare.

Double DQN (Hasselt-Guez-Silver 2015): nello spirito, una sola modifica al TD-target di DQN:

$$y_{\text{DDQN}} = r + \gamma Q_{\theta^-}\left(s', \arg\max_{a'} Q_\theta(s', a')\right).$$

Online network seleziona l’azione, target network la valuta. Cambio di una riga di codice. Score Atari medio +27% (riportato in Hasselt 2015 fig. 5).

Estensioni notevoli

• Dueling DQN (Wang 2016): la rete output decompone $Q(s,a) = V(s) + A(s,a) - \frac{1}{|A|}\sum_a A(s,a)$. Migliore quando in molti stati l’azione conta poco e basta stimare $V(s)$.
• Prioritized Experience Replay (Schaul 2016): probabilità di sample $\propto |\delta|^\omega$. Con importance sampling correction per non biasare il fit. Migliora sample efficiency su ambienti con reward sparso.
• Multi-step Q-learning: target $\sum_{k=0}^{n-1} \gamma^k r_{t+k+1} + \gamma^n \max_{a'} Q(s_{t+n}, a')$. Bias-varianza intermedio fra TD(0) e Monte Carlo.
• C51 (Bellemare-Dabney-Munos 2017): impara la distribuzione del return su 51 atomi, non solo il valor medio. Loss KL fra distribuzione predetta e Bellman target proiettato. QR-DQN (Dabney 2018) usa quantile regression, evitando la proiezione. IQN, FQF estensioni.
• Noisy Net (Fortunato 2017): parametric noise nei layer lineari, esplorazione learned al posto di ε-greedy.
• Rainbow (Hessel 2018): combina sei estensioni (double, dueling, PER, multi-step, distributional, noisy). SOTA Atari per circa due anni.

Soft Q-learning

Tuomas Haarnoja (Berkeley) propone nel 2017 il maximum entropy framework. Il return è regolarizzato con entropia della policy: $J = \mathbb{E}[\sum_t \gamma^t (r_t + \tau \mathcal{H}(\pi(\cdot|s_t)))]$, $\tau > 0$ è la temperatura. L’optimal policy non è deterministica ma stocastica:

$$\pi^*(a|s) \propto \exp\left( \frac{Q^*_{\text{soft}}(s,a)}{\tau} \right).$$

L’operatore di Bellman corrispondente sostituisce $\max$ con un soft-max regolarizzato (LogSumExp con temperatura):

$$T^*_{\text{soft}} Q(s,a) = R(s,a) + \gamma \mathbb{E}_{s'}\left[ \tau \log \sum_{a'} \exp\left( \frac{Q(s',a')}{\tau} \right) \right].$$

Per $\tau \to 0$ recupera Q-learning standard. Per $\tau$ finito incentiva esplorazione e robustezza. È la base teorica di Soft Actor-Critic (Haarnoja 2018) in continuous control. È anche uno dei ponti formali con DPO (vedi sezione 7).

Pseudocodice: Q-learning tabulare

import numpy as np

def q_learning(env, episodes=5000, alpha=0.1, gamma=0.99,
               eps_start=1.0, eps_end=0.05, eps_decay=2000):
    Q = np.zeros((env.n_states, env.n_actions))
    for ep in range(episodes):
        s = env.reset()
        eps = max(eps_end, eps_start - ep / eps_decay)
        done = False
        while not done:
            if np.random.rand() < eps:
                a = np.random.randint(env.n_actions)
            else:
                a = int(np.argmax(Q[s]))
            s_next, r, done = env.step(a)
            target = r + gamma * np.max(Q[s_next]) * (0.0 if done else 1.0)
            Q[s, a] += alpha * (target - Q[s, a])
            s = s_next
    return Q

Quattordici righe. Tutte le decisioni sono in chiaro: ε-greedy, target con bootstrap, mascheratura su done per non bootstrappare oltre il terminale.

Pseudocodice: DQN minimale (PyTorch-style)

import torch, torch.nn as nn, torch.nn.functional as F
from collections import deque
import random

class QNet(nn.Module):
    def __init__(self, obs_dim, n_actions):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(obs_dim, 128), nn.ReLU(),
            nn.Linear(128, 128), nn.ReLU(),
            nn.Linear(128, n_actions))
    def forward(self, x): return self.net(x)

def dqn(env, total_steps=200_000, batch_size=64, gamma=0.99,
        lr=1e-3, buffer_size=100_000, target_sync=1000,
        eps_start=1.0, eps_end=0.05, eps_decay=50_000):
    Q = QNet(env.obs_dim, env.n_actions)
    Q_target = QNet(env.obs_dim, env.n_actions)
    Q_target.load_state_dict(Q.state_dict())
    opt = torch.optim.Adam(Q.parameters(), lr=lr)
    buf = deque(maxlen=buffer_size)
    s = env.reset()
    for t in range(total_steps):
        eps = max(eps_end, eps_start - t * (eps_start - eps_end) / eps_decay)
        if random.random() < eps:
            a = random.randrange(env.n_actions)
        else:
            with torch.no_grad():
                a = int(Q(torch.tensor(s, dtype=torch.float32)).argmax())
        s_next, r, done = env.step(a)
        buf.append((s, a, r, s_next, done))
        s = s_next if not done else env.reset()
        if len(buf) >= batch_size:
            batch = random.sample(buf, batch_size)
            S, A, R, S2, D = zip(*batch)
            S  = torch.tensor(S,  dtype=torch.float32)
            S2 = torch.tensor(S2, dtype=torch.float32)
            A  = torch.tensor(A,  dtype=torch.int64).unsqueeze(1)
            R  = torch.tensor(R,  dtype=torch.float32)
            D  = torch.tensor(D,  dtype=torch.float32)
            q_sa = Q(S).gather(1, A).squeeze(1)
            with torch.no_grad():
                q_next = Q_target(S2).max(1).values
                target = R + gamma * q_next * (1.0 - D)
            loss = F.smooth_l1_loss(q_sa, target)
            opt.zero_grad(); loss.backward()
            nn.utils.clip_grad_norm_(Q.parameters(), 10.0)
            opt.step()
        if t % target_sync == 0:
            Q_target.load_state_dict(Q.state_dict())
    return Q

Cinquanta righe. Ogni elemento del paper Mnih 2015 è presente: ε-greedy con decay, replay buffer FIFO, target network sincronizzata ogni $target_sync$ step, Huber loss, gradient clipping, Adam. Per Double DQN, sostituire le due righe del target con:

a_next = Q(S2).argmax(1, keepdim=True)
q_next = Q_target(S2).gather(1, a_next).squeeze(1)

flowchart LR
  ENV[Environment] -->|s, r, done| AGENT[Azione ε-greedy]
  AGENT -->|a| ENV
  ENV -->|"(s, a, r, s', d)"| BUF[(Replay Buffer 1M)]
  BUF -->|sample 32| BATCH[Minibatch]
  BATCH --> Q[Online Q_θ]
  BATCH --> QT[Target Q_θ-]
  Q --> LOSS[Huber TD loss]
  QT --> LOSS
  LOSS --> OPT[Adam step su θ]
  OPT -. ogni C step .-> SYNC[θ- ← θ]

Figura 6 — training loop di DQN con i quattro componenti chiave — environment, agent ε-greedy, replay buffer 1M, target network sincronizzata ogni C step — e il flusso Huber TD loss + Adam

Esempi

Esempio 1 — MDP a tre stati, cinque step di Q-learning a mano

MDP: stati $\{A, B, C\}$, $C$ terminale assorbente. Azioni $\{L, R\}$ disponibili in ogni stato non terminale. Dinamica deterministica.

• Da $A$: $R \to B$, $r=0$. $L \to A$, $r=-1$.
• Da $B$: $R \to C$, $r=+10$, episodio termina. $L \to A$, $r=0$.

$\gamma = 0.9$, $\alpha = 0.5$. Inizializzo $Q = 0$ ovunque.

Calcolo $Q^*$ analitico per riferimento. Da $B$: $Q^*(B,R) = 10$, $Q^*(B,L) = 0 + 0.9 \cdot \max(Q^*(A,L), Q^*(A,R))$. Da $A$: $Q^*(A,R) = 0 + 0.9 \cdot \max(Q^*(B,L), Q^*(B,R)) = 0.9 \cdot 10 = 9$. $Q^*(A,L) = -1 + 0.9 \cdot 9 = 7.1$. Quindi $Q^*(B,L) = 0 + 0.9 \cdot 9 = 8.1$.

Trace di cinque step (suppongo policy esplorativa che, per fortuna, sceglie sempre $R$):

Step 1. $s=A$, $a=R$, $r=0$, $s'=B$. Target $= 0 + 0.9 \cdot \max(Q(B,L), Q(B,R)) = 0.9 \cdot 0 = 0$. $Q(A,R) \leftarrow 0 + 0.5 (0 - 0) = 0$.

Step 2. $s=B$, $a=R$, $r=10$, terminale. Target $= 10 + 0$ (mask done). $Q(B,R) \leftarrow 0 + 0.5 (10 - 0) = 5$.

Step 3 (nuovo episodio). $s=A$, $a=R$, $r=0$, $s'=B$. Target $= 0.9 \cdot \max(0, 5) = 4.5$. $Q(A,R) \leftarrow 0 + 0.5 (4.5 - 0) = 2.25$.

Step 4. $s=B$, $a=R$, $r=10$, terminale. $Q(B,R) \leftarrow 5 + 0.5 (10 - 5) = 7.5$.

Step 5 (nuovo episodio). $s=A$, $a=R$, $r=0$, $s'=B$. Target $= 0.9 \cdot 7.5 = 6.75$. $Q(A,R) \leftarrow 2.25 + 0.5 (6.75 - 2.25) = 4.5$.

Dopo cinque step: $Q(B,R) = 7.5 \to 10$ (vero), $Q(A,R) = 4.5 \to 9$ (vero). Convergenza visibile dopo poche dozzine di episodi (verificabile a mano o con uno script).

Lettura: il valore terminale $r=10$ si propaga all’indietro un passo per episodio. Dopo $n$ episodi, l’informazione ha attraversato $n$ stati. Su un MDP con 100 stati a catena, servono almeno 100 episodi prima che l’informazione del terminal arrivi al primo stato. Questo è il costo del bootstrap TD(0): lento su orizzonti lunghi. Multi-step TD ($n$-step) e Monte Carlo accelerano a costo di varianza maggiore.

Esempio 2 — Gridworld 5×5 in numpy

Griglia 5×5. Cella $(0,0)$ partenza. Cella $(4,4)$ goal con $r=+1$, terminale. Cella $(2,2)$ buca con $r=-1$, terminale. Tutti gli altri passi $r=-0.04$ (penalità per incoraggiare brevità). Quattro azioni: nord, sud, est, ovest. Movimento deterministico, restando fermo se contro un muro.

import numpy as np

class Grid:
    def __init__(self): self.n_states, self.n_actions = 25, 4
    def reset(self): self.r, self.c = 0, 0; return self._s()
    def _s(self): return self.r * 5 + self.c
    def step(self, a):
        dr, dc = [(-1,0),(1,0),(0,1),(0,-1)][a]
        nr, nc = max(0,min(4,self.r+dr)), max(0,min(4,self.c+dc))
        self.r, self.c = nr, nc
        s = self._s()
        if (nr,nc) == (4,4): return s, 1.0, True
        if (nr,nc) == (2,2): return s, -1.0, True
        return s, -0.04, False

env = Grid()
Q = np.zeros((25, 4)); alpha, gamma = 0.1, 0.95
for ep in range(3000):
    s = env.reset(); done = False
    eps = max(0.05, 1.0 - ep/2000)
    while not done:
        a = np.random.randint(4) if np.random.rand() < eps else int(np.argmax(Q[s]))
        s2, r, done = env.step(a)
        target = r + (0 if done else gamma * np.max(Q[s2]))
        Q[s, a] += alpha * (target - Q[s, a])
        s = s2

V = Q.max(axis=1).reshape(5,5)
print(np.round(V, 2))

Output atteso (approssimato, dipende dal seed):

[[ 0.62  0.69  0.78  0.87  0.96]
 [ 0.55  0.61    .  0.96  1.00]
 [ 0.48    .  -1.00    .  0.96]
 [ 0.55  0.61    .  0.87  0.92]
 [ 0.48  0.55  0.62  0.78  0.87]]

(Le celle con . sono visitate poco; i valori esatti variano.) La policy greedy estratta da $\arg\max_a Q$ converge alla policy ottima: cammino su nord-est evitando $(2,2)$. Si può confrontare con $V^*$ calcolato da Value Iteration esatta sullo stesso MDP (vedi 124, sezione esempi): differenza tipica < 0.05.

Esempio 3 — DQN su CartPole-v1

CartPole è il “Hello World” del deep RL. Asta su carrello, due azioni (sinistra/destra), reward +1 per ogni step in cui l’asta sta in piedi. Massimo episodio 500 step. Stato: 4 numeri (posizione carrello, velocità carrello, angolo asta, velocità angolare).

Il codice DQN della sezione “La meccanica” risolve CartPole-v1 in 50-100k step (5-15 minuti su CPU). Pipeline esplicita:

1. Inizializzazione. Q e $Q_target$ MLP 4→128→128→2. Adam lr=1e-3.
2. Rollout. Si parte da s = env.reset(). Per ogni step si calcola $\varepsilon$ in base alla schedule (decay lineare da 1.0 a 0.05 in 50k step), si campiona a ε-greedy, si chiama env.step(a), si pusha (s, a, r, s', done) nel buffer.
3. Training step. Quando il buffer ha almeno 64 elementi, ad ogni step si campiona un minibatch, si calcola target con $Q_target$, loss Huber, gradient step su Q. Gradient clipping per stabilità.
4. Target sync. Ogni 1000 step, Q_target.load_state_dict(Q.state_dict()).
5. Episode tracking. Si log la durata media degli ultimi 100 episodi. Quando supera 475 (criterio standard di solved), si ferma.

Tipica curva: per i primi 10k step l’agente cade subito (durata ~20). Tra 20k e 40k learn rapidamente, durata sale a 200-400. Dopo 50k stabile a 500 (massimo). Senza target network, la curva oscilla violentemente o diverge. Senza replay buffer, si appiattisce a ~50.

Diagnostica tipica quando non funziona: target sync troppo raro → instabilità; target sync troppo frequente → bias; learning rate troppo alto → divergenza; ε decay troppo veloce → exploitation prematura su Q sbagliata; buffer troppo piccolo → correlation residua.

flowchart LR
  ENV[Environment] -->|s, r, done| AGENT[Azione ε-greedy]
  AGENT -->|a| ENV
  ENV -->|"(s, a, r, s', d)"| BUF[(Replay Buffer 1M)]
  BUF -->|sample 32| BATCH[Minibatch]
  BATCH --> Q[Online Q_θ]
  BATCH --> QT[Target Q_θ-]
  Q --> LOSS[Huber TD loss]
  QT --> LOSS
  LOSS --> OPT[Adam step su θ]
  OPT -. ogni C step .-> SYNC[θ- ← θ]

Figura 6 — DQN training loop: mermaid diagram con env interaction, replay buffer, sample batch, Q forward, target Q forward, loss, optimizer, target sync periodic

Applicazioni pratiche

Atari e giochi classici. DQN e Rainbow restano la baseline standard su Arcade Learning Environment (Bellemare 2013). Agent57 (Badia 2020), R2D2 (Kapturowski 2019), Muesli sono estensioni distribuite.

Robotica e controllo. Q-learning con FQI o NFQ in setting batch è applicato a controllo industriale, manipolazione, scheduling. In domini reali con interazione costosa si combina con offline RL (CQL, IQL) su dataset esistenti.

Recommendation systems. YouTube e altri pubblicano lavori (Chen 2019, “Top-K Off-Policy Correction”) in cui Q-learning con importance sampling correction stima il long-term value di raccomandazioni, oltre l’engagement immediato. Sample efficiency è critica perché interazioni utente sono il vincolo.

Distributional RL in produzione. DeepMind ha applicato C51/QR-DQN a problemi reali di controllo dei datacenter (energy management) — il vantaggio della distribuzione è poter ottimizzare metriche di rischio (CVaR) oltre al valor medio.

Offline RL benchmarks. D4RL (Fu 2020) standardizza dataset per locomotion (HalfCheetah, Hopper, Walker2D), AntMaze, manipolazione (Adroit), kitchen tasks. CQL e IQL sono i due algoritmi di riferimento; Decision Transformer e RvS sono varianti non-Q-learning.

RLHF tramite DPO. Direct Preference Optimization (Rafailov 2023) addestra LLM a partire da preferenze pairwise senza un esplicito reward model né un esplicito Q-learning loop. La connessione formale: sotto KL-reg verso una reference policy $\pi_{\text{ref}}$ e in setting bandit (single-step), l’optimal policy ha forma chiusa $\pi^*(a|s) \propto \pi_{\text{ref}}(a|s) \exp(r(s,a)/\beta)$, equivalente a Soft Q-learning con $Q^* = r$ e $\tau = \beta$. La loss DPO è una BCE sulle preferenze pairwise. Equivalenza argomentabile sotto ipotesi: in setting bandit con KL-reg, DPO è la closed-form di Soft Q-learning. Nel caso multi-step (turn-by-turn dialogue) l’equivalenza si rompe e Rafailov stesso è cauto. Da non leggere come “DPO è Q-learning travestito” in senso generale.

LLM-as-agent value of information. Lavori recenti (Reflexion, Trial-and-Error 2024, ARES) usano stime di Q-value imparate o suggerite dall’LLM per decidere quali tool chiamare e quando fermarsi. È area giovane, non ancora consolidata.

Dove si rompe

Q-learning e DQN hanno una lista lunga di failure mode. Vale la pena conoscerli prima di scrivere codice.

Maximization bias. $\mathbb{E}[\max_a \hat Q(s,a)] \geq \max_a \mathbb{E}[\hat Q(s,a)]$. In early training, con stime rumorose, il target è inflazionato. Q diverge verso l’alto, la policy peggiora. Sintomo: Q-values medi crescono indefinitamente, score di valutazione non segue. Fix standard: Double DQN.

Deadly triad. FA + bootstrapping + off-policy. Nessuna garanzia di convergenza. Q-learning con NN incappa in tutti e tre, a meno che non si disinneschi qualcosa: target network rallenta il bootstrapping, replay decorrela ma non rimuove off-policy. Baird counterexample (1995) mostra divergenza esplicita su MDP a 7 stati. In pratica DQN funziona, ma su problemi nuovi diverge senza preavviso.

Bootstrapping lento su sparse reward. Se reward arriva solo a fine episodio lungo, l’informazione si propaga di un passo per episodio. Per orizzonti di migliaia di step, miliardi di episodi sono necessari. Soluzioni parziali: reward shaping (Ng-Harada-Russell 1999), intrinsic motivation (RND, ICM), Hindsight Experience Replay (Andrychowicz 2017).

Reward hacking. La policy massimizza il proxy reward, non l’obiettivo umano. Caso noto CoastRunners (OpenAI 2016): in un gioco di gare in barca, la barca AI gira in cerchio raccogliendo bonus invece di completare il percorso, perché reward proxy era la somma dei bonus, non il piazzamento. Ogni applicazione RL reale richiede reward design pensato.

Sample inefficiency. DQN su Atari richiede 50-200M frame per gioco, settimane di training su una GPU per gioco. Per applicazioni industriali con interazione costosa è inutilizzabile da solo. Mitigazioni: model-based RL, offline RL su dataset preesistenti, transfer learning, world models (Dreamer, MuZero).

Stato non Markov. Q-learning assume Markov. In molti task realistici (POMDP), uno stato che non incorpora la storia rompe la convergenza. DQN su Atari aggira impilando 4 frame. Per LLM agent lo “stato” è il prompt + tool history: pseudo-Markov ma non garantito. Negli agent harness questo si manifesta come ripetizioni, decisioni inconsistenti, perdita di contesto su orizzonti lunghi.

Estrapolazione in offline RL. Fujimoto-Meger-Precup 2019: in setting offline (dataset fisso, niente interazione), il $\max_{a'} Q(s',a')$ può selezionare azioni $a'$ mai osservate vicino a $s'$. Q su tali azioni è pura extrapolation FA, sistematicamente sovrastimata. Bootstrap si avvelena. Q values esplodono, policy diverge. Fix: BCQ vincola le azioni al supporto del dataset; CQL penalizza Q alto su OOD action; IQL evita del tutto il $\max$ esterno al dataset usando expectile regression.

Instability senza target network. È un punto pratico. Senza la copia congelata, il TD-target cambia ad ogni gradient step, e il problema di regressione è non stazionario. La rete insegue il proprio output, oscilla, diverge. La target network è non negoziabile.

Q values inflated anche con Double DQN. Hasselt 2015 fig. 3: in molti giochi Atari, anche con Double DQN, le Q-values stimate sono significativamente più alte del true return. Il bias è ridotto, non eliminato. Per task safety-critical questa sovrastima è inaccettabile e si passa a distributional RL (CVaR-aware) o conservative methods.

“Q” speculations*. Nel novembre 2023 circolano rumor su un sistema interno OpenAI chiamato “Q*” (presumibilmente un acronimo o un riferimento implicito a Q-learning + A*). Nessun paper pubblico, nessuna conferma tecnica. Analogia speculativa, non scienza. Trattare con la cautela dovuta a leak corporate non sostanziati. Il fatto che un Q-learning + search abbia una storia documentata (AlphaZero) non rende il rumor più solido.

DPO non è Q-learning in senso generale. Sotto setting bandit + KL-reg, c’è equivalenza in forma chiusa con Soft Q-learning. Multi-step (dialog turn-by-turn) rompe l’equivalenza. Trattare la connessione come equivalenza argomentabile sotto ipotesi, non come “DPO è Q-learning travestito”.

Reward model misalignment in RLHF Q-learning. Quando reward model è imparato da preferenze umane (Bradley-Terry su pairwise) ed è poi usato come reward in PPO o equivalente Q-learning, gli errori del reward model si compongono con gli errori di estimation Q. Reward hacking diventa più probabile, e mitigation richiede KL-reg verso reference policy (è uno dei motivi per cui RLHF moderno usa PPO con KL penalty piuttosto che Q-learning vanilla).

Collegamenti

• probabilita-base (103): aspettazioni e stimatori imparziali sono il linguaggio in cui si scrive il TD-target.
• discesa-gradiente (107): SGD e Adam sono il backend di DQN. Il “semi-gradient” di Q-learning è una variante di SGD con target staccato dal grafo.
• curse-dimensionalita (110): la ragione per cui tabular Q-learning non scala a Atari. La FA è la risposta, ma porta con sé il deadly triad.
• bias-varianza (111): il trade-off tra TD(0) e Monte Carlo è bias-varianza puro. Multi-step Q-learning interpola.
• multi-armed-bandits (120) e ucb-thompson (121): il bandit è un MDP a un solo stato. ε-greedy, UCB e Thompson sampling appaiono prima qui poi si trasferiscono a Q-learning come strategie di esplorazione.
• markov-decision-process (122): il framework formale.
• equazione-bellman (123): l’operatore $T^*_Q$ che Q-learning approssima. La contrazione $\gamma$ è il motivo per cui converge.
• value-iteration-policy-iteration (124): VI con modello noto. Q-learning è VI con modello sostituito da campioni.
• td-gammon-1992 (17): il primo TD+rete neurale convergente. Antenato diretto di DQN.
• dqn-atari-2013 (20): il momento storico in cui Q-learning + CNN diventa pubblico.
• policy-gradient (in preparazione): l’altra famiglia, gradient ascent diretto sul return invece di stima del valore.
• actor-critic (in preparazione): combinazione di entrambe.
• ppo-trpo (in preparazione): gli algoritmi policy-gradient con vincolo di trust region usati in RLHF.
• dpo-family (in preparazione): la closed-form sotto KL-reg in setting bandit.
• rlhf-ppo (in preparazione): RLHF con PPO, dove la connessione con Q-learning è indiretta.

Per andare oltre

• Sutton, R. S.; Barto, A. G. (2018). Reinforcement Learning: An Introduction. 2nd ed., MIT Press. Capitolo 6 (TD learning) per Q-learning e SARSA tabulari, Capitolo 11 per la trattazione del deadly triad. Disponibile gratuitamente in PDF dal sito di Barto.
• Mnih, V.; et al. (2015). “Human-level control through deep reinforcement learning”. Nature 518:529-533. Il paper DQN canonico. Da leggere per intero almeno una volta.
• Watkins, C. J. C. H.; Dayan, P. (1992). “Q-learning”. Machine Learning 8(3-4):279-292. Sette pagine. La prova originale di convergenza, leggibile.
• Hessel, M.; et al. (2018). “Rainbow: Combining Improvements in Deep Reinforcement Learning”. AAAI 2018, arXiv:1710.02298. Tabella di ablation che mostra il contributo di ogni estensione.
• Levine, S.; et al. (2020). “Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems”. arXiv:2005.01643. Sintesi sistematica del settore offline.