💻 computer science

Active Reward Machine Inference From Raw State Trajectories

Dieses Papier stellt ein Verfahren vor, das Belohnungsmaschinen direkt aus rohen Zustands- und Politik-Trajektorien lernt, ohne auf Belohnungen, Labels oder Maschinennodes zugreifen zu können, und erweitert dies durch ein aktives Lernverfahren zur effizienteren Datennutzung.

Ursprüngliche Autoren: Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

Veröffentlicht 2026-04-10

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Rätsel: Wie lernt ein Roboter, was er tun soll?

Stellen Sie sich vor, Sie geben einem Roboter eine Aufgabe: „Geh in den Keller, hole einen Hammer und bring ihn in die Garage."

Ein einfacher Roboter denkt vielleicht nur an den nächsten Schritt: „Ich muss mich bewegen." Aber für komplexe Aufgaben muss er sich erinnern, wo er gerade steht. Hat er den Hammer schon? Ist er schon im Keller?

In der Robotik nennt man diese „Erinnerungsstruktur" eine Belohnungsmaschine (Reward Machine). Sie ist wie eine Landkarte für die Aufgabe. Sie sagt dem Roboter nicht nur, wohin er soll, sondern auch, welche „Etappen" er erreicht hat (z. B. „Hammer geholt" = Etappe 1 beendet).

Das Problem: Normalerweise muss ein Mensch diese Landkarte mühsam von Hand zeichnen. Das ist wie ein Koch, der jedem neuen Koch genau sagt, wann er Salz, wann Pfeffer und wann den Ofen anmachen soll. Das ist langweilig, fehleranfällig und bei komplexen Aufgaben unmöglich.

Die Lösung: Den Roboter selbst raten lassen

Die Autoren dieses Papiers haben einen Weg gefunden, wie ein Roboter diese Landkarte selbst aus seinen eigenen Bewegungen lernen kann – ohne dass ihm jemand sagt, was „Salz" oder „Pfeffer" ist.

Stellen Sie sich das so vor:
Ein Roboter läuft durch ein Labyrinth (die Welt). Er weiß nicht, was die Wände bedeuten. Aber er beobachtet einen Experten, der das Labyrinth perfekt durchquert.

Der Experte geht immer erst zur blauen Tür, dann zur roten, dann zur grünen.
Der Roboter sieht nur die Bewegungen (die Spuren auf dem Boden). Er sieht nicht, dass die Türen farbig sind. Er sieht nicht, welche Belohnung der Experte bekommt.

Die Frage ist: Kann der Roboter aus diesen bloßen Spuren rekonstruieren, dass es eine blaue, eine rote und eine grüne Tür gibt und in welcher Reihenfolge sie passiert werden müssen?

Der Trick: Der Detektiv und die „Was-wäre-wenn"-Spiele

Die Forscher haben einen cleveren Algorithmus entwickelt, der wie ein Detektiv arbeitet:

Die Spuren sammeln: Der Roboter schaut sich an, wie der Experte durch die Welt läuft.
Die Hypothesen aufstellen: Der Roboter denkt sich tausende mögliche Landkarten aus.
- Hypothese A: Vielleicht ist die blaue Tür der Startpunkt?
- Hypothese B: Vielleicht ist die rote Tür der Startpunkt?
- Hypothese C: Vielleicht gibt es gar keine Farben, sondern nur Temperatur?
Die Falle stellen (Aktives Lernen): Hier kommt der geniale Teil. Statt alle möglichen Wege im Labyrinth abzulaufen (was Jahre dauern würde und den Speicher sprengen würde), fragt der Roboter gezielt: „Was wäre, wenn ich diesen Weg nehme und jenen Weg?"
- Er sucht nach zwei Wegen, die für die meisten seiner Hypothesen gleich aussehen, aber für einige wenige unterschiedlich sind.
- Wenn er dann sieht, wie der Experte diese Wege tatsächlich geht, kann er sagen: „Aha! Hypothese A ist falsch, weil der Experte dort anders reagiert hat."
- So kann er mit wenigen, gezielten Fragen (wie ein guter Schachspieler, der den Gegner in eine Falle lockt) tausende falsche Theorien ausschließen.

Ein Bild aus dem Alltag: Das „Wer ist es?"-Spiel

Stellen Sie sich das Spiel „Wer ist es?" vor. Sie müssen eine Person erraten, indem Sie Fragen stellen.

Der alte Weg (Exhaustiv): Sie fragen zu jedem einzelnen Detail: „Hat die Person rote Haare? Nein. Hat sie blaue Augen? Nein. Trägt sie eine Brille? Nein..." Das dauert ewig und Sie müssen sich alles merken.
Der neue Weg (Aktiv): Sie fragen strategisch: „Ist die Person ein Mann?" (Nein). „Ist sie eine Frau mit langen Haaren?" (Ja). Durch eine kluge Frage halbieren Sie die Anzahl der möglichen Kandidaten sofort.

Die Autoren haben gezeigt, dass man mit dieser „strategischen Frage"-Methode die Landkarte des Roboters viel schneller und mit viel weniger Speicherplatz finden kann als mit dem alten, stumpfen Ausprobieren aller Wege.

Was haben sie herausgefunden?

Es reicht, nur die Spuren zu sehen: Man braucht keine Belohnungen oder Labels zu kennen. Nur die Bewegung reicht aus, um die Logik der Aufgabe zu verstehen.
Es gibt einen „Sättigungspunkt": Irgendwann bringt es nichts mehr, noch längere Wege zu beobachten. Ab einer bestimmten Tiefe der Erinnerung ist die Landkarte so gut wie gefunden.
Aktives Lernen spart enorm: Wenn man nicht blind alles durchsucht, sondern gezielt nach den „wichtigsten" Unterschieden sucht, braucht man weniger Rechenleistung und weniger Speicherplatz. Das ist wie der Unterschied zwischen dem Durchsuchen eines ganzen Buches, um ein Wort zu finden, und dem Nutzen eines Inhaltsverzeichnisses.

Fazit

Diese Arbeit ist ein wichtiger Schritt, damit Roboter in der Zukunft nicht mehr von Menschen mit detaillierten Anweisungen gefüttert werden müssen. Stattdessen können sie sich ihre eigenen „Regelwerke" und „Erinnerungsstrukturen" aus Beobachtungen ableiten – ähnlich wie ein Kind, das lernt, wie man ein Puzzle löst, indem es einfach zusieht, wie ein Erwachsener es macht, ohne dass jemand sagt: „Nimm jetzt das rote Teil".

Es ist der erste Schritt zu Robotern, die wirklich verstehen, warum sie etwas tun, und nicht nur was sie tun.

1. Problemstellung

Das Paper adressiert das Problem des Lernens von Reward Machines (RMs) direkt aus rohen Zustands-Trajektorien in einem informationsarmen Szenario.

Hintergrund: Reward Machines sind endliche Automaten, die die für mehrstufige Aufgaben notwendige Gedächtnisstruktur kodieren. Sie werden oft mit Reinforcement Learning (RL) kombiniert, um Robotern komplexe, zeitlich extendede Ziele zu ermöglichen.
Die Herausforderung: Die manuelle Spezifikation einer RM (inklusive der Übergangsfunktion und der Labeling-Funktion, die niedriglevelige Zustände auf hochlevelige Propositionen abbildet) ist aufwendig und fehleranfällig.
Lücke in der aktuellen Forschung: Bestehende Methoden zur Inferenz von RMs setzen meist voraus, dass entweder:
1. Ground-Truth-Labels oder Belohnungen bekannt sind.
2. Eine vordefinierte Labeling-Funktion existiert.
3. Interaktive Abfragen (Oracles) möglich sind.
Das spezifische Problem: Die Autoren gehen von einem Szenario aus, in dem keine Belohnungen, keine Labels, keine Automaten-Knoten und keine vordefinierte Labeling-Funktion bekannt sind. Der Algorithmus erhält nur:
1. Ein MDP-Modell (Zustände, Aktionen, Übergangswahrscheinlichkeiten).
2. Eine „History Policy" (eine Darstellung des Agentenverhaltens basierend auf beobachtbaren Zustandssequenzen).
Ziel: Es soll eine RM und eine kompatible Labeling-Funktion gelernt werden, die die beobachtete Policy als optimal erklären, ohne dass externe Informationen über die Aufgabenstruktur vorliegen. Da das Problem unterbestimmt ist (mehrere RMs können dieselbe Policy erzeugen), wird nach einer minimalen, policy-äquivalenten Lösung gesucht.

2. Methodik

Die vorgeschlagene Methode kombiniert formale Verifikation (SAT-Lösung) mit aktivem Lernen.

A. Formale Grundlage

Produkt-MDP: Die Autoren definieren ein Produkt-MDP, das den physischen Zustand $s$ mit dem Zustand der Reward Machine $u$ kombiniert. Die optimale Policy in diesem Produkt-MDP induziert eine „History Policy" $\pi_h$ , die nur auf Zustandssequenzen $\tau$ basiert.
Policy-Äquivalenz: Zwei RMs gelten als äquivalent, wenn sie dieselbe History Policy induzieren. Das Ziel ist es, eine RM zu finden, die zur wahren (aber unbekannten) RM äquivalent ist.

B. SAT-basierte Inferenz (Schritt 1)

Um die Übergangsfunktion $\delta_u$ der RM und die Labeling-Funktion $L$ zu lernen, wird ein Boolean Satisfiability (SAT) Problem formuliert:

Kodierung: Die unbekannten Funktionen werden als binäre Matrizen kodiert.
Negative Beispiele: Der Kern der Constraints basiert auf dem Lemma, dass zwei Zustandssequenzen $\tau$ und $\tau'$ , die zu unterschiedlichen Aktionen in der Policy führen ( $\pi_h(a|s, \tau) \neq \pi_h(a|s, \tau')$ ), auch zu unterschiedlichen Knoten in der RM führen müssen. Diese Paare werden als „negative Beispiele" bezeichnet.
Constraints: Das SAT-Problem erzwingt, dass die gelernte Funktion konsistent mit allen negativen Beispielen ist, eine gültige Funktion darstellt und eine Ankerbedingung (z.B. $L(1)=1$ ) erfüllt, um Permutationen zu vermeiden.
Theoretisches Ergebnis (Proposition 1): Es wird bewiesen, dass eine ausreichende Tiefe $l^*$ existiert (spezifiziert als $l^* = |S| \cdot u_{max}^2$ ), sodass das SAT-Problem mit dieser Tiefe lösbar ist, wenn es für jede größere Tiefe lösbar ist. Dies garantiert, dass man nicht unendlich tief in die Historie schauen muss, um die Lösung einzugrenzen.

