🤖 AI

Composing Reinforcement Learning Policies, with Formal Guarantees

Dieses Paper schlägt ein neuartiges Framework vor, das reaktive Synthese für die High-Level-Planung mit einem Reinforcement-Learning-Ansatz für das Low-Level-Policy-Training auf latenten Strukturen kombiniert, um Controller für komplexe, zweistufige Umgebungen zu komponieren, während gleichzeitig formale Leistungsgarantien ohne die Notwendigkeit einer Modell-Distillation bereitgestellt werden.

Ursprüngliche Autoren: Florent Delgrange, Guy Avni, Anna Lukina, Christian Schilling, Ann Nowé, Guillermo A. Pérez

Veröffentlicht 2026-08-06

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Florent Delgrange, Guy Avni, Anna Lukina, Christian Schilling, Ann Nowé, Guillermo A. Pérez

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, durch ein riesiges, sich veränderndes Labyrinth zu navigieren. Dies ist nicht nur ein einfaches Labyrinth; es ist eine Welt, in der sich die Wände bewegen können, der Boden sich verändern kann und der Roboter in der Lage sein muss, blitzschnelle Entscheidungen zu treffen, um nicht mit fliegenden Hindernissen zusammenzustoßen. Dies ist die Welt des Reinforcement Learning (RL), eines Zweigs der künstlichen Intelligenz, bei dem Agenten durch Versuch und Irrtum lernen, ganz ähnlich wie ein Hund, der lernt, auf Kommando zu sitzen, um eine Belohnung zu erhalten. Das Ziel ist es, eine „Policy“ zu finden – einen Satz von Regeln, der dem Agenten sagt, was er in jeder Situation tun soll, um das beste Ergebnis zu erzielen.

Es gibt jedoch einen Haken. Während RL großartig darin ist, aus Erfahrung zu lernen, ist es notorisch schlecht darin, Garantien abzugeben. Wenn Sie einen Standard-RL-Roboter fragen würden: „Bist du dir zu 100 % sicher, dass du nicht gegen diesen Gabelstapler fährst?“, kann er normalerweise nicht mit einem mathematischen „Ja“ antworten. Er könnte sagen: „Ich denke, ich werde okay sein“, aber in sicherheitskritischen Aufgaben wie dem Fahren von Autos oder der Steuerung von Stromnetzen reicht ein „Ich denke“ nicht aus. Hier kommt die formale Verifikation ins Spiel. Es ist wie ein strenger mathematischer Beweis, der besagt: „Unter diesen spezifischen Bedingungen ist diese Aktion garantiert sicher.“ Die Herausforderung, vor der Wissenschaftler stehen, ist, dass diese beiden Welten – das Lernen aus Erfahrung und der mathematische Beweis – normalerweise nicht miteinander harmonieren. Lernen erfordert massive, chaotische Daten, während Beweise ordentliche, einfache Modelle erfordern. Dieses Paper begibt sich in dieses chaotische Schnittfeld, um zu sehen, ob wir beides haben können: einen Roboter, der das Schwierige lernt, aber dennoch ein Sicherheitszertifikat besitzt.

Die große Idee: Die Karte und die Räume

Die Autoren, ein Team von Forschern aus Belgien, Israel, den Niederlanden, Dänemark und dem Vereinigten Königreich, schlagen einen klugen Weg vor, das Problem in zwei Teile zu spalten. Stellen Sie sich ein riesiges Lagerhaus vor. Die High-Level-Ansicht ist eine einfache Karte: ein Raster aus Räumen, die durch Türen verbunden sind. Sie kennen die Karte perfekt. Sie wissen, dass Raum A mit Raum B verbunden ist und Raum B mit dem Ausgang. Aber innerhalb der einzelnen Räume? Das ist ein Mysterium. Die „Dynamik“ (wie sich Dinge bewegen, wo die Hindernisse sind) ist unbekannt und chaotisch.

Die Autoren nennen dies eine „Two-Level-Struktur“.

