Markov Decision Process (MDP)

Un processo decisionale di Markov (MDP) è il modello matematico di un problema decisionale sequenziale: un agente osserva uno stato, sceglie un'azione, riceve una ricompensa e passa a uno stato successivo, determinato in parte dalla sua scelta e in parte dal caso. Formalmente, un MDP è composto da un insieme di stati, un insieme di azioni, probabilità di transizione P(s′ | s, a), una funzione di ricompensa R(s, a) e, di solito, un fattore di sconto γ compreso tra 0 e 1. Risolverlo significa trovare una politica, cioè una regola che sceglie un'azione in ogni stato, che massimizzi la somma attesa scontata delle ricompense future. Gli MDP nacquero dalla ricerca operativa degli anni Cinquanta, quando la programmazione dinamica di Richard Bellman fornì i metodi per risolverli; sono la formulazione standard dei problemi di apprendimento per rinforzo (RL).

La proprietà di Markov#

L'assunzione fondamentale è la proprietà di Markov: lo stato successivo e la ricompensa dipendono solo dallo stato e dall'azione correnti, non dal percorso che ha condotto fin lì. Di conseguenza, lo stato è una rappresentazione completa di tutto ciò che è rilevante per l'agente. Un singolo fotogramma della videocamera non soddisfa questa assunzione per un oggetto in movimento, perché ne mostra la posizione ma non la velocità; per questo, il DQN di DeepMind che giocava ad Atari riceveva in input gli ultimi quattro fotogrammi sovrapposti, così da poter rilevare il movimento.

Quando l'agente non può osservare lo stato completo, come nel caso di un robot con sensori rumorosi o ostruiti, il problema è un MDP parzialmente osservabile (POMDP). L'agente agisce quindi sulla base di una stima dello stato, mantenuta con un filtro o una rete ricorrente, anziché sullo stato stesso.

Componenti di un MDP#

• Stati: le situazioni in cui può trovarsi l'agente, come gli angoli delle articolazioni di un robot e la posizione dell'oggetto che sta cercando di raggiungere.
• Azioni: le scelte disponibili in ciascuno stato. Lo spazio delle azioni può essere discreto (svoltare a sinistra, svoltare a destra) o continuo (un angolo di sterzata espresso in gradi).
• Probabilità di transizione: la probabilità di ciascuno stato successivo dopo un'azione; tiene conto dello slittamento delle ruote, degli altri conducenti e di ogni altra fonte di casualità.
• Ricompense: il feedback numerico immediato per una transizione. La scelta delle ricompense definisce l'attività e una progettazione superficiale può favorire il reward hacking.
• Fattore di sconto: quanto contano le ricompense future rispetto a quelle immediate. Con γ = 0.9, una ricompensa a dieci passi di distanza vale 0.9¹⁰ ≈ 0.35 rispetto alla stessa ricompensa ricevuta ora.

A ogni passo temporale si ripete la stessa interazione fino alla fine dell'episodio:

Risolvere un MDP#

Il valore di uno stato è il ritorno atteso a partire da quello stato seguendo una politica; i valori ottimali soddisfano l'equazione di Bellman: il valore di ogni stato equivale alla ricompensa immediata dell'azione migliore più il valore scontato e ponderato per probabilità degli stati raggiunti. Quando le probabilità di transizione e le ricompense sono note, la programmazione dinamica risolve direttamente l'equazione. L'iterazione del valore (Bellman, 1957) la applica ripetutamente finché i valori non smettono di cambiare; l'iterazione della politica (Howard, 1960) alterna la valutazione di una politica al suo miglioramento.

Questo esempio NumPy esegue l'iterazione del valore sul robot riciclatore descritto in Reinforcement Learning: An Introduction di Sutton e Barto: il robot deve scegliere se cercare lattine, aspettare o ricaricarsi, con batteria carica o scarica:

import numpy as np

# MDP del robot riciclatore: stati 0 = batteria carica, 1 = batteria scarica; azioni 0 = cerca, 1 = aspetta, 2 = ricarica
gamma = 0.9  # fattore di sconto
P = np.zeros((2, 3, 2))  # P[s, a, s'] = probabilità di raggiungere s' dopo aver eseguito a in s
P[0, 0] = [0.7, 0.3]  # cercare con la batteria carica può scaricarla fino al livello basso
P[1, 0] = [0.4, 0.6]  # cercare con la batteria scarica può esaurirla (il robot viene soccorso e ricaricato)
P[:, 1] = np.eye(2)  # aspettare mantiene invariato il livello della batteria
P[:, 2] = [1.0, 0.0]  # ricaricare ripristina sempre la batteria carica
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # R[s, a] atteso; ricerca con batteria scarica: 0.6 * 2 + 0.4 * -3 = 0

# Iterazione del valore: applica l'aggiornamento di ottimalità di Bellman finché i valori non smettono di cambiare
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # valore di ciascuna azione in ogni stato
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

Stampa valori pari a 15.75 per la batteria carica e 14.17 per quella scarica, nonché una politica che cerca con la batteria carica e ricarica con quella scarica: il rischio del 40% di una penalità di −3 per il soccorso rende meno conveniente cercare con la batteria scarica che ricaricarla.

Quando le probabilità di transizione non sono note, l'apprendimento per rinforzo stima gli stessi valori dall'esperienza. Q-learning aggiorna i valori delle azioni sulla base di transizioni campionate, i metodi del gradiente della politica modificano direttamente una politica e il deep reinforcement learning usa reti neurali quando lo spazio degli stati è troppo ampio per essere elencato. Gli algoritmi di pianificazione, come la ricerca ad albero Monte Carlo, risolvono online MDP di grandi dimensioni simulando solo i futuri raggiungibili dallo stato corrente.

MDP e modelli correlati#

• Catena di Markov: una sequenza di stati casuali senza azioni o ricompense. Un MDP aggiunge le scelte e l'obiettivo.
• Modello di Markov nascosto (HMM): una catena di Markov i cui stati sono osservabili solo attraverso segnali rumorosi. Un POMDP ha lo stesso rapporto con un MDP.
• Bandito multi-braccio: un MDP con un solo stato, in cui il risultato di ogni azione è indipendente dal passato.
• Apprendimento per rinforzo: la famiglia di metodi che apprende a comportarsi efficacemente in un MDP attraverso l'interazione, senza ricevere le probabilità di transizione.

Applicazioni#

• Robotica e controllo: afferrare, camminare e navigare vengono formulati come MDP e le relative politiche sono spesso addestrate in simulazione. Nel controllo basato su videocamera, un rilevatore come Ultralytics YOLO26 può fornire lo stato, trasformando ogni fotogramma in un breve elenco di classi di oggetti e coordinate dei riquadri, un input molto più compatto dei pixel grezzi per la politica.
• Addestramento dei modelli linguistici: RLHF e RLVR trattano la generazione di testo come un MDP in cui lo stato è composto dal prompt e dai token generati fino a quel momento, l'azione è il token successivo e la ricompensa viene assegnata al completamento della risposta.
• Ricerca operativa: il riordino delle scorte, la manutenzione delle apparecchiature e la tariffazione dinamica sono problemi classici formulabili come MDP; Ronald Howard sviluppò l'iterazione della politica mentre ottimizzava gli invii del catalogo Sears.