Come noto, 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 (move to $s_1$, move to $s_2$), la funzione di valore dello stato potrebbe essere definita così:

Questo può essere risolto utilizzando tecniche standard di 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 iniziali arbitrari a tutti gli stati, eccetto per gli stati terminali, che vengono 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 che contiene 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 del backup in-place è preferito perché richiede meno memoria e converge più rapidamente, grazie all'utilizzo immediato delle stime più recenti.

Quando interrompere l'aggiornamento?

Nella valutazione iterativa della policy, non esiste un punto esatto in cui l'algoritmo dovrebbe fermarsi. 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 soglia piccola $\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