Processi decisionali di Markov - utilità, equazione di Bellman, value e policy iteration

Fin qui l'agente decideva una azione alla volta (ricerca, logica) o ragionava soltanto sullo stato del mondo (reti bayesiane, filtraggio). Qui le due cose si uniscono: sequenze di decisioni in un ambiente incerto, dove ogni azione ha esiti probabilistici e conta il guadagno accumulato nel tempo. L'apprendimento per rinforzo (Cenni a reinforcement learning e reti per sequenzeapprofondimento: non nel programma di Telecomunicazioni, solo cenni (ultima lezione del corso). Reinforcement learning: un agente in uno stato $S_t$ sceglie azioni, l'ambiente restituisce ricompense; l'obiettivo non è minimizzare una loss ma massimizzare il ritorno $G_t=\sum_{k\ge0}\gamma^kR_{t+k+1}$ (fattore di sconto $\gamma\in[0,1)$) trovando la politica ottima $\pi^*=\arg\max G$. Apprendimento di sequenze: servono lunghezze variabili, dipendenze a lungo termine, ordine, parametri condivisi nel tempo; una rete ricorrente aggiorna uno stato $h_t=f_W(h_{t-1},x_t)$; le reti convolutive temporali (TCN) usano convoluzioni causali e dilatate con campo recettivo $1+(k-1)\sum d_\ell$. Chiude con i modelli generativi (VAE, GAN) già visti in Autoencoder.Cenni a reinforcement learning e reti per sequenze →) risolve lo stesso problema senza conoscere il modello; qui il modello è noto e si calcola la soluzione. Le esercitazioni sono Esercizio - Utilità attesa, maximax e maximin (laboratorio 9), Esercizio - MDP con value iteration, policy iteration e Q-learning (laboratorio 9), Esercizio - Quiz a domande crescenti e utilità degli stati (slide del corso), Esercizio - Value iteration sul mondo 4x3 (slide del corso) e Esercizio - Policy iteration sul mondo 4x3 (slide del corso).

1. Utilità attesa e decisioni sequenziali

Definizione (utilità attesa). Se l'azione $a$ porta nello stato $s'$ con probabilità $P(\text{RESULT}(a)=s')$ e $U(s')$ misura quanto è desiderabile $s'$ (di solito normalizzata tra 0 e 1, ma può essere in euro, punti, ...), l'utilità attesa dell'azione è $$EU(a)=\sum_{s'}P(\text{RESULT}(a)=s')\,U(s').$$ Il principio di massima utilità attesa (MEU) sceglie l'azione con $EU$ più alta. È un Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso → (Incertezza - probabilità, regola di Bayes e indipendenza condizionataUn agente con osservazioni parziali non può usare regole logiche rigide ("mal di denti implica carie" è falso): usa la probabilità come grado di credenza e, con la teoria dell'utilità, sceglie l'azione con utilità attesa massima. Strumenti: distribuzione congiunta completa (tabella di $2^n$ valori), marginalizzazione $P(Y\mid e)=\alpha\sum_h P(Y,e,h)$ con costante di normalizzazione $\alpha=1/P(e)$, regola del prodotto $P(a,b)=P(a\mid b)P(b)$, regola di Bayes $P(\text{causa}\mid\text{effetto})=\frac{P(\text{effetto}\mid\text{causa})P(\text{causa})}{P(\text{effetto})}$ e indipendenza condizionata $P(a,b\mid c)=P(a\mid c)P(b\mid c)$, che permette di scomporre la congiunta in tabelle più piccole. Un test con sensibilità 73% e falsi positivi 12% su una malattia con prior 1/700 dà una probabilità a posteriori di appena 0,9%.Incertezza - probabilità, regola di Bayes e indipendenza condizionata → per le probabilità).

Il MEU non è l'unico criterio. Il maximax valuta ogni azione con il suo miglior esito e sceglie il massimo (ottimista); il maximin la valuta con il suo peggior esito e sceglie il massimo (prudente). Possono dare scelte diverse dal MEU: lo si vede nell'esercizio del laboratorio 9.

