Riepilogo Tecnico: Apprendimento per Imitazione Avversario Off-Policy Provabilmente Efficiente con Garanzie di Convergenza

Definizione del Problema

L'Apprendimento per Imitazione Avversario (AIL) inquadra l'apprendimento per imitazione come un gioco a due giocatori in cui un agente aggiorna la propria politica per eguagliare le prestazioni di un esperto, mentre un avversario aggiorna una funzione di ricompensa per massimizzare il divario di prestazioni tra i due. Gli algoritmi AIL standard richiedono dati on-policy (campioni generati dalla politica attuale dell'agente) per valutare l'aspettativa delle ricompense cumulative durante gli aggiornamenti della funzione di ricompensa. Questo requisito porta a una significativa inefficienza campionaria, poiché necessita di nuove interazioni con l'ambiente ad ogni passo di aggiornamento, rendendo l'approccio impraticabile in contesti in cui le interazioni sono costose o limitate.

Sebbene siano stati proposti metodi off-policy per riutilizzare i dati delle politiche precedenti per migliorare l'efficienza campionaria, essi introducono un errore di spostamento della distribuzione perché i dati non corrispondono più perfettamente alla distribuzione di visita stato-azione della politica corrente. Gli approoli AIL off-policy esistenti si affidano o al campionamento per importanza (che induce un'alta varianza) o a complesse trasformazioni di variabili che alterano la funzione obiettivo, spesso rinunciando alle garanzie teoriche di convergenza. La sfida centrale affrontata in questo lavoro è: È possibile garantire la convergenza dell'AIL off-policy e assicurare l'efficienza campionaria senza fare affidamento su tecniche esplicite di correzione off-policy come il campionamento per importanza?

Metodologia

Gli autori propongono un algoritmo AIL off-policy che combina il mirror descent basato su modello per gli aggiornamenti della politica con la gradiente ascent off-policy proiettata per gli aggiornamenti della ricompensa. L'innovazione chiave risiede nel controllo dell'errore di spostamento della distribuzione attraverso la selezione accurata del numero di politiche passate ($N$) i cui dati vengono riutilizzati durante gli aggiornamenti della ricompensa.

1. Aggiornamenti della Politica

L'algoritmo impiega un approccio di mirror descent basato su modello.

• Stima del Modello: La funzione di transizione degli stati $\hat{P}_h$ viene stimata empiricamente dagli incontri stato-azione.
• Ottimizzazione della Politica: La politica viene aggiornata utilizzando un passo di mirror descent regolarizzato con divergenza KL (Equazione 3). Questa regola di aggiornamento, derivata dai valori Q stimati, assicura che i cambiamenti della politica siano sufficientemente conservativi da limitare la distanza di Variazione Totale (TV) tra le politiche consecutive. Questa stabilità è cruciale per controllare lo spostamento della distribuzione negli aggiornamenti della ricompensa off-policy.

2. Aggiornamenti della Ricompensa

Invece di utilizzare solo i dati della politica corrente $\pi_{k-1}$, l'aggiornamento della ricompensa utilizza una miscela di dati provenienti dalle $N(k)$ politiche più recenti.

• Distribuzione di Miscela: L'algoritmo campiona da una distribuzione di miscela $d^{k-1, mix}_h = \sum_{n=1}^{N} \beta_n d^{k-n}_h$, dove $\beta_n$ sono pesi uniformi.
• Obiettivo: I parametri della ricompensa $\mu$ vengono aggiornati tramite gradiente ascent proiettato per massimizzare la perdita $L(\pi^{k-1, mix}, \mu) = J(\pi_E, \mu) - \frac{1}{N}\sum_{n=1}^N J(\pi_{k-n}, \mu)$.
• Controllo dell'Errore: L'analisi teorica (Lemma 4.2 e Teorema 4.3) dimostra che se gli aggiornamenti della politica sono sufficientemente piccoli (controllati dal passo $\sigma$), la divergenza tra la distribuzione di miscela e la distribuzione della politica corrente rimane limitata.

3. Framework Teorico

Il regret dell'algoritmo AIL è scomposto in regret della politica e regret della ricompensa (Lemma 3.2). Gli autori derivano i limiti per entrambi:

