Un confronto tra i metodi Temporal-Difference(0) e Monte Carlo con α costante sul compito Random Walk

Confronto TD(0) e Monte Carlo con α costante sul Random Walk.

Immagine generata da Midjourney con un abbonamento a pagamento, che rispetta le condizioni commerciali generali [1].

Introduzione

I metodi di Monte Carlo (MC) e di Temporal-Difference (TD) sono entrambi tecniche fondamentali nel campo dell’apprendimento per rinforzo; risolvono il problema della previsione basandosi sull’esperienza acquisita interagendo con l’ambiente anziché sul modello dell’ambiente stesso. Tuttavia, il metodo TD è una combinazione di metodi MC e di Programmazione Dinamica (DP), differenziandosi dal metodo MC per quanto riguarda la regola di aggiornamento, il bootstrapping e il bias/varianza. I metodi TD sono anche dimostrati avere una migliore performance e una convergenza più rapida rispetto ai metodi MC nella maggior parte dei casi.

In questo post, confrontiamo TD e MC, o più specificamente, i metodi TD(0) e MC con α costante, su un semplice ambiente a griglia e su un ambiente di Random Walk [2] più completo. Sperando che questo post possa aiutare i lettori interessati all’Apprendimento per Rinforzo a comprendere meglio come ciascun metodo aggiorna la funzione di valore di stato e come le loro prestazioni differiscono nello stesso ambiente di test.

Implementeremo gli algoritmi e i confronti in Python, e le librerie utilizzate in questo post sono le seguenti:

python==3.9.16numpy==1.24.3matplotlib==3.7.1

La differenza tra TD e MC

L’introduzione di TD(0) e MC con α costante

Il metodo MC con α costante è un metodo MC regolare con un parametro di dimensione del passo α costante, e questo parametro costante aiuta a rendere la stima del valore più sensibile all’esperienza recente. Nella pratica, la scelta del valore α dipende da un compromesso tra stabilità e adattabilità. Di seguito è riportata l’equazione del metodo MC per l’aggiornamento della funzione di valore di stato al tempo t:

Il TD(0) è un caso speciale di TD(λ) che guarda solo un passo avanti ed è la forma più semplice di apprendimento TD. Questo metodo aggiorna la funzione di valore di stato con l’errore TD, la differenza tra il valore stimato dello stato e la ricompensa più il valore stimato dello stato successivo. Un parametro di dimensione del passo α costante funziona allo stesso modo del metodo MC sopra. Di seguito è riportata l’equazione del TD(0) per l’aggiornamento della funzione di valore di stato al tempo t:

In generale, la differenza tra i metodi MC e TD si verifica in tre aspetti:

  1. Regola di aggiornamento: I metodi MC aggiornano i valori solo dopo la fine dell’episodio; ciò potrebbe essere problematico se l’episodio è molto lungo, rallentando il programma, o nel caso di un compito continuo che non ha affatto episodi. Al contrario, il metodo TD aggiorna le stime dei valori ad ogni passo temporale; questo è un apprendimento online e può essere particolarmente utile nei compiti continui.
  2. Bootstrapping: Il termine “bootstrapping” nell’apprendimento per rinforzo si riferisce all’aggiornamento delle stime dei valori basato su altre stime dei valori. Il metodo TD(0) basa il suo aggiornamento sul valore dello stato successivo, quindi è un metodo di bootstrapping; al contrario, il MC non utilizza il bootstrapping in quanto aggiorna il valore direttamente dai rendimenti (G).
  3. Bias/Varianza: I metodi MC sono non tendenziosi poiché stimano il valore pesando i rendimenti effettivi osservati senza effettuare stime durante l’episodio; tuttavia, i metodi MC hanno una varianza elevata, specialmente quando il numero di campioni è basso. Al contrario, i metodi TD hanno dei bias perché utilizzano il bootstrapping, e il bias può variare in base all’implementazione effettiva; i metodi TD hanno una bassa varianza perché utilizzano la ricompensa immediata più la stima dello stato successivo, che attenua la fluttuazione che deriva dalla casualità delle ricompense e delle azioni.

Valutazione di TD(0) e MC con α costante su un semplice ambiente a griglia

Per rendere più semplice la differenza, possiamo creare un semplice ambiente di test Gridworld con due traiettorie fisse, eseguire entrambi gli algoritmi sull’ambiente creato fino alla convergenza e controllare come aggiornano i valori in modo diverso.

Innanzitutto possiamo configurare l’ambiente di test con i seguenti codici:

Figura 1 Sinistra: configurazione dell'ambiente. Destra: percorsi preimpostati. Fonte: figura dell'autore

