Laplacian Representations for Decision-Time Planning

Problematica
L'apprendimento per rinforzo (RL) basato su modelli offre potenziali vantaggi in termini di efficienza campionaria, generalizzazione e adattamento rispetto agli approcci model-free. Tuttavia, una sfida centrale rimane: la pianificazione con un modello appreso in ambienti che richiedono l'approssimazione di funzioni è ostacolata dal problema dell'errore cumulativo. Quando un agente simula traiettorie a lungo termine utilizzando un modello imperfetto, piccoli errori di previsione si accumulano, causando la divergenza delle traiettorie immaginate rispetto alla realtà. Questo problema è particolarmente acuto nella pianificazione decisionale (decision-time planning), dove le rappresentazioni dello stato devono supportare simultaneamente il calcolo dei costi locali e preservare le strutture temporali a lungo termine. Sebbene la pianificazione gerarchica possa decomporre le azioni di basso livello dagli obiettivi a lungo termine, essa richiede uno spazio latente capace di rappresentare le distanze nello spazio degli stati attraverso molteplici scale temporali per decomporre efficacemente i compiti in sottogruppi (subgoals).

Metodologia
Il documento propone che la rappresentazione Laplaciana fornisca uno spazio latente efficace per la pianificazione decisionale. Questa rappresentazione inserisce gli stati in uno spazio definito dagli autovettori del Laplaciano del grafo indotto dalla dinamica dell'ambiente. Le proprietà chiave di questa rappresentazione includono:

• Struttura multi-scala: Gli autovettori sono ordinati per scala temporale; gli autovettori precoci codificano la struttura globale (es. regioni), mentre quelli successivi catturano distinzioni locali.
• Raggiungibilità e Geometria: La distanza euclidea nello spazio Laplaciano scalato approssima la Commute Time Distance (CTD), che misura il numero atteso di passi per viaggare tra due stati e tornare indietro tramite un cammino casuale (random walk). Ciò rende lo spazio isometrico alla CTD, fornendo una geometria adatta alla pianificazione.
• Scoperta di Sottogruppi (Subgoal Discovery): La rappresentazione partiziona naturalmente l'ambiente in regioni ben connesse, rendendola ideale per il clustering spettrale al fine di identificare i sottogruppi nei colli di bottiglia (bottlenecks).

Sulla base di queste proprietà, gli autori introducono ALPS (Augmented Laplacian Planning with Subgoals), un algoritmo di pianificazione decisionale gerarchica. ALPS opera in due fasi:

1. Pre-training:
   • Apprendimento Laplaciano: Utilizza l'Augmented Lagrangian Laplacian Objective (ALLO) per apprendere autovettori e autovalori da un dataset offline, evitando il costo computazionale $O(|S|^3)$ della decomposizione in autovalori esatta.
   • Modello Forward: Apprende un modello forward auto-regressivo multi-step nello spazio degli stati originale per ridurre l'accumulo di errore.
   • Prior del Comportamento: Apprende una politica deterministica condizionata all'obiettivo ($\pi_{prior}$) per orientare il campionamento delle azioni, accelerando la convergenza.
   • Grafo dei Cluster: Esegue il clustering k-means nello spazio Laplaciano scalato ($\psi$-space) per definire i sottogruppi (centri dei cluster) e costruisce un grafo di transizioni tra i cluster.
2. Pianificazione Decisionale:
   • Livello Alto (High-Level): Dato uno stato iniziale e uno obiettivo, l'algoritmo identifica i rispettivi cluster e utilizza l'algoritmo di Dijkstra sul grafo dei cluster per trovare un percorso di sottogruppi.
   • Livello Basso (Low-Level): Per ogni sottogruppo, un pianificatore basato sul Metodo della Cross-Entropy (CEM) genera una sequenza di azioni. Il CEM è inizializzato usando il prior del comportamento e ottimizzato minimizzando una funzione di costo basata sulla distanza nello spazio $\psi$ (approssimando la CTD) e sull'ampiezza dell'azione.

Contributi Chiave

• Rappresentazione Laplaciana per la Pianificazione: Il documento dimostra che la rappresentazione Laplaciana cattura efficacemente le distanze nello spazio degli stati a molteplici scale temporali, scomponendo naturalmente i problemi a lungo termine in sottogruppi e mitigando gli errori cumulativi.
• Algoritmo ALPS: Un nuovo algoritmo di pianificazione decisionale gerarchica che integra l'identificazione dei sottogruppi basata sul Laplaciano con l'ottimizzazione della traiettoria basata su modello (CEM) e un prior del comportamento.
• Validazione Empirica: Gli autori valutano ALPS su OGBench (Offline Goal-Conditioned RL Benchmark), una suite di compiti precedentemente dominati da metodi model-free.

Risultati
Gli esperimenti sono stati condotti sugli ambienti Maze2D—PointMass e su un set diversificato di compiti OGBench che coinvolgono locomozione (pointmaze, antmaze, humanoidmaze) e manipolazione (cube, scene) con osservazioni sia basate sullo stato che sui pixel.

• Performance: ALPS supera significativamente i comuni baseline model-free (inclusi varianti di GCBC, IQL, QRL, CRL e HIQL) nella maggior parte dei compiti OGBench, con significatività statistica ($p < 0.001$).
• Robustezza: ALPS dimostra robustezza rispetto alla dimensione del labirinto e alla qualità del dataset offline. Eccelle in particolare nei dataset "explore" con dati a bassa qualità ma ad alta copertura, dove la decomposizione gerarchica permette al pianificatore di alto livello di compensare un orizzonte limitato di basso livello.
• Confronto con PcLast: Nei compiti Maze2D, ALPS (utilizzando la rappresentazione Laplaciana) supera PcLast (che utilizza stati latenti contrastivi), evidenziando l'utilità della metrica Laplaciana sia per la stima della distanza che per l'identificazione dei sottogruppi.
• Limitazioni: Il documento nota che ALPS fatica con i labirinti con "teleport" (teletrasporto), dove la simmetrizzazione inerente all'obiettivo Laplaciano causa l'accorpamento dei cluster tra ingressi e uscite dei teletrasporti, portando potenzialmente l'agente in regioni in cui non può uscire. Inoltre, le performance degradano nei compiti di manipolazione di oggetti multipli (es. double-cube) a causa della natura globale della rappresentazione Laplaciana che non riesce a catturare l'indipendenza condizionale tra gli stati degli oggetti.

Significatività
Il documento sostiene che la rappresentazione Laplaciana serva come un blocco costruttivo utile per una pianificazione di successo con modelli appresi, affrontando la sfida centrale degli errori cumulativi nei compiti a lungo termine. Fornendo uno spazio latente che cattura intrinsecamente la struttura temporale e la connettività, ALPS consente una pianificazione gerarchica efficace in spazi di stato continui e ad alta dimensionalità utilizzando solo dataset offline pre-raccolti. Il lavoro suggerisce che sfruttare le proprietà spettrali della dinamica dell'ambiente possa superare la storica difficoltà di applicare metodi model-based a complessi problemi di RL condizionati all'obiettivo a lungo termine.