The Laplacian Keyboard: Beyond the Linear Span

Riepilogo Tecnico: La Tastiera Laplaciana: Oltre lo Span Lineare

Definizione del Problema
Nell'Apprendimento per Rinforzo (RL), una sfida centrale è permettere agli agenti di risolvere nuovi compiti in modo efficiente utilizzando conoscenze pregresse, spesso inquadrato come RL non supervisionato o zero-shot. Gli approcci esistenti ricadono generalmente in due categorie: metodi basati sulla rappresentazione (apprendimento di caratteristiche per approssimare funzioni valore o ricompense) e metodi basati sul comportamento (apprendimento di una libreria di opzioni riutilizzabili).

I metodi basati sulla rappresentazione, come le rappresentazioni Forward-Backward (FB) o le Funzioni Proto-Valore, apprendono una base (ad esempio, autovettori di un Laplaciano di grafo) per approssimare le funzioni di ricompensa. Sebbene questi possano produrre soluzioni "zero-shot" combinando linearmente gli elementi della base, sono fondamentalmente limitati dallo span lineare delle caratteristiche apprese. Se la funzione di ricompensa di un compito a valle giace al di fuori di questo span, la politica indotta è subottimale. Viceversa, i metodi basati sul comportamento come la Option Keyboard (OK) apprendono a assemblare opzioni ma spesso dipendono da caratteristiche di ricompensa specificate manualmente o da compiti predefiniti per costruire la base comportamentale, limitandone la generalità e la scalabilità.