La figura a sinistra mostra una semplice configurazione dell’ambiente Gridworld. Tutte le celle colorate rappresentano stati terminali; l’agente riceve una ricompensa +1 quando si muove nella cella rossa ma riceve una ricompensa -1 quando si muove nelle celle blu. Tutti gli altri spostamenti sulla griglia restituiscono una ricompensa di zero. La figura a destra indica due percorsi preimpostati: uno arriva alla cella blu mentre un altro si ferma alla cella rossa; l’intersezione dei percorsi aiuta a massimizzare la differenza di valore tra i due metodi.

Poi possiamo utilizzare le equazioni della sezione precedente per valutare l’ambiente. Non scontiamo il ritorno né la stima e impostiamo α su un valore piccolo come 1e-3. Quando la somma assoluta degli incrementi di valore è inferiore a una soglia di 1e-3, consideriamo i valori convergenti.

Il risultato della valutazione è il seguente:

Figura 2 Il risultato delle valutazioni TD(0) e MC con alpha costante. Fonte: figura dell'autore

Le diverse modalità di stima dei valori dei due algoritmi diventano abbastanza evidenti nell’immagine sopra. Il metodo MC è fedele ai ritorni del percorso, quindi i valori su ciascun percorso rappresentano direttamente come termina. Tuttavia, il metodo TD fornisce una migliore previsione, specialmente sul percorso blu: i valori sul percorso blu prima dell’intersezione indicano anche la possibilità di raggiungere la cella rossa.

Con questo caso minimo in mente, siamo pronti a passare a un esempio molto più complicato e cercare di scoprire la differenza di prestazioni tra i due metodi.

Il compito del Random Walk

Il compito del Random Walk è un semplice processo di ricompensa di Markov proposto da Sutton et al. per scopi di previsione TD e MC[2], come mostrano le immagini seguenti. In questo compito, l’agente parte dal nodo centrale C. L’agente fa un passo a destra o a sinistra con uguale probabilità su ogni nodo. Ci sono due stati terminali su entrambi i lati della catena. La ricompensa di entrare nell’estremità sinistra è 0 e di entrare nell’estremità destra è +1. Tutti i passi prima della terminazione generano una ricompensa di 0.

Figura 3 Random Walk. Fonte: figura dell'autore

E possiamo usare il seguente codice per creare l’ambiente Random Walk:

=====Test: verifica della configurazione dell'ambiente=====Collegamenti:        Nessuno ← Nodo A → Nodo BRicompensa:          0 ← Nodo A → 0Collegamenti:      Nodo A ← Nodo B → Nodo CRicompensa:          0 ← Nodo B → 0Collegamenti:      Nodo B ← Nodo C → Nodo DRicompensa:          0 ← Nodo C → 0Collegamenti:      Nodo C ← Nodo D → Nodo ERicompensa:          0 ← Nodo D → 0Collegamenti:      Nodo D ← Nodo E → NessunaRicompensa:          0 ← Nodo E → 1

Il valore effettivo per ogni nodo dell’ambiente con una politica casuale è [1/6, 2/6, 3/6, 4/6, 5/6]. Il valore è stato calcolato tramite la valutazione della politica con l’equazione di Bellman:

Il nostro compito qui è trovare quanto le stime dei valori prodotti da entrambi gli algoritmi si avvicinano al valore reale; possiamo assumere arbitrariamente che l’algoritmo produca una funzione di valore più vicina alla funzione di valore reale, misurata dall’errore quadratico medio radice mediato (RMS), indicando una migliore performance.

La Performance di TD(0) e MC con Costante-a sul Random Walk

Algoritmi

Con l’ambiente pronto, possiamo iniziare ad eseguire entrambi i metodi sull’ambiente Random Walk e confrontarne la performance. Prima diamo un’occhiata ad entrambi gli algoritmi:

Fonte: Algoritmo scritto in LaTeX dall'autore
Fonte: Algoritmo scritto in LaTeX dall'autore

Come accennato in precedenza, il metodo MC dovrebbe aspettare la fine dell’episodio per aggiornare i valori dalla coda della traiettoria, mentre il metodo TD aggiorna i valori in modo incrementale. Questa differenza porta ad un trucco quando si inizializza la funzione di valore di stato: in MC, la funzione di valore di stato non include gli stati terminali, mentre in TD(0), la funzione dovrebbe includere lo stato terminale con il valore 0 perché il metodo TD(0) guarda sempre un passo avanti prima della fine dell’episodio.

Implementazione

