Reinforcement Learning with Symbolic Reward Machines

Dit paper introduceert Symbolische Reward Machines (SRM) en bijbehorende leeralgoritmen die de beperkingen van traditionele Reward Machines overwinnen door direct observaties te verwerken via symbolische formules, waardoor handmatige labelfuncties overbodig worden terwijl de prestaties en interpreteerbaarheid behouden blijven.

De kern

Stel je voor dat je een robot wilt leren een taak uitvoeren, zoals hout verzamelen en in een machine stoppen. In de wereld van kunstmatige intelligentie (Reinforcement Learning) leert een robot meestal door te proberen en fouten te maken. Als hij iets goed doet, krijgt hij een puntje (een beloning). Als hij iets fout doet, krijgt hij geen puntje of een minpuntje.

Het probleem met de oude methode
De klassieke manier waarop robots leren, werkt als volgt: de robot kijkt naar de huidige situatie en krijgt direct een beloning. Maar wat als de beloning pas komt na een hele reeks stappen?

• Stap 1: Hout verzamelen (geen beloning).
• Stap 2: Naar de machine lopen (geen beloning).
• Stap 3: Hout in de machine gooien (grote beloning!).

De oude methode heeft moeite met dit soort "verhaaltjes". Om dit op te lossen, hebben wetenschappers eerder Reward Machines (Beloningsmachines) bedacht. Dit zijn als het ware een extra set instructies die de robot helpt onthouden waar hij in het verhaal staat.
Maar hier zit een addertje onder het gras: Om deze machines te laten werken, moet een mens de robot eerst een heel specifiek "vertaalwerk" leren. De mens moet een functie schrijven die zegt: "Als de robot op positie X staat, noem dit 'Hout verzamelen'." Dit is lastig, tijdrovend en werkt niet goed met standaard robots die we al hebben. Het is alsof je een auto moet leren rijden, maar eerst de motor uit elkaar moet halen om hem aan te sluiten op een speciaal bord dat je zelf hebt gebouwd.

De nieuwe oplossing: Symbolische Reward Machines (SRM)
De auteurs van dit paper, Thomas en Daniel, hebben een slimme nieuwe uitvinding bedacht: Symbolische Reward Machines (SRM).

Stel je voor dat de oude methode een robot gaf die alleen kon lezen op basis van een woordenlijst die jij hem gaf (bijv. "Positie X = Hout").
De nieuwe SRM-methode geeft de robot een verstandige bril.

In plaats van dat jij de robot vertelt wat hij moet zien, kijkt de robot zelf naar de wereld door een bril met wiskundige regels (symbolische formules).

• De robot ziet niet alleen "Positie X".
• De robot ziet direct: "Is mijn x-positie groter dan 5 en kleiner dan 6?"
• Als dat zo is, springt hij naar de volgende stap in zijn verhaal.

Waarom is dit zo cool?

1. Geen vertaler nodig: Je hoeft geen menselijke expert te zijn om een "woordenlijst" te maken. De robot leest de cijfers en coördinaten direct uit de omgeving. Het werkt met elke standaard robot die er al is.
2. Het verhaal wordt verteld: De robot bouwt zijn eigen "verhaal" op. Als hij leert, kan hij je later laten zien: "Ah, ik heb geleerd dat ik eerst naar links moet gaan (want daar is x < 6) en daarna pas naar rechts." Dit maakt het proces uitlegbaar. Je ziet precies wat de robot heeft geleerd.

De twee slimme algoritmes
De auteurs hebben twee manieren bedacht om deze bril te gebruiken:

1. QSRM (De snelle leerling):
   Je geeft de robot de bril met de regels al klaar. Hij leert dan razendsnel de taak, veel sneller dan een robot zonder bril. Hij doet precies hetzelfde als de oude methode, maar dan zonder dat jij de vertaler hoeft te spelen.

