Esercizio - Policy iteration sul mondo 4x3 (slide del corso)

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 →, sezione 7. Il mondo è lo stesso di Esercizio - Value iteration sul mondo 4x3 (slide del corso) (muro in $(2,2)$, terminali $(4,3)$ con $+1$ e $(4,2)$ con $-1$, $r=-0{,}04$, azione voluta con $0{,}8$ e laterali $0{,}1+0{,}1$, urto = si resta, $\gamma=1$): le funzioni costruisci_mdp, stampa, STATI, IDX, NOMI, TERMINALI si riusano tali e quali.

Testo (dalle slide). Si consideri la politica $\pi_i$ delle slide: $\pi_i(1,1)=\text{Su}$, $\pi_i(1,2)=\text{Su}$, $\pi_i(1,3)=\text{Destra}$, e così via (riga 3 tutta Destra, colonna 1 Su, Su in $(3,2)$; per le celle in basso l'immagine delle slide non è leggibile con certezza e si sceglie $(2,1)$ Sinistra, $(3,1)$ Su, $(4,1)$ Sinistra).

(a) Scrivere e risolvere le equazioni di valutazione. (b) Eseguire il passo di miglioramento. (c) Iterare fino alla politica stabile e confrontarla con value iteration. (d) Partendo da "Su ovunque", in quante iterazioni converge?

Soluzione

(a) Valutazione

Con l'azione fissa $\pi_i(s)$ il $\max$ sparisce e le 9 equazioni sono lineari. Si indicano $a=U(1,1)$, $b=U(2,1)$, $c=U(3,1)$, $d=U(4,1)$, $e=U(1,2)$, $f=U(3,2)$, $g=U(1,3)$, $h=U(2,3)$, $i=U(3,3)$, con $r=-0{,}04$ e $\gamma=1$. Per ogni cella, 0,8 per la direzione voluta e 0,1 per ciascuna perpendicolare (un esito contro il muro o il bordo ricade nella stessa cella):

(Le equazioni di $(1,1)$, $(1,2)$ e $(1,3)$ coincidono con quelle mostrate nelle slide.) Sistema $9\times9$, risolto con np.linalg.solve:

$$a=0{,}7453,\ b=0{,}6953,\ c=0{,}6307,\ d=0{,}4095,\ e=0{,}8016,\ f=0{,}7003,\ g=0{,}8516,\ h=0{,}9078,\ i=0{,}9578.$$

Verifica di una equazione, quella di $c$: $0{,}8(-0{,}04+0{,}7003)+0{,}1(-0{,}04+0{,}6953)+0{,}1(-0{,}04+0{,}4095)=0{,}5282+0{,}0655+0{,}0370=0{,}6307$.

(b) Miglioramento

Con queste utilità si calcola $Q(s,a)=\sum_{s'}P(s'\mid s,a)[R+\gamma U(s')]$ per ogni azione. Quasi ovunque l'azione corrente è già la migliore. Fa eccezione $(3,1)$:

($Q(\text{Su})$ coincide con $U(3,1)$, come deve: è l'azione della politica; Sinistra la supera.) In $(4,1)$: Sinistra $0{,}4095$ (corrente), Giù $0{,}3916$, Destra $0{,}2326$, Su $-0{,}7040$: nessun cambio. Nuova politica $\pi_{i+1}$: la stessa, con $(3,1)$ = Sinistra.

(c) Seconda iterazione

Nuova valutazione con $\pi_{i+1}$: cambia solo $c$, e di conseguenza $d$: $$c=0{,}8(r+b)+0{,}1(r+f)+0{,}1(r+c)\ \text{(sinistra voluta; su e giù deviazioni)}\Rightarrow c=0{,}6514,\qquad d=0{,}4279,$$ mentre le altre sette utilità restano uguali. Il miglioramento non cambia nessuna azione: la politica è stabile, e le utilità sono esattamente quelle di value iteration ($0{,}6514$ e $0{,}4279$ per $(3,1)$ e $(4,1)$). Value iteration e policy iteration trovano la stessa politica, come previsto.

(d) Da "Su ovunque"

Servono 5 iterazioni, ciascuna con un sistema lineare da risolvere. Con la politica "Su ovunque" l'utilità è negativa (il robot sbatte contro i bordi), ma già alla seconda valutazione $U(1,1)$ passa da $-1{,}4262$ a $0{,}5482$. Value iteration, sullo stesso problema, ne richiede 40 (più semplici): è il confronto della teoria. Una politica intermedia di policy iteration è già usabile; un $U_k$ intermedio di value iteration no.

Il codice

def valuta(pi):
    """Valutazione: risolve (I - gamma P_pi) U = R_pi (nei terminali il futuro e' nullo)."""
    n = len(STATI)
    P_pi = np.array([P[pi[i], i] for i in range(n)])
    R_pi = np.array([R[i, pi[i]] for i in range(n)])
    for t in TERMINALI: P_pi[IDX[t], :] = 0
    return np.linalg.solve(np.eye(n) - gamma * P_pi, R_pi)

def migliora(U, pi):
    Q = R.T + gamma * P @ U                          # Q[a,s]
    nuova = Q.argmax(axis=0)
    for i in range(len(STATI)):                      # a parita' di Q si tiene l'azione corrente
        if np.isclose(Q[pi[i], i], Q[:, i].max()): nuova[i] = pi[i]
    return nuova, Q

P, R = costruisci_mdp(-0.04); gamma = 1.0
pi = np.array([NOMI.index("Su")] * len(STATI))       # politica iniziale: Su ovunque
for it in range(1, 10):
    U = valuta(pi)
    nuova, Q = migliora(U, pi)
    print(it, "U(1,1) = %.4f" % U[IDX[(1, 1)]], "U(3,1) = %.4f" % U[IDX[(3, 1)]])
    if (nuova == pi).all(): break
    pi = nuova

Output atteso:

1 U(1,1) = -1.4262 U(3,1) = -0.4854
2 U(1,1) = 0.5482 U(3,1) = 0.6166
3 U(1,1) = 0.7310 U(3,1) = 0.6166
4 U(1,1) = 0.7453 U(3,1) = 0.6307
5 U(1,1) = 0.7453 U(3,1) = 0.6514

La riga if np.isclose(...) evita oscillazioni quando due azioni hanno lo stesso $Q$: si tiene quella corrente, e il test "la politica non è cambiata" è affidabile.