La selezione del parametro α in questa implementazione fa riferimento a quella proposta nel libro [2]; i parametri per il metodo MC sono [0.01, 0.02, 0.03, 0.04], mentre quelli per il metodo TD sono [0.05, 0.10, 0.15]. Mi sono chiesto perché l’autore non abbia scelto lo stesso set di parametri per entrambi gli algoritmi finché non ho eseguito il metodo MD con i parametri per TD: i parametri di TD sono troppo alti per il metodo MC e quindi non possono rivelare la migliore performance di MC. Pertanto, ci atteniamo alla configurazione del libro nella ricerca dei parametri. Ora, eseguiamo entrambi gli algoritmi per scoprire la loro performance sulla configurazione del Random Walk.

Risultato

Figura 4 Risultato del confronto degli algoritmi. Fonte: figura dell'autore

Il risultato dopo 100 esecuzioni del confronto è come mostrato nell’immagine sopra. Il metodo TD genera generalmente stime dei valori migliori rispetto ai metodi MC, e il TD con α = 0.05 può avvicinarsi molto al valore reale. Il grafico mostra anche che il metodo MC ha una maggiore varianza rispetto ai metodi TD, poiché le linee orchidea fluttuano più delle linee blu acciaio.

È importante notare che per entrambi gli algoritmi, quando α è (relativamente) alto, la perdita RMS scende prima e poi risale di nuovo. Tale fenomeno è dovuto all’effetto combinato dell’inizializzazione del valore e del valore di α. Abbiamo inizializzato un valore relativamente alto di 0.5, che è più alto del valore reale di Nodo A e Nodo B. Poiché la politica casuale ha una probabilità del 50% di scegliere un passo “sbagliato”, che porta l’agente lontano dallo stato terminale corretto, un valore α più alto enfatizzerà anche i passi sbagliati e allontanerà il risultato dal valore reale.

Ora proviamo a ridurre il valore iniziale a 0.1 ed eseguiamo nuovamente il confronto, vediamo se il problema si allevia:

Figura 5 Risultato del confronto degli algoritmi con valore iniziale 0.1. Fonte: figura dell'autore

Il valore iniziale più basso aiuta chiaramente a mitigare il problema; non ci sono effetti evidenti di “scendere, poi salire”. Tuttavia, l’effetto collaterale di un valore iniziale più basso è che l’apprendimento è meno efficiente, poiché la perdita RMS non scende mai al di sotto di 0.05 dopo 150 episodi. Pertanto, c’è un compromesso tra il valore iniziale, il parametro e la performance dell’algoritmo.

Allenamento Batch

Un’ultima cosa che voglio menzionare in questo post è il confronto dell’allenamento batch su entrambi gli algoritmi.

Consideriamo la seguente situazione: abbiamo accumulato solo un numero limitato di esperienze sul compito Random Walk, o possiamo eseguire solo un certo numero di episodi a causa delle limitazioni di tempo e di calcolo. L’idea dell’aggiornamento batch [2] è stata proposta per affrontare tale situazione sfruttando appieno le traiettorie esistenti.

L’idea dell’allenamento batch è quella di aggiornare i valori su un insieme di traiettorie ripetutamente fino a quando i valori convergono a una risposta. I valori verranno aggiornati solo una volta che tutte le esperienze del batch saranno completamente elaborate. Implementiamo l’allenamento batch per entrambi gli algoritmi sull’ambiente Random Walk per vedere se il metodo TD continua a funzionare meglio del metodo MC.

Risultato

Figura 6 Il risultato dell'allenamento batch. Fonte: figura dell'autore

Il risultato dell’allenamento batch mostra che il metodo TD funziona ancora meglio del metodo MC con esperienza limitata, e la differenza tra le prestazioni dei due algoritmi è piuttosto evidente.

Conclusioni

In questo post, abbiamo discusso la differenza tra il metodo MC con α costante e i metodi TD(0) e abbiamo confrontato le loro prestazioni sul compito Random Walk. Il metodo TD sovrasta i metodi MC in tutti i test di questo post, quindi considerare il TD come un metodo per compiti di apprendimento per rinforzo è una scelta preferibile. Tuttavia, ciò non significa che il TD sia sempre migliore del MC, poiché quest’ultimo ha un vantaggio più evidente: nessun bias. Se ci troviamo di fronte a un compito che non tollera i bias, allora il MC potrebbe essere una scelta migliore; altrimenti, il TD potrebbe gestire meglio i casi generali.

Riferimenti

[1] Midjourney Termini di Servizio: https://docs.midjourney.com/docs/terms-of-service

[2] Sutton, Richard S., e Andrew G. Barto. Reinforcement learning: An introduction. MIT Press, 2018.

Il mio repository GitHub di questo post: [Link].