Answer-Set-Programming-based Abstractions for Reinforcement Learning

Dichiarazione del Problema
L'Apprendimento per Rinforzo (Reinforcement Learning, RL) consente agli agenti di apprendere politiche attraverso l'interazione, ma le applicazioni realistiche spesso soffrono di spazi di stato e di azione enormi, rendendo intrattabili gli approcci di apprendimento ingenui. Sebbene i metodi di approssimazione come il Deep Q-Learning offrano capacità di generalizzazione, essi richiedono frequentemente grandi quantità di dati di addestramento e possono esibire instabilità. Il Relational Reinforcement Learning (RRL) affronta queste limitazioni utilizzando la logica del primo ordine per ragionare su oggetti e sulle loro relazioni, facilitando la generalizzazione tra stati simili. Nello specifico, il framework CARCASS (Compact Abstraction using Relational Conjunctions for Aggregation of State-action Spaces) di van Otterlo (2004) modella i Processi Decisionali di Markov (MDP) utilizzando astrazioni logiche. Tuttavia, l'implementazione originale di CARCASS si basa su Prolog e sulla risoluzione SLDNF, che, pur essendo dichiarativi in linea di principio, spesso richiedono caratteristiche procedurali (come l'ordinamento delle regole o i tagli/cut) per l'efficienza e mancano di un supporto nativo per l'inferenza non monotona, l'ottimizzazione e la gestione delle preferenze.

Metodologia
Gli autori propongono un metodo generale per reimplementare il framework CARCASS utilizzando l'Answer-Set Programming (ASP). L'ASP è un linguaggio di rappresentazione della conoscenza basato sulla logica completamente dichiarativo che supporta il ragionamento non monotono, l'ottimizzazione e i vincoli.

1. Codifica ASP di CARCASS: Gli autori definiscono una funzione di etichettatura per mappare stati astratti e coppie stato-azione a termini di base (ground terms). Costruiscono una codifica modulare composta da:

   • Programmi ($P_{\hat{s}_i}$) che codificano i singoli stati astratti come regole in cui il corpo consiste nei letterali che definiscono lo stato astratto.
   • Programmi ($P_{\hat{s}_i, \hat{a}_{i,j}}$) che codificano la relazione di copertura per le coppie stato-azione astratte, collegando le azioni concrete a quelle astratte tramite atomi aCov.
   • Un meccanismo di lista decisionale ($P_{\hat{C}}$) utilizzando una regola di scelta per selezionare esattamente un stato di copertura astratto per ogni stato concreto e un vincolo per garantire che la selezione segua la lista ordinata (dando priorità all'indice più basso).
   • Uno stato astratto "vuoto" ($\hat{s}_\infty$) con l'indice più alto che copre tutti gli stati non coperti da regole specifiche, garantendo un fallback predefinito.

2. Integrazione dell'Apprendimento Online: Gli autori integrano questa codifica in un ciclo di Q-learning online (Algoritmo 2). Per un dato stato concreto, il solver ASP calcola un answer set ottimale per determinare lo stato di copertura astratto e l'insieme delle azioni astratte ammissibili. L'agente seleziona quindi un'azione concreta dal set coperto dall'azione astratta scelta e aggiorna il valore Q della coppia stato-azione astratta.

3. Conoscenza di Background: Il framework consente l'inclusione di conoscenza di background ($P_B$) per inferire proprietà complesse (ad esempio, ricerca di un percorso, completezza di una torre) direttamente all'interno del processo di astrazione, piuttosto che richiederne la pre-computazione o l'implementazione procedurale.

Contributi Chiave

1. Metodo di Codifica Generale: Il documento introduce un metodo sistematico per codificare le astrazioni CARCASS in ASP, dimostrando come un linguaggio completamente dichiarativo possa realizzare astrazioni stato-azione relazionali.
2. Adattamento dell'Apprendimento Online: Gli autori mostrano come utilizzare le astrazioni CARCASS basate su ASP all'interno di un contesto di Q-learning online, gestendo la selezione dinamica degli stati e delle azioni astratte.
3. Valutazione Empirica: L'implementazione è valutata in due domini distinti:
   • Blocks World: Un compito di impilamento di $n$ blocchi dove l'astrazione riduce lo spazio stato-azione a una dimensione costante indipendentemente da $n$.
   • MiniGrid: Una suite di compiti di navigazione in mondi a griglia (es. Door Key, Multi Room) dove la conoscenza di background viene utilizzata per inferire la disposizione delle stanze e i percorsi minimi, costruendo stati astratti basati sul nodo successivo nel percorso.

Risultati
La valutazione empirica confronta l'Abstract Q-learning rispetto al Concrete Q-learning in un mondo a 20 blocchi e in tre ambienti MiniGrid.

• Stabilità: L'Abstract Q-learning ha dimostrato una stabilità costante, con ritorni mediani e intervalli interquartili che rimangono elevati dopo l'apprendimento iniziale, mentre il Concrete Q-learning ha mostrato fluttuazioni significative o fallimenti nella convergenza in ambienti complessi.
• Qualità: L'Abstract Q-learning ha raggiunto tassi di successo elevati (ad esempio, vicino al 100% negli ultimi 500 episodi per i compiti MiniGrid), superando significativamente il Concrete Q-learning, che spesso non è riuscito a ottenere ritorni positivi nello stesso arco di tempo.
• Efficienza di Campionamento: L'approccio astratto ha richiesto significativamente meno episodi per apprendere politiche di alta qualità rispetto all'approccio concreto. Ad esempio, nel mondo a 20 blocchi, l'apprendimento astratto ha raggiunto ritorni mediani positivi all'episodio 376, mentre il Concrete learning rimaneva al valore di base negativo.
• Differenze di Modellazione: Nel caso di studio MiniGrid, la codifica ASP ha permesso una specifica compatta e dichiarativa di ricerca del percorso e dei vincoli, mentre l'equivalente implementazione in Prolog richiedeva una ricerca algoritmica esplicita (ricerca in ampiezza - BFS), evidenziando il vantaggio dell'ASP nel separare la specifica del problema dalla logica di controllo.

Significatività e Rivendicazioni
Il documento conclude che CARCASS implementato con ASP fornisce un approccio promettente per la costruzione di astrazioni nel RL, particolarmente quando la conoscenza del dominio è disponibile. Gli autori affermano che le astrazioni basate su ASP offrono un'alternativa flessibile al CARCASS basato su Prolog supportando:

• Generalizzazione: Attraverso rappresentazioni relazionali.
• Restrizioni delle Azioni: Tramite vincoli dichiarativi.
• Decomposizione del Problema: Codificando schemi di ragionamento complessi (come la ricerca di un percorso o l'analisi di una torre) direttamente nelle regole.
• Ragionamento Avanzato: Includendo l'inferenza non monotona, l'ottimizzazione e il ragionamento sotto conoscenza incompleta.

Gli autori notano con modestia che, sebbene le politiche apprese siano di qualità accettabile e apprese con meno campioni, non vi è alcuna garanzia di convergenza a una politica ottimale in generale, e l'astrazione stessa potrebbe non preservare la politica ottimale per problemi di pianificazione NP-difficili (come visto nel caso Blocks World dove l'astrazione scambia l'ottimalità con la trattabilità). Il lavoro si posiziona come un passo verso framework guidati dalla conoscenza per il RL relazionale che supportano l'apprendimento di politiche tolleranti all'elaborazione (elaboration-tolerant).