Reinforcement Learning Using known Invariances

1. Enunciato del Problema

L'Apprendimento per Rinforzo (RL) spesso fatica con l'efficienza del campione, in particolare in ambienti con spazi continui di stato-azione e approssimazioni di funzioni non lineari. Una fonte significativa di inefficienza è il mancato sfruttamento delle simmetrie strutturali intrinseche nei problemi del mondo reale (ad esempio, l'invarianza rotazionale nella robotica, la simmetria speculare nei giochi da tavolo o l'invarianza permutazionale nei sistemi multi-agente).

Sebbene lavori precedenti abbiano esplorato la simmetria tramite aumento dei dati o reti neurali equivarianti, manca un quadro teorico rigoroso che quantifichi i guadagni nella complessità dei campioni derivanti dall'incorporazione diretta di simmetrie di gruppo note nei metodi di RL basati su kernel non parametrici. Il paper affronta la domanda: Come possono le simmetrie ambientali note essere sfruttate sistematicamente per migliorare l'efficienza del campione e le garanzie di rimorso nell'approssimazione di funzioni non lineari?

2. Metodologia

Gli autori propongono un algoritmo Symmetry-Aware Kernel-based Optimistic Least-Squares Value Iteration (KOVI). La metodologia di base comprende tre componenti principali:

A. Kernel Invarianti e RKHS

Invece di apprendere le invarianze dai dati, gli autori assumono che il gruppo di simmetria $G$ sia noto a priori. Costruiscono un kernel totalmente invariante $k_G$ a partire da un kernel base $k$:
$$k_G(z, z') = \frac{1}{|G|} \sum_{g \in G} k(g(z), z')$$
Questo kernel induce uno Spazio di Hilbert a Kernel Riproduttivo (RKHS) $\mathcal{H}_{k_G}$ costituito esclusivamente da funzioni che sono invarianti rispetto all'azione del gruppo $G$. Limitando lo spazio delle ipotesi a questo RKHS invariante, l'algoritmo rispetta intrinsecamente le simmetrie delle dinamiche di ricompensa e transizione.

B. L'Algoritmo (KOVI)

L'algoritmo adatta la standard Kernel-based Optimistic Value Iteration (Yang et al., 2020a):

1. LSVI Ottimista: Ad ogni passo $h$ di un episodio, l'agente stima la funzione Q ottimale $\hat{Q}_h$ utilizzando la regressione ridge a kernel sui dati osservati.
2. Bonus di Confidenza: Viene aggiunto un bonus di limite superiore di confidenza (UCB) per incoraggiare l'esplorazione: $Q_h = \min(\hat{Q}_h + \beta b_h, H-h+1)$.
3. Integrazione della Simmetria: La regressione viene eseguita utilizzando il kernel invariante $k_G$, garantendo che le funzioni di valore stimate e le politiche greedy risultanti rispettino le simmetrie di gruppo.

C. Quadro Teorico

Gli autori derivano nuovi limiti teorici per questo contesto consapevole della simmetria:

• Guadagno Massimo di Informazione ($\Gamma(T)$): Stabiliscono che per i kernel invarianti, il guadagno massimo di informazione scala come $O(T^{1/p} / |G|^{1/p})$, dove $|G|$ è la dimensione del gruppo e $p$ è correlato al decadimento degli autovalori del kernel.
• Numeri di Copertura: Derivano nuovi limiti per il numero di copertura della classe di funzioni delle Q-funzioni invarianti, mostrando una riduzione proporzionale a $1/|G|$.
• Limiti di Rimorso: Combinando questi elementi, dimostrano che il rimorso cumulativo $R(T)$ scala con un fattore di $1/|G|$ rispetto ai metodi standard basati su kernel. Nello specifico, per dimensioni elevate, il limite del rimorso migliora significativamente, quantificando il guadagno nell'efficienza del campione.

3. Contributi Chiave

