Reinforcement Learning with Symbolic Reward Machines

Die Autoren stellen Symbolic Reward Machines (SRMs) sowie die Lernalgorithmen QSRM und LSRM vor, um die Einschränkungen manueller Labeling-Funktionen bei Reward Machines zu überwinden, indem sie Umgebungsbeobachtungen direkt über symbolische Formeln verarbeiten und dabei die Leistung bestehender Methoden erreichen, ohne die Standardumgebungsdefinitionen zu verletzen.

Das Wesentliche

Das Problem: Der Agent mit dem Amnesie-Problem

Stell dir vor, du trainierst einen Roboter, damit er ein Haus aufräumt.

• Der klassische Ansatz (Reinforcement Learning): Der Roboter bekommt nur zwei Dinge: Er sieht den Raum (z. B. "Da liegt ein Buch") und er bekommt einen Punkt (Belohnung) oder einen Schlag (Strafe).
• Das Problem: Wenn der Roboter heute einen Punkt dafür bekommt, dass er das Buch aufhebt, weiß er morgen vielleicht nicht mehr, warum er das getan hat. Er hat kein Gedächtnis für die Vergangenheit.
• Die echte Herausforderung: Viele Aufgaben sind wie eine Rezeptkette. Erst muss man das Holz sammeln, dann darf man es in den Ofen legen, und danach bekommt man den großen Preis. Wenn der Roboter das Holz noch nicht gesammelt hat, aber schon in den Ofen greift, passiert nichts. Klassische Lernmethoden scheitern oft daran, weil sie nur auf den letzten Moment schauen und nicht verstehen, dass die Reihenfolge wichtig ist.

Die alte Lösung: Der "Etikettierer" (Reward Machines)

Bisher gab es eine Lösung namens "Reward Machines" (Belohnungsmaschinen).

• Wie es funktionierte: Man musste dem Roboter einen menschlichen Assistenten (einen "Etikettierer") zur Seite stellen. Dieser Assistent schaut sich an, was der Roboter tut, und ruft laut: "Aha! Du hast jetzt Holz gesammelt!" oder "Super, du bist im Ofen!".
• Das Problem: Das ist extrem mühsam. Für jeden neuen Raum und jede neue Aufgabe muss ein Experte diesen Assistenten programmieren. Es ist, als müsste man für jedes neue Spiel, das man spielt, erst einen neuen Schiedsrichter einstellen, der die Regeln kennt. Das funktioniert in der echten Welt kaum, weil man nicht für jede Situation einen Experten hat.

Die neue Lösung: Symbolische Belohnungsmaschinen (SRMs)

Die Autoren dieses Papers haben eine clevere Idee entwickelt: Symbolische Belohnungsmaschinen (SRMs).

Stell dir das wie einen intelligenten Navigator vor, der direkt in den Kopf des Roboters eingebaut ist.

1. Kein Assistent nötig: Der Roboter muss nicht mehr auf jemanden warten, der ihm sagt, was passiert. Er schaut sich einfach die Umgebung selbst an.
2. Logische Regeln statt Etiketten: Statt auf ein Wort wie "Holz gesammelt" zu warten, nutzt der Roboter mathematische Regeln (wie ein Sicherheitsgurt-System im Auto).
   • Beispiel: Der Roboter denkt: "Wenn meine Position X größer als 5 und kleiner als 10 ist UND meine Geschwindigkeit Y positiv ist, dann bin ich im 'Holz-Sammel-Modus'."
   • Diese Regeln sind wie Wächter (im Englischen "Guards"), die entscheiden, ob der Roboter in den nächsten Schritt übergeht.
3. Der Vorteil: Der Roboter kann jetzt komplexe Aufgaben lernen, ohne dass jemand ihm vorher sagen muss, wie er die Umgebung beschreiben soll. Er lernt die Regeln direkt aus den Daten.

Die zwei Lern-Methoden

Die Autoren haben zwei Arten entwickelt, wie der Roboter diese Regeln lernt:

1. QSRM (Der Schüler mit dem Lehrbuch)

• Hier gibt der Mensch dem Roboter die Regeln (die SRM) vor.
• Der Roboter lernt dann, wie er die Aufgabe am besten löst.
• Vorteil: Er lernt viel schneller als ohne Regeln.
• Unterschied zur alten Methode: Er braucht keinen menschlichen Assistenten, der ihm die Regeln in Form von Wörtern sagt. Er versteht die Regeln direkt als Formeln.

2. LSRM (Der autodidaktische Genie)

