Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman

Un MDP su un mondo a griglia con un dirupo, il ritorno e lo sconto, la funzione di valore e l’equazione di Bellman, l’iterazione dei valori e l’iterazione delle politiche scritte da zero, come lo sconto, lo scivolamento e il costo del passo cambiano il comportamento ottimo, e un controllo con la simulazione.

11 minuti Matěj Žalmánek 2026-10-16

Serie Basi di IA Parte 47 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Finora i modelli della serie imparavano da esempi con la risposta giusta oppure cercavano una struttura nei dati. L’apprendimento per rinforzo è una terza strada: l’agente agisce, il mondo gli dà in cambio ricompense e punizioni, e l’agente deve capire come agire per accumularne il più possibile. Prima di metterci a imparare, ci serve un linguaggio con cui descrivere un problema del genere con precisione. Questo linguaggio è il processo decisionale di Markov. In questa parte lo costruiremo su un piccolo mondo con un dirupo e calcoleremo il comportamento migliore in modo esatto — supponendo di conoscere le regole del mondo.

Prosegue le parti Catene di Markov, Valore atteso, varianza e covarianza e Tipi di apprendimento automatico.

1. Agente, ambiente, ricompensa

Definizione — processo decisionale di Markov (MDP)

Un MDP è una quintupla (S, A, P, R, γ): un insieme di stati S, un insieme di azioni A, le probabilità di transizione P(s′ | s, a), la ricompensa R(s, a, s′) e il fattore di sconto γ ∈ [0, 1). A ogni passo l’agente nello stato s sceglie un’azione a, il mondo lo sposta a caso secondo P in s′ e l’agente riceve una ricompensa. Proprietà di Markov: lo stato successivo dipende solo dallo stato attuale e dall’azione, non dalla storia.

Il nostro mondo è una griglia 6 × 5. L’agente parte a sinistra (S) e può andare in su, a destra, in giù o a sinistra. Tutta la riga in basso è un dirupo: chi ci cade riceve −10 e la partita finisce. Poco lontano dalla partenza c’è un piccolo traguardo da +1, molto più a destra un grande traguardo da +10. Due muri chiudono la strada più corta in alto. E il pavimento può essere scivoloso: con probabilità p l’agente, invece di andare nella direzione voluta, scivola in una delle due direzioni perpendicolari.

P(s′ | s, a) = (1 − p) · [s′ = passo nella direzione a] + p/2 · [s′ = passo perpendicolare a sinistra] + p/2 · [s′ = passo perpendicolare a destra]

P(s′ | s, a)

con quale probabilità l’agente, dopo l’azione a, finisce nella casella s′ — l’intera distribuzione, non solo «dove dovrebbe andare», perché il valore di una mossa si calcolerà come media su tutti i possibili punti di arrivo

(1 − p) · […]

il movimento voluto — riceve la maggior parte della probabilità; con p = 0 resta solo questo termine e il mondo è deterministico

p/2 · […]

lo scivolone di lato, in parti uguali a sinistra e a destra — è per questo che la casella accanto al dirupo è pericolosa anche se camminiamo lungo il dirupo e non verso di esso

Esempio — un passo a destra lungo il dirupo

L’agente si trova sulla casella a destra della partenza (sopra c’è un muro, sotto il dirupo) e sceglie «destra», p = 0,2:

• 0,8 — la casella successiva a destra,
• 0,1 — il dirupo (ricompensa −10, fine),
• 0,1 — la casella a destra della partenza (scivola in su contro il muro e resta dov’è),

in totale 0,8 + 0,1 + 0,1 = 1. La ricompensa immediata attesa di questa mossa è 0,8 · 0 + 0,1 · (−10) + 0,1 · 0 = −1: in media un passo così su dieci finisce con una caduta.

2. Ritorno, sconto e politica

Definizione — ritorno e politica