Esempio (quiz a domande crescenti). Quattro domande $Q_1,\dots,Q_4$ da 100, 1 000, 10 000 e 50 000 euro, con probabilità di risposta esatta $\tfrac9{10},\tfrac34,\tfrac12,\tfrac1{10}$. A ogni domanda si può ritirarsi incassando quanto accumulato, oppure rispondere: se si sbaglia si perde tutto. Il montepremi accumulato dopo $Q_1,Q_2,Q_3$ è 100, 1 100, 11 100 euro.

Si ragiona dall'ultima domanda all'indietro, perché il valore di una domanda dipende da quello della successiva:

• $Q_4$: ritirarsi vale 11 100; rispondere vale $0{,}1\cdot61\,100+0{,}9\cdot0=6\,110$. Si ritira: $U(Q_4)=11\,100$.
• $Q_3$: ritirarsi vale 1 100; rispondere vale $0{,}5\cdot U(Q_4)=0{,}5\cdot11\,100=5\,550$. Si risponde: $U(Q_3)=5\,550$.
• $Q_2$: ritirarsi vale 100; rispondere vale $0{,}75\cdot5\,550=4\,162{,}5$. $U(Q_2)=4\,162{,}5$.
• $Q_1$: ritirarsi vale 0; rispondere vale $0{,}9\cdot4\,162{,}5=3\,746{,}25$. $U(Q_1)=3\,746{,}25$.

Il numero accanto a ogni stato è la sua utilità: il guadagno atteso da quel punto in poi se si agisce sempre in modo ottimale. È l'idea dell'equazione di Bellman, applicata qui a un problema che non ha cicli.

2. La famiglia dei modelli di Markov

Catene di Markov e HMM sono in Ragionamento probabilistico nel tempo - catene di Markov, HMM, filtraggio e smoothingPer ragionare sul tempo il mondo è una sequenza di istanti: stato nascosto $X_t$ ed evidenza osservata $E_t$. Ipotesi di Markov del primo ordine $P(X_t\mid X_{0:t-1})=P(X_t\mid X_{t-1})$ (modello di transizione) e ipotesi del sensore $P(E_t\mid X_{0:t},E_{1:t-1})=P(E_t\mid X_t)$ (modello del sensore): congiunta $P(X_0)\prod_t P(X_t\mid X_{t-1})P(E_t\mid X_t)$. Un HMM ha uno stato discreto a $S$ valori: transizione = matrice $\mathbf T$ ($T_{ij}=P(X_t=j\mid X_{t-1}=i)$), sensore = matrici diagonali $\mathbf O_t$. Compiti: filtraggio $P(X_t\mid e_{1:t})$, predizione $P(X_{t+k}\mid e_{1:t})$, smoothing $P(X_{t-k}\mid e_{1:t})$, spiegazione più probabile $\arg\max P(x_{1:t}\mid e_{1:t})$. Filtraggio ricorsivo: $\mathbf f_t=\alpha,\mathbf O_t\mathbf T^\top\mathbf f_{t-1}$ (predizione, poi aggiornamento). Mondo dell'ombrello: $\mathbf f_1=\langle0{,}818;\ 0{,}182\rangle$, $\mathbf f_2=\langle0{,}883;\ 0{,}117\rangle$. Senza normalizzare, $\mathbf s_t=\mathbf O_t\mathbf T^\top\mathbf s_{t-1}$ dà la verosimiglianza $P(e_{1:t})$.Ragionamento probabilistico nel tempo - catene di Markov, HMM, filtraggio e smoothing →. Un MDP aggiunge a una catena di Markov le azioni e le ricompense; un POMDP aggiunge a un MDP un modello di sensore, come in un HMM.

3. Definizione di MDP

Definizione (MDP). Problema decisionale sequenziale in un ambiente completamente osservabile e stocastico, dato da

