Esercizio - Value 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 →, sezioni 3-6.

Testo (dalle slide). Un robot si muove in una griglia con 4 colonne e 3 righe. Le celle sono indicate con (colonna, riga), partendo da $(1,1)$ in basso a sinistra. La cella $(2,2)$ è un muro. Le celle $(4,3)$ e $(4,2)$ sono terminali: entrare in $(4,3)$ ha ricompensa $+1$, entrare in $(4,2)$ ha ricompensa $-1$. Ogni altra transizione ha ricompensa $r=-0{,}04$. L'azione voluta (Su, Giù, Sinistra, Destra) riesce con probabilità $0{,}8$; con probabilità $0{,}1$ per parte il robot si muove perpendicolarmente. Un urto contro un muro o il bordo lascia il robot fermo. Fattore di sconto $\gamma=1$.

(a) Calcolare a mano $U_1$ e $U_2$ di value iteration partendo da $U_0=0$. (b) Scrivere il programma, trovare le utilità finali e il numero di iterazioni. (c) Ricavare la politica ottima e verificare la scelta in $(1,1)$. (d) Che cosa cambia con $r=-2$ e con $r=-0{,}01$?

Soluzione

Regole di calcolo. Per ogni stato non terminale $s$ e azione $a$: $$Q_k(s,a)=\sum_{s'}P(s'\mid s,a)\big[R(s,a,s')+\gamma U_k(s')\big],\qquad U_{k+1}(s)=\max_aQ_k(s,a),$$ con ricompensa $+1$ o $-1$ quando $s'$ è un terminale (e $U_k(\text{terminale})=0$: la ricompensa si incassa entrando, poi il gioco finisce) e $r+U_k(s')$ altrimenti. Un esito che urta un muro o il bordo ha $s'=s$.

(a) Iterazioni a mano

Iterazione 1 ($U_0=0$): $Q_0(s,a)$ è solo la ricompensa attesa del passo. Quasi ovunque $=r=-0{,}04$. Fanno eccezione le celle da cui si può entrare in un terminale:

• $(3,3)$, Destra: $0{,}8\cdot(+1)+0{,}1\,(r+0)+0{,}1\,(r+0)=0{,}8-0{,}008=\mathbf{0{,}792}$ (Su e Giù non entrano nel $+1$ con probabilità $0{,}8$, la deviazione a destra sì ma con $0{,}1$: valgono meno, per esempio Su: $0{,}1\cdot1+0{,}9\cdot r=0{,}064$);
• $(3,2)$, Su: $0{,}8\,(r+0)+0{,}1\,(r+0)+0{,}1\cdot(-1)=-0{,}04\cdot0{,}9-0{,}1=-0{,}136$; Giù: $0{,}8r+0{,}1r+0{,}1(-1)$ è uguale, e Sinistra ($0{,}8$ muro: resta; $0{,}1$ su; $0{,}1$ giù) vale $-0{,}04$. Il massimo è $-0{,}04$ (Sinistra, che non rischia il $-1$);
• $(4,1)$ e tutte le altre: $-0{,}04$.

Quindi $U_1(3,3)=0{,}792$ e tutti gli altri stati non terminali valgono $-0{,}04$.

Iterazione 2 (si usa $U_1$):

• $(3,3)$, Destra: $0{,}8\cdot1+0{,}1\,(r+U_1(3,3))+0{,}1\,(r+U_1(3,2))=0{,}8+0{,}1\cdot0{,}752+0{,}1\cdot(-0{,}08)=\mathbf{0{,}8672}$;
• $(2,3)$, Destra: $0{,}8\,(r+U_1(3,3))+0{,}1\,(r+U_1(2,3))$ (su: bordo, resta) $+\,0{,}1\,(r+U_1(2,3))$ (giù: muro, resta) $=0{,}8\cdot0{,}752+0{,}2\cdot(-0{,}08)=\mathbf{0{,}5856}$;
• $(3,2)$, Su: $0{,}8\,(r+U_1(3,3))+0{,}1\,(r+U_1(3,2))$ (sinistra: muro) $+\,0{,}1\cdot(-1)=0{,}6016-0{,}008-0{,}1=\mathbf{0{,}4936}$;
• tutte le altre celle hanno vicini non ancora "informati" (valgono $-0{,}04$) e la miglior azione non tocca i terminali: $U_2=-0{,}04+(-0{,}04)=-0{,}08$.

(b) Il programma

import numpy as np

MURI = {(2, 2)}
TERMINALI = {(4, 3): +1.0, (4, 2): -1.0}                 # ricompensa per l'ingresso
STATI = [(x, y) for y in (1, 2, 3) for x in (1, 2, 3, 4) if (x, y) not in MURI]
IDX = {s: i for i, s in enumerate(STATI)}
AZIONI = {"Su": (0, 1), "Giu": (0, -1), "Sx": (-1, 0), "Dx": (1, 0)}
LATERALI = {"Su": ("Sx", "Dx"), "Giu": ("Sx", "Dx"), "Sx": ("Su", "Giu"), "Dx": ("Su", "Giu")}
NOMI = list(AZIONI)