Il ritorno dall’istante t è la somma scontata delle ricompense future G_t = r_t+1 + γ r_t+2 + γ² r_t+3 + …. Una politica (policy) π dice quale azione scegliere in ciascuno stato — in modo deterministico π(s) = a, oppure come distribuzione π(a | s). L’obiettivo è la politica con il massimo ritorno atteso.

G_t = r_t+1 + γ · G_t+1

G_t

il ritorno da adesso fino alla fine — il numero che l’agente vuole rendere il più grande possibile

r_t+1

la ricompensa subito dopo il prossimo passo — l’unico che riceve senza aspettare, perciò senza sconto

γ

lo sconto — tutto ciò che arriva dopo viene ridotto di un fattore γ; così «più tardi» si traduce in «meno»

G_t+1

il ritorno dal passo successivo — la stessa grandezza un passo più in là; la ricorsione da cui tra poco nascerà l’equazione di Bellman

Teorema — con γ < 1 il ritorno è sempre finito

Se ogni ricompensa è in valore assoluto al più R_max, allora |G_t| ≤ R_max (1 + γ + γ² + …) = R_max / (1 − γ), anche se l’episodio non finisse mai.

Dimostrazione. La disuguaglianza triangolare dà |G_t| ≤ ∑_{k ≥ 0} γ^k |r_t+k+1| ≤ R_max ∑_{k ≥ 0} γ^k e la serie geometrica di ragione 0 ≤ γ < 1 ha somma 1/(1 − γ). ∎

Da noi R_max = 10 e γ = 0,9, quindi |G| ≤ 10 / 0,1 = 100. Senza costo per passo è molto meno ancora: una ricompensa diversa da zero la dà solo l’ingresso in un traguardo o nel dirupo, e al massimo una volta per episodio, quindi |G| ≤ 10. Per questo γ = 1 si può usare solo dove l’episodio finisce di sicuro.

Esempio — il ritorno del percorso più corto verso il grande traguardo

Sul pavimento fermo il percorso più corto verso il traguardo +10 conta 6 passi. I primi cinque passi danno ricompensa 0, il sesto (l’ingresso nel traguardo) +10. Con γ = 0,9:

G₀ = 0 + 0,9 · 0 + 0,9² · 0 + 0,9³ · 0 + 0,9⁴ · 0 + 0,9⁵ · 10 = 0,59049 · 10 = 5,9049.

Sul pavimento fermo non succede nulla di casuale, quindi questo è direttamente il valore della partenza — e il calcolo con l’iterazione dei valori nella sezione sulle politiche dà davvero 5,90. Il piccolo traguardo +1, anche a 3 passi, darebbe solo 0,9² · 1 = 0,81.

3. Il valore e le equazioni di Bellman

Definizione — funzione di valore ed equazione di ottimalità di Bellman

Il valore di uno stato sotto la politica π è il ritorno atteso quando l’agente parte da s e segue π: V^π(s) = E_π[G_t | s_t = s]. Il valore di un’azione Q^π(s, a) è la stessa cosa, ma la prima azione la scegliamo noi. I valori ottimi soddisfano l’equazione di Bellman (Richard Bellman, 1957):

V*(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V*(s′)],

e la politica ottima è π*(s) = argmax_a Q*(s, a), dove Q*(s, a) è l’espressione dentro il massimo.

V*(s) = max_a ∑_s′ P(s′ | s, a) [R(s, a, s′) + γ V*(s′)]

V*(s)

il miglior ritorno atteso dalla casella s — ciò che cerchiamo; compare da entrambe le parti, quindi l’equazione è una condizione che tutti i valori devono soddisfare insieme

max_a

la scelta dell’agente — l’azione la sceglie lui, e quindi prende la migliore; qui l’equazione «di ottimalità» si distingue dall’equazione per una politica fissa π, dove al posto del massimo c’è π(s)

∑_s′ P(s′ | s, a) […]

la media su dove il mondo scaraventa davvero l’agente — su questo l’agente non decide, perciò un valore atteso e non un massimo

R(s, a, s′)

