Markov Decision Process: il framework formale del decidere nel tempo

Un agente, uno stato, un’azione, una ricompensa, un altro stato. Ripetere. Il MDP è la grammatica minima di questa frase.

Perché questo capitolo

Tutto ciò che il libro ha detto finora sul decidere — bandits, minimax, equilibri di Nash — descrive scelte singole o giochi a struttura nota. Manca un pezzo: cosa succede quando le mie azioni cambiano lo stato del mondo, e quel mondo nuovo influenza le mie azioni successive. Quasi tutti i problemi interessanti hanno questa forma: pilotare un drone, giocare a Go, scegliere il prossimo token di una risposta, decidere se chiamare un tool o rispondere direttamente.

Il Markov Decision Process — d’ora in poi MDP — è il modello matematico che cattura esattamente questo. È al contempo poco e molto: poco perché la sua definizione sta in cinque simboli, $(S, A, P, R, \gamma)$ ; molto perché ogni algoritmo di reinforcement learning, da Q-learning del 1989 a PPO che addestra GPT-4 nel 2024, opera dentro questa cornice. Capire MDP non è opzionale per chi vuole capire RL. È RL, prima ancora che gli si dia un nome.

C’è una seconda ragione, più recente. Quando un LLM agisce dentro un harness — pensa, chiama un tool, legge il risultato, decide se ripetere o concludere — sta giocando un MDP. Non sempre lo sa, e quasi mai lo si dichiara, ma il loop ReAct, l’addestramento RLHF, il decoding token-per-token sono tutti realizzabili come MDP con scelte specifiche di stato, azione e ricompensa. Riconoscere il framework permette di importare cinquant’anni di teoria, e di vedere dove questa teoria si rompe quando l’agente è un trasformer da un trilione di parametri invece che un robottino in un gridworld.

Contesto

Il MDP nasce a metà anni Cinquanta dal programma di dynamic programming di Richard Bellman (matematico americano, RAND Corporation). Bellman cercava un linguaggio per problemi di controllo ottimale ricorsivi e nel 1957 pubblica due cose: il libro Dynamic Programming (Princeton University Press) e l’articolo A Markovian Decision Process sul Journal of Mathematics and Mechanics, dove la tupla compare per la prima volta con questo nome. Tre anni dopo Ronald Howard (ingegnere operations research, MIT poi Stanford) pubblica Dynamic Programming and Markov Processes (1960), introducendo Policy Iteration come algoritmo alternativo a Value Iteration e dimostrandone la convergenza in numero finito di passi.

Sul lato multi-agent, Lloyd Shapley (matematico, futuro Nobel per l’economia 2012) aveva già anticipato il framework nel 1953 con Stochastic Games (PNAS): la generalizzazione di MDP a più giocatori che agiscono simultaneamente in stati condivisi. Il filo si riannoda mezzo secolo dopo nel multi-agent reinforcement learning.

La rinascita pratica arriva con due svolte. Chris Watkins (PhD Cambridge 1989) introduce Q-learning, un algoritmo che impara $Q^*$ senza conoscere $P$ né $R$ — il primo passo concreto fuori dal mondo del planning a modello noto. Volodymyr Mnih e colleghi DeepMind nel 2015 (Human-level control through deep reinforcement learning, Nature 518) sostituiscono la tabella $Q$ con una rete neurale convoluzionale: nasce DQN, gioca Atari leggendo i pixel. Da lì la cascata: AlphaGo (2016), policy gradient, PPO, RLHF.

Sul fronte LLM, Paul Christiano e colleghi (Deep Reinforcement Learning from Human Preferences, NeurIPS 2017) mostrano che il reward $R$ non deve venire dall’ambiente: si può apprenderlo da preferenze umane su coppie di traiettorie. Long Ouyang e il team OpenAI (Training Language Models to Follow Instructions with Human Feedback, NeurIPS 2022) applicano la ricetta a un LLM su scala produttiva: nasce InstructGPT, base diretta di ChatGPT.

Il grafo concettuale è denso. MDP discende da dynamic programming (filiazione documentata, Bellman cita esplicitamente i propri lavori del 1953). Stochastic games di Shapley sono parente in linea collaterale (entrambi figli di una matematica del decidere stocastico, ma sviluppati in parallelo). Q-learning, policy gradient, DQN, PPO, RLHF sono tutti figli diretti — ottimizzano la stessa funzione obiettivo dentro lo stesso framework, cambiando solo come la stimano. Bandits (capitolo 120) ne è un caso degenere a uno stato. Sono filiazioni vere, non analogie.

L’intuizione