• Das ist der wahre Clou. Hier gibt der Mensch gar keine Regeln vor.
• Der Roboter fängt an zu lernen, macht Fehler, und wenn er merkt: "Moment, ich habe hier einen Punkt bekommen, aber meine innere Logik sagte mir, ich sollte keinen bekommen!", dann passt er seine eigenen Regeln an.
• Er baut sich sein eigenes "Regelbuch" (die SRM) während des Trainings.
• Das Ergebnis: Am Ende hat der Roboter nicht nur gelernt, wie man die Aufgabe löst, sondern er kann dem Menschen auch erklären: "Schau mal, ich habe gelernt, dass ich erst hierhin muss, dann dorthin, um den großen Preis zu bekommen." Das ist wie ein Roboter, der am Ende des Kurses ein Lehrbuch schreibt, das genau beschreibt, wie die Aufgabe funktioniert.

Warum ist das wichtig?

• Einfacher: Man muss keine komplizierten "Etikettierer" programmieren. Man kann Standard-Umgebungen (wie die, die man aus Videospielen kennt) direkt verwenden.
• Verständlicher: Da die Regeln in Formeln geschrieben sind (z. B. "x muss größer als 5 sein"), kann ein Mensch sie lesen und verstehen. Der Roboter wird nicht zu einer "Blackbox".
• Effektiver: In Tests haben diese neuen Methoden genauso gut oder besser funktioniert als die alten, komplizierten Methoden, aber sie waren viel flexibler.

Zusammenfassung in einer Metapher

• Alte Methode: Du trainierst einen Hund, indem du ihm sagst: "Wenn du den Ball siehst, sag 'Ball!'". Du musst ihm jedes Mal sagen, was er sieht.
• Neue Methode (SRM): Du gibst dem Hund eine Brille, durch die er selbst erkennt: "Wenn der Ball rot ist und sich bewegt, dann ist es Zeit zu jagen." Der Hund lernt die Regeln selbst und kann dir am Ende sogar sagen: "Ich habe gelernt, dass ich erst warten muss, bis der Ball rollt."

Die Autoren haben also eine Methode erfunden, mit der KI-Agenten komplexe, zeitabhängige Aufgaben lernen können, ohne dass Menschen ihnen ständig die Regeln in die Hand drücken müssen. Sie machen die KI schlauer und verständlicher.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert die Herausforderung, nicht-Markovsche Belohnungsfunktionen (Non-Markovian Reward Functions) im Reinforcement Learning (RL) effizient zu handhaben.

• Hintergrund: Klassisches RL basiert auf Markov-Entscheidungsprozessen (MDPs), bei denen die Belohnung nur vom aktuellen Zustand und der Aktion abhängt. Viele reale Aufgaben erfordern jedoch eine Sequenz von Schritten (z. B. erst Holz sammeln, dann in die Maschine füllen), was eine Abhängigkeit von der Historie (Trajektorie) erfordert.
• Bestehende Lösung & Limitierung: Reward Machines (RMs) sind ein etablierter Ansatz, um solche Aufgaben zu modellieren. RMs verwenden jedoch eine Labeling-Funktion, die Rohzustände in hochlevelige, abstrakte Labels (Propositionen) umwandelt.
  • Nachteil: Diese Labeling-Funktion muss manuell für jede Umgebung und Aufgabe erstellt werden. Sie erfordert Expertenwissen und ist technisch aufwendig. Zudem ist sie oft nicht flexibel genug, um sowohl generisch als auch spezifisch zu sein. Dies verhindert die direkte Anwendung in standardisierten RL-Frameworks (wie Gymnasium), da diese keine hochleveligen Labels ausgeben.

2. Methodik: Symbolic Reward Machines (SRMs)

Die Autoren schlagen Symbolic Reward Machines (SRMs) als neue Repräsentation vor, die die Notwendigkeit einer manuellen Labeling-Funktion eliminiert.

• Konzept: SRMs integrieren Elemente von Reward Machines und symbolischen Automaten.
  • Eingabe: Im Gegensatz zu RMs, die Labels erhalten, verarbeiten SRMs den rohen Umgebungszustand direkt.
  • Guard-Logik: Die Übergänge zwischen den Zuständen der SRM werden nicht durch Labels, sondern durch symbolische Formeln (Guards) gesteuert. Diese Formeln prüfen direkt Bedingungen im Zustandsraum (z. B. $x \ge 5 \land y < 10$).
  • Logik: Das Paper nutzt Linear Real Arithmetic (LRA) als Logikkomponente, was die Handhabung kontinuierlicher Werte ermöglicht.
  • Eigenschaften: SRMs sind deterministisch und vollständig (für jeden Eingabewert existiert ein Übergang).

Lernalgorithmen:
Auf Basis von SRMs werden zwei Algorithmen vorgestellt:

1. QSRM (und DQSRM): Ein Algorithmus, der eine gegebene SRM nutzt, um eine optimale Policy zu lernen. Er erweitert Q-Learning (bzw. Deep Q-Learning), indem es die SRM-Zustände in den Q-Tabelle (bzw. in die Q-Netzwerke) integriert. Es wird bewiesen, dass QSRM unter den gleichen Bedingungen wie klassisches Q-Learning konvergiert.
2. LSRM (Learning SRM): Ein Algorithmus, der die SRM end-to-end lernt, ohne dass sie vorgegeben ist.
   • Ansatz: LSRM beginnt mit einer einfachen Hypothese (ein Zustand, ein Selbstübergang). Es trainiert eine Policy und vergleicht die vom Algorithmus generierten Belohnungen mit den tatsächlichen Belohnungen der Umgebung.
   • Counterexamples: Bei Inkonsistenzen wird die Trajektorie als Gegenbeispiel (Counterexample) gespeichert.
   • Inferenz: Ein SMT-Solver (Z3) wird verwendet, um eine neue SRM-Hypothese zu generieren, die konsistent mit allen gesammelten Gegenbeispielen ist. Dies geschieht durch die Kodierung als Constraint Satisfaction Problem (CSP).
   • Varianten:
     • LSRM-GF (Given Formulas): Der Nutzer gibt eine Menge möglicher Formeln vor.
     • LSRM-FT (Formula Templates): Der Nutzer gibt nur Formel-Templates vor (z. B. Intervalle mit freien Variablen), und der Algorithmus inferiert die konkreten Werte. Dies ermöglicht das Lernen ohne jegliches Vorwissen über die Reward-Struktur.

3. Schlüsselbeiträge

• Einführung von SRMs: Eine neue Architektur, die nicht-Markovsche Belohnungen direkt auf Basis von Rohzuständen modelliert, ohne manuelle Labeling-Funktionen.
• Kompatibilität: SRMs sind kompatibel mit dem Standard-RL-Interface (nur Zustand und Belohnung), was die Anwendung in bestehenden Frameworks (wie Gymnasium) ermöglicht.
• Interpretierbarkeit: Die gelernten SRMs liefern dem Nutzer eine schrittweise Erklärung der Aufgabenstruktur durch die symbolischen Formeln (Guards).
• Algorithmen & Konvergenz: Vorstellung von QSRM und LSRM mit formalen Konvergenzbeweisen. Es wird gezeigt, dass LSRM im Limit eine fast sicher äquivalente SRM lernt und somit zu einer optimalen Policy konvergiert (bei endlichen Zustandsräumen).
• End-to-End Lernen: LSRM-FT ermöglicht das vollständige Lernen von Policy und Reward-Struktur aus Standardumgebungen.

4. Experimentelle Ergebnisse

Die Autoren evaluierten ihre Methoden in diskreten (Office World) und kontinuierlichen (Mountain Car) Umgebungen.

• Vergleich mit Baselines:
  • Klassisches Q-Learning und DQN (selbst mit Frame-Stacking) scheiterten oder performten schlecht bei nicht-Markovschen Aufgaben, da sie die Historie nicht effizient genug nutzen konnten.
  • QSRM vs. QRM: QSRM erreichte exakt die gleichen Ergebnisse wie das etablierte QRM, bestätigte aber die These, dass SRMs ohne Labeling-Funktion funktionieren.
• Leistung von LSRM:
  • LSRM-GF und LSRM-FT lernten in diskreten Umgebungen optimale Policies (Performance-Wert 1.0).
  • In kontinuierlichen Umgebungen wurden sehr gute, wenn auch nicht immer perfekte Werte erreicht (bedingt durch die Approximation bei unendlichen Zustandsräumen).
• Qualität der gelernten SRMs:
  • Die von LSRM inferierten SRMs waren in den meisten Fällen fast sicher äquivalent zu den im Experiment verwendeten „wahren" SRMs.
  • Auch wenn die Struktur oder die genauen Intervallgrenzen leicht variierten (besonders bei LSRM-FT in kontinuierlichen Umgebungen), reichte die gelernte Struktur aus, um hohe Performance zu erzielen.
  • Die gelernten SRMs boten dem Nutzer eine klare, interpretierbare Darstellung der Aufgabenlogik.

5. Bedeutung und Fazit

Das Paper stellt einen signifikanten Schritt vorwärts dar, um RL auf komplexe, sequenzielle Aufgaben anzuwenden, ohne dass manuelle Engineering-Arbeit für die Reward-Struktur nötig ist.

• Praktische Relevanz: Durch die Beseitigung der Labeling-Funktion wird RL in standardisierten Umgebungen viel zugänglicher.
• Interpretierbarkeit: Die Fähigkeit, die Reward-Struktur in Form von symbolischen Formeln zu lernen, bietet Transparenz, die bei reinen Deep-RL-Ansätzen oft fehlt.
• Zukunft: Die Methode ist besonders vielversprechend für Anwendungen, bei denen die Reward-Funktion komplex ist, aber aus Beobachtungen ableitbar sein sollte (z. B. Robotik, autonome Systeme).

Zusammenfassend demonstrieren die Autoren, dass Symbolic Reward Machines eine flexible, interpretierbare und leistungsfähige Alternative zu klassischen Reward Machines sind, die das Lernen in nicht-Markovschen Umgebungen ohne manuelle Eingriffe ermöglicht.