Performance-Driven Environment Abstraction with Multi-Timescale Learning

Sintesi Tecnica: Astrazione dell'Ambiente Guidata dalle Prestazioni con Apprendimento su Multi-Timescale

Formulazione del Problema
Il documento affronta la sfida del processo decisionale in processi decisionali di Markov (MDP) su larga scala, dove la pianificazione diretta nello spazio degli stati originale è computazionalmente impraticabile. Mentre gli approcci esistenti si affidano spesso alla compressione informazionale o a euristiche strutturali che preservano proprietà geometriche o topologiche, questo lavoro sostiene che l'astrazione appropriata sia intrinsecamente dipendente dal compito. Gli autori propongono un framework di astrazione dello stato guidata dalle prestazioni. L'obiettivo centrale è trovare un'aggregazione degli stati (partizionando lo spazio degli stati in "superstati") e una corrispondente politica che massimizzino la qualità decisionale minimizzando al contempo la complessità della rappresentazione.

Un vincolo critico in questa formulazione è il vincolo della Stessa Distribuzione di Azione (Same-Action-Distribution o SAD): tutti gli stati all'interno di un singolo superstato aggregato devono condividere la stessa distribuzione di azioni. Sebbene ciò riduca lo spazio di ricerca della politica, introduce errori di approssimazione. Il documento cerca di bilanciare il compromesso tra la complessità dell'astrazione (numero di superstati) e la perdita di prestazioni indotta dal vincolo SAD e dall'approssimazione della funzione di valore.

Metodologia
La soluzione proposta è un framework di apprendimento per rinforzo multi-timescale che adatta congiuntamente la politica e un'astrazione dell'ambiente a struttura ad albero.

1. Fondamento Teorico:

   • Gli autori derivano un limite delle prestazioni per il processo decisionale sotto un'aggregazione fissa. Questo limite separa la subottimalità totale in due fonti distinte:
     • Errore di approssimazione della funzione di valore ($\epsilon_\Gamma$): l'errore derivante dalla rappresentazione della funzione di valore ottimale con valori costanti a tratti sui superstati.
     • Perdita di condivisione delle azioni ($\delta_\Gamma$): la perdita di prestazioni specificamente indotta dal vincolo SAD, derivante dalla non-commutatività di massimizzazione e media (ovvero, forzare una singola distribuzione di azioni per un gruppo di stati che potrebbero richiedere ottimamente azioni diverse).
   • Viene derivato un limite superiore computabile basato sul mismatch del residuo di Bellman, che funge da proxy per la sconosciuta funzione di valore ottimale.

2. Aggregazione Adattiva Basata su Alberi:

   • Lo spazio degli stati è rappresentato da un albero gerarchico (nello specifico, quadtree negli esperimenti). Le foglie dell'albero definiscono gli attuali superstati.
   • Stima di Q (Q-Estimation): Per guidare i cambiamenti strutturali, l'algoritmo mantiene stime dei valori Q ai nodi foglia. Fondamentalmente, mantiene anche stime per i potenziali figli dei nodi espandibili. Ciò consente al sistema di valutare il beneficio potenziale del raffinamento di una regione senza impegnarsi completamente nell'espansione.
   • Criteri di Espansione e Collasso:
     • Espansione (Raffinamento): Un nodo foglia viene espanso se il guadagno stimato nelle prestazioni del valore Q (permettendo ai figli di adottare distribuzioni di azione distinte) supera una soglia determinata dal parametro di regolarizzazione $\lambda$ e dal fattore di sconto $\beta$.
     • Collasso (Coarsening/Raggruppamento): Un nodo genitore viene collassato se la fusione dei suoi figli non risulta in un calo significativo delle prestazioni rispetto al costo di mantenere nodi separati.
   • Apprendimento Multi-Timescale: Il framework opera su tre scale temporali (timescale):
     • Più veloce: l'Actor-Critic aggregato aggiorna la politica e la funzione di valore per la partizione attuale fissa.
     • Intermedia: le stime di Q per gli aggiornamenti strutturali vengono perfezionate.
     • Più lenta: la struttura dell'albero (partizione) viene aggiornata sulla base delle stime di Q. Ciò assicura che la politica converga sotto un'astrazione quasi-statica prima che la struttura cambi.

Contributi Chiave
Il documento identifica tre contributi primari:

1. Limite delle Prestazioni: Un limite teorico per il processo decisionale sotto astrazione dell'ambiente che separa esplicitamente l'errore di approssimazione del valore dalla perdita causata dal vincolo SAD.
2. Criterio Guidato dai Valori Q: Un criterio rigoroso per raffinare e aggregare le astrazioni basate su alberi, derivato dall'analisi teorica e implementato tramite discrepanze dei valori Q.
3. Algoritmo Multi-Timescale: Un algoritmo di apprendimento unificato che adatta congiuntamente la politica e la struttura dell'astrazione, consentendo la ristrutturazione continua dello spazio degli stati.

Risultati
Il metodo è stato valutato su compiti di navigazione discreta (mondi a griglia, labirinti, mappe del terreno di Marte) e un compito di controllo continuo (Mountain Car), confrontandolo con l'Actor-Critic piatto, l'Actor-Critic gerarchico basato su quantizzatore e i Conditional Abstraction Trees (CAT).

• Compressione dello Stato: L'algoritmo ha ottenuto una sostanziale compressione dello stato (ad esempio, riducendo 1024 stati a 232 superstati in un labirinto 32x32) pur preservando le strutture topologiche rilevanti per il compito.
• Efficienza di Campionamento e Velocità: La variante Tree-AC-Replan proposta (avviata a caldo con un'astrazione precedentemente appresa) ha dimostrato capacità di convergenza e ri-pianificazione significativamente più veloci rispetto ai baseline, in particolare quando i parametri del compito (come le posizioni degli obiettivi) cambiavano.
• Adattabilità: Il sistema si è adattato con successo a nuovi compiti raffinando le regioni vicino ai nuovi obiettivi e raggruppando le regioni che non richiedevano più un'alta risoluzione.
• Compromessi: Gli esperimenti hanno rivelato una relazione a forma di U tra la profondità iniziale dell'albero e il numero di episodi necessari per raggiungere un target di tasso di successo, indicando una granularità intermedia ottimale per l'inizializzazione. L'analisi della frontiera di Pareto ha mostrato che il metodo bilancia efficacemente la dimensione dell'astrazione rispetto alle prestazioni della politica.

Significatività e Rivendicazioni
Il documento sostiene che la costruzione automatica di rappresentazioni gerarchiche sia una componente fondamentale dell'intelligenza. Spostandosi dalle astrazioni che preservano la geometria verso quelle guidate dalle prestazioni, il framework proposto affronta il vuoto nella letteratura esistente dove le astrazioni sono spesso specifiche del dominio o mancano di un'ottimizzazione esplicita per le prestazioni del compito a valle.

Gli autori sottolineano che il loro approccio fornisce garanzie teoriche riguardo alla perdita di prestazioni, che i precedenti metodi basati su euristiche non possedevano. La capacità di apprendere congiuntamente la politica e la struttura dell'astrazione permette agli agenti di gestire compiti complessi pur rimanendo adattabili ad ambienti in evoluzione. Il lavoro suggerisce che questo framework sia un passo verso l'autonomia scalabile dove la pianificazione nello spazio degli stati originale è impraticabile, offrendo un meccanismo per regolare dinamicamente la "risoluzione" del modello del mondo dell'agente in base alle necessità immediate di prestazione.