Come già saprai, una funzione di valore dello stato di una data policy può essere determinata risolvendo un'equazione di Bellman:

Se si dispone di un modello completo dell'ambiente (cioè, probabilità di transizione e ricompense attese note per tutte le coppie stato-azione), le uniche variabili sconosciute che rimangono nell'equazione sono i valori degli stati. Pertanto, l'equazione sopra può essere riformulata come un sistema di $|S|$ equazioni lineari con $|S|$ incognite.

Ad esempio, se un MDP ha 2 stati ($s_1$, $s_2$) e 2 azioni (muoversi verso $s_1$, muoversi verso $s_2$), la funzione di valore dello stato potrebbe essere definita così:

Questo sistema può essere risolto utilizzando le tecniche standard dell'algebra lineare.

Una soluzione unica per tale sistema lineare è garantita se almeno una delle seguenti condizioni è soddisfatta:

• Il fattore di sconto soddisfa $γ < 1$;
• La politica $\pi$, se seguita da qualsiasi stato $s$, garantisce che l'episodio termini eventualmente.

Valutazione Iterativa della Politica

La soluzione può essere calcolata direttamente, ma un approccio iterativo è più comunemente utilizzato per la sua facilità di implementazione. Questo metodo inizia assegnando valori arbitrari a tutti gli stati, eccetto per gli stati terminali, che sono impostati a 0. I valori vengono poi aggiornati iterativamente utilizzando l'equazione di Bellman come regola di aggiornamento:

La funzione di valore di stato stimata $v_k$ converge infine alla vera funzione di valore di stato $v_\pi$ quando $k \to \infty$ se $v_\pi$ esiste.

Strategie di backup del valore

Durante l'aggiornamento delle stime di valore, le nuove stime vengono calcolate sulla base dei valori precedenti. Il processo di conservazione delle stime precedenti è noto come backup. Esistono due strategie comuni per eseguire i backup:

• Backup completo: questo metodo prevede la memorizzazione delle nuove stime in un array separato, distinto da quello contenente i valori precedenti (di backup). Di conseguenza, sono necessari due array: uno per mantenere le stime precedenti e un altro per memorizzare i nuovi valori calcolati;
• Backup in-place: questo approccio mantiene tutti i valori all'interno di un unico array. Ogni nuova stima sostituisce immediatamente il valore precedente. Questo metodo riduce l'utilizzo della memoria, poiché è necessario un solo array.

Generalmente, il metodo backup in-place è preferito perché richiede meno memoria e converge più rapidamente, grazie all'utilizzo immediato delle stime più recenti.

Quando interrompere gli aggiornamenti?

Nell'iterative policy evaluation, non esiste un punto esatto in cui l'algoritmo debba essere interrotto. Sebbene la convergenza sia garantita al limite, continuare i calcoli oltre un certo punto è inutile nella pratica. Un criterio di arresto semplice ed efficace consiste nel monitorare la differenza assoluta tra le stime di valore consecutive, $|v_{k+1}(s) - v_k(s)|$, e confrontarla con una piccola soglia $\theta$. Se, dopo un ciclo completo di aggiornamento (in cui i valori di tutti gli stati vengono aggiornati), nessuna variazione supera $\theta$, il processo può essere terminato in sicurezza.

Pseudocodice