Active Reward Machine Inference From Raw State Trajectories

Titolo: Inferenza Attiva delle Macchine di Ricompensa da Traiettorie di Stato Grezze

1. Il Problema

Il lavoro affronta la sfida di apprendere Macchine di Ricompensa (Reward Machines - RM) direttamente da dati di esperienza grezzi, in un regime di scarsità di informazioni.

• Contesto: Le RM sono automi a stati finiti che catturano la memoria necessaria per compiti multi-fase, mappando eventi ad alto livello (proposizioni atomiche) su transizioni di stato. Sono fondamentali per la sintesi di politiche robotiche in compiti complessi.
• Limitazione degli approcci esistenti: La maggior parte dei metodi precedenti richiede:
  1. Conoscenza delle etichette (label) degli stati o delle proposizioni atomiche.
  2. Accesso ai valori di ricompensa osservati.
  3. Conoscenza della struttura dell'automa o delle sue transizioni.
• Obiettivo del paper: Il problema studiato è molto più difficile: si assume che non siano disponibili osservazioni di ricompense, etichette, né nodi della macchina. L'unico input disponibile sono le traiettorie di stato grezze (raw state trajectories) generate da una politica esperta (o una politica storica).
• Sfida principale: Senza etichette o ricompense, il problema è mal posto (ill-posed), poiché molte RM diverse potrebbero rendere ottimale la stessa politica. L'obiettivo è identificare una RM "minima" e una funzione di etichettatura compatibili con i dati osservati.

2. Metodologia

Gli autori propongono un framework che combina la teoria degli automi, l'apprendimento per rinforzo (MaxEntRL) e la soddisfacibilità booleana (SAT), integrato con una strategia di apprendimento attivo.

A. Formulazione del Problema e Equivalenza delle Politiche

• Viene definita una politica storica ($\pi_h$) che cattura il comportamento dell'agente basandosi solo sulla sequenza di stati osservati, senza accesso diretto agli stati interni della RM.
• Due RM etichettate sono considerate equivalenti rispetto alla politica se inducono la stessa politica storica ottimale.
• Il problema è formalizzato come: data una politica storica limitata a una profondità $l$, è possibile recuperare una RM policy-equivalente a quella vera?

B. Formulazione SAT per l'Inferenza
Il cuore dell'algoritmo è un problema di Soddisfacibilità Booleana (SAT) che apprende congiuntamente:

1. La funzione di transizione della RM ($\delta_u$).
2. La funzione di etichettatura ($L$) che mappa gli stati MDP alle proposizioni atomiche.

• Codifica: Le funzioni sono codificate come variabili binarie.
• Vincoli:
  • Funzionalità: Garantire che $\delta_u$ e $L$ siano funzioni ben definite.
  • Esempi Negativi: Se due traiettorie di stato $\tau$ e $\tau'$ portano a comportamenti diversi nella politica storica ($\pi_h(a|s, \tau) \neq \pi_h(a|s, \tau')$), allora devono portare a nodi diversi nella RM. Questo vincolo è cruciale per escludere soluzioni errate.
  • Ancoraggio: Per evitare ambiguità di permutazione, si fissa un punto di partenza (es. $L(1)=1$).

C. Teoria della Profondità Sufficiente
Gli autori dimostrano un risultato teorico chiave (Proposizione 1): esiste una profondità sufficiente $l^*$ (dove $l^* = |S| \cdot u_{max}^2$, con $|S|$ stati MDP e $u_{max}$ un limite superiore sui nodi della RM) tale che, se il problema SAT è soddisfacibile a questa profondità, lo è per qualsiasi profondità maggiore. Questo garantisce che non sia necessario esplorare traiettorie infinite.

D. Estensione Attiva (Active Learning)
Poiché enumerare tutte le traiettorie fino alla profondità $l^*$ è computazionalmente proibitivo (crescita esponenziale), viene introdotto un algoritmo di estensione attiva:

• Idea: Non tutte le traiettorie sono ugualmente informative. L'algoritmo seleziona attivamente coppie di traiettorie estese che massimizzano la riduzione dello spazio delle ipotesi.
• Strategia: Si cerca di trovare coppie di traiettorie $\{\tau, \tau'\}$ che dividano lo spazio delle soluzioni candidate a metà (metà delle RM candidate prevedono lo stesso nodo, l'altra metà un nodo diverso).
• Algoritmo:
  1. Si parte con una profondità iniziale (burn-in) e si risolve il SAT per ottenere un insieme di soluzioni candidate.
  2. Si campionano traiettorie che potrebbero distinguere tra queste soluzioni.
  3. Si interrogano le politiche storiche estese per verificare se sono "esempi negativi".
  4. Si aggiornano i vincoli SAT e si restringe l'insieme delle soluzioni.
  5. Si ripete fino a convergenza o raggiungimento della profondità sufficiente.

3. Risultati Sperimentali

Gli esperimenti sono stati condotti su ambienti Grid World (4x4) con due compiti principali:

1. Pick and Drop: Il robot deve raccogliere un oggetto e deporlo evitando una zona pericolosa.
2. Patrol ABCD: Il robot deve visitare le stanze in un ordine specifico (A $\to$ B $\to$ C $\to$ D).

Punti chiave dei risultati:

• Recupero Corretto: L'algoritmo riesce a recuperare la RM vera e la funzione di etichettatura (a meno di rinominazione dei nodi) partendo solo da traiettorie di stato.
• Efficienza dell'Approccio Attivo:
  • Memoria: L'approccio esaustivo (full depth restriction) richiede circa 24.76 GB di memoria per memorizzare gli esempi negativi a profondità 9. L'approccio attivo riduce questo requisito a 0.147 GB (riduzione di due ordini di grandezza), mantenendo solo le traiettorie informative.
  • Tempo di Esecuzione: L'approccio attivo riduce il tempo totale di calcolo da ~7185 secondi (esaustivo) a ~3544 secondi, grazie a una riduzione significativa del tempo di risoluzione SAT.
  • Convergenza: Con un budget di query limitato ($B=250$) e un campione attivo di $N_{active}=200$, l'algoritmo converge alla soluzione vera nel 96.6% dei casi alla profondità 13, mentre la baseline casuale fallisce.

4. Contributi Chiave

1. Inferenza senza supervisione simbolica: È il primo framework che apprende sia la struttura della RM che la funzione di etichettatura partendo esclusivamente da tracce di stato, senza bisogno di etichette predefinite o ricompense osservate.
2. Condizione di Identificabilità: Dimostrazione teorica dell'esistenza di una profondità sufficiente ($l^*$) che garantisce l'identificabilità della soluzione.
3. Algoritmo di Apprendimento Attivo: Sviluppo di una strategia di query che riduce drasticamente i costi computazionali e di memoria, rendendo fattibile l'inferenza in spazi di stati più grandi rispetto ai metodi esaustivi.
4. Formulazione SAT Unificata: Integrazione dell'apprendimento della funzione di etichettatura all'interno del problema SAT, generalizzando lavori precedenti che assumevano etichette note.

5. Significato e Implicazioni

Questo lavoro rappresenta un passo fondamentale verso l'apprendimento autonomo di strutture di memoria per robot.

• Riduzione del carico umano: Elimina la necessità per gli esperti umani di definire manualmente le transizioni logiche e le proposizioni atomiche, che è un processo laborioso e soggetto a errori.
• Scalabilità: L'approccio attivo dimostra che è possibile scalare l'inferenza di RM a compiti complessi senza esplodere le risorse computazionali, aprendo la strada all'applicazione in domini robotici reali.
• Fondamento Teorico: Fornisce una base per comprendere la necessità di memoria nei processi decisionali sequenziali, distinguendo tra memoria dovuta all'osservazione parziale (POMDP) e memoria dovuta alla struttura del compito (RM).

In sintesi, il paper propone un metodo robusto ed efficiente per far "scoprire" al robot la logica sottostante di un compito complesso osservando semplicemente dove va e cosa fa, senza bisogno di istruzioni esplicite o feedback di ricompensa diretto.