Apprenticeship learning with prior beliefs using inverse optimization

Diese Arbeit stellt einen regularisierten Rahmen für das Apprenticeship Learning vor, der Vorwissen über die Kostenstruktur nutzt, um die Inverse Optimierung und das Inverse Reinforcement Learning für suboptimale Experten zu vereinen und durch einen stochastischen Spiegelabstiegslöser effizient zu lösen.

Das Wesentliche

Stell dir vor, du möchtest ein neues Auto lernen zu fahren. Normalerweise müsstest du dem Auto erst eine lange Liste von Regeln geben: „Fahre schnell, aber nicht zu schnell", „Halte Abstand", „Sparsam mit dem Benzin". Das ist schwierig, weil man diese Regeln oft gar nicht genau kennt oder falsch formuliert.

In diesem Papier beschreiben die Autoren einen clevereren Weg: Lernen durch Beobachten, kombiniert mit einem intuitiven Bauchgefühl.

Hier ist die Geschichte in einfachen Schritten:

1. Das Problem: Der perfekte Lehrer existiert nicht

Stell dir vor, du hast einen Fahrlehrer (den „Experten"), der sehr gut fährt. Du beobachtest ihn und willst genau so fahren.

• Das alte Problem: Früher haben Computer versucht, aus dem Verhalten des Lehrers allein herauszufinden, welche Regeln er befolgt. Das ist wie ein Rätsel, bei dem es tausend verschiedene Lösungen gibt. Vielleicht fährt der Lehrer schnell, weil er es eilig hat, oder weil er den Motor liebt? Ohne weitere Hinweise ist das unlösbar.
• Das neue Problem: Oft ist der Lehrer gar nicht perfekt. Vielleicht ist er müde, hat einen schlechten Tag oder fährt einfach nur „gut genug". Wenn der Computer annimmt, der Lehrer sei ein Gott, wird er verwirrt, wenn der Lehrer mal einen Fehler macht.

2. Die Lösung: Ein „Bauchgefühl" (Prior Beliefs)

Die Autoren sagen: „Halt! Wir brauchen nicht nur den Lehrer, sondern auch unser eigenes Wissen."
Stell dir vor, du hast ein Bauchgefühl (im Papier „Prior Beliefs" genannt). Du weißt aus Erfahrung: „Autos verbrauchen Benzin, also sollte das Fahren etwas kosten. Und Unfälle sind schlecht, also sollte das Risiko teuer sein."

Du nimmst dieses Bauchgefühl (eine grobe Schätzung der Regeln) und mischst es mit dem, was du vom Lehrer siehst.

• Wenn der Lehrer perfekt ist, vertraust du ihm mehr.
• Wenn der Lehrer Fehler macht (suboptimal), vertraust du deinem Bauchgefühl mehr, um die wahren Regeln zu finden.

3. Der Trick: Ein mathematisches Seilziehen

Das Herzstück des Papiers ist eine Art Seilziehen zwischen zwei Zielen:

1. Ziel A: Finde Regeln, die das Verhalten des Lehrers erklären.
2. Ziel B: Bleib nah an deinem Bauchgefühl (damit die Regeln nicht völlig verrückt werden).

Die Autoren haben ein mathematisches Werkzeug entwickelt (ein „Seilziehen-Problem"), das diese beiden Ziele balanciert. Ein spezieller Schalter (genannt $\alpha$) entscheidet, wie stark du auf dein Bauchgefühl hörst.

• Schalter auf 0: Du ignoriert dein Bauchgefühl und glaubst blind dem Lehrer (selbst wenn er dumm ist).
• Schalter hoch: Du hörst mehr auf dein Bauchgefühl, um die Fehler des Lehrers zu korrigieren.

4. Die Methode: Der lernende Roboter (Stochastic Mirror Descent)

Um dieses Seilziehen zu lösen, benutzen die Autoren einen Algorithmus, den sie „Stochastic Mirror Descent" nennen.

• Die Analogie: Stell dir vor, du bist in einem dunklen Raum und suchst den tiefsten Punkt (die besten Regeln). Du tastest dich vorsichtig vor, machst kleine Schritte, prüfst, ob es besser wird, und korrigierst deinen Weg.
• Weil der Raum riesig und komplex ist (viele Straßen, viele Entscheidungen), machen sie das nicht Schritt für Schritt, sondern nehmen zufällige Schnappschüsse („Stochastic"), um schnell voranzukommen.

5. Was passiert in der Praxis? (Die Experimente)

Die Autoren haben das an zwei Beispielen getestet:

• Ein Lagerhaus: Ein Roboter muss Waren bestellen. Ein „falscher" Lehrer bestellt zu wenig, weil er denkt, Lagerkosten wären höher als sie sind. Das System nutzt das Bauchgefühl (die echten Lagerkosten), um dem Roboter die richtigen Bestellungen beizubringen, obwohl der Lehrer falsch lag.
• Ein Labyrinth (Gridworld): Ein Roboter muss durch ein Labyrinth mit Hindernissen laufen. Ein Lehrer läuft manchmal gegen Wände. Das System lernt trotzdem die richtigen Regeln für das Labyrinth, indem es die Hindernisse (die „teuren" Stellen) mit Hilfe des Bauchgefühls identifiziert, auch wenn der Lehrer sie ignoriert hat.

Zusammenfassung

Dieses Papier sagt im Grunde:
„Lass uns nicht versuchen, den perfekten Lehrer zu finden. Stattdessen nehmen wir einen Lehrer, der vielleicht Fehler macht, und kombinieren seine Beobachtungen mit unserem eigenen gesunden Menschenverstand (dem Bauchgefühl). Mit einem cleveren mathematischen Seilziehen finden wir so die besten Regeln, um ein Verhalten zu lernen, das besser ist als das des Lehrers selbst."

Es ist wie ein Schüler, der nicht nur den Lehrer kopiert, sondern auch sein eigenes Wissen nutzt, um zu verstehen, warum der Lehrer so handelt – und dabei sogar Fehler des Lehrers korrigiert.

Technische Zusammenfassung

Titel: Apprenticeship Learning mit Vorwissen unter Verwendung von inverser Optimierung

Autoren: Mauricio Junca (Universidad de los Andes) und Esteban Leiva (University of Southern California).

---

1. Problemstellung

Das Papier adressiert das Problem des Lernens aus Demonstrationen (Learning from Demonstrations, LfD) im Kontext von Markov-Entscheidungsprozessen (MDPs).

• Hintergrund: In der klassischen Reinforcement Learning (RL)-Praxis muss eine Kostenfunktion (Cost Function) manuell definiert werden, was in realen Szenarien oft schwierig und fehleranfällig ist. Inverse Reinforcement Learning (IRL) versucht, diese Kostenfunktion aus dem Verhalten eines Experten abzuleiten.
• Herausforderungen:
  1. Fehlgestelltheit (Ill-posedness): Es gibt oft unendlich viele Kostenfunktionen, die das beobachtete Expertenverhalten erklären können.
  2. Suboptimale Experten: In der Praxis sind Experten selten perfekt optimal. Herkömmliche IRL-Methoden, die von optimalen Experten ausgehen, scheitern oder liefern suboptimale Ergebnisse, wenn der Experte nur annähernd optimal handelt.
  3. Einschränkungen bestehender Methoden: Der etablierte Ansatz des Apprenticeship Learning (AL) von Abbeel & Ng (2004) und dessen Weiterentwicklungen (z. B. Kamoutsi et al., 2021) gehen oft davon aus, dass die wahre Kostenfunktion eine konvexe Kombination bekannter Basisvektoren ist. Dies erfordert eine aufwendige und fehleranfällige Feature-Engineering-Phase.

Das Ziel der Autoren ist es, ein Framework zu entwickeln, das Vorwissen (Prior Beliefs) über die Struktur der Kostenfunktion integriert, um die Suche nach plausiblen Kostenfunktionen zu steuern, und dabei robust gegenüber suboptimalen Experten ist.

---

2. Methodik

Die Autoren verbinden die Konzepte der Inversen Optimierung (IO), des Inversen Reinforcement Learning (IRL) und des Apprenticeship Learning (AL).

A. Theoretisches Framework

1. Inverse Optimierung (IO): Das Problem wird als inverses Optimierungsproblem formuliert, bei dem eine Kostenfunktion $c$ gesucht wird, die ein beobachtetes Verhalten (hier: die Besetzungsmaßnahme $\mu_{\pi_E}$ des Experten) als optimal erklärt.
2. Einbeziehung von Vorwissen: Um die Fehlgestelltheit zu adressieren, führen die Autoren einen Proxy-Kostenvektor $\hat{c}$ ein, der das Vorwissen des Lernenden repräsentiert.
3. Problemformulierung für suboptimale Experten (IO-AL$\alpha$):
   Da Experten oft suboptimal sind, wird die strikte Komplementaritätsbedingung (Complementary Slackness) relaxiert. Das resultierende Problem ist ein reguliertes Min-Max-Problem:
   $$\min_{c, u} \alpha \|c - \hat{c}\|^2_2 + \langle \mu_{\pi_E}, c - T_\gamma^\top u \rangle$$
   unter der Nebenbedingung $c - T_\gamma^\top u \geq 0$.
   • $c$: Zu lernender Kostenvektor.
   • $u$: Dualvariable (Wertfunktion).
   • $\mu_{\pi_E}$: Besetzungsmaßnahme des Experten.
   • $\alpha$: Regularisierungsparameter, der den Trade-off zwischen der Nähe zum Vorwissen $\hat{c}$ und der Erklärung des Expertenverhaltens steuert.
   • Der Term $\langle \mu_{\pi_E}, c - T_\gamma^\top u \rangle$ misst die Suboptimalität des Experten unter der gefundenen Kostenfunktion.

B. Umformulierung als Min-Max-Problem

Mittels Lagrange-Dualität wird das Problem in ein konvex-konkaves Min-Max-Problem (RLfD$\alpha$) überführt:
$$\min_{(c,u) \in \mathcal{B}} \max_{\mu \in \Delta} \left( \alpha \|c - \hat{c}\|^2_2 + \langle \mu_{\pi_E} - \mu, c - T_\gamma^\top u \rangle \right)$$
Dies ermöglicht die Anwendung effizienter stochastischer Optimierungsalgorithmen.

C. Algorithmus: Stochastic Mirror Descent (SMD-RLfD)

Um das Min-Max-Problem zu lösen, entwickeln die Autoren einen angepassten Stochastic Mirror Descent (SMD) Algorithmus:

• Gradientenschätzer: Da der Zustandsübergang und die Experten-Besetzungsmaßnahme nicht analytisch bekannt sind, werden erwartungstreue Gradientenschätzer basierend auf einem Generative-Model-Oracle (Zufallsstichproben von Trajektorien) konstruiert.
• Konvergenzgarantie: Es werden theoretische Konvergenzschranken hergeleitet. Die Anzahl der Iterationen $T$ skaliert quadratisch mit der Anzahl der Aktionen und kubisch mit der Anzahl der Zuständen.
• Besonderheit: Der Algorithmus liefert eine erwartete $\epsilon$-approximative Lösung, die sowohl eine gute Kostenfunktion als auch eine gute Apprenticeship-Policy (Schüler-Policy) liefert.

---

3. Hauptbeiträge

1. Einheitliche Sichtweise: Das Papier zeigt, dass das konvex-analytische AL-Formalismus von Kamoutsi et al. (2021) ein Spezialfall (eine Relaxierung) des vorgeschlagenen IO-Frameworks ist, wenn der Regularisierungsterm fehlt ($\alpha = 0$) und der Experte optimal ist.
2. Handling suboptimaler Experten: Durch die Einführung des Regularisierungsterms $\alpha \|c - \hat{c}\|^2_2$ wird das Problem für suboptimale Experten lösbar. Der Parameter $\alpha$ balanciert zwischen der Treue zu den Demonstrationen und dem Vorwissen.
3. Vermeidung von Feature-Engineering: Im Gegensatz zu klassischen AL-Ansätzen, die eine konvexe Hülle vordefinierter Basisvektoren benötigen, erlaubt das vorgeschlagene Framework die Suche in einer allgemeinen konvexen Klasse von Kostenfunktionen (z. B. einem Box-Bereich), was die Notwendigkeit manueller Feature-Extraktion eliminiert.
4. Theoretische Fundierung: Herleitung von Konvergenzschranken für den SMD-Algorithmus in diesem spezifischen Kontext und Beweis, dass die Lösung des Min-Max-Problems direkt mit der optimalen Lösung des ursprünglichen IO-Problems korreliert.

---

4. Ergebnisse und Experimente

Die Autoren testen das Framework an zwei Szenarien: einem Inventarsteuerungsproblem (niedrige Dimension) und einem Gridworld (höhere Dimension).

• Robustheit gegenüber suboptimalen Experten:
  • In Experimenten mit einem suboptimalen Experten (der aufgrund falscher Kostenannahmen handelt) konnte das Framework durch die richtige Wahl von $\hat{c}$ und $\alpha$ die wahre Kostenfunktion und eine überlegene Policy wiederherstellen.
  • Ohne Regularisierung ($\alpha=0$) oder mit falschem Vorwissen versagte die Methode teilweise. Mit passendem $\alpha$ übertraf die gelernte Policy den Experten deutlich.
• Einfluss von $\alpha$:
  • Ein höheres $\alpha$ führt zu einer Kostenfunktion, die näher am Vorwissen $\hat{c}$ liegt, aber möglicherweise die Demonstrationen weniger genau erklärt.
  • Ein niedrigeres $\alpha$ passt sich stärker den Demonstrationen an, ignoriert aber das Vorwissen.
  • Die Ergebnisse zeigen einen klaren Trade-off, wobei moderate Werte von $\alpha$ oft die beste Balance für die Policy-Performance bieten.
• Vergleich mit konvexer Hülle (Convex Hull):
  • Während die Methode mit konvexer Hülle (Kamoutsi et al.) in kleinen Zustandsräumen schneller konvergiert, übertrifft das vorgeschlagene Framework (Box-Formulierung) es in höheren Dimensionen (Gridworld).
  • Der Grund liegt in der Flexibilität: Die konvexe Hülle ist zu starr für komplexe, hochdimensionale Umgebungen, während die Box-Formulierung flexibler auf Fehler in den Daten reagieren kann.
• Gridworld-Experiment:
  • Hier wurde gezeigt, dass selbst bei unvollständigem Vorwissen (nur teilweise korrekte Kosten für Hindernisse und Ziele) die Regularisierung hilft, eine Kostenfunktion zu lernen, die der wahren Struktur näher kommt als ohne Regularisierung.

---

5. Bedeutung und Fazit

Das Papier leistet einen signifikanten Beitrag zur Theorie des Inversen Reinforcement Learning und des Apprenticeship Learning:

• Praktische Relevanz: Es bietet einen robusten Ansatz für reale Szenarien, in denen Experten nicht perfekt sind und in denen man über physikalisches oder domänenspezifisches Vorwissen verfügt, das nicht in den Demonstrationen enthalten ist.
• Theoretische Klarheit: Es verbindet die Lücken zwischen IO, IRL und AL und zeigt, wie Regularisierung die mathematische Struktur dieser Probleme stabilisiert.
• Algorithmische Effizienz: Der vorgestellte SMD-Algorithmus ist skalierbar und benötigt keine vollständige Kenntnis der MDP-Dynamik (nur Orakel-Zugriff), was ihn für komplexe Umgebungen geeignet macht.

Zukunftsausblick: Die Autoren sehen offenen Forschungsbedarf bei der automatischen Auswahl des Parameters $\alpha$ und der Erweiterung auf sparse Kostenfunktionen (z. B. mittels $L_0$-Norm), was besonders für Umgebungen mit wenigen relevanten Kostenstellen relevant ist.