• Regret della Politica: Limitato da $\tilde{O}(\sqrt{H^4 S^2 A K})$ utilizzando l'aggiornamento di mirror descent.
• Regret della Ricompensa: Limitato da un termine che comprende il regret standard, un termine di errore indotto dagli aggiornamenti off-policy e un termine di errore di stima (Teorema 4.4).
• Risultato Principale (Teorema 4.5): Il regret totale è sublineare rispetto al numero di iterazioni $K$, a condizione che il numero di politiche riutilizzate $N(k)$ scali come $o(\sqrt{K})$. Nello specifico, se $N$ è fisso, la scalabilità ottimale è $N^* = \tilde{O}((S/(HAB))^{1/3})$.

Contributi Chiave

1. Garanzie di Convergenza senza Correzione: Il documento fornisce le prime garanzie teoriche di convergenza per un algoritmo AIL off-policy che non richiede tecniche di correzione off-policy (ad es., campionamento per importanza).
2. Analisi dell'Efficienza Campionaria: Gli autori stabiliscono che il riutilizzo dei campioni delle $o(\sqrt{K})$ politiche più recenti non mina la convergenza. Dimostrano che l'errore di spostamento della distribuzione è dominato dai benefici della maggiore disponibilità di dati, in particolare quando la dimensione dello spazio degli stati ($S$) è grande rispetto all'orizzonte ($H$) e allo spazio delle azioni ($A$).
3. Validazione Pratica: L'algoritmo è validato su compiti MiniGrid a spazio discreto e benchmark OpenAI Gym (MuJoCo) a spazio continuo, dimostrando che le varianti off-policy ($N > 1$) convergono più velocemente e richiedono meno campioni rispetto alle controparti on-policy ($N=1$).

Risultati Sperimentali

• MiniGrid (Discreto): Nei compiti EmptyRoom di varie dimensioni ($3\times3$, $5\times5$, $9\times9$), gli algoritmi off-policy con $N=32$ hanno raggiunto prestazioni da esperto con circa 1.000 interazioni, mentre l'algoritmo on-policy ($N=1$) ha richiesto l'intero orizzonte di 10.000 interazioni per convergere. I risultati hanno confermato che spazi di stato più grandi beneficiano di un $N$ maggiore.
• MuJoCo (Continuo): Nei compiti HalfCheetah, Hopper e Walker2d, gli algoritmi off-policy hanno costantemente superato la baseline on-policy. Sebbene l' $N$ ottimale variasse tra gli ambienti, sono stati osservati guadagni significativi anche con $N$ piccoli (ad es., $N=4$ o $N=16$).
• Osservazione: Gli esperimenti supportano la tesi teorica secondo cui l'AIL off-policy può ottenere una superiore efficienza campionaria, sebbene il numero ottimale di politiche riutilizzate dipenda dalle caratteristiche specifiche dell'ambiente.

Significato e Rivendicazioni

Il documento sostiene di colmare il divario tra la comprensione teorica e l'applicazione pratica dell'AIL off-policy. Mentre lavori precedenti avevano dimostrato il successo pratico dell'AIL off-policy, mancavano di rigorose prove di convergenza. Questo lavoro dimostra che:

• Supporto Teorico: È possibile garantire la convergenza per l'AIL off-policy semplicemente controllando lo spostamento della distribuzione attraverso aggiornamenti della politica conservativi e limitando il numero di politiche riutilizzate.
• Efficienza Campionaria: L' "errore" introdotto dai dati off-policy è teoricamente dimostrato essere superato dai benefici statistici di avere più dati, specialmente in spazi di stato ad alta dimensionalità.
• Semplicità: Il metodo proposto evita complesse tecniche di riduzione della varianza come il campionamento per importanza, offrendo un'alternativa più semplice e teoricamente fondata che si allinea con le osservazioni empiriche dell'efficienza campionaria nella pratica.

Gli autori notano con modestia che la loro analisi teorica assume impostazioni tabulari (estese ai modelli MDP lineari nell'appendice) e che l' $N$ ottimale nei contesti di deep RL (MuJoCo) potrebbe non allinearsi perfettamente con i limiti teorici del caso peggiore a causa della parametrizzazione delle reti neurali, tuttavia le tendenze delle prestazioni rimangono coerenti con la teoria.