Sostituendo la fase di valutazione della politica nell'algoritmo standard di iterazione della politica con le tecniche di stima Monte Carlo descritte nel capitolo precedente, è già possibile derivare una nuova variante dell'iterazione della politica—una che si basa su esperienza campionata invece della programmazione dinamica.

Tuttavia, esiste una limitazione fondamentale. Nell'iterazione della politica tradizionale, la fase di miglioramento della politica dipende dall'accesso a un modello completo dell'ambiente. In particolare, per aggiornare la politica, utilizziamo la seguente espressione:

Questa equazione presuppone che si conoscano le probabilità di transizione $p(s', r | s, a)$. Ma questo è proprio il problema: i metodi Monte Carlo sono progettati per contesti model-free, in cui la dinamica di transizione dell'ambiente è sconosciuta. Se fosse disponibile un modello completo, converrebbe utilizzare la programmazione dinamica in ogni fase, inclusa la valutazione della politica, poiché sarebbe più efficiente e precisa.

Pertanto, sebbene sostituire i metodi Monte Carlo per la stima dei valori sia un passo verso l'apprendimento per rinforzo model-free, è necessario anche trovare un modo per eseguire il miglioramento della politica senza fare affidamento sulla conoscenza del modello. Questo richiede il passaggio dalla funzione di valore di stato alla funzione di valore d'azione.

Perché i valori d'azione?

Utilizzando i valori d'azione, è possibile eseguire il miglioramento della politica senza la necessità di un modello dell'ambiente. Invece di fare affidamento sulle probabilità di transizione per calcolare i ritorni attesi, si possono selezionare direttamente le azioni che sembrano offrire il valore più alto. Il passo di miglioramento della politica diventa quindi:

Ed è semplice dimostrare che la nuova politica non è peggiore della precedente, poiché il teorema di miglioramento della politica può ancora essere applicato:

E, come nella programmazione dinamica, questo teorema garantisce che $\pi_{k+1}$ sia migliore di $\pi_k$, oppure che siano entrambe uguali e ottimali.

Stima della Funzione di Valore d'Azione

Il processo di stima è quasi identico alla funzione di valore di stato. Tutte le idee utilizzate per stimare i valori di stato possono essere impiegate per stimare i valori d'azione.

Pseudocodice

In questo modo, con un numero sufficiente di iterazioni, i valori d'azione stimati dovrebbero avvicinarsi ai veri valori d'azione.

Con questo approccio, è già possibile costruire un metodo simile all'iterazione di politica che non si basa su un modello. Per farlo, si sostituiscono le fasi di valutazione della politica e miglioramento della politica con i processi descritti sopra.

Ottimizzazione

Sebbene la fase di valutazione possa essere eseguita utilizzando la stima Monte Carlo come descritto, tende a essere computazionalmente inefficiente. Come già osservato, i metodi Monte Carlo richiedono generalmente un gran numero di campioni per produrre stime ragionevolmente accurate. Se si segue una struttura simile all'iterazione di politica, questa inefficienza viene amplificata: dopo ogni miglioramento della politica, è necessario rieseguire la stima Monte Carlo per rivalutare la nuova politica — comportando un notevole sovraccarico e un apprendimento lento.

Un'alternativa più naturale consiste nell'aggiornare la politica immediatamente dopo l'elaborazione di ogni episodio. Invece di attendere il completamento di un intero ciclo di valutazione della politica, si consente all'agente di affinare il proprio comportamento episodio dopo episodio, utilizzando le stime più recenti dei valori d'azione.

Questo porta a un metodo che assomiglia maggiormente all'iterazione di valore: combinando aspetti di valutazione e miglioramento in un unico passaggio. Ciò aumenta l'efficienza del campionamento, incrementando la velocità di calcolo.

Pseudocodice

Questo algoritmo segue un framework GPI, poiché include i passaggi di valutazione della politica e miglioramento della politica, ed è chiamato controllo Monte Carlo. L'unico grande svantaggio di questa specifica implementazione è l'assunzione di exploring starts. Nei prossimi capitoli vedrai perché questo rappresenta un problema e come può essere affrontato.