• un insieme di stati $S$, con stato iniziale $s_0$;
• un insieme di azioni $A(s)$ per ogni stato;
• un modello di transizione $P(s'\mid s,a)$: probabilità di arrivare in $s'$ eseguendo $a$ in $s$;
• una funzione di ricompensa $R(s,a,s')$, numero (positivo o negativo) assegnato alla transizione.

La proprietà di Markov dice che $P(s'\mid s,a)$ non dipende dalla storia passata.

Si distingue: la ricompensa è locale (riguarda una transizione), l'utilità è globale (somma anche tutto il futuro).

Modello di transizione e azioni incerte. Se l'agente ha una distribuzione $P(s)$ sullo stato corrente, la probabilità di arrivare in $s'$ con l'azione $a$ è $$P(\text{RESULT}(a)=s')=\sum_sP(s)\,P(s'\mid s,a),$$ che è la probabilità totale (Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →) ed è la probabilità che serve per l'$EU(a)$. Ha la stessa forma della formula di aggiustamento di Interventi e operatore do - criterio backdoor e aggiustamentoOsservare $X=x$ e forzare $X=x$ sono cose diverse: $P(y\mid x)\ne P(y\mid do(x))$ quando c'è un confondente. L'intervento $do(X=x)$ si calcola con la «chirurgia» del grafo (si tolgono le frecce entranti in X) e si traduce in probabilità osservazionali con la formula di aggiustamento $P(y\mid do(x))=\sum_z P(y\mid x,z)P(z)$, dove $Z$ sono i genitori di X, o più in generale un insieme S che soddisfa il criterio backdoor: blocca ogni cammino backdoor (cammino da X a Y che inizia con una freccia entrante in X) e non contiene discendenti di X. Effetto causale medio $ACE=P(y\mid do(x))-P(y\mid do(\neg x))$. Se il confondente non è osservabile ma c'è un mediatore Z con X→Z→Y, vale il front-door $P(y\mid do(x))=\sum_z P(z\mid x)\sum_{x'}P(y\mid x',z)P(x')$. Mediazione: effetto diretto controllato CDE con $do(x),do(z)$. Se due insiemi backdoor danno risultati diversi sui dati, il modello è sbagliato. Argomento del corso da 9 CFU.Interventi e operatore do - criterio backdoor e aggiustamento →: si media su ciò che non si controlla.

Esempio (il mondo 4x3). Griglia con 4 colonne e 3 righe; la cella $(2,2)$ è un muro. Le celle $(4,3)$ e $(4,2)$ sono terminali: entrare in $(4,3)$ dà ricompensa $+1$, entrare in $(4,2)$ dà $-1$. Ogni altra transizione ha ricompensa $r$ (qui $r=-0{,}04$, un piccolo costo per ogni passo). L'azione ha esito incerto: con probabilità $0{,}8$ il robot va nella direzione voluta, con probabilità $0{,}1$ per parte devia a sinistra o a destra rispetto alla direzione voluta. Un urto contro un muro o il bordo lascia fermi.

Politica. La soluzione di un MDP non è una sequenza di azioni (con esiti incerti non si sa dove si finirà) ma una politica $\pi$: per ogni stato raggiungibile dice che azione eseguire, $a=\pi(s)$. Una politica si misura con l'utilità attesa delle sequenze di azioni che produce; la politica ottima $\pi^*$ è quella con utilità attesa massima.

Nel mondo 4x3 la politica ottima dipende da $r$. Ricalcolata con value iteration, per $r=-0{,}04$ la politica ottima è

e per $r$ molto negativo (sotto circa $-1{,}65$) restare in gioco costa troppo e da $(4,1)$ l'agente va Su, dritto nel $-1$, per finire subito; per $r$ appena sotto zero (tra circa $-0{,}027$ e $0$) il passo costa poco e l'agente evita il $-1$ con più prudenza, per esempio da $(4,1)$ va Giù e urta il bordo; con $r>0$ conviene non terminare mai. Le soglie sono quelle delle slide del corso.

4. Utilità nel tempo e fattore di sconto

L'orizzonte può essere finito (dopo $N$ passi non conta più nulla: la politica ottima dipende dal tempo rimasto, è non stazionaria) oppure infinito (nessun motivo di comportarsi diversamente nello stesso stato in momenti diversi: la politica è stazionaria, dipende solo dallo stato). Il corso tratta il caso infinito.

L'utilità di una sequenza di stati è la somma delle ricompense scontate con un fattore $\gamma\in[0,1]$: $$U([s_0,s_1,s_2,\dots])=R_1+\gamma R_2+\gamma^2R_3+\dots$$ $\gamma$ vicino a 1: l'agente aspetta volentieri una ricompensa lontana; $\gamma$ vicino a 0: non vuole aspettare. Con $\gamma<1$ e ricompense limitate la serie converge (Cenni a reinforcement learning e reti per sequenzeapprofondimento: non nel programma di Telecomunicazioni, solo cenni (ultima lezione del corso). Reinforcement learning: un agente in uno stato $S_t$ sceglie azioni, l'ambiente restituisce ricompense; l'obiettivo non è minimizzare una loss ma massimizzare il ritorno $G_t=\sum_{k\ge0}\gamma^kR_{t+k+1}$ (fattore di sconto $\gamma\in[0,1)$) trovando la politica ottima $\pi^*=\arg\max G$. Apprendimento di sequenze: servono lunghezze variabili, dipendenze a lungo termine, ordine, parametri condivisi nel tempo; una rete ricorrente aggiorna uno stato $h_t=f_W(h_{t-1},x_t)$; le reti convolutive temporali (TCN) usano convoluzioni causali e dilatate con campo recettivo $1+(k-1)\sum d_\ell$. Chiude con i modelli generativi (VAE, GAN) già visti in Autoencoder.Cenni a reinforcement learning e reti per sequenze → per i passaggi); con $\gamma=1$ serve che la politica raggiunga prima o poi uno stato terminale, altrimenti l'utilità diverge (come nel mondo 4x3).

5. L'equazione di Bellman

Definizione (equazione di Bellman). L'utilità di uno stato è la ricompensa attesa della prossima transizione più l'utilità scontata dello stato successivo, supponendo di scegliere l'azione ottima: $$U(s)=\max_{a\in A(s)}\sum_{s'}P(s'\mid s,a)\,\big[R(s,a,s')+\gamma\,U(s')\big].$$ La somma da massimizzare è la funzione azione-utilità (Q-function) $$Q(s,a)=\sum_{s'}P(s'\mid s,a)\,\big[R(s,a,s')+\gamma\,U(s')\big],\qquad U(s)=\max_aQ(s,a).$$ La politica ottima si legge da $U$: $\ \pi^*(s)=\arg\max_aQ(s,a)$.

Con $n$ stati ci sono $n$ equazioni in $n$ incognite (le utilità), ma non sono lineari a causa del $\max$: non si risolvono con l'algebra lineare, e si risolvono iterando.

Esempio: lo stato $(1,1)$ del mondo 4x3 con $\gamma=1$, $r=-0{,}04$ e le utilità finali $U(1,2)=0{,}8016$, $U(2,1)=0{,}6953$, $U(1,1)=0{,}7453$. Le quattro azioni, tenendo presente che il muro o il bordo lasciano fermi:

• Su: $0{,}8(r+U(1,2))+0{,}1(r+U(2,1))+0{,}1(r+U(1,1))=0{,}8\cdot0{,}7616+0{,}1\cdot0{,}6553+0{,}1\cdot0{,}7053=\mathbf{0{,}7453}$;
• Sinistra: $0{,}9(r+U(1,1))+0{,}1(r+U(1,2))=0{,}9\cdot0{,}7053+0{,}1\cdot0{,}7616=0{,}7109$ (a sinistra c'è il bordo: $0{,}8+0{,}1$ restano fermi);
• Giù: $0{,}9(r+U(1,1))+0{,}1(r+U(2,1))=0{,}7003$;
• Destra: $0{,}8(r+U(2,1))+0{,}1(r+U(1,2))+0{,}1(r+U(1,1))=0{,}6709$.

Il massimo è Su, e vale proprio $U(1,1)$: l'equazione è soddisfatta. La politica in $(1,1)$ è Su (come nelle slide).

6. Value iteration

Idea. Si parte da utilità arbitrarie (di solito 0) e si applica l'equazione di Bellman come aggiornamento, finché le utilità non cambiano più: $$U_{k+1}(s)\leftarrow\max_aQ_k(s,a),\qquad Q_k(s,a)=\sum_{s'}P(s'\mid s,a)\big[R(s,a,s')+\gamma U_k(s')\big].$$ L'aggiornamento è simultaneo: $U_{k+1}$ si calcola per tutti gli stati usando solo $U_k$. Si ferma quando la massima variazione $\delta=\max_s|U_{k+1}(s)-U_k(s)|$ scende sotto $\varepsilon(1-\gamma)/\gamma$ (garantisce che l'errore sulle utilità sia al più $\varepsilon$). L'uscita serve poi a ricavare la politica con $\arg\max_aQ(s,a)$: questo è il passo in più che manca all'algoritmo.

Esempio completo: prime iterazioni nel mondo 4x3 ($\gamma=1$, $r=-0{,}04$, $U_0=0$ ovunque).

Iterazione 1. Con $U_0=0$ ogni $Q$ vale la ricompensa attesa immediata. Per $(3,3)$, azione Destra: $0{,}8\cdot(+1)$ (entra in $(4,3)$) $+\,0{,}1(r+0)$ (su: bordo, resta) $+\,0{,}1(r+0)$ (giù: va in $(3,2)$) $=0{,}8-0{,}008=0{,}792$. Gli stati lontani dai terminali valgono solo $r=-0{,}04$.

Iterazione 2. Ora $U_1(3,3)=0{,}792$ propaga l'informazione. Per $(3,3)$, Destra: $0{,}8+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)=0{,}8672$. Per $(2,3)$, Destra: $0{,}8(r+U_1(3,3))+0{,}2(r+U_1(2,3))=0{,}8\cdot0{,}752+0{,}2\cdot(-0{,}08)=0{,}5856$.

Le utilità delle prime iterazioni (verificate con NumPy; per i terminali è scritta la ricompensa):

L'informazione parte dai terminali e si diffonde come un'onda: dopo $k$ iterazioni sono "informate" solo le celle a distanza al più $k$ dai terminali. Fermando l'iterazione quando $\delta<10^{-10}$ servono 40 iterazioni e si ritrovano esattamente i valori delle slide. (Con $\gamma=1$ la soglia $\varepsilon(1-\gamma)/\gamma$ si annulla: si fissa direttamente una tolleranza su $\delta$.)

Pregi e limiti. Value iteration ha iterazioni semplici e veloci ma ne servono molte; i risultati intermedi non sono politiche utili; è adatto a spazi di stati piccoli.

import numpy as np

def value_iteration(P, R, gamma, eps=1e-6):
    """P: (A,S,S) probabilita' P[a,s,s'], R: (S,A) ricompensa attesa R[s,a]."""
    V = np.zeros(P.shape[1])
    while True:
        Q = R.T + gamma * P @ V          # Q[a,s] = R(s,a) + gamma * sum_s' P(s'|s,a) V(s')
        V_new = Q.max(axis=0)            # aggiornamento simultaneo di tutti gli stati
        delta = np.abs(V_new - V).max()
        V = V_new
        if delta <= eps * (1 - gamma) / gamma:
            return V, Q.argmax(axis=0)   # utilita' e politica greedy

7. Policy iteration

Idea. Si lavora direttamente sulle politiche. Partendo da una politica $\pi_0$ si alternano due passi:

1. valutazione: dato $\pi_i$ fisso, si calcola $U_i=U^{\pi_i}$, l'utilità di ogni stato se si seguisse $\pi_i$;
2. miglioramento: con $U_i$ si calcola la politica $\pi_{i+1}(s)=\arg\max_aQ_i(s,a)$.

Si termina quando il miglioramento non cambia la politica.

Valutazione. È la stessa equazione di Bellman senza il max, perché l'azione è fissata a $\pi_i(s)$: $$U_i(s)=\sum_{s'}P(s'\mid s,\pi_i(s))\big[R(s,\pi_i(s),s')+\gamma U_i(s')\big].$$ Sono $n$ equazioni lineari in $n$ incognite: si risolvono con l'algebra lineare, $(I-\gamma P_\pi)U=R_\pi$ (con $P_\pi$ la matrice di transizione della politica, $R_\pi$ il vettore delle ricompense attese). Per esempio, con $\pi_i(1,1)=\text{Su}$, $\pi_i(1,2)=\text{Su}$, $\pi_i(1,3)=\text{Destra}$: $$\begin{aligned}U_i(1,1)&=0{,}8[-0{,}04+U_i(1,2)]+0{,}1[-0{,}04+U_i(2,1)]+0{,}1[-0{,}04+U_i(1,1)]\\U_i(1,2)&=0{,}8[-0{,}04+U_i(1,3)]+0{,}2[-0{,}04+U_i(1,2)]\\U_i(1,3)&=0{,}8[-0{,}04+U_i(2,3)]+0{,}1[-0{,}04+U_i(1,2)]+0{,}1[-0{,}04+U_i(1,3)]\end{aligned}$$ e così per le altre celle. Nell'esercizio Esercizio - Policy iteration sul mondo 4x3 (slide del corso) il sistema è risolto per intero.

Esempio (riassunto). Partendo dalla politica "Su ovunque", policy iteration nel mondo 4x3 converge in 5 iterazioni: l'utilità di $(1,1)$ sotto la politica corrente vale $-1{,}4262$; poi $0{,}5482$; $0{,}7310$; $0{,}7453$ e infine ancora $0{,}7453$ (la politica non cambia più). La politica finale coincide con quella di value iteration.

def policy_iteration(P, R, gamma):
    S = P.shape[1]
    pi = np.zeros(S, dtype=int)          # politica iniziale: azione 0 ovunque
    while True:
        P_pi = P[pi, np.arange(S)]       # riga s = P(.|s, pi(s))
        R_pi = R[np.arange(S), pi]
        V = np.linalg.solve(np.eye(S) - gamma * P_pi, R_pi)   # valutazione: sistema lineare
        Q = R.T + gamma * P @ V
        new = Q.argmax(axis=0)           # miglioramento: azione greedy rispetto a V
        if (new == pi).all():
            return V, pi
        pi = new

Confronto.

	value iteration	policy iteration
iterazione	semplice e veloce (un aggiornamento di Bellman)	più pesante (risolve un sistema lineare)
numero di iterazioni	molte per convergere a $U^*$	poche per convergere a $\pi^*$
politica	serve un passo finale $\arg\max_aQ$	ogni iterazione dà una politica utilizzabile, anche se non ottima
uso	pochi stati	molti stati

8. Cenno al Q-learning

Value e policy iteration richiedono di conoscere $P$ e $R$. Se il modello è ignoto (apprendimento per rinforzo) si stima $Q$ provando le azioni: dopo ogni passo $(s,a,r,s')$, $$Q(s,a)\leftarrow Q(s,a)+\alpha\Big[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\Big],$$ con $\alpha$ passo di apprendimento. È l'algoritmo QLearning della libreria del laboratorio 9; con poche iterazioni la politica può restare sbagliata (vedi l'esercizio). Il quadro generale del RL è in Cenni a reinforcement learning e reti per sequenzeapprofondimento: non nel programma di Telecomunicazioni, solo cenni (ultima lezione del corso). Reinforcement learning: un agente in uno stato $S_t$ sceglie azioni, l'ambiente restituisce ricompense; l'obiettivo non è minimizzare una loss ma massimizzare il ritorno $G_t=\sum_{k\ge0}\gamma^kR_{t+k+1}$ (fattore di sconto $\gamma\in[0,1)$) trovando la politica ottima $\pi^*=\arg\max G$. Apprendimento di sequenze: servono lunghezze variabili, dipendenze a lungo termine, ordine, parametri condivisi nel tempo; una rete ricorrente aggiorna uno stato $h_t=f_W(h_{t-1},x_t)$; le reti convolutive temporali (TCN) usano convoluzioni causali e dilatate con campo recettivo $1+(k-1)\sum d_\ell$. Chiude con i modelli generativi (VAE, GAN) già visti in Autoencoder.Cenni a reinforcement learning e reti per sequenze →.

9. POMDP: quando lo stato non si vede

Un POMDP è un MDP con in più un modello di sensore $P(e\mid s)$: l'agente non conosce lo stato vero ma riceve osservazioni $e$.

Definizione (stato di credenza, belief state). Distribuzione di probabilità $b$ sugli stati: $b(s)=P(\text{stato}=s)$. Si risolve il problema come un normale MDP i cui stati sono le credenze.

Ciclo decisionale. (1) dato $b$, si esegue $a=\pi^*(b)$; (2) si osserva $e$; (3) si aggiorna la credenza e si ripete. L'aggiornamento è il filtraggio con in più l'azione (stessa struttura di Ragionamento probabilistico nel tempo - catene di Markov, HMM, filtraggio e smoothingPer ragionare sul tempo il mondo è una sequenza di istanti: stato nascosto $X_t$ ed evidenza osservata $E_t$. Ipotesi di Markov del primo ordine $P(X_t\mid X_{0:t-1})=P(X_t\mid X_{t-1})$ (modello di transizione) e ipotesi del sensore $P(E_t\mid X_{0:t},E_{1:t-1})=P(E_t\mid X_t)$ (modello del sensore): congiunta $P(X_0)\prod_t P(X_t\mid X_{t-1})P(E_t\mid X_t)$. Un HMM ha uno stato discreto a $S$ valori: transizione = matrice $\mathbf T$ ($T_{ij}=P(X_t=j\mid X_{t-1}=i)$), sensore = matrici diagonali $\mathbf O_t$. Compiti: filtraggio $P(X_t\mid e_{1:t})$, predizione $P(X_{t+k}\mid e_{1:t})$, smoothing $P(X_{t-k}\mid e_{1:t})$, spiegazione più probabile $\arg\max P(x_{1:t}\mid e_{1:t})$. Filtraggio ricorsivo: $\mathbf f_t=\alpha,\mathbf O_t\mathbf T^\top\mathbf f_{t-1}$ (predizione, poi aggiornamento). Mondo dell'ombrello: $\mathbf f_1=\langle0{,}818;\ 0{,}182\rangle$, $\mathbf f_2=\langle0{,}883;\ 0{,}117\rangle$. Senza normalizzare, $\mathbf s_t=\mathbf O_t\mathbf T^\top\mathbf s_{t-1}$ dà la verosimiglianza $P(e_{1:t})$.Ragionamento probabilistico nel tempo - catene di Markov, HMM, filtraggio e smoothing →): $$b'(s')=\alpha\,P(e\mid s')\sum_sP(s'\mid s,a)\,b(s),$$ dove $\alpha$ normalizza. Si scrive $b'=\text{FORWARD}(b,a,e)$: è deterministico perché $b$, $a$, $e$ sono dati.

Esempio. Tre stati $s_1,s_2,s_3$ in fila. L'azione "avanti" porta in avanti di una cella con probabilità $0{,}8$ e lascia fermi con $0{,}2$; da $s_3$ si resta in $s_3$. Il sensore dice "muro davanti" con probabilità $0{,}9$ in $s_3$ e $0{,}1$ in $s_1$ e $s_2$. Credenza iniziale $b=(\tfrac13,\tfrac13,\tfrac13)$, azione "avanti", osservazione "muro".

• Predizione $\sum_sP(s'\mid s,a)b(s)$: $s_1$: $0{,}2\cdot\tfrac13=0{,}0667$; $s_2$: $(0{,}8+0{,}2)\tfrac13=0{,}3333$; $s_3$: $(0{,}8+1)\tfrac13=0{,}6$.
• Aggiornamento con il sensore: $0{,}1\cdot0{,}0667=0{,}00667$; $0{,}1\cdot0{,}3333=0{,}03333$; $0{,}9\cdot0{,}6=0{,}54$. La somma è $0{,}58$ (è $P(e\mid a,b)$).
• Normalizzazione: $b'=(0{,}0115,\;0{,}0575,\;0{,}931)$.

Le probabilità di transizione tra credenze e la ricompensa $\rho(b,a)=\sum_sb(s)\sum_{s'}P(s'\mid s,a)R(s,a,s')$ definiscono un MDP osservabile sullo spazio delle credenze, la cui politica ottima è ottima anche per il POMDP. Però anche con pochi stati ci sono infinite credenze (sono numeri reali): si discretizza oppure si usano metodi approssimati, come point-based value iteration (PBVI), perché la soluzione esatta è in generale intrattabile.

Applicazioni. Un sistema di guida per persone con demenza durante il lavaggio delle mani (MDP con oltre 20 milioni di stati, 20 istruzioni vocali come azioni); un dispositivo per cercare oggetti a persone ipovedenti (POMDP con stati "oggetto in vista, passi, tappa" e azioni Sinistra, Destra, Su, Giù).

Errori tipici

• Applicare la regola "ritirarsi o rispondere" confrontando solo il guadagno immediato: l'utilità conta anche il futuro.
• Aggiornare gli stati uno alla volta usando valori già nuovi: in value iteration l'aggiornamento è simultaneo (usa solo $U_k$).
• Dimenticare che un urto contro un muro lascia nella stessa cella e contribuisce con $r+U(s)$ alla somma.
• Confondere ricompensa (locale) e utilità (globale).
• Usare $\gamma=1$ senza stati terminali raggiungibili: le utilità divergono.
• Pensare che policy iteration abbia il max nella valutazione: lì l'azione è fissa e il sistema è lineare.
• Dare la politica senza il passo finale $\arg\max_aQ(s,a)$ dopo value iteration.

Domande d'esame

1. Un'azione ha tre esiti con probabilità 0,5, 0,3, 0,2 e utilità 8, 1, 5; un'altra ha esiti 10 e −20 con probabilità 0,95 e 0,05. Quale sceglie il MEU? La prima vale $0{,}5\cdot8+0{,}3\cdot1+0{,}2\cdot5=5{,}3$; la seconda $0{,}95\cdot10+0{,}05\cdot(-20)=8{,}5$. Il MEU sceglie la seconda.
2. Quale differenza c'è tra value iteration e policy iteration? Value iteration applica l'aggiornamento di Bellman (con max) a tutti gli stati finché le utilità si stabilizzano, e ricava la politica alla fine; policy iteration alterna valutazione lineare di una politica fissa e miglioramento greedy, fino a politica stabile. Poche iterazioni ma più costose.
3. Perché in un POMDP non si può usare lo stato? Perché non è osservabile: si usa lo stato di credenza $b$, aggiornato con $b'(s')=\alpha P(e\mid s')\sum_sP(s'\mid s,a)b(s)$, e si risolve l'MDP sulle credenze.
4. In value iteration con $\gamma=0{,}9$ e $\varepsilon=0{,}01$, a quale soglia di $\delta$ ci si ferma? $\varepsilon(1-\gamma)/\gamma=0{,}01\cdot0{,}1/0{,}9=0{,}00111$.