def passo(s, a):
    t = (s[0] + AZIONI[a][0], s[1] + AZIONI[a][1])
    return s if (t in MURI or not (1 <= t[0] <= 4 and 1 <= t[1] <= 3)) else t

def costruisci_mdp(r):
    n = len(STATI)
    P = np.zeros((4, n, n)); R = np.zeros((n, 4))        # P[a,s,s'], R[s,a] = ricompensa attesa
    for ai, a in enumerate(NOMI):
        for s in STATI:
            if s in TERMINALI:
                P[ai, IDX[s], IDX[s]] = 1                 # terminale: assorbente, nessuna ricompensa
                continue
            for b, p in ((a, .8), (LATERALI[a][0], .1), (LATERALI[a][1], .1)):
                t = passo(s, b)
                P[ai, IDX[s], IDX[t]] += p
                R[IDX[s], ai] += p * TERMINALI.get(t, r)  # +1 / -1 se entra in un terminale, altrimenti r
    return P, R

def stampa(V):
    for y in (3, 2, 1):
        print("  ".join("  muro " if (x, y) in MURI else f"{V[IDX[(x, y)]]:7.4f}" for x in (1, 2, 3, 4)))

def value_iteration(P, R, gamma, tol=1e-10):
    V = np.zeros(P.shape[1]); storia = [V]
    while True:
        Q = R.T + gamma * P @ V
        V_new = Q.max(axis=0); storia.append(V_new)
        if np.abs(V_new - V).max() < tol:
            return V_new, Q.argmax(axis=0), storia
        V = V_new

P, R = costruisci_mdp(-0.04)
V, pol, storia = value_iteration(P, R, 1.0)
print("iterazioni:", len(storia) - 1)
for k in (1, 2):
    print("U_%d" % k); stampa(storia[k])

Output atteso (i terminali compaiono con 0 nelle tabelle di $U_k$, perché la loro ricompensa è incassata nell'ingresso):

iterazioni: 40
U_1
-0.0400  -0.0400   0.7920   0.0000
-0.0400    muro   -0.0400   0.0000
-0.0400  -0.0400  -0.0400  -0.0400
U_2
-0.0800   0.5856   0.8672   0.0000
-0.0800    muro    0.4936   0.0000
-0.0800  -0.0800  -0.0800  -0.0800

Gli stessi valori che si sono ricavati a mano. Dopo 40 iterazioni (tolleranza $10^{-10}$; con $\gamma=1$ la soglia $\varepsilon(1-\gamma)/\gamma$ non si può usare) le utilità sono quelle delle slide:

(c) Politica

La politica è $\pi^*(s)=\arg\max_aQ(s,a)$. In $(1,1)$, con $U(1,2)=0{,}8016$, $U(2,1)=0{,}6953$, $U(1,1)=0{,}7453$:

• Su: $0{,}8\cdot0{,}7616+0{,}1\cdot0{,}6553+0{,}1\cdot0{,}7053=0{,}7453$;
• Sinistra: $0{,}9\cdot0{,}7053+0{,}1\cdot0{,}7616=0{,}7109$;
• Giù: $0{,}9\cdot0{,}7053+0{,}1\cdot0{,}6553=0{,}7003$;
• Destra: $0{,}8\cdot0{,}6553+0{,}1\cdot0{,}7616+0{,}1\cdot0{,}7053=0{,}6709$.

Vince Su, e $0{,}7453=U(1,1)$ (equazione di Bellman soddisfatta). Politica completa:

È una politica prudente: dalle celle in basso $(2,1)$, $(3,1)$, $(4,1)$ si va a sinistra e si sale lungo la colonna 1 (il giro lungo), perché la strada breve passa da $(3,2)$, che confina con il $-1$: una deviazione a destra costerebbe $0{,}1\cdot(-1)$. Nel codice la politica si legge con NOMI[pol[IDX[(x, y)]]].

(d) Altri valori di $r$

Cambiando solo costruisci_mdp(r):

• $r=-2$ (33 iterazioni): ogni passo costa moltissimo, conviene finire subito. Riga 3: Dx Dx Dx; riga 2: Su, muro, Dx; riga 1: Dx Dx Dx e Su in $(4,1)$: dall'angolo in basso a destra si va dritti nel $-1$, perché restare in gioco costa più di $-1$. È la politica "sotto $-1{,}6497$" delle slide.
• $r=-0{,}01$ (200 iterazioni: con un costo così basso l'informazione si stabilizza lentamente): il costo del passo è basso, si evita il $-1$ a ogni costo. Riga 3: Dx Dx Dx; riga 2: Su, muro, Sx; riga 1: Su, Sx, Sx e Giù in $(4,1)$: in $(3,2)$ si va a sinistra (urtando il muro) per non rischiare lo scivolamento in $(4,2)$, e in $(4,1)$ si urta il bordo inferiore (Giù). È la politica "tra $-0{,}0274$ e $0$" delle slide.
• Con $r=-0{,}6$ (intervallo $-0{,}7311<r<-0{,}4526$ delle slide) si ottiene la politica Dx Dx Dx / Su, muro, Su / Su, Dx, Su, Su, uguale a quella del corso.

Confermato per i tre valori con lo stesso programma.