🤖 machine learning

Policy Gradient Methods for Non-Markovian Reinforcement Learning

Dieser Beitrag stellt ein belohnungszentriertes Framework für nicht-Markowsche Verstärkungslernen vor, das die Zustandsdynamik des Agenten und die Steuerungsstrategien gemeinsam optimiert, einen neuartigen Policy-Gradient-Theorem sowie den ASMPG-Algorithmus mit theoretischen Konvergenzgarantien und überlegener empirischer Leistung gegenüber prädiktiven Baselines etabliert.

Ursprüngliche Autoren: Avik Kar, Siddharth Chandak, Rahul Singh, Soumitra Sinhahajari, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos

Veröffentlicht 2026-05-12

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Avik Kar, Siddharth Chandak, Rahul Singh, Soumitra Sinhahajari, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos

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

Stellen Sie sich vor, Sie versuchen, einem Roboter beizubringen, ein Labyrinth zu navigieren, aber es gibt einen Haken: Der Roboter ist blind. Er kann weder die Wände noch den Ausgang sehen. Alles, was er weiß, sind die Geräusche, die er hört (wie ein knarrendes Dielenbrett), und die Gefühle, die er spürt (wie das Anstoßen an eine Wand).

In der Welt des Reinforcement Learning (RL) wird dies als nicht-markovisches Problem bezeichnet. Die aktuelle Situation des Roboters hängt nicht nur vom Jetzt ab; sie hängt vollständig von allem ab, was zuvor geschehen ist. Wenn der Roboter gegen eine Wand stößt, weiß er nicht, welche Wand es ist, es sei denn, er erinnert sich daran, wo er gestartet ist und welche Wendungen er genommen hat.

Die meisten Standard-KI-Methoden haben hier Schwierigkeiten, da sie versuchen, die Zukunft allein basierend auf dem „Jetzt" vorherzusagen, oder sie versuchen, eine perfekte Karte der Vergangenheit zu erstellen, die zu schwer und kompliziert wird, um sie mit sich herumzutragen.

Dieser Artikel stellt eine neue Methode vor, um diese blinden Roboter zu unterrichten, genannt ASMPG (Agent State-Markov Policy Gradient). So funktioniert es, unter Verwendung einfacher Analogien:

1. Das Problem: Der „Amnesiker" vs. der „Überdenker"

Der Amnesiker (Standard-MDP): Stellen Sie sich einen Roboter vor, der alles vergisst, sobald er einen Schritt macht. Er weiß nur: „Ich bin hier, ich habe Hunger." Wenn die Umgebung komplex ist (wie ein Gespräch oder ein Labyrinth), scheitert dieser Roboter, weil er den Kontext nicht kennt.
Der Überdenker (historiebasiert): Stellen Sie sich einen Roboter vor, der versucht, jedes einzelne Wort eines Gesprächs oder jeden einzelnen Schritt eines Labyrinths zu merken. Obwohl dies alle Informationen enthält, wächst die Liste der Erinnerungen ins Unendliche. Es wird unmöglich, sie zu verarbeiten.

2. Die Lösung: Das „Smarte Tagebuch" (Agentenzustand)