C. Aktive Erweiterung (Schritt 2)

Da die Anzahl der möglichen Trajektorien exponentiell mit der Tiefe wächst, ist eine exhaustive Enumeration (alle Pfade speichern) oft unmöglich.

Idee: Nicht alle Trajektorien sind gleich informativ. Viele Pfade führen zu redundanten Informationen bezüglich der Einschränkung des Hypothesenraums.
Algorithmus:
1. Start mit einer „Burn-in"-Tiefe $l$ und einer Menge zulässiger SAT-Lösungen.
2. Aktive Abfrage: Der Algorithmus sucht nach Paaren von Trajektorien $\{\tau, \tau'\}$ , die den aktuellen Hypothesenraum am effektivsten teilen (Volume-Removal-Ansatz). Konkret werden Paare gesucht, bei denen etwa die Hälfte der aktuellen Kandidaten-RMs zu demselben Knoten führt und die andere Hälfte zu einem anderen.
3. Query: Diese vielversprechenden Paare werden an die History Policy „gefragt" (d.h. geprüft, ob sie tatsächlich negative Beispiele sind).
4. Inkrementelles Lernen: Neue negative Beispiele werden dem SAT-Problem hinzugefügt, um die Menge der zulässigen Lösungen zu verfeinern, ohne das gesamte Problem neu zu lösen.

3. Schlüsselergebnisse

Die Methode wurde in Grid-World-Umgebungen (Warehouse und Patrouille) evaluiert:

Erfolgreiche Recovery: In beiden Aufgaben („pick_n_drop" und „patrolABCD") konnte der Algorithmus die Ground-Truth-RM und die Labeling-Funktion (bis auf Umbenennung) vollständig wiederherstellen.
Effizienzgewinn (Speicher):
- Bei einer Tiefe von 13 benötigte die exhaustive Methode (alle Pfade speichern) ca. 24,76 GB Speicher für negative Beispiele.
- Die aktive Methode benötigte nur 0,147 GB (eine Reduktion um zwei Größenordnungen), da sie nur ca. 10.300 relevante Trajektorien-Äste speicherte statt 414 Millionen.
Effizienzgewinn (Rechenzeit):
- Die exhaustive Methode benötigte im Durchschnitt über 7100 Sekunden für das SAT-Lösen (und stoppte bereits bei Tiefe 9 aufgrund von Speicherengpässen).
- Die aktive Methode erreichte eine mittlere Gesamtzeit von 3544 Sekunden (ca. 2-fache Beschleunigung) und konnte bis zur Tiefe 13 skalieren.
Konvergenz: Mit einer aktiven Abfrage-Strategie ( $N_{active}=100$ oder $200$) konvergierte der Algorithmus in 96,6% der Fälle bis zur Tiefe 13 zur wahren Lösung, während eine zufällige Abfragestrategie selbst bei Tiefe 20 versagte.

4. Bedeutung und Beiträge

Erster Ansatz ohne Labels: Dies ist der erste Ansatz, der sowohl die Reward Machine als auch die Labeling-Funktion de novo aus reinen Zustands-Trajektorien lernt, ohne auf vordefinierte Symbole oder Beobachtungen von Belohnungen angewiesen zu sein.
Identifizierbarkeit: Das Paper liefert theoretische Garantien (Proposition 1) dafür, dass das Problem unter bestimmten Bedingungen (ausreichende Tiefe) lösbar ist.
Skalierbarkeit durch aktives Lernen: Durch die Einführung eines aktiven Abfrage-Mechanismus wird das Problem der exponentiellen Explosion des Zustandsraums gelöst. Dies macht die Inferenz von RMs in komplexeren Umgebungen praktikabel, wo exhaustive Methoden an Speicher- und Rechengrenzen stoßen.
Grundlage für zukünftige Forschung: Die Arbeit etabliert ein Fundament für das Verständnis von „Gedächtnis" in sequentiellen Entscheidungsprozessen. Sie zeigt, wie die strukturelle Gedächtnisnotwendigkeit (im Gegensatz zur epistemischen Unsicherheit) direkt aus Policy-Daten extrahiert werden kann.

Fazit: Das Paper bietet einen robusten Rahmen, um die verborgene logische Struktur komplexer Roboteraufgaben automatisch zu entdecken, indem es formale Verifikation mit effizientem aktivem Lernen kombiniert, um die Abhängigkeit von manueller Spezifikation und externen Labels zu eliminieren.