R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimes

Sintesi Tecnica: R-GTD: Un'Analisi Geometrica dell'Apprendimento Gradient Temporal-Difference in Regimi Singolari

Enunciato del Problema
Gli algoritmi di apprendimento Gradient Temporal-Difference (GTD), in particolare GTD2, sono metodi consolidati per la valutazione di politiche off-policy con approssimazione lineare di funzioni. Essi minimizzano l'Errore di Bellman Proiettato al Quadrato Medio (MSPBE) per trovare un'approssimazione della funzione valore che soddisfi l'equazione di Bellman all'interno di uno spazio di caratteristiche. Tuttavia, le garanzie teoriche di convergenza dei metodi GTD esistenti si basano su un'assunzione restrittiva: la Matrice di Interazione delle Caratteristiche (FIM), definita come $\Phi^\top D_\beta (\gamma P^\pi - I) \Phi$, deve essere non singolare. Nella pratica, la FIM può diventare singolare o quasi singolare (mal condizionata), portando a instabilità, divergenza o prestazioni degradate. Sebbene lavori precedenti abbiano tentato di affrontare questo problema tramite regolarizzazione, le loro garanzie teoriche dipendono spesso da altre condizioni altamente restrittive, come la restrizione della soluzione ottimale all'origine o l'assunzione di non singolarità globale per derivare limiti di errore. Inoltre, la relazione geometrica tra le soluzioni regolarizzate e l'insieme delle soluzioni originali di GTD2 in regimi singolari rimane inesplorata.

Metodologia
Gli autori propongono R-GTD (Gradient Temporal-Difference Regolarizzato), un nuovo algoritmo derivato da una riformulazione dell'obiettivo di ottimizzazione. La metodologia fondamentale comprende i seguenti passaggi:

1. Riformulazione dell'Obiettivo: Gli autori estendono il problema di ottimizzazione vincolata di GTD2 introducendo una variabile di slack ausiliaria $w$ e un termine di penalità quadratica. Ciò porta a un problema di ottimizzazione regolarizzato (Problema 4) che minimizza una somma pesata dell'errore di Bellman proiettato e di un termine che coinvolge la variabile ausiliaria.
2. Formulazione a Punto di Sella: Questo problema vincolato viene riformulato come un problema di punto di sella min-max convesso-concavo (Problema 5) utilizzando una funzione Lagrangiana. Si dimostra che la Lagrangiana è fortemente convessa nelle variabili primali ($\theta, w$) e concava nella variabile duale ($\lambda$), garantendo l'esistenza di un unico punto di sella anche quando la FIM è singolare.
3. Derivazione dell'Algoritmo: Applicando le Dinamiche del Gradiente Primal-Dual (PDGD) alla Lagrangiana, gli autori derivano le regole di aggiornamento di R-GTD (Algoritmo 1). Queste regole incorporano il campionamento per importanza per i dati off-policy e aggiornano tre parametri: i pesi della funzione valore ($\theta$), la variabile ausiliaria ($w$) e la variabile duale ($\lambda$).
4. Analisi Geometrica: Il documento fornisce un'analisi geometrica rigorosa del comportamento della soluzione. Caratterizza la soluzione R-GTD come una perturbazione dell'insieme delle soluzioni GTD2. Nello specifico, analizza il comportamento limite al tendere del parametro di regolarizzazione $c \to \infty$, distinguendo tra casi non singolari e singolari.

Contributi Chiave
Il documento apporta tre contributi principali:

• Rimozione delle Assunzioni di Non Singolarità: R-GTD garantisce la convergenza a una soluzione unica senza richiedere che la FIM sia non singolare. A differenza dei metodi regolarizzati precedenti che impongono condizioni aggiuntive restrittive per gestire le singolarità, R-GTD ottiene questo risultato attraverso la sua specifica formulazione senza assunzioni extra.
• Caratterizzazione Geometrica e Limiti di Errore: Gli autori forniscono un'analisi geometrica dettagliata del regime singolare. Stabiliscono limiti di errore espliciti tra la soluzione R-GTD e la soluzione proiettata vera. Nel caso singolare, dimostrano che la soluzione R-GTD converge alla proiezione ortogonale dell'insieme delle soluzioni GTD2 sul complemento del nucleo della matrice $G = M^\top B^{-1} M$. Ciò chiarisce esattamente quale soluzione all'interno dell'insieme affine GTD2 viene selezionata dalla regolarizzazione.
• Validazione Empirica: L'algoritmo è validato in contesti in cui la FIM è strettamente singolare. Gli esperimenti dimostrano che R-GTD converge in modo coerente a una soluzione unica di punto di sella con maggiore stabilità rispetto a GTD2 e ad altre linee di base regolarizzate (ad esempio, Ghiassian et al., 2020; Yu, 2017).

Risultati

• Convergenza: L'analisi teorica conferma che le dinamiche in tempo continuo di R-GTD convergono globalmente a un unico punto di sella. Utilizzando il metodo dell'Equazione Differenziale Ordinaria (ODE), si dimostra che le iterazioni stocastiche dell'Algoritmo 1 convergono a questa soluzione con probabilità uno.
• Limiti di Errore: Nel caso non singolare, l'errore tra la soluzione R-GTD e la soluzione GTD2 è limitato da $O(1/c)$. Nel caso singolare, la soluzione R-GTD converge a un elemento specifico dell'insieme affine delle soluzioni GTD2 (quello ortogonale al nucleo di $G$) con un limite di errore di $O(1/c)$.
• Prestazioni Sperimentali: Negli esperimenti che coinvolgono MDP singolari, il controesempio di Baird e ambienti stocastici (Frozen Lake), R-GTD sopprime in modo coerente la componente del nucleo che causa instabilità nel GTD2 standard. Raggiunge un errore finale inferiore e una varianza ridotta rispetto ai metodi di base, in particolare quando la FIM è mal condizionata. L'analisi di sensibilità suggerisce che valori intermedi del parametro di regolarizzazione $c$ (ad esempio, $c \in [1, 4]$) offrono il miglior compromesso tra stabilità e bias.

Significato
Il documento afferma che R-GTD colma un vuoto teorico nella comprensione dell'apprendimento GTD in condizioni singolari. Rimuovendo l'assunzione di non singolarità, fornisce un quadro robusto per la valutazione off-policy in scenari in cui le interazioni delle caratteristiche sono degenerate. L'analisi geometrica offre una comprensione precisa di come la regolarizzazione selezioni una soluzione unica dall'insieme potenzialmente infinito di soluzioni GTD2, garantendo stabilità senza sacrificare la struttura teorica fondamentale di GTD2. Gli autori notano che l'analisi attuale è limitata all'approssimazione lineare di funzioni e alla convergenza asintotica, lasciando l'approssimazione non lineare e le garanzie a tempo finito come direzioni per lavori futuri.