Esercizio - Value iteration di Mario nel grid world (esempio d'esame 2)

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 →. Esercizio collegato: Esercizio - Value iteration sul mondo 4x3 (slide del corso). Domanda 9 del quiz da 9 CFU (ricompensa per transizione $-0{,}2$) e domanda 2 di quello da 6 CFU ($-0{,}3$): stessa figura e stesso testo, solo il numero cambia.

Testo. In un video game a griglia il protagonista Mario si muove di una cella alla volta in una delle quattro direzioni (avanti, indietro, sinistra, destra). A causa di un joystick difettoso si muove nella direzione desiderata solo nel $70\%$ dei casi; nel restante $30\%$ la direzione è una delle tre rimanenti, tutte con la stessa probabilità. Nella situazione della figura, calcolare l'utilità $U$ dello stato in cui si trova Mario (seconda riga, seconda colonna) dopo una sola iterazione del value iteration.

Assunzioni: le utilità di tutti gli stati sono inizialmente nulle, eccetto i terminali; il reward di ogni transizione è $-0{,}2$ (9 CFU) oppure $-0{,}3$ (6 CFU); lo sconto è $\gamma=1$. Equazione di Bellman: $U(s)=\max_{a\in A(s)}\sum_{s'}P(s'\mid s,a)\,[R(s,a,s')+\gamma\,U(s')]$.

La figura. Griglia $3\times4$ (3 righe, 4 colonne). Il castello è in riga 1, colonna 4, con $U=+100$ (terminale); il fungo cattivo (goomba) è in riga 3, colonna 4, con $U=-100$ (terminale); Mario è in riga 2, colonna 2; tutte le altre celle hanno $U=0$.

Soluzione

Le quattro celle vicine a Mario (sopra: riga 1 colonna 2; sotto: riga 3 colonna 2; sinistra: riga 2 colonna 1; destra: riga 2 colonna 3) hanno tutte $U_0=0$, e non sono terminali. Mario è in una cella interna, quindi nessuna mossa sbatte contro il bordo.

Per un'azione qualunque $a$ (la direzione voluta ha probabilità $0{,}7$, ciascuna delle altre tre $0{,}1$): $$\sum_{s'}P(s'\mid s,a)[R+\gamma U_0(s')]=0{,}7\,(-0{,}2+0)+3\cdot0{,}1\,(-0{,}2+0)=-0{,}14-0{,}06=-0{,}2.$$ Il risultato è lo stesso per tutte e quattro le azioni (tutti gli esiti hanno utilità $0$, e la somma delle probabilità è $1$), quindi anche il massimo vale $$U_1(2,2)=-0{,}2\ \ (\text{9 CFU}),\qquad U_1(2,2)=-0{,}3\ \ (\text{6 CFU}).$$

Perché non entrano $+100$ e $-100$. Il castello e il fungo sono a distanza $3$ da Mario (3 mosse in linea orizzontale e verticale), non tra i suoi vicini: una sola mossa non può portarlo in un terminale. Dopo la prima iterazione la sola informazione che si propaga è il reward della transizione. L'errore tipico è includere $\pm100$ come se Mario fosse accanto a un terminale, oppure dimenticare il reward negativo e rispondere $0$.

Cosa succede nelle iterazioni successive (oltre la domanda)

Le celle adiacenti ai terminali cambiano subito: per la cella sotto il castello (riga 1, colonna 3) con la mossa verso il castello, $U_1=0{,}7\,(-0{,}2+100)+0{,}3\,(-0{,}2+0)=69{,}86-0{,}06=69{,}8$ (assumendo che un urto contro il bordo lasci la cella al suo posto). L'informazione arriva a Mario dopo tre iterazioni:

(i valori dopo la terza iterazione dipendono dall'ipotesi sul bordo; la risposta alla domanda no). Ricalcolati con Python su tutta la griglia.

H, W = 3, 4
term = {(0, 3): 100, (2, 3): -100}
mosse = {"N": (-1, 0), "S": (1, 0), "W": (0, -1), "E": (0, 1)}
def passo(U, r):
    Un = {}
    for i in range(H):
        for j in range(W):
            if (i, j) in term: Un[(i, j)] = term[(i, j)]; continue
            def q(a):                                   # somma su s' di P(s'|s,a) [R + U(s')]
                tot = 0
                for b, (di, dj) in mosse.items():
                    ni, nj = i + di, j + dj
                    if not (0 <= ni < H and 0 <= nj < W): ni, nj = i, j
                    tot += (.7 if a == b else .1) * (r + U[(ni, nj)])
                return tot
            Un[(i, j)] = max(q(a) for a in mosse)
    return Un
U = {(i, j): term.get((i, j), 0) for i in range(H) for j in range(W)}
U = passo(U, -.2); print(U[(1, 1)])                     # -0.2