Il problema centrale affrontato è come costruire una base comportamentale agnostica rispetto al compito che sia sia principiale (derivata dalla dinamica dell'ambiente senza ingegneria manuale delle ricompense) sia capace di risolvere compiti che superano l'espressività di una base lineare fissa.

Metodologia: La Tastiera Laplaciana (LK)
Gli autori propongono la Tastiera Laplaciana (LK), un framework gerarchico che colma il divario tra approcci basati sulla rappresentazione e approcci basati sul comportamento. Il metodo opera in due fasi:

1. Fase di Pre-addestramento (Senza Ricompensa):

   • Rappresentazione Laplaciana: L'agente apprende una rappresentazione dello stato $\phi(s)$ da un dataset offline privo di ricompense. Questa rappresentazione è derivata dai primi $k$ autovettori del Laplaciano di grafo, che codifica la struttura di transizione dell'ambiente. Questi autovettori fungono da base naturale per approssimare funzioni di ricompensa lisce.
   • Approssimatore Universale delle Caratteristiche Successive (USFA): Un USFA viene addestrato su questa base Laplaciana. L'USFA apprende una politica $\pi(a|s, w)$ e caratteristiche successive $\psi(s, a, w)$ condizionate da un vettore di pesi $w$. Per qualsiasi funzione di ricompensa $r(s) = w^\top \phi(s)$ all'interno dello span degli autovettori, l'USFA può teoricamente recuperare la politica ottimale.

2. Fase a Valle (Controllo Gerarchico):

   • Meta-Politica: Invece di impegnarsi in una singola combinazione lineare della base (che sarebbe limitata allo span), LK addestra una meta-politica $\pi_{LK}(s) \to w$. Questa meta-politica produce un vettore di pesi $w$ che istanzia un'opzione specifica (politica) dalla libreria USFA.
   • Composizione Sequenziale: La meta-politica esegue l'opzione selezionata per un orizzonte fisso $t_{term}$, osserva lo stato risultante e quindi seleziona un nuovo vettore di pesi. Ciò permette all'agente di assemblare dinamicamente una sequenza di comportamenti, componendo efficacemente una traiettoria a tratti che può approssimare politiche ottimali per funzioni di ricompensa che giacciono al di fuori dello span lineare originale.

Analisi Teorica
Il documento stabilisce limiti teorici sull'errore di approssimazione quando si utilizza una base Laplaciana troncata.

• Errore di Approssimazione del Valore: Il Teorema 3.1 fornisce un limite superiore alla differenza tra la vera funzione valore ottimale $v^*$ e la funzione valore $v^*_k$ derivata da una ricompensa ricostruita utilizzando i primi $k$ autovettori. Il limite è $\|v^* - v^*_k\|_\infty \leq \frac{\|r\|_G}{(1-\gamma)\sqrt{\lambda_k}}$, dove $\|r\|_G$ è la norma del grafo (lisciatura) della ricompensa e $\lambda_k$ è l'autovettore più grande nella base troncata.
• Implicazione: Ciò conferma che mentre le ricompense lisce sono ben approssimate da una base piccola, le ricompense con struttura ad alta frequenza (grande $\|r\|_G$) richiedono basi più grandi. Crucialmente, nessuna base finita fissa può coprire tutte le possibili funzioni di ricompensa, motivando la necessità della composizione gerarchica fornita da LK.

Contributi Chiave

1. Il Framework della Tastiera Laplaciana: Un'architettura gerarchica che compone comportamenti indotti dal Laplaciano tramite una meta-politica appresa. Ciò permette agli agenti di trascendere lo span lineare della rappresentazione, risolvendo compiti inesprimibili da una singola combinazione statica di autovettori.
2. Validazione Teorica ed Empirica delle Basi Laplaciane: Gli autori forniscono un'analisi rigorosa degli autovettori Laplaciani come base di ricompensa, inclusi limiti di errore teorici e validazione empirica che mostra come essi costituiscano un punto di partenza credibile per il controllo zero-shot, comparabile a metodi di rappresentazione all'avanguardia come FB.

Risultati Sperimentali
Gli autori hanno valutato LK su tre domini DeepMind Control (DMC) (Cheetah, Quadruped, Walker) e sul gridworld Item-Collector.

• Prestazioni Zero-Shot: Con una base sufficientemente grande ($k=50$), la base Laplaciana da sola raggiunge prestazioni zero-shot comparabili alle rappresentazioni Forward-Backward, confermandone la validità come fondamento agnostico rispetto al compito.
• Oltre lo Span Lineare: In regimi in cui la dimensione della base è vincolata (piccolo $k$), la soluzione zero-shot è spesso insufficiente. LK supera significativamente la baseline zero-shot in queste impostazioni. Ad esempio, nel dominio Cheetah con $k=1$, LK ha migliorato le prestazioni di oltre il 100% su diversi compiti passando tra le due opzioni disponibili, dimostrando che la composizione gerarchica aggiunge valore oltre la base stessa.
• Efficienza del Campionamento: LK dimostra un'efficienza del campionamento superiore rispetto ad agenti piatti (TD3 standard) che apprendono da zero. In molti compiti, LK accumula ricompense più rapidamente, specialmente quando la base Laplaciana cattura una struttura rilevante per il compito (ad esempio, compiti Quadruped dove il primo autovettore cattura la regolazione dell'altezza del torso).
• Confronto con Baseline Privilegiate: Nel dominio Item-Collector, LK (addestrato senza caratteristiche di ricompensa artigianali) ha raggiunto prestazioni vicine alla Option Keyboard Basis (OKB), che si basa su caratteristiche di ricompensa privilegiate e specificate manualmente. Ciò suggerisce che gli autovettori Laplaciani possono servire come alternativa scalabile e automatica alle basi comportamentali ingegnerizzate manualmente.

Significato e Affermazioni
Il documento afferma che la Tastiera Laplaciana offre una soluzione principiale ai limiti sia dei metodi RL basati sulla rappresentazione sia di quelli basati sul comportamento.

• Supera il limite di espressività dei metodi dello span lineare abilitando una composizione dinamica e sequenziale dei comportamenti.
• Supera il limite di specificazione dei metodi basati sul comportamento derivando la base comportamentale automaticamente dalla dinamica dell'ambiente (tramite autovettori Laplaciani) piuttosto che richiedere un'ingegneria manuale delle caratteristiche di ricompensa.
• Gli autori sottolineano che LK tratta la base Laplaciana non come una soluzione completa, ma come un "punto di partenza strutturato". Combinando l'ottimalità zero-shot all'interno della base con una composizione efficiente al di fuori di essa, LK raggiunge una forte efficienza del campionamento e robustezza attraverso compiti diversificati senza informazioni privilegiate sulle ricompense.

Gli autori notano limitazioni, in particolare l'uso di una terminazione delle opzioni a orizzonte fisso invece di condizioni di terminazione principiali dipendenti dallo stato, il che potrebbe limitare la qualità delle politiche composte. Osservano inoltre che in alcuni casi (ad esempio Quadruped con determinati dataset), la soluzione zero-shot è già vicina all'ottimo, lasciando poco spazio per miglioramenti gerarchici, e che la qualità del dataset influenza significativamente l'espressività della base appresa.