Iniziamo rivisitando un concetto familiare: la funzione di valore di stato, indicata come $v_\pi(s)$. Può essere definita come

L'obiettivo di questo capitolo è stimare questa funzione a partire dai dati, assumendo di avere una politica fissata $\pi$ ma senza accesso al modello dell'ambiente.

Stima Monte Carlo

I metodi Monte Carlo affrontano questo compito di stima campionando episodi di esperienza secondo la politica $\pi$, utilizzando poi questi campioni per ottenere stime empiriche di $v_\pi(s)$.

In generale, il processo può essere suddiviso nei seguenti passaggi:

1. Generazione di un episodio utilizzando la politica $\pi$;
2. Salvataggio del valore di ritorno ottenuto per ogni stato che compare nell'episodio;
3. Ripetizione dei passaggi 1-2 per un certo periodo;
4. Calcolo dei nuovi valori mediando i ritorni per ciascuno stato.

Raccolta dei ritorni

La stima Monte Carlo della funzione di valore richiede la raccolta dei ritorni dagli episodi generati. Per calcolare questi ritorni, si possono utilizzare due approcci principali:

• First-visit: per ogni stato $s$ incontrato in un episodio, viene considerato solo il ritorno successivo alla sua prima occorrenza. Le occorrenze successive dello stesso stato all'interno dello stesso episodio vengono ignorate ai fini della stima;
• Every-visit: viene utilizzata ogni occorrenza di uno stato $s$ all'interno di un episodio. Ovvero, il ritorno successivo a ciascuna visita allo stato viene incluso nella stima, anche se lo stato appare più volte nello stesso episodio.

Esplorazione degli inizi

Immagina un mondo semplice unidimensionale rappresentato da una linea che si estende da -10 a +10. L'agente inizia dalla posizione 0 e la sua politica attuale stabilisce che si muove sempre verso destra a ogni passo temporale.

Se proviamo a generare episodi sotto questa politica, cosa succede? L'agente si muoverà continuamente verso l'estremità positiva della linea — visitando stati come 1, 2, 3, e così via — ma non visiterà mai stati negativi. Di conseguenza, non possiamo stimare le funzioni di valore per gli stati a sinistra dell'origine, semplicemente perché l'agente non li sperimenta mai.

Quindi il problema principale è: se alcune parti dello spazio degli stati non vengono mai esplorate, le loro stime di valore rimarranno inaccurate o non definite. Una soluzione comune a questo problema è l'uso degli exploring starts.

Con gli exploring starts, ogni episodio non inizia da uno stato iniziale fisso come 0, ma da uno stato selezionato casualmente. Una volta iniziato l'episodio, l'agente segue la sua politica attuale come di consueto. Nel tempo, iniziando da molti punti diversi nello spazio degli stati, l'agente è in grado di visitare tutti gli stati — non solo quelli verso cui la sua politica lo condurrebbe naturalmente. Questo permette al metodo Monte Carlo di produrre stime di valore più accurate e complete per l'intero spazio degli stati.

Pseudocodice

Questo pseudocodice utilizza l'approccio every-visit insieme agli exploring starts.