2. LSRM (De detective):
   Dit is nog slimmer. Je geeft de robot geen bril. Hij begint met een lege bril en probeert de regels zelf te raden.

   • Hij probeert iets.
   • Als hij een fout maakt (bijvoorbeeld: hij krijgt een beloning die hij niet verwachtte), denkt hij: "Huh? Mijn regels kloppen niet."
   • Hij past zijn bril aan (hij leert een nieuwe regel, bijvoorbeeld: "Oh, ik moet pas beloning krijgen als ik beide bergen heb beklommen").
   • Uiteindelijk leert hij de regels van de wereld zelf, van begin tot eind.

De resultaten
In hun tests hebben ze laten zien dat:

• De robots met de nieuwe "bril" (SRM) net zo goed leren als de robots met de oude "woordenlijst" (RM).
• De robots met de "detective-methode" (LSRM) zelfs de regels zelf kunnen ontdekken en toch een perfecte taak uitvoeren.
• Het werkt zowel in simpele, blokjes-achtige werelden als in complexe, echte werelden met continue beweging (zoals een auto die over een weg rijdt).

Kortom
Dit paper introduceert een manier om robots te leren complexe taken te doen zonder dat een mens de hele tijd moet ingrijpen om de regels te vertalen. De robot krijgt een "verstandige bril" die direct kijkt naar de cijfers in de wereld, en hij kan zelfs zijn eigen bril zelf maken terwijl hij leert. Het maakt kunstmatige intelligentie niet alleen slimmer, maar ook makkelijker te gebruiken en makkelijker te begrijpen voor mensen.

Technische samenvatting

Probleemstelling

Traditionele Reinforcement Learning (RL) methoden veronderstellen vaak dat beloningen (rewards) Markoviaans zijn; dit betekent dat de beloning alleen afhangt van de huidige toestand en de uitgevoerde actie. Veel real-world taken vereisen echter niet-Markoviaanse beloningen, waarbij de beloning afhangt van de geschiedenis van toestanden en acties (bijvoorbeeld: eerst hout verzamelen, dan de machine vullen).

Een bestaande oplossing hiervoor zijn Reward Machines (RMs). RMs modelleren deze complexe taken als automata die input ontvangen van een labeling function. Deze functie moet handmatig door een expert worden ontworpen om hoge-level gebeurtenissen (labels) te genereren op basis van de ruwe omgevingstoestand.
De belangrijkste beperkingen van RMs zijn:

1. Handmatige input: Voor elke nieuwe omgeving en taak moet een specifieke labeling functie worden gecreëerd.
2. Afwijking van standaard RL: RMs vereisen een uitgebreide interactieschema waarbij de omgeving labels moet uitsturen, wat niet compatibel is met standaard RL-frameworks (zoals Gymnasium) die alleen observaties en beloningen teruggeven.
3. Moeilijke toepasbaarheid: Het ontwerpen van een labeling functie die zowel generiek genoeg is voor de omgeving als specifiek genoeg voor de taak, is technisch uitdagend en beperkt de bruikbaarheid.

Methodologie

Het paper introduceert Symbolic Reward Machines (SRMs) als een nieuw mechanisme om niet-Markoviaanse beloningen te representeren zonder handmatige labeling functions.

1. Symbolic Reward Machines (SRM)
In tegenstelling tot RMs die input krijgen van discrete labels, ontvangen SRMs direct de omgevingstoestand (state).

• Transities: In plaats van labels gebruiken SRMs symbolische formules (guards) als transitiecondities. Een transitie wordt genomen als de huidige omgevingstoestand voldoet aan de logische formule (guard).
• Logica: Het paper focust op Linear Real Arithmetic (LRA), wat het mogelijk maakt om intervallen en vergelijkingen op continue of discrete variabelen te gebruiken (bijv. $x \ge 5 \land x < 10$).
• Eigenschappen: SRMs zijn deterministisch en compleet (voor elke mogelijke input is er een geldige transitie).

2. Leeralgoritmen
De auteurs stellen twee nieuwe algoritmen voor die werken met SRMs:

• QSRM (Q-learning for SRMs): Dit algoritme neemt een SRM als input (vergelijkbaar met QRM). Het update de Q-waarden voor elke SRM-toestand. Het belangrijkste verschil met QRM is dat QSRM geen labeling function nodig heeft; het werkt direct met de standaard MDP-interactie (state, action, reward). Het bewijst convergentie naar een optimale policy onder dezelfde voorwaarden als standaard Q-Learning.
• LSRM (Learning SRMs): Dit algoritme leert de SRM end-to-end tijdens het trainingsproces. LSRM start met een hypothetische SRM (initieel één toestand) en verbetert deze iteratief:
  • Het agent leert een policy met de huidige hypothese.
  • Als de beloning van de omgeving niet overeenkomt met de beloning van de hypothetische SRM, wordt de trajectorie toegevoegd aan een set van tegenvoorbeelden (counterexamples).
  • Een SMT-solver (Z3) wordt gebruikt om een nieuwe SRM te genereren die consistent is met alle tegenvoorbeelden.
  • LSRM-GF (Given Formulas): De gebruiker geeft een set mogelijke formules mee; de solver kiest welke worden gebruikt.
  • LSRM-FT (Formula Templates): De gebruiker geeft alleen sjablonen mee (bijv. $x \ge b_1 \land x < b_2$). De solver infereert zowel de structuur van de SRM als de specifieke waarden voor de variabelen in de sjablonen. Dit maakt het volledig autonoom.

Belangrijkste Bijdragen

1. Innovatie in Representatie: Introductie van SRMs die niet-Markoviaanse taken modelleren zonder handmatige labeling functions, waardoor ze direct compatibel zijn met standaard RL-omgevingen.
2. Algoritmische Ontwikkeling: Voorstellen van QSRM en LSRM (met varianten GF en FT) die respectievelijk leren met een gegeven SRM en het leren van een SRM end-to-end.
3. Theoretische Garantie: Bewijzen van convergentie. QSRM convergeert naar een optimale policy. LSRM convergeert (in de limiet) naar een SRM die "almost surely equivalent" is aan de ware reward structuur, mits voldoende data wordt verzameld.
4. Interpreteerbaarheid: De geleerde SRMs bieden menselijke inzicht in de taakstructuur via symbolische formules, in plaats van een "black box" policy.

Experimentele Resultaten

De methoden zijn getest in discrete (Office World) en continue (Mountain Car) omgevingen.

• Prestatie t.o.v. Baselines:
  • Standaard Q-Learning en DQN presteren slecht omdat ze geen geschiedenis kunnen modelleren of te grote "frame stacks" nodig hebben.
  • (D)QSRM presteert even goed als de bestaande (D)QRM methode (die labels nodig heeft), maar werkt zonder de extra labeling overhead.
  • LSRM leert effectieve policies end-to-end. In discrete omgevingen convergeert het naar de optimale performance. In continue omgevingen bereikt het zeer goede, zij het niet altijd perfect optimale, resultaten.
• Leren van de SRM:
  • LSRM-GF en LSRM-FT leren SRMs die in de meeste gevallen almost surely equivalent zijn aan de ware SRM in de omgeving.
  • Zelfs als de geleerde SRM niet exact identiek is aan de ware structuur (bijv. door kleine verschillen in continue intervallen), levert het toch een hoge performance op.
  • De geleerde SRMs zijn visueel en logisch interpreteerbaar voor de gebruiker.

Significantie

Dit werk is significant omdat het de kloof overbrugt tussen de theorie van niet-Markoviaanse RL en de praktische toepasbaarheid in standaard RL-frameworks.

• Verwijdering van de bottleneck: Het elimineert de noodzaak voor handmatige labeling functions, wat een grote technische barrière was voor de adoptie van Reward Machines.
• End-to-End Leren: Met LSRM-FT kunnen agents complexe, temporale taken leren en de onderliggende reward structuur automatisch ontdekken en verklaren.
• Toepasbaarheid: De methode werkt zowel voor discrete als continue ruimtes, wat het relevant maakt voor een breed scala aan real-world toepassingen, van robotica tot logistiek.

Kortom, SRMs bieden een flexibeler, bruikbaarder en interpreteerbaarder alternatief voor traditionele Reward Machines in het domein van Reinforcement Learning.