1. Innovazione Algoritmica: Introduzione di una variante consapevole della simmetria dell'LSVI ottimista che incorpora invarianze di gruppo sia nelle dinamiche di ricompensa che in quelle di transizione tramite kernel totalmente invarianti.
2. Avanzamento Teorico: La prima analisi teorica che quantifica i guadagni nella complessità dei campioni nel RL dovuti all'incorporazione della simmetria. Forniscono limiti nuovi sul guadagno massimo di informazione e sui numeri di copertura per gli RKHS invarianti, mostrando esplicitamente un miglioramento di $1/|G|$ nei limiti di rimorso.
3. Validazione Empirica: Esperimenti estesi che dimostrano come il RL consapevole della simmetria superi significativamente i corrispettivi kernel standard e persino le reti neurali profonde equivaranti in specifici regimi a basso dato.

4. Risultati Sperimentali

Gli autori hanno validato il loro approccio su tre contesti distinti:

• MDP Sintetico: Un contesto semplificato con $|G|=2$ (identità e inversione). Il KOVI con kernel invariante ha raggiunto un rimorso cumulativo significativamente inferiore rispetto al KOVI con kernel RBF standard.
• Frozen Lake (OpenAI Gym):
  • Layout Fisso: L'ambiente è invariante sotto il gruppo di simmetria $D_4$ (rotazioni e riflessioni di un quadrato). Il KOVI con kernel invarianti ha converguto più velocemente e ha ottenuto rendimenti superiori rispetto al KOVI RBF standard.
  • Layout Casuale: Un contesto più impegnativo in cui il layout cambia ogni episodio ma mantiene la simmetria $D_4$. Il kernel invariante ha costantemente superato il kernel standard, dimostrando una generalizzazione robusta.
  • Confronto con RL Profondo: Il KOVI con kernel invarianti ha superato sia il DQN standard che il SymDQN (un DQN con livelli equivaranti) in termini di efficienza del campione, convergendo a rendimenti ottimali con meno passi temporali.
• Problema di Posizionamento 2D (SynPl): Un compito ispirato alla progettazione di chip che prevede il posizionamento di 8 unità su una griglia $8\times8$. Questo problema coinvolge vincoli geometrici complessi e spazi di stato ad alta dimensionalità. L'approccio con kernel invariante ha prodotto un rimorso inferiore e configurazioni di posizionamento migliori rispetto alla baseline, evidenziando l'utilità della simmetria nei problemi di progettazione strutturata.

5. Significato e Conclusione

• Efficienza del Campione: Il paper dimostra che codificare esplicitamente prior strutturali noti (simmetrie) nella classe di approssimazione delle funzioni (tramite kernel invarianti) porta a riduzioni sostanziali nella complessità dei campioni. Ciò è cruciale per le applicazioni del mondo reale dove la raccolta dei dati è costosa o dispendiosa in termini di tempo.
• Rigorismo Teorico: A differenza dell'aumento dei dati euristico o delle reti equivaranti parametriche, questo lavoro fornisce garanzie formali di rimorso e quantifica il beneficio esatto della simmetria in termini della dimensione del gruppo $|G|$.
• Vantaggio Non Parametrico: I risultati suggeriscono che nei regimi a basso dato, i metodi kernel non parametrici con vincoli di simmetria possono superare gli approcci di deep learning (anche quelli progettati con simmetria), poiché richiedono meno dati per convergere a politiche ottimali.
• Limitazioni: Gli autori riconoscono che la complessità computazionale dei metodi kernel ($O(HT^4)$) può essere proibitiva per dataset molto grandi, sebbene suggeriscano ottimizzazioni come GP sparsi o aggiornamenti di Cholesky per mitigare questo problema.

In sintesi, questo lavoro colma il divario tra la teoria dei gruppi teorica e il RL pratico, fornendo un quadro robusto per sfruttare le simmetrie note per costruire agenti di apprendimento più efficienti e generalizzabili.