Answer-Set-Programming-based Abstractions for Reinforcement Learning

Probleemstelling
Reinforcement Learning (RL) stelt agenten in staat om beleidsregels (policies) te leren door interactie, maar realistische toepassingen lijden vaak onder enorme toestands- en actieruimtes, waardoor naïeve leerbenaderingen onhandelbaar worden. Hoewel benaderingsmethoden zoals Deep Q-Learning generalisatie bieden, vereisen ze vaak enorme hoeveelheden trainingsdata en kunnen ze instabiliteit vertonen. Relational Reinforcement Learning (RRL) pakt deze beperkingen aan door gebruik te maken van eerste-orde logica om te redeneren over objecten en hun relaties, wat generalisatie over vergelijkbare toestanden faciliteert. Specifiek modelleert het CARCASS-framework (Compact Abstraction using Relational Conjunctions for Aggregation of State-action Spaces) door van Otterlo (2004) Markov Decision Processes (MDP's) met behulp van logische abstracties. De oorspronkelijke CARCASS-implementatie leunt echter op Prolog en SLDNF-resolutie, wat weliswaar in principe declaratief is, maar vaak procedurele kenmerken (zoals de volgorde van regels of cuts) vereist voor efficiëntie en geen natuurlijke ondersteuning biedt voor niet-monotoon redeneren, optimalisatie en het afhandelen van voorkeuren.

Methodologie
De auteurs stellen een algemene methode voor om het CARCASS-framework te reimplementeren met behulp van Answer-Set Programming (ASP). ASP is een volledig declaratieve, op logica gebaseerde kennisrepresentatietaal die niet-monotoon redeneren, optimalisatie en constraints ondersteunt.

1. ASP-codering van CARCASS: De auteurs definiëren een labelingsfunctie om abstracte toestanden en toestands-actieparen naar grondtermen (ground terms) te mappen. Ze construeren een modulaire codering bestaande uit:

   • Programma's ($P_{\hat{s}_i}$) die individuele abstracte toestanden coderen als regels waarbij de body bestaat uit de literalen die de abstracte toestand definiëren.
   • Programma's ($P_{\hat{s}_i, \hat{a}_{i,j}}$) die de dekkingrelatie (covering relation) voor abstracte toestands-actieparen coderen, door concrete acties aan abstracte acties te koppelen via aCov-atomen.
   • Een beslissingslijst-mechanisme ($P_{\hat{C}}$) dat gebruikmaakt van een choice rule om precies één dekkende abstracte toestand per concrete toestand te selecteren en een constraint om ervoor te zorgen dat de selectie de geordende lijst volgt (waarbij prioriteit wordt gegeven aan de laagste index).
   • Een "lege" abstracte toestand ($\hat{s}_\infty$) met de hoogste index die alle toestanden dekt die niet door specifieke regels worden gedekt, wat zorgt voor een standaard fallback.

2. Integratie van Online Learning: De auteurs integreren deze codering in een online Q-learning loop (Algoritme 2). Voor een gegeven concrete toestand berekent de ASP-solver een optimaal answer set om de dekkende abstracte toestand en de set toegestane abstracte acties te bepalen. De agent selecteert vervolgens een concrete actie uit de set die wordt gedekt door de gekozen abstracte actie en werkt de Q-waarde van het abstracte toestands-actiepaar bij.

3. Achtergrondkennis: Het framework maakt het mogelijk om achtergrondkennis ($P_B$) op te nemen om complexe eigenschappen (bijv. padvinden, de volledigheid van een toren) direct binnen het abstractieproces af te leiden, in plaats van dat deze vooraf berekend of procedureel geïmplementeerd moeten worden.

Belangrijkste Bijdragen

1. Algemene Coderingmethode: Het artikel introduceert een systematische methode voor het coderen van CARCASS-abstracties in ASP, en demonstreert hoe een volledig declaratieve taal relationele toestand-actie abstracties kan realiseren.
2. Adaptatie voor Online Learning: De auteurs tonen aan hoe ASP-gebaseerde CARCASS-abstracties binnen een online Q-learning setting kunnen worden gebruikt, waarbij de dynamische selectie van abstracte toestanden en acties wordt afgehandeld.
3. Empirische Evaluatie: De implementatie wordt geëvalueerd in twee verschillende domeinen:
   • Blocks World: Een $n$-block stapeltaak waarbij de abstractie de toestand-actieruimte reduceert tot een constante grootte, ongeacht $n$.
   • MiniGrid: Een suite van grid-world navigatietaken (bijv. Door Key, Multi Room) waarbij achtergrondkennis wordt gebruikt om kamerlay-outs en kortste paden af te leiden, waarbij abstracte toestanden worden geconstrueerd op basis van de volgende node in het pad.

Resultaten
De empirische evaluatie vergelijkt abstract Q-learning met concrete Q-learning in een 20-blocks world en drie MiniGrid-omgevingen.

• Stabiliteit: Abstract Q-learning vertoonde consistente stabiliteit, waarbij de mediaan van de returns en de interkwartielafstand hoog bleven na de initiële leerfase, terwijl concrete Q-learning significante fluctuaties of een gebrek aan convergentie vertoonde in complexe omgevingen.
• Kwaliteit: Abstract Q-learning bereikte hoge succespercentages (bijv. bijna 100% in de laatste 500 episodes voor MiniGrid-taken), wat aanzienlijk beter is dan concrete Q-learning, dat vaak niet in staat was om positieve returns te behalen binnen dezelfde tijdspanne.
• Sample Efficiëntie: De abstracte benadering had aanzienlijk minder episodes nodig om hoogwaardige policies te leren vergeleken met de concrete benadering. In de 20-blocks world bereikte abstract leren bijvoorbeeld positieve mediane returns bij episode 376, terwijl concrete learning op de baseline negatieve return bleef.
• Modelleringsverschillen: In de MiniGrid casestudy maakte de ASP-codering een compacte, declaratieve specificatie van padvinden en constraints mogelijk, terwijl de equivalente Prolog-implementatie een expliciete algoritmische zoekopdracht (breadth-first search) vereiste, wat het voordeel van ASP benadrukt in het scheiden van probleemspecificatie van controlelogica.

Betekenis en Claims
Het artikel concludeert dat CARCASS geïmplementeerd met ASP een veelbelovende aanpak biedt voor het construeren van abstracties in RL, met name wanneer domeinkennis beschikbaar is. De auteurs beweren dat ASP-gebaseerde abstracties een flexibel alternatief bieden voor de op Prolog gebaseerde CARCASS door ondersteuning te bieden voor:

• Generalisatie: Door relationele representaties.
• Actiebeperkingen: Via declaratieve constraints.
• Probleemdecompositie: Door complexe redeneerpatronen (zoals padvinden of torenanalyse) direct in de regels te coderen.
• Geavanceerd Redeneren: Inclusief niet-monotoon redeneren, optimalisatie en redeneren onder onvolledige kennis.

De auteurs merken bescheiden op dat hoewel de geleerde policies van aanvaardbare kwaliteit zijn en met minder samples zijn geleerd, er geen garantie is op convergentie naar een optimale policy in het algemeen, en dat de abstractie zelf de optimale policy mogelijk niet behoudt voor NP-harde planningsproblemen (zoals te zien in de Blocks World casus waar de abstractie optimaliteit inruilt voor hanteerbaarheid). Het werk positioneert zich als een stap naar kennisgestuurde frameworks voor relationele RL die ondersteuning bieden aan elaboratie-tolerante policy-lering.