Esercizio - Quiz a domande crescenti e utilità degli stati (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 1.

Testo (dalle slide). Un quiz ha quattro domande di difficoltà e premio crescenti: la prima da 100 euro, la seconda da 1 000, la terza da 10 000, la quarta da 50 000. Probabilità di rispondere correttamente: $\tfrac9{10}$, $\tfrac34$, $\tfrac12$, $\tfrac1{10}$. A ogni passo ci sono due azioni: ritirarsi incassando quanto vinto finora, oppure rispondere alla domanda successiva: se si sbaglia si perde tutto. Rispondere correttamente alla quarta porta a $100+1\,000+10\,000+50\,000=61\,100$ euro e il gioco finisce. Prima della domanda $Q_k$ il montepremi accumulato è: $Q_1$: 0; $Q_2$: 100; $Q_3$: 1 100; $Q_4$: 11 100.

(a) Per ogni domanda, conviene ritirarsi o rispondere? Qual è l'utilità di ogni stato? (b) Per quale probabilità di successo $p_4$ della domanda $Q_4$ conviene rispondere? (c) Cosa cambia se $p_4=0{,}3$?

Soluzione

Idea. L'utilità $U(Q_k)$ è il guadagno atteso partendo dallo stato "sono davanti a $Q_k$" supponendo di agire in modo ottimale da lì in poi. Dipende dall'utilità dello stato successivo, quindi si calcola partendo dalla fine (come nell'equazione di Bellman, senza cicli): $$U(Q_k)=\max\big(\text{ritirarsi},\ p_k\cdot U(Q_{k+1})\big),$$ dove il ritirarsi vale il montepremi accumulato, e la risposta sbagliata vale 0 (perde tutto). Per $Q_4$ la risposta esatta porta a 61 100 e il gioco finisce.

(a)

• $Q_4$: ritirarsi $11\,100$; rispondere $0{,}1\cdot61\,100+0{,}9\cdot0=6\,110$. Si ritira, $U(Q_4)=\mathbf{11\,100}$. (Rischiare per $50\,000$ con probabilità $\tfrac1{10}$ non conviene: $6\,110<11\,100$.)
• $Q_3$: ritirarsi $1\,100$; rispondere: $0{,}5\cdot U(Q_4)=0{,}5\cdot11\,100=5\,550$. Si risponde, $U(Q_3)=\mathbf{5\,550}$. Si usa $U(Q_4)=11\,100$ e non 61 100, perché arrivati a $Q_4$ ci si ritira: il valore di passare la terza domanda è quello dello stato successivo giocato in modo ottimale.
• $Q_2$: ritirarsi $100$; rispondere $0{,}75\cdot5\,550=4\,162{,}5$. $U(Q_2)=\mathbf{4\,162{,}5}$ (le slide arrotondano a 4 163).
• $Q_1$: ritirarsi $0$; rispondere $0{,}9\cdot4\,162{,}5=3\,746{,}25$. $U(Q_1)=\mathbf{3\,746{,}25}$ (3 747 nelle slide).

La strategia ottima (la politica) è: rispondere a $Q_1$, $Q_2$, $Q_3$ e ritirarsi davanti a $Q_4$. Il premio atteso del gioco, partendo da zero, è $3\,746{,}25$ euro.

(b) Davanti a $Q_4$ si risponde se $p_4\cdot61\,100>11\,100$, cioè $p_4>\dfrac{11\,100}{61\,100}=0{,}1817$. Con $p_4=0{,}1$ si resta sotto la soglia.

(c) Con $p_4=0{,}3$: rispondere a $Q_4$ vale $0{,}3\cdot61\,100=18\,330>11\,100$, quindi $U(Q_4)=18\,330$. Allora $U(Q_3)=0{,}5\cdot18\,330=9\,165$; $U(Q_2)=0{,}75\cdot9\,165=6\,873{,}75$; $U(Q_1)=0{,}9\cdot6\,873{,}75=6\,186{,}375$. Una domanda più facile alza l'utilità di tutti gli stati precedenti, perché l'informazione si propaga all'indietro.

Verifica con Python.

def quiz(p, premi=(11100, 1100, 100, 0), finale=61100):
    """p = probabilita' di successo di Q1..Q4; premi = montepremi accumulato prima di Q4, Q3, Q2, Q1."""
    U = max(premi[0], p[3] * finale)                    # Q4: si ritira o si risponde (e si vince 61100)
    risultato = [U]
    for k in (2, 1, 0):                                 # Q3, Q2, Q1, sempre all'indietro
        U = max(premi[3 - k], p[k] * U)
        risultato.append(U)
    return risultato[::-1]                              # [U(Q1), U(Q2), U(Q3), U(Q4)]

print(quiz([0.9, 0.75, 0.5, 0.1]))   # [3746.25, 4162.5, 5550.0, 11100]
print(quiz([0.9, 0.75, 0.5, 0.3]))   # [6186.375, 6873.75, 9165.0, 18330.0]