Das High-Level (Die Karte): Dies ist der einfache Teil. Es ist lediglich ein Graph aus Räumen und Türen.
Das Low-Level (Die Räume): Dies ist der schwierige Teil. Innerhalb jedes Raums muss der Agent fahrenden Gabelstaplern, Arbeitern oder anderen Robotern ausweichen. Die Regeln hier sind komplex und unbekannt.

Der Haupttrick der Autoren ist die „Separation of Concerns“ (Trennung der Zuständigkeiten). Sie verwenden zwei verschiedene Werkzeuge für die zwei verschiedenen Ebenen. Für die High-Level-Karte verwenden sie Reactive Synthesis. Betrachten Sie dies als einen superintelligenten, logischen Planer, der die Karte und eine Reihe von Regeln (wie „Erreiche den Ausgang, ohne etwas zu treffen“) betrachten und mathematisch den besten Weg beweisen kann. Es ist wie ein GPS, das sich nie verirrt, weil es eine perfekte Karte besitzt.

Aber das GPS kann dem Roboter nicht sagen, wie er innerhalb eines Raums einem Gabelstapler ausweichen soll. Dafür nutzen sie Reinforcement Learning (RL). Der Roboter lernt durch Simulationen innerhalb jedes Raums, wie er vom Eingang zum Ausgang gelangt, ohne zu kollidieren. Das Problem ist, dass Standard-RL eine „Black Box“ ist – man weiß nicht genau, wie es funktioniert, und man kann nicht beweisen, dass es sicher ist.

Der magische Trick: Das „latente“ Modell

Hier wird das Paper wirklich interessant. Anstatt den Roboter einfach ein unordentliches, riesiges neuronales Netz (ein Gehirn aus Mathematik) für jeden Raum lernen zu lassen, bringen die Autoren dem Roboter bei, ein kompaktes latentes Modell zu lernen.

Stellen Sie sich vor, Sie versuchen, einem Freund einen chaotischen Raum voller beweglicher Hindernisse zu beschreiben. Sie könnten versuchen, jede einzelne Bewegung jedes einzelnen Objekts zu beschreiben, was ewig dauern würde und unmöglich zu merken wäre. Oder Sie könnten eine vereinfachte Skizze (das „latente Modell“) erstellen, die das Wesen des Raums einfängt: „Wenn ich nach links gehe, treffe ich meistens eine Wand; wenn ich nach rechts gehe, finde ich meistens die Tür.“

Die Autoren entwickelten eine neue Trainingsmethode namens WAE-DQN. Dies ist ein schicker Name für einen Prozess, bei dem der Roboter zwei Dinge gleichzeitig lernt:

Wie er handelt (die Policy).
Wie er die vereinfachte Skizze zeichnet (das latente Modell).

Entscheidend ist, dass sie die Skizze nicht nur raten; sie berechnen eine Garantie darüber, wie gut die Skizze ist. Sie verwenden etwas namens PAC-Bounds (Probably Approximately Correct). Betrachten Sie dies als einen „Konfidenzwert“. Es sagt nicht: „Diese Skizze ist perfekt.“ Es sagt: „Wir sind zu 95 % sicher, dass diese Skizze maximal 1 % vom tatsächlichen Verhalten des Raums abweicht.“

Alles zusammenfügen: Der Planer

Sobald der Robot diese vereinfachten Skizzen und die „Konfidenzwerte“ für jeden Raum gelernt hat, setzt der High-Level-Planer ein. Der Planer betrachtet die Karte und die Skizzen. Er fragt: „Wenn ich den Roboter in Raum A schicke und ihm sage, er soll nach rechts gehen, wie hoch ist die Wahrscheinlichkeit, dass er die Tür erreicht?“ Er nutzt die Konfidenzwerte der Skizzen, um dies mathematisch zu beantworten.

Da der Planer die „Sicherheitsmarge“ der Skizze jedes Raums kennt, kann er einen globalen Plan erstellen, der mathematisch garantiert funktioniert, obwohl der Roboter die Details der Räume durch Versuch und Irrtum gelernt hat.

Die Experimente: Funktioniert es?

Das Team testete diese Idee in zwei sehr unterschiedlichen Welten:

Eine Grid World: Ein digitales Labyrinth mit beweglichen Feinden.
ViZDoom: Eine Videospiel-Umgebung (basierend auf dem Klassiker Doom), in der der Roboter unter Verwendung visueller Eingaben (wie einer Kamera) navigieren muss, während er Hindernissen ausweicht.

In der Grid World erstellten sie ein Labyrinth mit 9 Räumen und 11 beweglichen Feinden. Standard-KI (unter Verwendung einer Methode namens DQN) hatte Schwierigkeiten, einen guten Pfad zu lernen, und blieb oft stecken oder kollidierte. Aber die neue Methode? Sie lernte, erfolgreich zu navigieren. Noch beeindruckender war, dass sie das System an einem viel größeren Labyrinth mit 49 Räumen und 47 Feinden testeten. Der Roboter, der dieselben gelernten „Skizzen“ aus den kleinen Räumen verwendete, konnte das riesige Labyrinth erfolgreich durchqueren. Dies beweist die „Wiederverwendbarkeit“ ihres Ansatzes: Sobald man gelernt hat, wie man mit einem Typ von Raum umgeht, kann man dieses Wissen in jedem ähnlichen Raum anwenden, egal wie groß die Karte ist.

Im ViZDoom-Experiment musste der Roboter mit visuellen Eingaben und schießenden Feinden umgehen. Die Ergebnisse zeigten, dass die „latenten Werte“ (die Vorhersagen, die durch die vereinfachten Skizzen getroffen wurden) sehr nah an dem lagen, was tatsächlich im Spiel geschah. Wenn der Robot beispielsweise eine Erfolgschance von 24 % in einem bestimmten Szenario vorhersagte, lag die tatsächliche Erfolgsrate bei etwa 23 %. Diese Nähe beweist, dass die „Skizzen“ genau genug waren, um ihnen zu vertrauen.

Warum das wichtig ist

Der größte Gewinn hier ist nicht nur, dass der Roboter besser im Spiel wurde. Es ist, dass der Roboter besser wurde – mit einem Sicherheitszertifikat.

In der Vergangenheit mussten Sie, wenn Sie wollten, dass ein Roboter durch eine komplexe Umgebung navigiert, zwischen zwei Optionen wählen:

Sicherheit: Die Verwendung eines einfachen Modells, bei dem man alles beweisen kann, der Roboter aber zu „dumm“ ist, um mit dem Chaos der realen Welt umzugehen.
Geschicklichkeit: Die Verwendung eines leistungsstarken Lern-Roboters, der mit Chaos umgehen kann, bei dem man aber keine Ahnung hat, ob er abstürzen wird.

Dieses Paper zeigt einen dritten Weg. Durch die Trennung von „Karte“ und „Räumen“ und indem man den Roboter lehrt, vereinfachte, verifizierte Skizzen der Räume zu lernen, haben sie ein System geschaffen, das sowohl intelligent (es kann mit beweglichen Hindernissen und visuellen Eingaben umgehen) als auch sicher (es kommt mit mathematischen Garantien) ist.

Die Autoren geben zu, dass ihre Methode noch eine „Karte“ der Umgebung benötigt, um zu starten. Sie können einen Roboter nicht einfach in eine völlig unbekannte Welt werfen und erwarten, dass er die Karte von Grund auf selbst erstellt. Aber für Umgebungen, in denen wir das Layout kennen (wie ein Lagerhaus, ein Stadtplan oder ein Softwaresystem), aber nicht die Details dessen, was in den Räumen passiert, bietet dieser Ansatz ein mächtiges neues Werkzeug. Er verwandelt die „Black Box“ des Lernens in eine „Glass Box“, die man inspizieren, verifizieren und vertrauen kann.

Technische Zusammenfassung: Komposition von Reinforcement-Learning-Policies mit formalen Garantien

Problemformulierung
Die Arbeit befasst sich mit der Herausforderung, Steuerungs-Policies für Umgebungen mit einer zweistufigen Struktur zu konstruieren: einem bekannten High-Level-Graphen („Karte“), bei dem jeder Knoten durch einen Markov-Entscheidungsprozess (MDP) mit unbekannter Dynamik, bezeichnet als „Raum“, besetzt ist. Das Ziel besteht darin, eine langfristige Aufgabe zu erfüllen, die durch eine logische Formel über die High-Level-Karte spezifiziert ist (z. B. „erreiche schließlich Knoten $T$ “), während man durch diese Räume navigiert.

