Esercizio - MDP con pymdptoolbox, matrici di transizione e ricompensa (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 guida con la stessa libreria: Esercizio - MDP con value iteration, policy iteration e Q-learning (laboratorio 9). Domanda 4 del quiz da 9 CFU e domanda 4 di quello da 6 CFU: identiche (24 blank).

Testo. Processo di Markov con 3 stati (numerati da 0 a 2) e due azioni.

• "Stay" (indice 0): ha sempre successo e lascia l'agente dove è.
• "Jump" (indice 1): porta l'agente avanti di una posizione con probabilità $0{,}7$, con probabilità $0{,}3$ lo lascia dov'è.
• Nello stato 2 l'agente resta con probabilità $1$. Lo stato 2 ha ricompensa $1$ (valore che include già eventuali costi).
• Ogni altra azione Stay costa $-0{,}10$, ogni altra azione Jump costa $-0{,}05$.

Completare l'implementazione con MDP toolbox. Q1: la matrice P1 delle probabilità di transizione, 18 blank (diciotto numeri), ciascuno con menu $0$, $1$, $0{,}3$, $0{,}7$. Q2: la matrice R1 delle ricompense, 6 blank, ciascuno con menu $-0{,}10$, $-0{,}05$, $1$, $0$. (Nella trascrizione le parentesi quadre del codice sono sbilanciate; la struttura è quella spiegata qui sotto.)

Struttura degli array

pymdptoolbox usa:

• P di forma (A, S, S): P[a][s][s'] è la probabilità di passare da s a s' con l'azione a. Qui forma $(2,3,3)$: $2\cdot3\cdot3=18$ numeri, i 18 blank. Ogni riga P[a][s] deve sommare a $1$.
• R di forma (S, A): R[s][a] è la ricompensa di eseguire a in s. Qui $(3,2)$: 6 numeri.

Soluzione

Q1. Prima matrice, azione 0 (Stay): l'identità, perché non ci si muove mai. Seconda matrice, azione 1 (Jump):

• stato 0: resta in 0 con $0{,}3$, va in 1 con $0{,}7$: riga $(0{,}3;\ 0{,}7;\ 0)$;
• stato 1: resta in 1 con $0{,}3$, va in 2 con $0{,}7$: riga $(0;\ 0{,}3;\ 0{,}7)$;
• stato 2: resta in 2 con $1$ (non c'è uno stato 3 in cui saltare): riga $(0;\ 0;\ 1)$.

import numpy as np
P1 = np.array([
    [[1, 0, 0],       [0, 1, 0],       [0, 0, 1]],        # azione 0, Stay
    [[0.3, 0.7, 0],   [0, 0.3, 0.7],   [0, 0, 1]],        # azione 1, Jump
])

Q2. R1[s][a]: negli stati 0 e 1 Stay costa $-0{,}10$ (colonna 0) e Jump $-0{,}05$ (colonna 1); nello stato 2 la ricompensa è $1$ per entrambe le azioni, perché il valore "include già eventuali costi":

R1 = np.array([[-0.10, -0.05],      # stato 0: Stay, Jump
               [-0.10, -0.05],      # stato 1
               [ 1,     1   ]])     # stato 2

Blank 19-24, in ordine: $-0{,}10;\ -0{,}05;\ -0{,}10;\ -0{,}05;\ 1;\ 1$.

Perché le scelte alternative sono sbagliate

• Mettere $0{,}3$ e $0{,}7$ scambiati (salto con probabilità $0{,}3$): contraddice il testo, il salto riesce con $0{,}7$.
• Mettere $0{,}7$ nella colonna di destra nello stato 2 non ha senso: non esiste uno stato oltre il 2, e la riga non sommerebbe a $1$ (serve $(0;\ 0;\ 1)$).
• Trasporre R (forma $(A,S)$ invece di $(S,A)$): la libreria si aspetta R[s][a]; con la forma sbagliata il controllo fallisce o le ricompense vanno agli stati sbagliati.
• Ricompensa $0$ nello stato 2 o $-0{,}10$ per Jump: il testo dà $1$ nello stato 2 e $-0{,}05$ per Jump.

Verifica

Le righe di P1 sommano tutte a $1$ (P1.sum(axis=2) dà una matrice di soli uni). Con mdptoolbox.mdp.ValueIteration(P1, R1, 0.9) (sconto non dato dal testo, qui $0{,}9$) il valore di stato soddisfa $U(2)=1/(1-0{,}9)=10$ e, usando Jump negli stati 0 e 1, $U(1)=\dfrac{-0{,}05+0{,}9\cdot0{,}7\cdot10}{1-0{,}9\cdot0{,}3}=8{,}5616$ e $U(0)=\dfrac{-0{,}05+0{,}9\cdot0{,}7\cdot8{,}5616}{0{,}73}=7{,}3203$. La politica ottima è Jump, Jump, e in 2 le due azioni sono equivalenti (la libreria sceglie la prima, Stay). Valori ricalcolati con NumPy (la libreria non è installata).