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

Tuttavia, esiste una limitazione fondamentale. Nella policy iteration tradizionale, la fase di miglioramento della politica dipende dall'accesso a un modello completo dell'ambiente. In particolare, per aggiornare la politica, si utilizza 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 il reinforcement learning 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 a quello della funzione di valore di stato. Tutte le idee utilizzate per stimare i valori di stato possono essere applicate 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, è già possibile costruire un metodo simile all'iterazione delle politiche che non si basa su un modello. Per fare ciò, 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à visto, i metodi Monte Carlo richiedono tipicamente un gran numero di campioni per produrre stime ragionevolmente accurate. Se si segue una struttura simile all'iterazione delle politiche, questa inefficienza viene amplificata: dopo ogni miglioramento della politica, è necessario rieseguire la stima Monte Carlo per rivalutare la nuova politica — con conseguente notevole sovraccarico e apprendimento lento.

Un'alternativa più naturale è aggiornare la politica immediatamente dopo l'elaborazione di ogni episodio. Invece di attendere il completamento di una valutazione completa della politica, si consente all'agente di perfezionare il proprio comportamento episodio per episodio, utilizzando le stime più recenti dei valori d'azione.

Questo porta a un metodo che assomiglia maggiormente all'iterazione dei valori: 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 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 verrà spiegato perché questo rappresenta un problema e come può essere affrontato.