Prima del formalismo, due angoli concreti. Servono entrambi: chi entra dal primo capisce la dinamica, chi entra dal secondo capisce l’obiettivo.

Angolo 1: il labirinto rumoroso

Immagina di trovarti in una griglia di stanze. Da ogni stanza puoi tentare di muoverti in quattro direzioni. La porta funziona quasi sempre, ma una volta su dieci si inceppa e finisci in una stanza laterale a caso. In una stanza c’è una buca: ci cadi, fine, perdi. In un’altra c’è un’uscita: ci arrivi, hai vinto. Ogni passo costa un po’ (la batteria si scarica).

La domanda non è “qual è il percorso più corto”. È “qual è la regola di scelta — una azione per ogni stanza in cui mi posso trovare — che massimizza il guadagno atteso, tenendo conto del rumore delle porte e del costo dei passi?”. La risposta non è unica per stanza in isolamento: dipende da dove le altre stanze ti mandano. Il valore di stare in una stanza è fatto di passato (come ci sei arrivato non conta, bonus della Markov property) e futuro (cosa aspetti, in media, da qui in avanti). Il MDP è il linguaggio per dire questo bene.

Angolo 2: il valore atteso del futuro

Stai giocando in un casinò strano: ogni scelta ti mette davanti a una nuova tavola con nuove probabilità. Vuoi rispondere alla domanda “quanto vale, in monete, trovarmi qui?” La risposta non è quanto vinci ora — quello è il reward immediato. È quanto, in media, vinci da qui fino alla fine, sommando tutto, scontando un po’ le vincite lontane (perché preferisci vincere prima che dopo, e perché i conti devono convergere quando il gioco non finisce mai).

Questa quantità — il valore di uno stato sotto una strategia — è la value function. Una volta che sai calcolarla, sai anche scegliere: in ogni stato prendi l’azione che massimizza il valore atteso del prossimo stato. È una procedura ricorsiva: il valore di qui dipende dal valore di lì, che dipende dal valore di altrove, che dipende dal valore di qui. Sembra un loop che non chiude. In realtà chiude, e l’equazione che lo dimostra è una delle più importanti del Novecento applicato.

La meccanica

Definizione formale

Un MDP è la tupla $(S, A, P, R, \gamma)$ dove:

$S$ è l’insieme degli stati. Per ora finito.
$A$ è l’insieme delle azioni. Per ora finito. A volte $A(s)$ dipende dallo stato.
$P(s' \mid s, a)$ è la probabilità di transizione: dato $s$ e azione $a$ , probabilità di finire in $s'$ . Soddisfa $\sum_{s'} P(s' \mid s, a) = 1$ per ogni $(s, a)$ .
$R(s, a)$ è la ricompensa attesa ricevuta prendendo $a$ in $s$ . Convenzione equivalente: $R(s, a, s')$ ricompensa puntuale, e si prende l’attesa.
$\gamma \in [0, 1]$ è il discount factor.

Il tempo è discreto: $t = 0, 1, 2, \ldots$ . Lo stato iniziale $s_0$ è dato (o campionato da una distribuzione iniziale). A ogni passo l’agente osserva $s_t$ , sceglie $a_t$ secondo la propria policy, riceve $r_{t+1}$ e si trova in $s_{t+1} \sim P(\cdot \mid s_t, a_t)$ .

flowchart LR
    A["Agente"] -- "azione a_t" --> E["Ambiente"]
    E -- "stato s_{t+1}" --> A
    E -- "reward r_{t+1}" --> A

Figura 1 — -agent-environment-loop

Markov property

L’assunzione che dà il nome al modello:

P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t)

In parole: la storia non conta, lo stato corrente racchiude tutto ciò che serve per prevedere il futuro. È un’idealizzazione, non una proprietà fisica del mondo. Spesso si forza facendo crescere lo stato: in giochi a turni completamente osservabili (scacchi, Go) la posizione attuale basta; in Atari serve includere più frame consecutivi (si vede direzione e velocità della pallina); per un LLM agent lo “stato” è tutto il contesto in finestra.

Quando lo stato non basta, il problema è formalmente un POMDP, di cui parleremo più avanti.

Policy

Una policy $\pi$ mappa stati in distribuzioni su azioni:

Deterministica: $a = \pi(s)$ .
Stocastica: $\pi(a \mid s) \in [0, 1]$ , $\sum_a \pi(a \mid s) = 1$ .

Per ogni MDP finito esiste almeno una policy deterministica ottima — questo è un teorema, non un’osservazione casuale. Lo notiamo perché autorizza, senza perdita di generalità, a cercare l’ottimo nello spazio piccolo delle policy deterministiche.

Return

Il return $G_t$ è la somma scontata delle ricompense future:

G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \ldots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}

