Processo decisionale di Markov

Un processo decisionale di Markov (MDP, Markov decision process) è un modello matematico per decisioni sequenziali in presenza di incertezza. Estende le catene di Markov introducendo azioni e ricompense.

Un MDP è descritto da:

(\mathcal{S},\mathcal{A},P,r,\gamma),

dove $\mathcal{S}$ è lo spazio degli stati, $\mathcal{A}$ l’insieme delle azioni, $P$ la probabilità di transizione, $r$ la ricompensa e $\gamma$ un eventuale fattore di sconto.

In una versione a costi, invece di ricompense $r$ si usano costi $c$ da minimizzare. Le due formulazioni sono equivalenti se si cambia segno:

r(s,a)=-c(s,a).

Proprietà di Markov

La proprietà centrale è:

\mathbb{P}(S_{t+1}=s'\mid S_t=s,A_t=a,\text{storia}) = \mathbb{P}(S_{t+1}=s'\mid S_t=s,A_t=a).

Dato lo stato corrente e l’azione scelta, la distribuzione dello stato successivo non dipende dalla storia precedente. Questo rende possibile usare una funzione valore che dipende dallo stato, non dall’intera sequenza passata.

Questa condizione non significa che il passato sia irrilevante in senso fisico. Significa che il passato rilevante è già riassunto nello stato. Se lo stato non contiene informazione sufficiente, il modello non è davvero markoviano.

Politica

Una politica specifica quale azione scegliere in ogni stato. Può essere deterministica:

a=\pi(s),

oppure stocastica:

\pi(a\mid s)=\mathbb{P}(A_t=a\mid S_t=s).

L’obiettivo è trovare una politica che massimizzi la ricompensa attesa cumulata o minimizzi un costo atteso.

Una politica può essere stazionaria, se non dipende dal tempo, oppure non stazionaria, se cambia con lo stadio decisionale. Nei problemi a orizzonte finito è normale usare politiche dipendenti da $t$ ; negli orizzonti infiniti si cerca spesso una politica stazionaria ottima.

Ricompensa cumulata

Con fattore di sconto $\gamma$ , il ritorno atteso da uno stato iniziale è:

G_0= \sum_{t=0}^{+\infty}\gamma^t r(S_t,A_t).

Se $0\le\gamma\lt1$ , le ricompense lontane pesano meno. Questo può rappresentare preferenza temporale, incertezza sul futuro o una scelta matematica per garantire convergenza.

Se l’orizzonte è finito, si usa invece:

G_0= \sum_{t=0}^{T-1} r_t(S_t,A_t)+g(S_T).

$g(S_T)$ è il valore terminale.

Equazione di Bellman

Per una politica fissata, il valore di uno stato è:

V^\pi(s)= \mathbb{E}_\pi \left[ \sum_{t=0}^{+\infty}\gamma^t r(S_t,A_t) \mid S_0=s \right].

Il valore ottimo soddisfa una forma dell’equazione di Bellman:

V^\ast(s)= \max_{a\in\mathcal{A}} \left\{ r(s,a)+ \gamma\sum_{s'}P(s'\mid s,a)V^\ast(s') \right\}.

La politica ottima associata sceglie un’azione che realizza il massimo:

\pi^\ast(s)\in \arg\max_{a\in\mathcal{A}} \left\{ r(s,a)+ \gamma\sum_{s'}P(s'\mid s,a)V^\ast(s') \right\}.

Questa separazione tra valore e politica è alla base di molti algoritmi.

Algoritmi classici

Per MDP finiti e noti si usano:

Metodo	Idea
iterazione sui valori	aggiorna ripetutamente la funzione valore
iterazione sulle politiche	alterna valutazione e miglioramento della politica
programmazione dinamica all’indietro	usa un orizzonte finito e una condizione terminale

Se il modello di transizione non è noto, si entra nell’ambito dell’apprendimento per rinforzo: l’agente deve stimare valore o politica interagendo con l’ambiente.

Applicazioni

Gli MDP compaiono in controllo, robotica, manutenzione, gestione di scorte, instradamento, pricing dinamico, apprendimento per rinforzo e decisioni operative con incertezza.

In programmazione dinamica si risolvono MDP piccoli o strutturati tramite iterazione sui valori, iterazione sulle politiche o ricorrenze a orizzonte finito. Per spazi di stato grandi, la maledizione della dimensionalità rende necessari metodi approssimati.

Un esempio gestionale è la manutenzione: lo stato descrive il livello di degrado di una macchina, le azioni sono continuare, ispezionare o sostituire, le transizioni descrivono l’evoluzione probabilistica del guasto e la ricompensa include costi di fermo e manutenzione.

Un esempio di robotica è la navigazione: lo stato descrive posizione e configurazione, le azioni sono comandi, le transizioni includono rumore di movimento e la ricompensa penalizza collisioni e distanza dall’obiettivo.

Osservabilità

Un MDP assume che lo stato sia osservabile. Se l’agente non osserva direttamente lo stato vero, ma solo segnali parziali o rumorosi, serve un modello più ricco: il processo decisionale di Markov parzialmente osservabile. In pratica, si costruisce uno stato di credenza che riassume la distribuzione possibile degli stati reali.

Errori comuni

Un errore frequente è chiamare MDP qualunque processo sequenziale. Serve la proprietà di Markov: lo stato deve riassumere tutte le informazioni rilevanti per il futuro.

Un secondo errore è confondere transizione e politica. La transizione descrive come risponde l’ambiente; la politica descrive come decide l’agente.

Un terzo errore è ignorare la dimensione dello stato. Un MDP formalmente corretto può essere troppo grande per essere risolto esattamente; in quel caso occorrono approssimazioni, decomposizioni o simulazione.

Differenza da una catena di Markov

In una catena di Markov le transizioni sono date. In un MDP, invece, le transizioni dipendono dall’azione:

P(s'\mid s,a).

Questo cambia il problema: non si tratta solo di prevedere l’evoluzione del sistema, ma di scegliere azioni che modificano quell’evoluzione. La catena descrive un processo; l’MDP descrive un processo controllabile.

Modello noto e modello appreso

Se $P$ e $r$ sono noti, si parla di soluzione basata sul modello. Se invece il decisore deve imparare transizioni e ricompense dall’esperienza, si entra nel campo model-free o model-based dell’apprendimento per rinforzo.

La distinzione è operativa: con modello noto si può pianificare prima di agire; con modello ignoto bisogna bilanciare esplorazione e sfruttamento.