Die Kernschwierigkeit liegt im Kompromiss zwischen Skalierbarkeit und formalen Garantien. Traditionelle reaktive Synthese kann formale Garantien für High-Level-Aufgaben liefern, erfordert jedoch ein explizites Modell der gesamten Umgebung, was unmöglich ist, wenn die Raumdynamiken unbekannt oder hochdimensional sind. Im Gegensatz dazu bewältigt Reinforcement Learning (RL) unbekannte, hochdimensionale Dynamiken, verfügt jedoch im Allgemeinen nicht über formale Garantien und hat Schwierigkeiten mit spärlichen Belohnungen (sparse rewards) bei langfristigen Aufgaben. Die Autoren schlagen ein Framework vor, das „Anliegen trennt“ (separation of concerns), indem es reaktive Synthese für den High-Level-Planer und ein neuartiges RL-Verfahren für die Low-Level-Steuerung anwendet, mit dem Ziel, die Skalierbarkeit von RL mit den formalen Garantien der Synthese zu kombinieren.

Methodik
Das Framework liefert einen zweistufigen Controller, bestehend aus einer Sammlung von Low-Level-Policies ( $\Pi$ ) und einem High-Level-Planer ( $\tau$ ).

Low-Level-Lernen (WAE-DQN):
Anstatt eine Policy direkt auf der Rohumgebung zu trainieren und sie dann in ein Modell zu destillieren (ein gängiger zweistufiger Ansatz), schlagen die Autoren ein einheitliches, einstufiges Verfahren namens WAE-DQN vor. Diese Methode trainiert gleichzeitig:
- Eine latente Policy ( $\pi$ ) mittels Deep Q-Networks (DQN).
- Ein prägnantes latentes Modell (einen kleinen MDP) mittels Wasserstein Auto-Encoded MDPs (WAE-MDPs).
Das latente Modell abstrahiert den Zustandsraum des Raums über eine Einbettungsfunktion $\phi$ . Das Trainingsziel minimiert einen Transitionsverlust ( $L_P$ ), der die Diskrepanz zwischen den Übergangsdynamiken der ursprünglichen Umgebung und dem latenten Modell unter der Policy misst. Dieser Prozess liefert „Probably Approximately Correct“ (PAC)-Garantien auf die Qualität der Abstraktion und die Performance der Policy, ohne einen separaten Destillationsschritt.
High-Level-Synthese:
Gegeben sei eine Karte, eine Menge gelernter Low-Level-Policies (eine pro Raum und Ausgangsrichtung) und eine High-Level-Spezifikation, synthetisiert das Framework einen Planer.
- Sie konstruieren einen prägnanten MDP ( $M^G_\Pi$ ), dessen Zustände die Richtung des Eintritts in einen Raum repräsentieren und dessen Aktionen die Wahl der nächsten Ausgangsrichtung darstellen.
- Die Übergangswahrscheinlichkeiten in diesem prägnanten Modell werden durch die Erwartungswerte (Erfolgswahrscheinlichkeiten) der latenten Low-Level-Policies definiert.
- Ein Standard-Planer wird auf diesem prägnanten Modell synthetisiert, um das High-Level-Ziel zu maximieren.
Lifting-Garantien:
Ein entscheidender theoretischer Beitrag ist der Beweis, dass lokal für jeden Raum gelernte Garantien auf den globalen zweistufigen Controller „geliftet“ werden können. Die Autoren zeigen, dass, wenn die initiale Verteilung jedes Raums während des Trainings eine ausreichende Zustandsabdeckung bietet, die Wertunterschiede zwischen der wahren Umgebung und dem abstrahierten Controller beschränkt sind. Dies ermöglicht es, dass die PAC-Schranken der einzelnen Raum-Abstraktionen in formale Garantien für den globalen Planer übergehen.