Il discount $\gamma$ ha due letture, complementari:

Preferenza temporale (analogia, non causalità): una ricompensa oggi vale più di una ricompensa identica fra dieci passi, come in finanza il valore presente di un flusso futuro.
Convergenza: con reward limitati e $\gamma < 1$ , la serie geometrica converge sempre, e l’operatore di Bellman che vedremo è una contrazione. Senza $\gamma < 1$ (su task continuing) molte cose smettono di funzionare in modo pulito.

Su task episodici (esiste uno stato terminale) si può usare $\gamma = 1$ e il return è una somma finita.

Value functions

Date una policy $\pi$ , definiamo:

V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s]

Q^\pi(s, a) = \mathbb{E}_\pi[G_t \mid s_t = s, a_t = a]

$V^\pi$ è il valore di uno stato sotto $\pi$ : quanto, in attesa, otterrò partendo da $s$ e seguendo $\pi$ . $Q^\pi$ è il valore di una coppia stato-azione: quanto, in attesa, otterrò se in $s$ prendo $a$ e poi seguo $\pi$ . La differenza:

A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s)

è l’advantage: quanto è meglio (o peggio) prendere $a$ in $s$ rispetto alla scelta media sotto $\pi$ . Tornerà in policy gradient (capitolo policy-gradient, in preparazione) come stimatore a varianza ridotta.

Relazione utile: $V^\pi(s) = \sum_a \pi(a \mid s) Q^\pi(s, a)$ .

Equazioni di Bellman, expectation

Sfruttando la Markov property e la definizione ricorsiva di $G_t = r_{t+1} + \gamma G_{t+1}$ :

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

Q^\pi(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) \sum_{a'} \pi(a' \mid s') Q^\pi(s', a')

Letta riga per riga, la prima dice: il valore di $s$ sotto $\pi$ è la media, pesata da $\pi$ , di “ricompensa immediata di $a$ più valore scontato del prossimo stato, mediato sulla dinamica $P$ ”. Le tre somme corrispondono a tre fonti di stocasticità: la scelta dell’azione (interna a $\pi$ ), la transizione dello stato (esterna, da $P$ ), e — implicitamente — il futuro da $s'$ in poi (catturato in $V^\pi(s')$ ).

In forma matriciale, fissata $\pi$ :

V^\pi = R^\pi + \gamma P^\pi V^\pi \quad \Rightarrow \quad V^\pi = (I - \gamma P^\pi)^{-1} R^\pi

dove $R^\pi$ è il vettore delle ricompense attese sotto $\pi$ e $P^\pi$ è la matrice di transizione marginalizzata su $\pi$ . Il sistema è lineare e si risolve in chiusa: $\mathcal{O}(|S|^3)$ per l’inversione. Su MDP grandi non è praticabile, ma è importante notarlo: valutare una policy fissata è un problema lineare.

-bellman-backup-diagram

Equazioni di Bellman, optimality

Definendo $V^*(s) = \max_\pi V^\pi(s)$ e $Q^*(s, a) = \max_\pi Q^\pi(s, a)$ :

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

