On the Variance of Temporal Difference Learning and its Reduction Using Control Variates

Sintesi Tecnica: Sulla Varianza dell'Apprendimento Temporal Difference e la sua Riduzione tramite Variabili di Controllo

Enunciato del Problema
La valutazione della policy è una sfida fondamentale nell'apprendimento per rinforzo (RL). Mentre i metodi Monte Carlo (MC) forniscono stime non distorte delle funzioni di valore, essi soffrono di un'elevata varianza a causa della necessità di mediare su intere traiettorie. Al contrario, l'apprendimento Temporal Difference (TD) utilizza il bootstrapping (aggiornare le stime basandosi su altre stime) per ridurre la varianza, ma ciò introduce distorsione (bias). Il meccanismo preciso attraverso cui il TD riduce la varianza, in particolare nel regime online, e come questo si confronti asintoticamente con l'MC, è stato oggetto di un dibattito sfumato. Inoltre, sebbene la Direct Advantage Estimation (DAE) abbia mostrato un successo empirico nel deep RL, la sua giustificazione teorica riguardo alla riduzione della varianza è stata limitata alle proprietà di convergenza piuttosto che a un'analisi rigorosa dei suoi limiti di varianza rispetto al TD standard.

Metodologia
Gli autori analizzano la varianza dell'apprendimento TD multi-step all'interno di un contesto a fasi (sincrono) utilizzando rappresentazioni tabulari. Questo setting astrae le complessità associate agli aggiornamenti asincroni e alle approssimazioni stocastiche, permettendo un isolamento più chiaro dei meccanismi di varianza.

1. Decomposizione della Varianza: Il documento deriva una relazione di ricorrenza per la varianza degli aggiornamenti TD multi-step. Espandendo questa ricorrenza, gli autori confrontano la varianza asintotica degli stimatori TD rispetto a quelli MC.
2. Framework delle Variabili di Controllo: Gli autori inquadrano la funzione di vantaggio ($A^\pi$) come una variabile di controllo per la valutazione della policy. Utilizzano il concetto di variabili di controllo regolate per regressione, dove la funzione di vantaggio viene stimata simultaneamente alla funzione di valore per minimizzare la varianza dello stimatore del rendimento.
3. Direct Advantage Estimation (DAE): Il documento analizza la DAE (Pan et al., 2022) come un problema di minimi quadrati vincolato. Trattando le stime della funzione di vantaggio come parametri di disturbo in un framework di regressione, gli autori riformulano la regola di aggiornamento DAE per mostrare esplicitamente la sua struttura come variabile di controllo regolata per regressione.
4. Validazione Empirica: Le affermazioni teoriche sono illustrate utilizzando ambienti Chain MDP accuratamente progettati. Questi esperimenti variano il grado di stocasticità (mascheramento del reward, transizioni "sticky") e la copertura stato-azione per testare i comportamenti asintotici di MC, TD e DAE in diverse condizioni.

Contributi Chiave

1. Limite Asintotico della Varianza di TD: Gli autori dimostrano che, sia in contesti a fasi (sincroni) che IID (asincroni), il limite superiore della varianza asintotica dell'apprendimento TD multi-step è dato dalla varianza dei metodi Monte Carlo.

   • Meccanismo: Il documento identifica che il TD riduce la varianza non solo tramite il compromesso bias-varianza, ma aggregando efficacemente un pool più ampio di traiettorie indipendenti. Quando gli stati di bootstrapping sono diversificati e debolmente correlati, la media dei loro valori riduce la varianza. Al contrario, se gli stati di bootstrapping sono identici (altamente correlati), la capacità di riduzione della varianza del TD diminuisce e si avvicina asintoticamente alla varianza dell'MC.
   • Effetto Orizzonte: Per un numero fisso di campioni, gli aggiornamenti a orizzonte più breve (k minore) comportano meno varianza rispetto agli aggiornamenti a singolo orizzonte lungo.

2. DAE come Variabile di Controllo Regolata per Regressione: Il documento dimostra che la funzione di vantaggio può servire come variabile di controllo per gli stimatori MC. Stabilisce inoltre che la Direct Advantage Estimation (DAE) è una forma di variabile di controllo regolata per regressione che stima simultaneamente le funzioni di valore e di vantaggio.

   • Limite di Varianza: Nel limite dei grandi campioni, la DAE raggiunge un limite superiore di varianza più stretto rispetto allo standard TD. Nello specifico, la varianza della DAE è limitata dalla varianza di uno stimatore MC regolato dalla funzione di vantaggio (MC-A), che è a sua volta inferiore o uguale alla varianza dell'MC standard.

3. Illustrazioni Empiriche:

   • In ambienti deterministici dove gli stati di bootstrapping sono identici, il TD non riesce a ridurre la varianza rispetto all'MC, confermando la dipendenza teorica dalla diversità delle traiettorie.
   • In ambienti con transizioni stocastiche, il TD mostra il previsto compromesso bias-varianza, e la DAE converge rapidamente (similmente alle iterazioni di Bellman) perché la funzione di vantaggio spiega completamente la varianza.
   • Negli scenari di reward masking (dove la varianza del reward non può essere spiegata dalle azioni), le stime del vantaggio della DAE non possono eliminare completamente la varianza, risultando in un leggero scarto asintotico rispetto alle iterazioni di Bellman, pur superando comunque il TD.
   • In situazioni a bassa copertura (spazi di azione sottocampionati), la DAE può soffrire di un bias dovuto ai piccoli campioni a causa di stime del vantaggio inaffidabili, eppure converge comunque a un Errore Quadratico Medio (MSE) inferiore rispetto al TD, suggerendo robustezza anche con variabili di controllo imperfette.

Risultati e Significato
Il documento fornisce una spiegazione teorica rigorosa delle capacità di riduzione della varianza del bootstrapping, andando oltre l'intuitivo "compromesso bias-varianza" per proporre un meccanismo basato sull'aggregazione delle traiettorie. Chiarisce che la superiorità del TD rispetto all'MC è condizionata dalla diversità degli stati di bootstrapping.

Inoltre, il lavoro offre una base teorica per la DAE, spiegando il suo successo empirico nel deep RL inquadrandola come un metodo di variabile di controllo. I risultati suggeriscono che l'utilizzo della funzione di vantaggio come variabile di controllo può teoricamente raggiungere limiti di varianza più stretti rispetto al TD standard.

Limitazioni e Ambito
Gli autori rilevano diverse limitazioni:

• I risultati teorici sono derivati per contesti a fasi e IID; la generalizzazione a schemi di campionamento Markoviani realistici rimane una questione aperta.
• L'analisi si concentra sulla riduzione della varianza; la DAE comporta costi computazionali aggiuntivi (risoluzione di minimi quadrati) e requisiti di memoria superiori.
• I limiti stretti della varianza per la DAE si basano su un'approssimazione a grandi campioni in cui i coefficienti della variabile di controllo sono ottimali. Sebbene i risultati empirici suggeriscano benefici nei regimi di piccoli campioni, un'analisi rigorosa del bias nei piccoli campioni della DAE è lasciata a lavori futuri.

Il documento conclude che la comprensione dell'aggregazione di traiettorie indipendenti è centrale per la riduzione della varianza del TD, e che la regressione della variabile di controllo (tramite DAE) offre una via fondata per ridurre ulteriormente la varianza nella valutazione della policy.