Efficient Hypergradient Descent for Inverse Reinforcement Learning

Sintesi Tecnica: Discesa del Gradiente dell'Ipergradiente Efficiente per l'Apprendimento per Rinforzo Inverso

Definizione del Problema
L'Apprendimento per Rinforzo Inverso (IRL) mira a recuperare una funzione di ricompensa dalle dimostrazioni di un esperto, tale che la politica ottimale sotto tale ricompensa riproduca il comportamento osservato. Gli autori si concentrano sulla Maximum-Likelihood IRL (ML-IRL), che può essere formulata come un problema di ottimizzazione bi-livello. Il livello interno ottimizza una politica regolarizzata dall'entropia sotto una ricompensa appresa $r_\phi$, mentre il livello esterno minimizza la discrepanza (specificamente, la divergenza KL) tra la politica indotta e i dati dell'esperto.

Il principale collo di bottiglia computazionale nel risolvere questo problema bi-livello tramite differenziazione implicita è il requisito di calcolare l'ipergradiente. Esplicitamente, la costruzione dell'Essia richiede una memoria quadratica ($O(d_\theta^2)$), mentre le approssimazioni iterative (ad esempio, gradienti coniugati) possono essere computazionalmente costose e sensibili al condizionamento. Sebbene sia stata proposta la Natural Hypergradient Descent (NHGD) per sostituire l'Essia con un surrogato della matrice di informazione di Fisher, la NHGD standard assume una distribuzione dei dati fissa. Nella ML-IRL, l'obiettivo interno implica una divergenza KL inversa su una distribuzione di traiettorie indotta dalla politica, rendendo la diretta applicazione della NHGD non banale.

Metodologia
Il documento propone un metodo per calcolare efficientemente l'ipergradiente per la ML-IRL sfruttando la struttura geometrica del problema interno e impiegando lo sketching di matrici.

1. Equivalenza Fisher-Essia: Gli autori dimostrano che, sotto l'esatta ottimalità interna e la realizzabilità (dove la classe di politiche è sufficientemente ricca da modellare perfettamente la distribuzione dell'esperto), l'Essia dell'obiettivo interno è proporzionale alla matrice di informazione di Fisher delle traiettorie scontate ($F_\theta$). Nello specifico, $\nabla^2_\theta L_{inner} = \alpha F_\theta$. Ciò consente che il prodotto vettore-inversa-Essia richiesto per l'ipergradiente sia sostituito da un prodotto vettore-inversa-Fisher.
2. Stima dell'Ipergradiente: Il metodo decompone il calcolo dell'ipergradiente in tre componenti:
   • Il gradiente esterno rispetto ai parametri della politica.
   • La soluzione di un sistema lineare smorzato che coinvolge la matrice di Fisher e il gradiente esterno.
   • Un termine di derivata mista che coinvolge il gradiente della ricompensa e la soluzione del sistema lineare.
3. Streaming Spectral Sketching (SCFD): Per evitare il costo di memoria $O(d_\theta^2)$ associato allo stoccaggio della densa matrice di Fisher, gli autori approssimano il prodotto vettore-inversa-Fisher richiesto utilizzando uno sketch Streaming Spectral Compensation Frequent Directions (SCFD). Invece di materializzare la matrice di Fisher, l'algoritmo trasmette vettori di punteggio della politica (policy-score) dalle traiettorie dell'agente in uno sketch compatto di dimensione $m$. Ciò riduce la complessità di stoccaggio a $O(md_\theta)$. Lo sketch viene quindi utilizzato per risolvere approssimativamente il sistema lineare smorzato.

Contributi Chiave

• Derivazione Teorica: Il documento deriva stimatori basati su campioni per l'ipergradiente implicito della ML-IRL e dimostra che l'Essia interna è proporzionale alla matrice di informazione di Fisher al raggiungimento di un ottimo interno realizzabile. Questo è presentato come la prima applicazione di questa identità per il calcolo dell'ipergradiente implicito nella ML-IRL.
• Solver Scalabile: Gli autori propongono un solver basato su SCFD che trasmette vettori di punteggio della politica. Questo approccio evita la costruzione della matrice di punteggio o della densa matrice di Fisher, riducendo significativamente i requisiti di memoria.
• Validazione Empirica: Il metodo è valutato rispetto a un baseline di ML-IRL a singolo ciclo (single-loop) a primo ordine e a un solver Fisher esplicito in ambienti di controllo discreti (CartPole) e continui (LQR).

Risultati
Gli esperimenti sono stati condotti sotto budget computazionali corrispondenti (limite di 24 ore di addestramento) con architetture e ottimizzazione degli iperparametri identiche.

• Performance della Politica: I metodi basati su Fisher hanno raggiunto una qualità della politica competitiva. Su CartPole, tutti i metodi hanno raggiunto i rendimenti dell'esperto. Su LQR, la ML-IRL a singolo ciclo ha ottenuto il miglior Negative Log-Likelihood (NLL) della politica e il miglior rendimento dell'ambiente, sebbene il margine rispetto al metodo "Fisher with Sketching" sia stato ridotto.
• Classificazione della Ricompensa: I metodi basati su Fisher hanno dimostrato una forte qualità nella classificazione della ricompensa. Su LQR, il metodo "Fisher with Sketching" ha ottenuto la RankCorrelation più alta (0.972) tra i rendimenti delle traiettorie appresi e quelli reali (ground-truth), superando sia il baseline a singolo ciclo che il solver Fisher esplicito.
• Efficienza:
  • Memoria: Lo sketching ha fornito il beneficio più significativo nell'ambiente LQR ad alta dimensionalità, riducendo l'uso di memoria di picco fino a 1.31$\times$ rispetto al solver Fisher esplicito.
  • Velocità: Su CartPole, lo sketching ha prodotto un'accelerazione di 1.29$\times$. Su LQR, dimensioni moderate dello sketch (ad esempio, $m=32$) hanno offerto un leggero aumento di velocità (1.04$\times$), mentre dimensioni maggiori ($m=256$) sono diventate più lente del solver esplicito a causa dell'overhead del processo di sketching, nonostante i valori di perdita finale inferiori.
  • Stabilità: Gli autori hanno riscontrato che il solver con sketching rimane stabile sotto parametri di smorzamento ($\lambda$) sostanzialmente più deboli rispetto alla formulazione esplicita, suggerendo che il processo di sketching possa agire come un regolarizzatore implicito.

Significatività e Rivendicazioni
Il documento sostiene di affrontare il collo di bottiglia della scalabilità della ML-IRL bi-livello stabilendo un collegamento diretto tra l'Essia interna e la matrice di informazione di Fisher nel contesto dell'ottimizzazione della divergenza KL inversa. Combinando questa intuizione teorica con lo streaming di sketching di matrici, gli autori dimostrano che è possibile calcolare ipergradienti impliciti senza il costo di memoria quadratica della costruzione esplicita dell'Essia o della matrice di Fisher.

Gli autori concludono con modestia che, sebbene i metodi basati su Fisher siano competitivi con la ML-IRL a singolo ciclo in termini di qualità finale della politica, offrono un vantaggio distinto in termini di performance di classificazione della ricompensa ed efficienza computazionale (specificamente la riduzione della memoria) per problemi ad alta dimensionalità. Il lavoro suggerisce che dimensioni moderate dello sketch offrano il compromesso ottimale tra qualità dell'ottimizzazione, uso della memoria e tempo di esecuzione.