Esercizio - MDP con value iteration, policy iteration e Q-learning (laboratorio 9)

Teoria: Processi decisionali di Markov - utilità, equazione di Bellman, value e policy iterationUn MDP (processo decisionale di Markov) modella un problema decisionale sequenziale in ambiente stocastico e completamente osservabile con stati S, azioni A(s), modello di transizione P(s'|s,a) e ricompensa R(s,a,s'). La soluzione è una politica pi(s). L'utilità U(s) è il ritorno scontato atteso e soddisfa l'equazione di Bellman U(s)=max_a sum_s' P(s'|s,a)[R(s,a,s')+gamma U(s')]; la quantità tra parentesi quadre sommata su s' è la funzione azione-utilità Q(s,a). Value iteration parte da U=0, applica Bellman a tutti gli stati insieme e si ferma quando delta <= eps(1-gamma)/gamma; la politica è argmax_a Q(s,a). Policy iteration alterna valutazione (sistema lineare, senza max) e miglioramento greedy, e termina quando la politica non cambia. Nei POMDP lo stato è nascosto: si lavora sullo stato di credenza b aggiornato come nel filtraggio, b'(s')=alpha P(e|s') sum_s P(s'|s,a)b(s).Processi decisionali di Markov - utilità, equazione di Bellman, value e policy iteration →. Il laboratorio usa la libreria pymdptoolbox (pip install pymdptoolbox), che descrive un MDP con due array:

• P di forma (A, S, S): P[a, s, s'] è la probabilità di passare da s a s' con l'azione a;
• R di forma (S, A): R[s, a] è la ricompensa per eseguire a in s (qui è un costo dell'azione).

mdptoolbox.util.check(P, R) controlla che gli array siano coerenti (tace se va tutto bene). Gli algoritmi sono mdp.ValueIteration(P, R, sconto), mdp.PolicyIteration(...), mdp.QLearning(...); dopo run() si leggono V (utilità), policy (azione per stato), iter e time.

Esempio guida: la corsia a quattro stati

Testo. Quattro stati $0,1,2,3$ in fila, da sinistra a destra. Due azioni: $0$ = "Stay" (resta fermo, riesce sempre), $1$ = "Right" (sposta a destra con probabilità $0{,}8$, resta fermo con probabilità $0{,}2$). Lo stato $3$ è assorbente (ci si resta con probabilità $1$). Lo stato $3$ ha ricompensa $1$, qualsiasi azione negli altri stati costa $-0{,}04$. Sconto $0{,}9$. Trovare utilità e politica con value iteration e con policy iteration.

Costruzione degli array. La prima matrice $4\times4$ è "Stay" (l'identità), la seconda "Right":

import numpy as np
import mdptoolbox as mt        # pip install pymdptoolbox (non installato qui: il codice e' quello del corso)

P1 = np.array([[[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]],            # Stay
               [[.2, .8, 0, 0], [0, .2, .8, 0], [0, 0, .2, .8], [0, 0, 0, 1]]])      # Right
R1 = np.array([[-.04, -.04], [-.04, -.04], [-.04, -.04], [1, 1]])                   # R[s, a]
mt.util.check(P1, R1)

vi1 = mt.mdp.ValueIteration(P1, R1, 0.9); vi1.run()
print(vi1.V, vi1.policy)
pi1 = mt.mdp.PolicyIteration(P1, R1, 0.9); pi1.run()
print(pi1.V, pi1.policy)

Output riportato dal corso:

(2.766226988084275, 3.7438891127976524, 4.857502678650809, 6.12579511)   (1, 1, 1, 0)
(6.6402692938291725, 7.6180844735276665, 8.731707317073173, 10.000000000000002)   (1, 1, 1, 0)

Il corso commenta: "i due metodi non concordano sui valori, ma concordano sulla politica" (Right in $0,1,2$, poi Stay). Perché i valori sono diversi? Lo si capisce rifacendo i calcoli.

Value iteration a mano ($U_0=0$, sconto $0{,}9$; $U_{k+1}(s)=\max_a\big[R(s,a)+0{,}9\sum_{s'}P(s'\mid s,a)U_k(s')\big]$):

• iterazione 1: con $U_0=0$ vale solo la ricompensa: $U_1=(-0{,}04,\,-0{,}04,\,-0{,}04,\,1)$;
• iterazione 2: stato 3: $1+0{,}9\cdot1=1{,}9$. Stato 2, Right: $-0{,}04+0{,}9\,(0{,}2\cdot(-0{,}04)+0{,}8\cdot1)=-0{,}04+0{,}9\cdot0{,}792=0{,}6728$; Stay: $-0{,}04+0{,}9\cdot(-0{,}04)=-0{,}076$. Stati 0 e 1: Stay e Right valgono entrambi $-0{,}076$. Quindi $U_2=(-0{,}076,\,-0{,}076,\,0{,}6728,\,1{,}9)$;
• iterazione 3: stato 2, Right: $-0{,}04+0{,}9(0{,}2\cdot0{,}6728+0{,}8\cdot1{,}9)=1{,}4491$; stato 1, Right: $-0{,}04+0{,}9(0{,}2\cdot(-0{,}076)+0{,}8\cdot0{,}6728)=0{,}4307$; stato 3: $1+0{,}9\cdot1{,}9=2{,}71$.

Lo stato 3 è assorbente con ricompensa $1$ a ogni passo: $U_n(3)=\sum_{k=0}^{n-1}0{,}9^k=10\,(1-0{,}9^n)$, che tende a $10=\tfrac1{1-0{,}9}$ solo lentamente.

Il criterio di arresto della libreria. ValueIteration si ferma quando la variazione scende sotto $\varepsilon(1-\gamma)/\gamma=0{,}01\cdot0{,}1/0{,}9=0{,}00111$, ma misura la variazione con lo span (massimo meno minimo) del vettore $U_{k+1}-U_k$, non con il massimo. Dopo 9 iterazioni le differenze $U_{k+1}-U_k$ valgono quasi lo stesso numero in tutti gli stati (tutti crescono insieme, per $\gamma^k$), quindi lo span è piccolo anche se i valori sono ancora lontani da quelli esatti: è garantita l'ottimalità della politica, non l'accuratezza dei valori. Ripetendo i calcoli con NumPy si ritrova il vettore del corso, e dopo 9 iterazioni: $(2{,}7662,\,3{,}7439,\,4{,}8575,\,6{,}1258)$. Tutte e quattro le utilità sono inferiori di circa $3{,}874$ rispetto alla policy iteration, come se mancasse una costante. Con il criterio del testo (massimo delle differenze, soglia $0{,}00111$) servono 66 iterazioni e si ottiene $(6{,}631,\,7{,}609,\,8{,}722,\,9{,}990)$, vicino ai valori esatti.

Policy iteration a mano. Parte dalla politica "Stay ovunque".

1. Valutazione: negli stati $0,1,2$ si resta fermi a costo $-0{,}04$ per sempre: $U=\dfrac{-0{,}04}{1-0{,}9}=-0{,}4$; nello stato 3 $U=\dfrac1{0{,}1}=10$. Miglioramento: in $2$, $Q(2,\text{Right})=-0{,}04+0{,}9(0{,}2\cdot(-0{,}4)+0{,}8\cdot10)=7{,}088>-0{,}4$: si passa a Right. In $0$ e $1$ Right e Stay sono pari ($-0{,}4$): si resta.
2. Valutazione con $\pi=(S,S,R,S)$: $U(2)=-0{,}04+0{,}9(0{,}2\,U(2)+0{,}8\cdot10)$, cioè $0{,}82\,U(2)=7{,}16$, $U(2)=8{,}7317$. Miglioramento: $Q(1,\text{Right})=-0{,}04+0{,}9(0{,}2\cdot(-0{,}4)+0{,}8\cdot8{,}7317)=6{,}1748>-0{,}4$: stato 1 passa a Right.
3. Valutazione con $\pi=(S,R,R,S)$: $0{,}82\,U(1)=-0{,}04+0{,}9\cdot0{,}8\cdot8{,}7317$, $U(1)=7{,}6181$. Miglioramento: $Q(0,\text{Right})=-0{,}04+0{,}9(0{,}2\cdot(-0{,}4)+0{,}8\cdot7{,}6181)=5{,}373>-0{,}4$.
4. Valutazione con $\pi=(R,R,R,S)$: $0{,}82\,U(0)=-0{,}04+0{,}9\cdot0{,}8\cdot7{,}6181$, $U(0)=6{,}6403$. Nessun cambio: fine.

Risultato: $U=(6{,}6403,\;7{,}6181,\;8{,}7317,\;10)$, coincidente con l'output del corso. Il valore di $U(3)=10$ è esatto perché la policy iteration risolve un sistema lineare, senza errori di arresto.

Esercizio 1 del laboratorio: cosa fare all'aeroporto

Vedi Esercizio - Utilità attesa, maximax e maximin (laboratorio 9).

Esercizio 2: risolvere un MDP con mdptoolbox

Testo. Quattro stati e quattro azioni. Le azioni sono: $0$ = Destra, $1$ = Sinistra, $2$ = Su, $3$ = Giù. Gli stati $0,1,2,3$ sono disposti così: $$\begin{array}{cc}2&3\\0&1\end{array}$$ Il modello di moto prevede probabilità $0{,}8$ di muoversi nella direzione dell'azione e $0{,}1$ in ciascuna delle due direzioni perpendicolari. Quindi $2$ è sopra $0$, $1$ è a destra di $0$, e così via. Il costo di ogni azione (in ogni stato) è $-0{,}04$. Nel caso di movimenti "non fattibili" (contro il bordo) l'agente resta nello stato corrente con probabilità $0{,}8+0{,}1$; si considerano comunque le direzioni perpendicolari. La ricompensa dello stato $3$ è $1$, quella dello stato $1$ è $-1$, e l'agente non lascia quegli stati. Sconto $0{,}99$.

(a) Qual è la politica secondo value iteration? (b) Secondo policy iteration? (c) Secondo il Q-learning? (d) Usare setVerbose() e l'attributo time degli oggetti MDP per confrontare il numero di iterazioni (attributo iter) e il tempo di CPU di value iteration e policy iteration.

Soluzione.

Costruzione di $P$. Per ogni azione, una matrice $4\times4$. Esempio, azione Destra (prima matrice del codice):

• stato 0: a destra c'è lo stato 1 (probabilità $0{,}8$); le direzioni perpendicolari sono Su (stato 2, $0{,}1$) e Giù (il bordo, quindi resta in 0, $0{,}1$). Riga: $(0{,}1,\ 0{,}8,\ 0{,}1,\ 0)$;
• stato 2: a destra c'è lo stato 3 ($0{,}8$); Su è il bordo (resta in 2, $0{,}1$), Giù porta in 0 ($0{,}1$). Riga: $(0{,}1,\ 0,\ 0{,}1,\ 0{,}8)$;
• stati 1 e 3: assorbenti, righe $(0,1,0,0)$ e $(0,0,0,1)$.

Le altre azioni si costruiscono nello stesso modo. Per Sinistra, nello stato 0 "a sinistra" è il bordo: resta in 0 con $0{,}8+0{,}1$ e va in 2 con $0{,}1$ (riga $(0{,}9,0,0{,}1,0)$).

Ricompense. $R[s,a]$: $-0{,}04$ in $0$ e $2$, $-1$ in $1$ (ogni azione), $+1$ in $3$.

transitions = np.array([
    [[0.1, 0.8, 0.1, 0], [0, 1, 0, 0], [0.1, 0, 0.1, 0.8], [0, 0, 0, 1]],   # 0 Destra
    [[0.9, 0, 0.1, 0],   [0, 1, 0, 0], [0.1, 0, 0.9, 0],   [0, 0, 0, 1]],   # 1 Sinistra
    [[0.1, 0.1, 0.8, 0], [0, 1, 0, 0], [0, 0, 0.9, 0.1],   [0, 0, 0, 1]],   # 2 Su
    [[0.9, 0.1, 0, 0],   [0, 1, 0, 0], [0.8, 0, 0.1, 0.1], [0, 0, 0, 1]]])  # 3 Giu
rewards = np.array([[-0.04] * 4, [-1] * 4, [-0.04] * 4, [1] * 4])
discount_factor = 0.99

vi = mt.mdp.ValueIteration(transitions, rewards, discount_factor); vi.run()
pi = mt.mdp.PolicyIteration(transitions, rewards, discount_factor); pi.run()
ql = mt.mdp.QLearning(transitions, rewards, discount_factor); ql.run()
print("VI:", vi.policy, vi.iter, vi.time)
print("PI:", pi.policy, pi.iter, pi.time)
print("QL:", ql.policy)

Output del corso:

Value Iteration policy: (1, 0, 0, 0)    iterazioni: 985    CPU time: 0.0384
Policy Iteration policy: (1, 0, 0, 0)   iterazioni: 3      CPU time: 0.0188
Q-Learning policy: (2, 3, 0, 0)

(a), (b) La politica è $(1,0,0,0)$: nello stato 0 Sinistra, nello stato 2 Destra (negli stati 1 e 3 l'azione è irrilevante, sono assorbenti). Il caso di Sinistra è il punto interessante: andare a Sinistra dallo stato 0 sembra insensato (a sinistra c'è il bordo), ma serve proprio a non muoversi senza rischi. Con le utilità ottime $U=(88{,}24,\,-100,\,97{,}55,\,100)$ le $Q(0,\cdot)$ sono:

Da $0$ l'unica uscita sicura è passare per $2$; Su ci arriva con probabilità $0{,}8$ ma con $0{,}1$ finisce nel $-1$ (per la deviazione verso destra), mentre Sinistra aspetta nello stato 0 e con probabilità $0{,}1$ scivola in $2$, senza mai rischiare lo stato 1. Nello stato $2$ l'azione migliore è Destra ($97{,}55$, contro Su $96{,}78$, Sinistra $95{,}62$, Giù $89{,}40$). Le utilità sono molto più grandi di 1 perché lo stato $3$ paga $1$ a ogni passo per sempre: $\tfrac1{1-0{,}99}=100$.

(c) Il Q-learning della libreria dà $(2,3,0,0)$: in $2$ l'azione 0 (Destra) è giusta, ma in $0$ sceglie Su. Valutando la politica Su-in-0, Destra-in-2 si ottiene $U(0)=73{,}27$ contro $88{,}24$ della politica ottima: è sbagliata. È un algoritmo che apprende con un numero fisso di campioni ($10\,000$ passi di default), insufficienti con $\gamma=0{,}99$ e due stati assorbenti, quindi il risultato cambia da una esecuzione all'altra. Lo stato 1 e lo stato 3 mostrano azioni (3 e 0) senza senso: sono assorbenti e ogni azione vale lo stesso.

(d) Numero di iterazioni e tempo. Value iteration: 985 iterazioni, $0{,}038$ s. Policy iteration: 3 iterazioni, $0{,}019$ s. Ciascuna iterazione di policy iteration è più costosa (risolve un sistema lineare $4\times4$) ma ne servono molte meno: è proprio il confronto della teoria. Per $\gamma$ vicino a 1 value iteration ha bisogno di molte iterazioni, dato che l'errore decresce come $\gamma^k$ (con $0{,}99$ servono centinaia di passi). Ricalcolando con un'implementazione in NumPy dello stesso criterio di arresto della libreria si ottengono 986 iterazioni (il corso riporta 985: differenza di conteggio di uno), politica $(1,0,0,0)$ e utilità $(88{,}23,\,-99{,}995,\,97{,}55,\,99{,}995)$ per value iteration; $(88{,}236,\,-100,\,97{,}553,\,100)$ per policy iteration (politica identica in 3 iterazioni).