la ricompensa immediata per questa transizione (+1, +10, −10 o il costo del passo)

γ

lo sconto — il futuro è un passo più in là, perciò un fattore γ (come nella formula G_t = r_t+1 + γ G_t+1)

V*(s′)

il miglior ritorno dal punto di arrivo — tutto il futuro riassunto in un solo numero, così non serve percorrere tutti i lunghi cammini

Esempio — l’equazione di Bellman alla partenza (scivolamento 20 %, γ = 0,9)

Valori ottimi già calcolati dei vicini della partenza: la casella sopra la partenza V* = 3,325, la casella a destra V* = 2,260, la partenza stessa V* = 2,854; il dirupo è terminale (valore 0, ricompensa −10). Sostituiamo nel membro destro per ogni azione:

• ↑: 0,8 · (0 + 0,9 · 3,325) + 0,1 · (0 + 0,9 · 2,260) + 0,1 · (0 + 0,9 · 2,854) = 2,854,
• →: 0,8 · (0 + 0,9 · 2,260) + 0,1 · (−10 + 0,9 · 0,000) + 0,1 · (0 + 0,9 · 3,325) = 0,926,
• ↓: 0,8 · (−10 + 0,9 · 0,000) + 0,1 · (0 + 0,9 · 2,854) + 0,1 · (0 + 0,9 · 2,260) = −7,540,
• ←: 0,8 · (0 + 0,9 · 2,854) + 0,1 · (0 + 0,9 · 3,325) + 0,1 · (−10 + 0,9 · 0,000) = 1,354,

Il più grande è ↑ con 2,854, ed è esattamente V*(partenza) — l’equazione vale (la differenza nell’ultima cifra è arrotondamento). L’azione «su» conviene nonostante la probabilità del 10 % che l’agente scivoli a sinistra, urti il bordo e resti sulla partenza: per questo V*(partenza) compare anche a destra. L’azione «giù» porta all’80 % nel dirupo e risulta fortemente negativa.

4. Iterazione dei valori

Definizione — iterazione dei valori

Parti da V₀ = 0 e ripeti per tutti gli stati V_k+1(s) = max_a ∑_s′ P(s′ | s, a) [R + γ V_k(s′)], finché i valori cambiano. Per γ < 1 l’operatore di Bellman è una contrazione: max_s |V_k+1 − V*| ≤ γ · max_s |V_k − V*|, quindi l’errore cala almeno come γ^k.

# iterazione dei valori
V = 0 in tutti gli stati
ripeti:
    per ogni stato non terminale s:
        per ogni azione a:
            Q[a] = ∑ su s′ ( P(s′ | s, a) · (R(s, a, s′) + γ · V(s′)) )
        V_nuovo(s) = max(Q)
    variazione = max su s |V_nuovo(s) − V(s)|
    V = V_nuovo
finché variazione ≥ 10⁻⁶
π(s) = azione con il Q[a] più grande (calcolato dal V finale)

Esempio — i primi tre giri (scivolamento 20 %, γ = 0,9)

Seguiamo due caselle della riga centrale: A subito a sinistra del grande traguardo +10 e B una casella più in là, subito a destra del piccolo traguardo +1. Sopra B c’è un muro, sopra A è libero, sotto entrambe c’è pavimento normale.

giro k	Vk(A)	azione migliore in A	Vk(B)	azione migliore in B
1	8,000	→	0,800	←
2	8,000	→	5,832	→
3	9,166	→	6,343	→

Giro 1 (ovunque V₀ = 0): da A il passo a destra porta con probabilità 0,8 al traguardo, cioè 0,8 · 10 = 8,000. Da B per ora non si vede niente di lontano; la cosa migliore è un passo a sinistra verso il piccolo traguardo: 0,8 · 1 = 0,800.

Giro 2: da B verso destra si arriva in A, che ha già valore 8: 0,8 · 0,9 · 8 = 5,76, più 0,1 · 0,9 · 0,8 = 0,072 per lo scivolone in su (muro, resta in B con V₁ = 0,8) e 0 per lo scivolone in giù — in totale 5,832. L’azione migliore in B è passata da ← a →: l’informazione sul grande traguardo ha viaggiato di una casella.

