Processo decisionale di Markov

I processi decisionali di Markov (MDP), dal nome del matematico Andrej Andreevič Markov (1856-1922), forniscono un framework matematico per la modellizzazione del processo decisionale in situazioni in cui i risultati sono in parte casuali e in parte sotto il controllo di un decisore. Gli MDP sono utili per lo studio di una vasta gamma di problemi di ottimizzazione, risolti con la programmazione dinamica e l'apprendimento per rinforzo. Gli MDP sono noti fin dal 1950. Essi sono utilizzati in una vasta area di discipline in cui il processo di presa di decisione avviene in un intorno dinamico, tra cui la robotica, l'automazione, l'economia, e la produzione industriale.

Più precisamente, un processo decisionale di Markov è un processo di controllo stocastico a tempo discreto. Se gli spazi degli stati e delle azioni sono finiti, allora il problema è chiamato MDP finito. Gli MDP finiti sono particolarmente importanti per la teoria dell'apprendimento per rinforzo (reinforcement learning).

Definizione

Un MDP finito è definito da:

• uno spazio degli stati $S$;
• uno spazio delle azioni $A=U_{s}\in _{s}A(s)$ che possono essere intraprese in funzione dello stato;
• le probabilità di transizione $P_{a}(s,s'):S\times A\times S\mapsto \mathbb {R}$ definiscono le dinamiche one-step dell'ambiente, ovvero, la probabilità che, dato uno stato $s$ e un'azione $a$al tempo $t$, si raggiunga il possibile stato successivo $s'$: $P_{a}(s,s')=\Pr(s_{t+1}=s'\mid s_{t}=s,a_{t}=a)$;
• il valore atteso della ricompensa $R_{a}(s,s')$: dato uno stato $s$ e un'azione $a$, se si passa allo stato $s'$ si ottiene una ricompensa pari a ($E$ rappresenta il valore atteso o previsione) $R_{a}(s,s')=R(s'|s,a)=E(r_{t+1}\mid s_{t}=s,a_{t}=a,s_{t+1}=s')$;
• $\gamma \in [0,1]$ è il fattore di sconto (discount) che rappresenta l'importante differenza tra le ricompense future (future rewards) e le ricompense presenti (present rewards).

(Nota: la teoria del processo decisionale di Markov non specifica che $S$ o $A$ sono finiti, ma i precedenti algoritmi di base assumono che lo siano.)

Problema

Il problema centrale di un MDP è quello di identificare quale sia la migliore azione da eseguire in un dato stato, in modo da ottenere il massimo valore possibile di una funzione cumulativa della ricompensa. La funzione che per ogni stato $s\in S$ identifica l'azione $a\in A$ da applicare è chiamata "politica" (policy) stazionaria $\pi =S\mapsto A$. Tipicamente questa funzione che valuta la ricompensa è il valore atteso di una somma con sconto su un orizzonte potenzialmente infinito:

$\sum _{t=0}^{\infty }{\gamma ^{t}R_{a_{t}}(s_{t},s_{t+1})}$ dove $a_{t}=\pi (s_{t})$ sono le azioni date dalla politica ${\textstyle \pi }$, $\gamma$ è il fattore di sconto compreso fra 0 e 1.

Per via della proprietà di Markov, la politica ottimale $\pi ^{*}$ che massimizza la ricompensa con sconto attesa, per questo problema può essere scritta come una funzione del solo stato ${\textstyle s}$. Per ottenere una politica ottimale in tempo polinomiale per un MDP dato, spesso si usano algoritmi di programmazione lineare o, più tradizionalmente, di programmazione dinamica.

Algoritmi

La famiglia standard di algoritmi che calcola questa politica ottimale fa uso di due vettori, indicizzati con lo stato, che si chiamano: "valore" $V$, che contiene valori reali, e "politica"' $\pi$, che contiene le azioni. Quando l'algoritmo termina, $\pi$ contiene la politica soluzione e $V(s)$ contiene la somma con sconto delle ricompense da ottenere (in media) seguendo la soluzione $\pi (s)$ a partire dallo stato $s$.

L'algoritmo prevede due tipi di passo: un aggiornamento del valore e un aggiornamento della politica, i quali sono ripetuti in tutti gli stati e in un certo ordine, fintanto che non avvengano più cambiamenti ai valori. I due aggiornamenti, ricalcolano ricorsivamente un nuovo valore stimato per la politica ottimale e per il valore dello stato, usando una stima precedente di questi valori.

$\pi (s):={\arg \max }_{a}\left\{\sum _{s'}P_{a}(s,s')\left(R_{a}(s,s')+\gamma V(s')\right)\right\}$

$V(s):=\sum _{s'}P_{\pi (s)}(s,s')\left(R_{\pi (s)}(s,s')+\gamma V(s')\right)$

L'ordine degli aggiornamenti dipende dalla variante dell'algoritmo. Si possono applicare su tutti gli stati assieme, o stato per stato, sequenzialmente, o anche più spesso per certi stati che per altri. Fintanto che nessuno stato viene escluso dai passi di aggiornamento, l'algoritmo eventualmente convergerà verso una soluzione .

Bibliografia

• Ronald A. Howard, Dynamic Programming and Markov Processes, The M.I.T. Press, 1960.

Voci correlate

• Andrej Andreevič Markov (1856-1922)