Wesentliche Beiträge
Die Arbeit skizziert drei wesentliche theoretische Beiträge:

Lern-Garantien für Low-Level-Policies: Die Autoren etablieren eine Schranke (Theorem 1) für den Unterschied zwischen den Werten des latenten Modells und der wahren Umgebung basierend auf dem Transitionsverlust ( $L_P$ ). Sie beweisen ferner (Theorem 2), dass diese Schranken PAC-lernbar sind, was eine Methode zur Berechnung der Stichprobenkomplexität zur Erreichung einer gewünschten Genauigkeit bereitstellt.
Garantien für den synthetisierten Controller: Das Paper beweist Speicher-Schranken für den optimalen High-Level-Planer (Theorem 3) und zeigt, dass ein Planer mit einer Speichergröße, die proportional zur Anzahl der Knoten in der Karte ist, ausreichend ist. Des Weiteren demonstrieren sie (Theorem 4), dass das Finden eines optimalen Planers äquivalent zum Lösen eines MDPs ist, dessen Größe nur von der Kartenstruktur abhängt und die potenziell massive Größe der einzelnen Räume ignoriert.
Einheitliche Lern- und Synthese-Garantien: Die Autoren zeigen (Theorem 5), dass die Minimierung der Verlustfunktion zum Lernen von Abstraktionen unabhängig für jeden Raum garantiert, dass die Werte, die durch den zusammengesetzten zweistufigen Controller in der Abstraktion erzielt werden, den Werten in der wahren Umgebung nahe kommen. Dies validiert den „Separation of Concerns“-Ansatz.

Ergebnisse und Fallstudien
Die Autoren validieren ihr Framework durch zwei Fallstudien, bei denen ein Agent in Umgebungen mit beweglichen adversariellen Hindernissen navigiert:

Grid World: Eine skalierbare Gitterumgebung mit variierenden Zahlen von Räumen und Adversarien. Standard-DQN mit Reward Shaping hatte Schwierigkeiten, Policies zu finden, während das vorgeschlagene WAE-DQN erfolgreich Low-Level Reach-Avoid-Ziele lernte.
ViZDoom: Eine visuelle Umgebung unter Verwendung der Doom-Game-Engine, die komplexe visuelle Eingaben und stochastische Adversary-Verhaltensweisen aufweist.

In beiden Studien erreichte der synthetisierte zweistufige Controller hohe Erfolgswahrscheinlichkeiten, was die Fähigkeit des Ansatzes demonstriert, die Herausforderungen durch spärliche Belohnungen zu bewältigen. Die vorhergesagten Werte in den latenten Modellen stimmten eng mit den empirisch beobachteten Werten in den wahren Umgebungen überein, was die Qualität der gelernten Abstraktionen bestätigt. Bemerkenswerterweise zeigten die Low-Level-Policies, dass sie wiederverwendbar sind; dieselbe Menge an Policies, die auf einer kleineren Konfiguration trainiert wurden, funktionierte effektiv, als die Umgebung hochskaliert wurde (mehr Räume/Adversarien), ohne dass die Low-Level-Komponenten neu trainiert werden mussten.

Bedeutung
Das Paper behauptet, dass sein primärer Vorteil darin besteht, formale Garantien für Controller in Umgebungen zu liefern, in denen traditionelle Synthese aufgrund unbekannter oder komplexer Low-Level-Dynamiken nicht skalierbar ist. Durch die Trennung der High-Level-Planung (gehandhabt durch Synthese) von der Low-Level-Steuerung (gehandhabt durch RL mit PAC-Garantien) reduziert das Framework den Engineering-Aufwand der Reward-Shaping-Aufgaben auf lokale Aufgaben. Es bietet eine Lösung für das Problem der spärlichen Belohnungen in RL und ermöglicht die Wiederverwendbarkeit von Low-Level-Policies über ähnliche Räume oder sich ändernde High-Level-Aufgaben hinweg. Die Arbeit schließt die Lücke zwischen der Skalierbarkeit von Deep RL und der Strenge formaler Methoden und bietet einen Weg zur Verifizierung und Synthese von Controllern für komplexe, mehrstufige autonome Systeme.