max_s |V_k+1(s) − V_k(s)| ≤ γ^k · max_s |V₁(s) − V₀(s)|

max |V_k+1 − V_k|

la variazione più grande al giro k + 1 — ciò che il calcolo tiene d’occhio e in base a cui si ferma; nel grafico sotto la linea verde (γ = 0,9) e quella blu (γ = 0,99)

γ^k

ogni giro riduce la differenza tra due stime almeno di γ volte (contrazione); dopo k giri quindi di γ^k volte — da qui la convergenza lenta per γ vicino a 1

max |V₁ − V₀|

l’ampiezza della prima variazione; con V₀ = 0 è la massima ricompensa attesa per un singolo passo, da noi al più 10 — da qui il limite tratteggiato 10 · γ^k nel grafico

Con γ = 0,9 i valori si stabilizzano (variazione sotto 10⁻⁶) dopo 50 iterazioni, con γ = 0,99 dopo 77. L’errore cala più in fretta di quanto garantisca il limite γ^k — che vale sempre, ma in un mondo concreto tende a essere pessimistico. Più γ è vicino a uno, più lontano nel futuro deve propagarsi l’informazione e più a lungo dura il calcolo.

5. Che cosa cambiano lo sconto, lo scivolamento e il costo del passo

Ora la parte più interessante. Lo stesso mondo, solo con altre impostazioni — e la politica ottima appare del tutto diversa.

Sul pavimento fermo il percorso più corto verso il grande traguardo passa rasente il dirupo: 6 passi e un valore della partenza di 5,90. Quando il pavimento scivola, il bordo del dirupo è pericoloso — ogni passo lì significa una probabilità del 10 % di cadere. La politica ottima perciò aggira i muri passando in alto: 10 passi invece di 6, ma nel dirupo cade solo il 0,7 % degli episodi. Se sul pavimento scivoloso usassimo la politica rischiosa, l’agente cadrebbe nel 30 % dei casi e il valore della partenza scenderebbe a 0,64 invece di 2,85.

Con γ = 0,5 il grande traguardo è così lontano che non conviene — +10 fra 10 passi oggi pesa solo 10 · 0,5¹⁰ ≈ 0,01. L’agente va con prudenza in alto verso il piccolo traguardo. Quando invece ogni passo costa −1, conviene rischiare: l’agente va verso il grande traguardo lungo il bordo del dirupo e cade nel 27 % degli episodi. Il percorso lungo e sicuro gli costerebbe di più della perdita media dovuta alle cadute.

La colonna «simulazione» è un controllo: il ritorno medio di 10 000 episodi secondo la politica trovata, con scivolamento casuale. Il ritorno medio differisce dal valore calcolato della partenza al più di qualche centesimo — l’equazione di Bellman calcola davvero il ritorno atteso.

La lezione per le applicazioni reali: il comportamento dell’agente non lo determina solo «qual è l’obiettivo», ma anche dettagli come lo sconto e il costo per passo. Chi progetta le ricompense progetta il comportamento — anche quello che non voleva.

6. Iterazione delle politiche

Definizione — iterazione delle politiche

L’iterazione delle politiche (Ronald Howard, 1960) alterna due passi. Valutazione: per una politica fissa π calcola V^π risolvendo il sistema V^π(s) = ∑_s′ P(s′ | s, π(s)) [R + γ V^π(s′)]. Miglioramento: in ogni stato scegli l’azione con il valore più grande secondo V^π. Quando la politica smette di cambiare, è ottima.