Q^*(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) \max_{a'} Q^*(s', a')

Differenza cruciale rispetto alle expectation: il max sostituisce la media pesata da $\pi$ . Le optimality equations non sono lineari. Non si invertono — si iterano.

Una volta noto $Q^*$ , la policy ottima si legge banalmente: $\pi^*(s) = \arg\max_a Q^*(s, a)$ . Si capisce perché i metodi value-based (Q-learning, DQN) puntano a $Q^*$ : contiene già la decisione.

Esistenza e unicità di V*

Definiamo l’operatore di Bellman ottimale $T^*: \mathbb{R}^{|S|} \to \mathbb{R}^{|S|}$ :

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

Si dimostra (TEOREMA, classe: teorema vero, dimostrazione standard in Puterman 1994) che $T^*$ è una contrazione in norma sup con costante $\gamma$ :

\|T^* V - T^* V'\|_\infty \le \gamma \|V - V'\|_\infty

Per il teorema del punto fisso di Banach (analisi funzionale, ogni contrazione su spazio metrico completo ha un unico punto fisso e la successione iterata converge), $T^*$ ha un unico punto fisso $V^*$ . La successione $V_{k+1} = T^* V_k$ converge a $V^*$ a partire da qualunque $V_0$ , geometricamente: $\|V_k - V^*\|_\infty \le \gamma^k \|V_0 - V^*\|_\infty$ .

Questo non è folklore: è la ragione formale per cui Value Iteration funziona. Ed è il motivo per cui $\gamma < 1$ è importante: se $\gamma = 1$ , la stima sopra non dice nulla, e in effetti su task continuing si possono avere problemi di non-convergenza.

Value iteration

L’algoritmo è quasi una trascrizione dell’operatore.

Input: MDP (S, A, P, R, gamma), tolleranza eps
V <- zeros(|S|)
repeat:
  delta <- 0
  for s in S:
    v_old <- V(s)
    V(s) <- max over a of [ R(s,a) + gamma * sum over s' of P(s'|s,a) * V(s') ]
    delta <- max(delta, |V(s) - v_old|)
  until delta < eps
pi(s) <- argmax over a of [ R(s,a) + gamma * sum over s' of P(s'|s,a) * V(s') ] for each s
return pi, V

Convergenza geometrica con rate $\gamma$ . Costo per iterazione: $\mathcal{O}(|S|^2 |A|)$ .

Policy iteration

L’idea di Howard (1960) è alternare valutazione completa e miglioramento.

Input: MDP, policy iniziale pi_0
pi <- pi_0
repeat:
  # Policy evaluation
  V <- solve V = R^pi + gamma * P^pi * V       # sistema lineare
  # 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: stop
  pi <- pi_new
return pi, V

TEOREMA (Howard 1960): su MDP finiti, Policy Iteration converge alla policy ottima in un numero finito di passi (al più $|A|^{|S|}$ , ma in pratica molto meno). La differenza pratica con Value Iteration: Policy Iteration fa più lavoro per iterazione (risolvere un sistema lineare) ma le iterazioni necessarie sono spesso poche.

Generalized Policy Iteration (Sutton-Barto) è la famiglia di algoritmi che alternano valutazione parziale e miglioramento parziale: VI e PI sono i due estremi.

Pseudocodice numpy: Value Iteration su gridworld

import numpy as np

# Gridworld 4x4
# 0 = libera, 1 = pit (-1, terminal), 2 = goal (+1, terminal)
GRID = np.array([
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 2],
])
H, W = GRID.shape
N_STATES = H * W
ACTIONS = [(-1,0), (1,0), (0,-1), (0,1)]   # N, S, W, E
GAMMA = 0.95
STEP_REWARD = -0.04
SLIP = 0.1                                  # 10% di slip su perpendicolare

def to_idx(r, c): return r * W + c
def is_terminal(s):
    r, c = divmod(s, W)
    return GRID[r, c] in (1, 2)

def transitions(s, a):
    """Ritorna lista di (prob, next_state, reward)."""
    if is_terminal(s):
        return [(1.0, s, 0.0)]
    r, c = divmod(s, W)
    intended = ACTIONS[a]
    perp = [ACTIONS[(a+2) % 4], ACTIONS[(a+3) % 4]] if a < 2 else [ACTIONS[0], ACTIONS[1]]
    outcomes = [(1 - SLIP, intended)] + [(SLIP/2, p) for p in perp]
    result = []
    for prob, (dr, dc) in outcomes:
        nr, nc = max(0, min(H-1, r+dr)), max(0, min(W-1, c+dc))
        ns = to_idx(nr, nc)
        cell = GRID[nr, nc]
        if cell == 1:   reward = -1.0 + STEP_REWARD
        elif cell == 2: reward = +1.0 + STEP_REWARD
        else:           reward = STEP_REWARD
        result.append((prob, ns, reward))
    return result

V = np.zeros(N_STATES)
for it in range(1000):
    V_new = np.zeros_like(V)
    for s in range(N_STATES):
        if is_terminal(s):
            V_new[s] = 0.0
            continue
        q_values = []
        for a in range(len(ACTIONS)):
            q = sum(p * (r + GAMMA * V[ns]) for p, ns, r in transitions(s, a))
            q_values.append(q)
        V_new[s] = max(q_values)
    if np.max(np.abs(V_new - V)) < 1e-6:
        break
    V = V_new

# Policy greedy
policy = np.zeros(N_STATES, dtype=int)
for s in range(N_STATES):
    q_values = [sum(p * (r + GAMMA * V[ns]) for p, ns, r in transitions(s, a))
                for a in range(len(ACTIONS))]
    policy[s] = int(np.argmax(q_values))

print(V.reshape(H, W))
print(policy.reshape(H, W))

Trenta righe di numpy che risolvono un MDP. È la cosa che fa Bellman 1957 a mano, su carta.

-gridworld-value-iteration

flowchart LR
  A[Inizializza policy] --> B[Osserva stato s_t]
  B --> C[Seleziona azione a_t ~ pi]
  C --> D[Esegui azione]
  D --> E[Osserva reward r_t+1 e s_t+1]
  E --> F[Aggiorna policy / value]
  F --> B

Figura 5 — loop dell’agente RL come ciclo di osservazione, scelta dell’azione, esecuzione, aggiornamento di policy/value

Esempi

Esempio 1: MDP a tre stati, calcolo a mano

Tre stati $S = \{0, 1, 2\}$ , due azioni $A = \{a, b\}$ , $\gamma = 0.9$ . Lo stato 2 è terminale (assorbente, reward 0). Dinamica:

stato	azione	next	prob	reward
0	a	1	1.0	0
0	b	2	1.0	1
1	a	0	1.0	0
1	b	2	1.0	2

Intuizione: in stato 0, “b” porta direttamente al terminale con reward 1, “a” rimanda allo stato 1. Da 1, “b” porta al terminale con reward 2, “a” torna a 0. Conviene mai non andare al terminale?

Calcoliamo $V^*$ via tre passi di Value Iteration partendo da $V_0 = (0, 0, 0)$ .

Iterazione 1:

$V_1(0) = \max(0 + 0.9 \cdot 0, \, 1 + 0.9 \cdot 0) = 1$
$V_1(1) = \max(0 + 0.9 \cdot 0, \, 2 + 0.9 \cdot 0) = 2$
$V_1(2) = 0$ (terminale)

Iterazione 2:

$V_2(0) = \max(0 + 0.9 \cdot 2, \, 1 + 0.9 \cdot 0) = \max(1.8, 1.0) = 1.8$
$V_2(1) = \max(0 + 0.9 \cdot 1, \, 2 + 0.9 \cdot 0) = \max(0.9, 2.0) = 2.0$

Iterazione 3:

$V_3(0) = \max(0 + 0.9 \cdot 2.0, \, 1.0) = 1.8$
$V_3(1) = \max(0 + 0.9 \cdot 1.8, \, 2.0) = \max(1.62, 2.0) = 2.0$

Convergenza. $V^* = (1.8, 2.0, 0)$ . Policy ottima: in 0 prende “a” (vale di più passare per 1!), in 1 prende “b”. Lezione: scontare un reward più grande di $1/\gamma$ volte può valere più che incassarne uno piccolo subito. La greedy miope ( $\gamma = 0$ ) sceglierebbe “b” in 0 (reward 1 immediato) e perderebbe. È il punto di tutto MDP: ottimizzare il futuro scontato, non il presente.

Esempio 2: gridworld 4x4 in numpy

Lo pseudocodice della sezione precedente, eseguito sul gridworld con pit in (1,1) e goal in (3,3), $\gamma = 0.95$ , slip 0.1, reward di passo $-0.04$ , converge in circa 50 iterazioni a tolleranza $10^{-6}$ . La heatmap di $V^*$ mostra valori positivi vicino al goal, valori negativi vicino al pit, gradiente regolare. La policy greedy:

In ogni cella adiacente al pit, preferisce muoversi lontano dal pit anche pagando un passo extra, perché il rischio di slip in quel passo (10%) costa $-1$ in attesa, molto più del costo del passo aggiuntivo.
In angolo opposto, va dritta verso il goal.
Mai va sopra il pit, anche se geometricamente sarebbe più corto.

Questa è la differenza tra “shortest path” e “ottima sotto incertezza”. La prima ignora il rumore; la seconda lo paga e di conseguenza devia.

Esempio 3: LLM agent ReAct come MDP

Un agente ReAct (capitolo react, in preparazione) opera così: legge il task, alterna passi di tipo “Thought” (testo libero di ragionamento) e “Action” (chiamata a un tool con argomenti), riceve “Observation” (risultato del tool), termina con “Final answer”.

Realizziamolo come MDP:

Stato $s_t$ : la concatenazione attuale del prompt iniziale, di tutte le Thought/Action/Observation generate finora, e dei flag di terminazione. Lo stato è alto-dimensionale ma osservabile (sta nel context window).
Azione $a_t$ : una scelta tra $\{$ Thought( $\cdot$ ), Action(tool, args), FinalAnswer( $\cdot$ ) $\}$ . Il " $\cdot$ " è esso stesso una sequenza di token, per cui in realtà l’azione è composita; possiamo o quantizzare a livello macro (3 azioni discrete + parametri) o scendere al token e dire che ogni azione è un singolo token.
Transizione $P$ : deterministica per Thought e FinalAnswer (lo stato si aggiorna concatenando l’output). Stocastica per Action(tool, args) perché il tool può ritornare risultati variabili (web search, lettura file mutevoli, query a un DB con dati nuovi).
Ricompensa $R$ : zero su tutti i passi non terminali; al passo terminale, +1 se la FinalAnswer è corretta secondo un evaluator (test che passa, golden answer match, judge LLM con score sufficiente), 0 altrimenti. Episodi di lunghezza limitata.
Discount $\gamma$ : tipicamente $\gamma = 1$ con horizon limitato, così che la ricompensa terminale non sia indebitamente schiacciata.

Markov property regge se e solo se il context window contiene tutto il rilevante. Se l’agente ha avuto compaction o si è dimenticato un’osservazione precedente, lo stato non è più Markov (ASSUMPTION da dichiarare in qualunque setup serio).

Adesso il punto chiave. RLHF (Christiano 2017, Ouyang 2022 InstructGPT) addestra un policy $\pi_\theta$ — il modello — a massimizzare il return atteso in un MDP token-level dove:

Stato: prompt + token generati finora.
Azione: il prossimo token.
Transizione: deterministica (concatenazione del token allo stato).
Ricompensa: data dal reward model $\hat R_\phi$ appreso da preferenze umane via Bradley-Terry, applicata alla traiettoria completa, più una KL penalty verso la policy SFT per non allontanarsi troppo (KL term, vedi entropia-cross-entropy nel capitolo 105).

Argomentabile equivalenza (classe: equivalenza, ma con condizioni): “addestrare il modello con RLHF” è formalmente “trovare $\pi_\theta$ che approssima $\pi^*$ per l’MDP definito sopra”. La differenza con un RL classico è che $R$ non è dato dall’ambiente ma appreso a parte; la struttura matematica del problema non cambia. Questo non è un’analogia retorica — è l’algoritmo PPO, applicato alla lettera, dentro la libreria TRL/RLHF.

flowchart LR
  S["contesto = prompt + history (stato)"] --> A1["Thought<br/>token di ragionamento"]
  S --> A2["Action: tool_call"]
  S --> A3["Final answer (terminale)"]
  A1 --> S
  A2 --> O["Observation<br/>output del tool"]
  O --> S
  A3 --> R["reward = successo del task"]

Figura 6 — ReAct come istanza di MDP — stato = contesto, azioni Thought / Action(tool) / Final answer, reward solo allo stato terminale

Applicazioni pratiche

Deep RL classico: DQN (Mnih 2015) approssima $Q^*$ con una rete neurale, l’aggiornamento è una versione stocastica dell’operatore di Bellman. PPO (Schulman 2017) ottimizza una policy parametrizzata massimizzando un surrogate del return atteso con vincolo di trust region.
AlphaGo e successori: MCTS guidato da una value network che stima $V$ , una policy network che propone azioni. Il framework MDP è la cornice formale; MCTS è la procedura di pianificazione.
RLHF e RLAIF: il LLM è la policy, il reward model è il $R$ appreso. PPO ottimizza, KL al modello SFT regolarizza. Constitutional AI (Anthropic 2022) sostituisce le preferenze umane con feedback generato da un altro modello che applica una “costituzione”.
Tool-use agent harness: ogni harness (Claude Code, Cursor, ReAct agent) implementa un loop MDP. Le decisioni di design — quali tool esporre, come aggregare le observation, quando interrompere — sono progettazione di $S$ , $A$ , $R$ .
Dialogue policy nei voice agent: scegliere se chiedere chiarimento, dare risposta breve, deferire a umano. Modellabile come MDP con stato = stato della conversazione.
Robotica: pianificazione di traiettorie, controllo di manipolatori. Spazi continui, tipicamente function approximation + policy gradient.
Operations research: gestione inventario, manutenzione predittiva, routing veicoli — applicazioni storiche, precedono il deep learning.

Dove si rompe

La cornice è elegante. La realtà la mette sotto pressione su molti assi.

Markov property. Quasi nessun problema reale è Markov senza fatica. Storia non visibile, sensori che falsano lo stato, tool con effetti collaterali a tempo lungo. Lo si forza facendo crescere lo stato, ma cresce rapidamente: frame stack in Atari, hidden state ricorrenti in robotic, intero context window negli LLM agent. Quando lo stato non basta davvero, si è in POMDP: lo stato è latente, l’agente osserva $o_t$ correlato e mantiene un belief $b_t$ (distribuzione su $S$ ). POMDP è formalmente un MDP sul belief space, ma intrattabile in generale. La regola, non l’eccezione: la maggior parte dei problemi reali è POMDP travestito.

Reward shaping e reward hacking. L’agente massimizza $R$ , non l’intenzione del designer. Se $R$ è disegnato male, l’agente trova scorciatoie. Caso classico CoastRunners (OpenAI 2016): agente in barca premiato per i bonus lungo il percorso invece che per finire la gara — impara a girare in cerchio raccogliendo bonus in loop, mai finisce. Negli LLM agent reward hacking si manifesta come “compiace il judge”, “gioca con i metric senza risolvere il task”, “fabbrica output che superano l’eval ma non il reale obiettivo”.

Discount $\gamma$ . Troppo basso ( $\gamma = 0.5$ ): l’agente è miope, non investe in azioni con payoff lontano. Troppo alto ( $\gamma \to 1$ ): la varianza degli stimatori esplode, il segnale del singolo reward si annacqua nel mare delle traiettorie. Nessun valore di $\gamma$ è “neutro” — è un iperparametro che codifica una preferenza temporale.

Spazi grandi e function approximation. Sui MDP tabulari i teoremi di convergenza sono puliti. Appena si parametrizza $V_\theta$ o $\pi_\theta$ con una rete neurale, le garanzie cadono. Q-learning con function approximation può divergere (deadly triad: bootstrapping, off-policy, function approximation insieme). DQN funziona grazie a trucchi (replay buffer, target network) che mitigano il problema senza risolverlo formalmente. Riprenderemo quando parleremo di Q-learning (in preparazione).

Curse of dimensionality. Anche prima del function approximation: $|S|$ cresce esponenzialmente con il numero di variabili dello stato. Gridworld $4 \times 4$ ha 16 stati, ma 16 variabili binarie già danno $2^{16}$ stati. Il capitolo 110 (curse-dimensionalita) lo dice in generale; qui significa che VI/PI tabulari sono eseguibili solo su MDP molto piccoli.

Non-stationarity. MDP assume $P$ e $R$ fissi. In realtà gli utenti cambiano comportamento, l’ambiente evolve, in multi-agent gli altri imparano insieme a te (e quindi la “loro” parte di $P$ è non stazionaria dal tuo punto di vista). Multi-agent RL eredita gli stochastic games di Shapley e tutte le loro difficoltà.

Offline RL. Quando non si può interagire — perché interagire è caro, pericoloso, o perché si hanno solo log esistenti — si fa RL su dataset fissati. Il problema diventa extrapolation error: la policy migliora rispetto a stime $Q$ che possono essere arbitrariamente sbagliate fuori dal supporto del dataset. Algoritmi come CQL, IQL, BCQ tentano di vincolare la policy al supporto dei dati, ma è una battaglia in salita.

LLM agent: i problemi specifici. Reward signal sparso (success solo a fine task, episodi lunghi), branching factor enorme (vocabolario di decine di migliaia di token, o spazio di tool combinatorio), Markov fragile (compaction, dimenticanze), credit assignment difficile su orizzonti lunghi (quale tra cento Thought ha portato al successo?). RLHF mitiga alcuni problemi ma non li risolve: il reward model è una proxy del reward vero, e ottimizzarlo troppo aggressivamente porta a Goodhart-style failure (la metrica diventa il target e smette di essere proxy).

ASSUMPTION non sempre verificata: trattare l’agent loop di un LLM come MDP richiede di stipulare che il context window sia uno stato sufficiente. Lo è se il task è breve e si scrive tutto in contesto. Smette di esserlo con compaction, con sub-agent, con memory esterna persistente. Quando si rompe, formalmente si scivola in POMDP, e si dovrebbe dirlo.

Bandits come MDP degenere, e perché la cosa conta. Il capitolo 120 (multi-armed-bandits) descrive un problema senza stato: tira una leva, ricevi reward, ricomincia. Visto come MDP, è il caso $|S| = 1$ (oppure $\gamma = 0$ , equivalentemente con horizon 1). In questa luce le tecniche di esplorazione di UCB e Thompson sampling (capitolo 121) sono casi particolari del problema generale di esplorare un MDP. Non sorprende che l’estensione al caso multi-stato — UCB-tree dentro MCTS, posterior sampling per RL — sia attiva e fertile. La filiazione è documentata, non inventata: i paper di RL bayesiano citano esplicitamente Thompson 1933.

Stochastic games come MDP multi-agent. Nella formulazione di Shapley 1953, ogni stato è esso stesso un gioco normale: i giocatori scelgono simultaneamente azioni, le ricompense e la transizione dipendono dal vettore di azioni. MDP è il caso single-agent, gioco a un giocatore contro la natura stocastica. Multi-agent reinforcement learning eredita questa cornice e i suoi guai: equilibri multipli (vedi equilibrio-nash, capitolo 115), non-stationarity per ogni singolo agente che vede gli altri imparare, problema di coordinamento. È un’area dove la teoria pulita di Bellman si frantuma rapidamente, e vale la pena saperlo per non importare ingenuamente garanzie del single-agent in setting cooperativi o competitivi.

flowchart LR
    S0((S0))
    S1((S1))
    S2((S2))
    S0 -- "stay: p=0.7, r=0" --> S0
    S0 -- "stay: p=0.3, r=0" --> S1
    S0 -- "move: p=1.0, r=-1" --> S2
    S1 -- "stay: p=0.6, r=+1" --> S1
    S1 -- "move: p=0.4, r=0" --> S0
    S2 -- "any: p=1.0, r=0" --> S0

Figura 2 — -mdp-3-state-graph

flowchart LR
  A[Inizializza policy] --> B[Osserva stato s_t]
  B --> C[Seleziona azione a_t ~ pi]
  C --> D[Esegui azione]
  D --> E[Osserva reward r_t+1 e s_t+1]
  E --> F[Aggiorna policy / value]
  F --> B

Figura 5 — -rl-agent-loop-mermaid

Collegamenti

probabilita-base — valore atteso, distribuzioni, varianza: la matematica con cui si calcola tutto sopra.
bayes-base — non centrale qui, ma fondamentale per POMDP (aggiornamento del belief).
entropia-cross-entropy — KL divergence: usata come penalty in RLHF tra $\pi_\theta$ e $\pi_{\text{SFT}}$ .
gradienti-intuito e discesa-gradiente — fondamenta per policy gradient e per addestrare $V_\theta$ , $Q_\theta$ , $\pi_\theta$ con neural networks.
curse-dimensionalita — perché VI/PI tabulari muoiono su MDP grandi.
giochi-definizione e minimax — single-agent vs multi-agent, MDP vs stochastic games.
multi-armed-bandits e ucb-thompson — bandit come MDP a uno stato, esplorazione vs sfruttamento.
equazione-bellman (in preparazione) — approfondimento sulla ricorsione e sulle sue varianti.
value-iteration-policy-iteration (in preparazione) — i due algoritmi di planning trattati a fondo.
q-learning (in preparazione) — apprendere $Q^*$ senza conoscere $P$ né $R$ .
policy-gradient (in preparazione) — ottimizzare direttamente $\pi_\theta$ via gradiente del return atteso.
ppo-trpo (in preparazione) — il policy gradient con vincolo di trust region che addestra RLHF.
rlhf-ppo (in preparazione) — RLHF come MDP con reward model appreso.
agente-definizione (in preparazione) — definizione operativa dell’agente, di cui MDP è la cornice formale.
react (in preparazione) — il pattern ReAct visto qui come MDP.

Note sulla notazione

In questo capitolo abbiamo usato $V$ per state-value, $Q$ per action-value, $A$ per advantage, $G$ per return, $\pi$ per policy. È la convenzione standard di Sutton-Barto, che si è imposta nella letteratura RL moderna. Il libro di Puterman usa altre lettere ( $v$ , $q$ , $h$ per il return, $d$ per la policy). Lo segnaliamo per chi consulterà entrambe: la matematica è la stessa, i simboli no.

Il discount $\gamma$ in alcuni testi è chiamato $\beta$ (specialmente in operations research). Il fattore di transizione $P(s' \mid s, a)$ in altri è scritto come kernel $T(s, a, s')$ o come matrice $\mathcal{P}^a_{ss'}$ . Sono notazioni equivalenti.

Per andare oltre

Sutton, R. S. & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Capitoli 3-4 sono il riferimento canonico per MDP, value functions, dynamic programming. Disponibile gratis sul sito degli autori.
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley. Il trattato matematico di riferimento. Per chi vuole le dimostrazioni complete della contrazione e della convergenza.
Bellman, R. (1957). A Markovian Decision Process. Journal of Mathematics and Mechanics, 6(5), 679-684. L’articolo originale. Sei pagine, leggibile, vale per il piacere storico.
Christiano, P. F. et al. (2017). Deep Reinforcement Learning from Human Preferences. NeurIPS 2017. arXiv:1706.03741. Per vedere dove RL incontra LLM e cambia faccia all’AI applicata.
Ouyang, L. et al. (2022). Training Language Models to Follow Instructions with Human Feedback (InstructGPT). arXiv:2203.02155. Per la versione su scala produttiva.