Die Autoren schlagen einen Mittelweg vor. Statt alles zu vergessen oder alles zu merken, führt der Roboter ein smartes Tagebuch (genannt „Agentenzustand").

Wie es funktioniert: Jedes Mal, wenn der Roboter eine Aktion ausführt oder etwas Neues sieht, aktualisiert er sein Tagebuch. Er schreibt nicht die gesamte Geschichte auf; er schreibt nur eine Zusammenfassung.
- Beispiel: In einem Chatbot erinnert sich das Tagebuch nicht an das gesamte 100-seitige Gespräch, sondern sagt einfach: „Der Benutzer fragt nach dem Status seiner Bestellung und scheint ungeduldig."
Die Wendung: Bei früheren Methoden würden Wissenschaftler versuchen, diese Tagebuchzusammenfassung zu schreiben, indem sie fragten: „Können Sie vorhersagen, was der Benutzer als Nächstes sagen wird?" (ein prädiktives Ziel).
Die Innovation: Dieser Artikel sagt: „Hören Sie auf, die Zukunft zu erraten. Schreiben Sie einfach die Zusammenfassung, die Ihnen hilft, die Belohnung zu erhalten (den zufriedenen Kunden)." Sie bringen dem Roboter bei, das Tagebuch zu schreiben und gleichzeitig zu entscheiden, was zu tun ist, speziell um den Score zu maximieren.

3. Die Methode: Der „Zwillingsmotor"-Ansatz

Der Artikel stellt einen neuen Algorithmus namens ASMPG vor. Stellen Sie sich ein Flugzeug mit zwei Triebwerken vor, bei dem beide Triebwerke gemeinsam optimiert werden:

Motor A (Der Schreiber): Aktualisiert das Tagebuch (den Agentenzustand) basierend auf neuen Eingaben.
Motor B (Der Pilot): Liest das Tagebuch und entscheidet, welche Aktion zu ergreifen ist.

Bei älteren Methoden war der Schreiber festgelegt oder separat trainiert, um ein „guter Vorhersager" zu sein. Bei ASMPG werden Schreiber und Pilot gemeinsam trainiert. Wenn der Pilot eine bestimmte Details im Tagebuch benötigt, um eine gute Entscheidung zu treffen, lernt der Schreiber, dieses Detail aufzunehmen. Wenn der Pilot ein Detail nicht benötigt, lernt der Schreiber, es zu ignorieren. Sie arbeiten als Team, um das Spiel zu gewinnen.

4. Der Beweis: Warum es funktioniert

Die Autoren haben die Mathematik durchgeführt, um zu beweisen, dass dieser Ansatz des „gemeinsamen Trainings" gültig ist.

Sie haben eine neue Formel abgeleitet (ein „Policy-Gradient-Theorem"), die genau zeigt, wie Schreiber und Pilot angepasst werden müssen, um bessere Scores zu erzielen.
Sie haben bewiesen, dass der Roboter, wenn er kleine Anpassungen basierend auf dieser Formel vornimmt, schließlich eine sehr gute Strategie erlernt (mathematisch garantiert konvergent).

5. Die Ergebnisse: Das Spiel gewinnen

Sie haben diesen neuen Ansatz mit dem „smarten Tagebuch" an fünf verschiedenen kniffligen Aufgaben getestet, bei denen der Roboter nicht das gesamte Bild sehen konnte:

CheeseMaze: Ein Roboter, der Käse in einem Labyrinth findet, in dem verschiedene Stellen identisch aussehen.
Hallway Navigation: Gehen durch einen Flur, in dem man nur die Wände direkt neben sich sehen kann.
Gesundheitswesen: Entscheidungen über medizinische Behandlungen, bei denen die Reaktion des Patienten von seiner verborgenen Geschichte früherer Behandlungen abhängt (Toxizität und Resistenz).
Maschinenreparatur: Eine Maschine reparieren, bei der man nur sehen kann, ob sie „krank" oder „gesund" ist, aber die wahre Ursache verborgener Verschleiß und Abnutzung aus der Vergangenheit ist.
CartPole: Ein Stab auf einem Wagen balancieren, wenn man nur die Geschwindigkeit, nicht aber die Position sehen kann.

Das Ergebnis: In allen fünf Fällen lernte der ASMPG-Roboter (der mit dem gemeinsam trainierten smarten Tagebuch) schneller und erzielte höhere Scores als Roboter, die versuchten, durch Vorhersage der Zukunft oder durch Verwendung fester Speichersysteme zu lernen.

Zusammenfassung

Dieser Artikel handelt davon, KI-Agenten beizubringen, wie sie mit Situationen umgehen, in denen „die Gegenwart" nicht ausreicht, um eine Entscheidung zu treffen. Anstatt alles zu merken oder die Zukunft zu erraten, bringen die Autoren der KI bei, eine dynamische, sich entwickelnde Zusammenfassung ihrer Vergangenheit zu führen. Entscheidend ist, dass sie der KI beibringen, diese Zusammenfassung speziell zu erstellen, um das Spiel zu gewinnen, und nicht nur, um ein guter Historiker zu sein. Das Ergebnis ist ein intelligenterer und effizienterer Lerner für komplexe, reale Probleme.

Technische Zusammenfassung: Policy-Gradient-Methoden für nicht-markovsche Reinforcement Learning

Problemstellung

Reinforcement Learning (RL) stützt sich traditionell auf das Framework des Markov-Entscheidungsprozesses (MDP) und geht davon aus, dass Dynamiken und Belohnungen ausschließlich vom aktuellen Zustand und der aktuellen Aktion abhängen. Viele reale Umgebungen – wie teilweise beobachtbare Systeme, Dialog-Agenten, Empfehlungssysteme und Finanzmärkte – sind jedoch inhärent nicht-markovsche Entscheidungsprozesse (NMDPs). In diesen Settings hängen Beobachtungen und Belohnungen von der gesamten Interaktionshistorie ab.

Eine direkte Bedingung der Policies auf die vollständige Historie ist rechnerisch nicht handhabbar, da der Historienraum exponentiell wächst. Während bestehende Ansätze versuchen, die Historie zu komprimieren, stoßen sie oft auf Einschränkungen:

Feste Dynamiken: Einige Methoden gehen davon aus, dass die internen Zustand dynamiken des Agenten feststehen, und optimieren lediglich die Steuerungs-Policy (z. B. Dong et al., 2022).
Prädiktive Ziele: Andere Methoden lernen Zustandsrepräsentationen durch die Optimierung zusätzlicher prädiktiver Ziele (z. B. Vorhersage zukünftiger Beobachtungen), was hochdimensionale Repräsentationen erfordern kann und nicht direkt mit dem ultimativen Ziel der Maximierung der kumulativen Belohnung übereinstimmt (z. B. Subramanian et al., 2022).

Dieser Beitrag adressiert die Herausforderung, in NMDPs gemeinsam eine kompakte Zustandsrepräsentation und eine Steuerungs-Policy zu lernen, ohne sich auf feste Dynamiken oder intermediäre prädiktive Ziele zu verlassen.

Methodik

Agent State-Markov (ASM) Policies

Die Autoren führen eine Klasse von Agent State-Markov (ASM) Policies ein. In diesem Rahmen pflegt der Agent einen internen Zustand $S_t$ , der rekursiv basierend auf dem vorherigen Zustand, der vorherigen Aktion und der aktuellen Beobachtung aktualisiert wird:
$S_t \sim \nu_t(\cdot \mid S_{t-1}, A_{t-1}, O_t)$
Die Steuerungs-Policy $\phi$ bildet dann den aktuellen Agentenzustand auf eine Aktion ab:
$A_t \sim \phi_t(\cdot \mid S_t)$
Das Paar $(\nu, \phi)$ bildet die ASM-Policy. Entscheidend ist, dass die Autoren vorschlagen, die Parameter sowohl der Zustand dynamiken $\nu$ als auch der Steuerungs-Policy $\phi$ gemeinsam zu optimieren, um die erwartete kumulative Belohnung zu maximieren, anstatt $\nu$ festzulegen oder es über Vorhersage zu lernen.

Theoretische Beiträge

Der Beitrag etabliert einen Policy-Gradient-Satz für ASM-Policies und erweitert klassische Ergebnisse sowohl auf episodische als auch auf unendlich-horizontige diskontierte NMDPs.

Gradienten-Ausdruck: Für eine parametrisierte ASM-Policy $\pi_\theta$ wird der Gradient der erwarteten Rendite $J(\theta)$ hergeleitet als:
$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} \left[ \sum_{t} R_{t:\infty} \nabla_\theta \log \pi_\theta(S_t, A_t \mid S_{t-1}, A_{t-1}, O_t) \right]$
wobei $R_{t:\infty}$ die zukünftige Rendite (Belohnung bis zum Ende) darstellt.
Faktorisierung: Aufgrund der Struktur von ASM-Policies faktorisiert der Log-Wahrscheinlichkeits-Term in die Zustand dynamiken und die Steuerungs-Policy:
$\nabla_\theta \log \pi_\theta = \nabla_\theta \log \nu_\theta + \nabla_\theta \log \phi_\theta$
Dies ermöglicht separate, aber simultane Updates der Zustandsrepräsentation und der Policy.
Konvergenzgarantien: Unter Standardannahmen bezüglich Glattheit und Beschränktheit beweisen die Autoren:
- Endzeit-Konvergenz: Die zeitgemittelte quadrierte Gradientennorm konvergiert bei episodischen Aufgaben mit einer Rate von $\tilde{O}(H^{3.5}/\sqrt{K})$ (wobei $H$ der Horizont und $K$ die Anzahl der Iterationen ist).
- Fast-sichere Konvergenz: Bei abnehmenden Schrittwerten konvergiert die Gradientennorm fast sicher gegen null.
- Ähnliche Garantien werden für das unendlich-horizontige diskontierte Setting etabliert, wobei der effektive Horizont durch den Diskontfaktor $\gamma$ bestimmt wird.

Algorithmus: ASMPG

Basierend auf dem Gradientensatz schlagen die Autoren den Agent State-Markov Policy Gradient (ASMPG) Algorithmus vor. Es handelt sich um einen Online-Algorithmus im REINFORCE-Stil, der:

Trajektorien unter Verwendung der aktuellen ASM-Policy sampelt.
Die Gradientenschätzung unter Ausnutzung der rekursiven Struktur des Agentenzustands berechnet.
Die Parameter sowohl des Zustandsdynamik-Netzwerks als auch des Policy-Netzwerks mittels stochastischem Gradientenanstieg aktualisiert.

Experimentelle Ergebnisse

Die Autoren evaluierten ASMPG in fünf nicht-markovschen Umgebungen:

CheeseMaze: Eine teilweise beobachtbare Navigationsaufgabe mit verdeckten (aliasierten) Beobachtungen.
HallwayNavigation: Eine deterministische Labyrinthaufgabe, bei der lokale Wandkonfigurationen mehrdeutig sind.
HealthcareTreatment: Eine Behandlungsplanungs-Aufgabe mit versteckten Variablen für Toxizität und Resistenz.
MachineRepair: Eine Wartungsaufgabe mit versteckten Verschleißniveaus, die den Maschinenverschleiß beeinflussen.
VelocityOnlyCartPole: Eine Steuerungsaufgabe, bei der nur die Geschwindigkeit (nicht die Position) beobachtet wird.

Vergleich: ASMPG wurde mit AIS-KL und AIS-MMD (Subramanian et al., 2022) verglichen, die Zustandsrepräsentationen über prädiktive Ziele (Approximate Information States) lernen.

Ergebnisse:

Über alle fünf Umgebungen hinweg erzielte ASMPG höhere durchschnittliche Belohnungen pro Schritt oder pro Episode im Vergleich zu den prädiktiven Baselines.
Die Leistungslücke war besonders auffällig bei Aufgaben, die Langzeitgedächtnis erfordern, wie CheeseMaze, MachineRepair und VelocityOnlyCartPole.
Die Ergebnisse deuten darauf hin, dass die direkte Optimierung der Zustand dynamiken für das Belohnungsziel effektiver ist als die Optimierung auf prädiktive Suffizienz.

Bedeutung und Behauptungen

Der Beitrag behauptet, dass sein primärer Beitrag eine belohnungszentrierte Formulierung für nicht-markovsches RL ist. Indem die Zustand dynamiken des Agenten als lernbare Komponente behandelt werden, die gemeinsam mit der Steuerungs-Policy optimiert wird, umgeht die Methode die Notwendigkeit zusätzlicher prädiktiver Ziele oder fester Zustandsrepräsentationen.

Zu den wichtigsten Behauptungen gehören:

Theoretische Validität: Die Herleitung eines Policy-Gradient-Satzes für allgemeine NMDPs bietet eine rigorose Grundlage für die gemeinsame Optimierung und erweitert klassische MDP-Ergebnisse.
Praktische Wirksamkeit: Empirische Ergebnisse zeigen, dass die belohnungszentrierte gemeinsame Optimierung Methoden übertrifft, die auf prädiktiven Zustandsrepräsentationen basieren, selbst wenn die Repräsentationsgrößen vergleichbar sind.
Optimalitätsbedingungen: Der Beitrag stellt fest, dass, falls eine „ideale" Agentenzustandsdynamik existiert (eine, die eine hinreichende Statistik für Belohnungen und zukünftige Beobachtungen ist), die Einschränkung der Suche auf ASM-Policies keinen Verlust an Optimalität mit sich bringt.

Die Autoren räumen ein, dass die vorgeschlagene Methode auf REINFORCE-artigen Schätzern beruht, die unter hoher Varianz leiden können. Sie identifizieren die Entwicklung von Actor-Critic-Varianten für ASM-Policies als einen natürlichen Richtungswechsel für zukünftige Arbeiten, um die Varianz zu reduzieren und gleichzeitig das belohnungszentrierte Ziel zu bewahren.