# iterazione delle politiche
π = «su ovunque»
ripeti:
    # valutazione: V^π risolvendo il sistema (da noi con sostituzioni ripetute)
    V = 0
    ripeti finché V cambia di più di 10⁻⁹:
        V(s) = ∑ su s′ ( P(s′ | s, π(s)) · (R + γ · V(s′)) )   per ogni s
    # miglioramento: in ogni stato l’azione migliore secondo V^π
    π_nuova(s) = argmax su a  ∑ su s′ ( P(s′ | s, a) · (R + γ · V(s′)) )
    cambiati = numero di stati dove π_nuova(s) ≠ π(s)
    π = π_nuova
finché cambiati > 0

Teorema — del miglioramento della politica

Se la nuova politica π′ sceglie in ogni stato l’azione con il Q^π(s, a) più grande, allora V^π′(s) ≥ V^π(s) in tutti gli stati. Se π′ non differisce da π, V^π soddisfa l’equazione di ottimalità di Bellman, e π è quindi ottima.

Schizzo di dimostrazione. Per la scelta di π′ vale V^π(s) = Q^π(s, π(s)) ≤ Q^π(s, π′(s)) = E[r + γ V^π(s′)]. In V^π(s′) sostituiamo la stessa disuguaglianza, poi di nuovo… Dopo lo sviluppo resta il ritorno atteso della politica che gioca π′ in tutti i passi, cioè V^π′(s). ∎

Le politiche deterministiche sono in numero finito — da noi 4 azioni in 19 caselle non terminali, cioè 4¹⁹ ≈ 2,7 · 10¹¹. Nessuna può ripetersi (ogni giro migliora il valore oppure termina), quindi l’iterazione delle politiche termina sempre. In realtà bastano sorprendentemente pochi giri: da noi 6.

Sul pavimento scivoloso con γ = 0,9, partendo dalla politica «su ovunque»:

Dopo 6 giri la politica è la stessa dell’iterazione dei valori. I giri sono pochi, ma ognuno contiene una valutazione completa (da noi da decine a centinaia di passate sul mondo). Quale dei due metodi sia più veloce dipende dal problema; in pratica si combinano.

7. Quando non conosciamo le regole del mondo

Tutto quanto sopra presuppone che conosciamo P e R — che possiamo «guardare nelle regole». Questa è pianificazione (programmazione dinamica). Nel vero apprendimento per rinforzo l’agente è gettato in un mondo di cui non conosce le regole: deve provare, raccogliere esperienza e stimare i valori a partire da essa. L’equazione di Bellman però resta il cuore di quasi tutti i metodi — solo che al posto della media esatta su P si usa un campione da un singolo passo reale. Questo è il Q-learning, tema della prossima parte.

Lo stesso schema descrive un robot che impara a camminare, la gestione delle scorte in un magazzino, un sistema di raccomandazione e anche un modello linguistico addestrato sulle preferenze umane nella parte sull’RLHF — lì lo stato è il testo scritto finora, l’azione il token successivo e la ricompensa la valutazione della risposta.

8. Riepilogo

• MDP = stati, azioni, transizioni casuali, ricompense e sconto; lo stato successivo dipende solo dallo stato attuale e dall’azione.
• Il valore di uno stato è il ritorno scontato atteso; i valori ottimi soddisfano l’equazione di Bellman.
• L’iterazione dei valori ripete l’equazione di Bellman; l’errore cala almeno come γ^k (da noi 50 iterazioni per γ = 0,9).
• Lo scivolamento sposta il percorso lontano dal dirupo (caduta nel 0,7 % invece che nel 30 %), un γ piccolo porta al piccolo traguardo vicino, un costo per passo porta a rischiare.
• L’iterazione delle politiche alterna valutazione e miglioramento; da noi 6 giri.
• Senza conoscere le regole del mondo, i valori vanno imparati dall’esperienza — questo è l’apprendimento per rinforzo.

Vuoi provarlo con mano? Fai programmare a un agente IA questo mondo con il dirupo, con la possibilità di cambiare in modo interattivo γ, lo scivolamento e il costo del passo — e osserva quando la politica «scatta» da un percorso a un altro.

La vedi diversamente? Scrivi a support@coden-app.com.