💻 computer science

Neurosymbolic Reasoning with Incremental Knowledge for Sample Efficient Hierarchical Reinforcement Learning

Dieses Paper schlägt ein neurosymbolisches hierarchisches Reinforcement-Learning-Framework vor, das inkrementelles Wissen (InK) und die Belief World Tree Search integriert, um eine aktualisierbare symbolische Planung sowie ein reward-shaped neuronales Lernen zu ermöglichen und dadurch die Sample-Effizienz bei Navigationsaufgaben mit spärlichen Belohnungen und langen Zeithorizonten signifikant zu verbessern.

Ursprüngliche Autoren: Subrat Prasad Panda, Blaise Genest, Arvind Easwaran

Veröffentlicht 2026-08-05

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Subrat Prasad Panda, Blaise Genest, Arvind Easwaran

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 bringen einem Roboter bei, durch ein riesiges, sich veränderndes Labyrinth zu navigieren. In der Welt der Künstlichen Intelligenz ist dies eine klassische Herausforderung, die als Reinforcement Learning (RL) bekannt ist. Denken Sie daran wie beim Training eines Hundes: Sie geben ihm ein Leckerli (eine Belohnung), wenn er etwas richtig macht, und er lernt, diese Handlung zu wiederholen. Aber hier ist der Haken: Wenn das Labyrinth riesig ist und die Leckerlis sehr weit entfernt versteckt sind, könnte der Hund eine Million Jahre lang umherwandern, bevor er zufällig den Pfad findet. Dies ist das Problem der „Sample Efficiency“ – wie viele Versuche benötigt die KI, um zu lernen?

Um dies zu lösen, verwenden Wissenschaftler oft „Hierarchical Reinforcement Learning“ (HRL). Anstatt dass ein Roboter versucht, jeden einzelnen Schritt auf einmal zu verstehen, geben Sie ihm einen Chef und einen Arbeiter. Der Chef (der High-Level-Planer) entscheidet über große Ziele, wie zum Beispiel „gehe in die Küche“, während der Arbeiter (der Low-Level-Controller) die winzigen Muskelbewegungen herausfindet, um dorthin zu gelangen. Normalallerweise ist der Chef eine starre, vorprogrammierte Karte, die sich nie ändert. Aber was ist, wenn das Labyrinth geheime Wände hat, die erst erscheinen, wenn man gegen sie stößt? Ein starrer Chef würde immer wieder versuchen, durch eine Wand zu laufen, die gerade erst erschienen ist, und so Zeit verschwenden. Dieses Paper untersucht einen klügeren Weg: einen Roboter, der die Karte lernt, während er sich bewegt, und die Karte seines Chefs in Echtzeit aktualisiert, basierend auf dem, was der Arbeiter entdeckt.

Die große Idee des Papers: Ein Roboter, der lernt, während er unterwegs ist

Die Autoren, Subrat Prasad Panda und sein Team, schlagen ein neues System namens Neurosymbolic HRL with Incremental Knowledge (InK) vor. Lassen Sie uns den Namen aufschlüsseln: „Neurosymbolic“ bedeutet, dass sie zwei Arten von Gehirnen mischen. Der „neuronale“ Teil ist ein flexibles, lernendes Gehirn (wie ein Deep-Learning-Neuronales Netz), das die physischen Bewegungen handhabt. Der „symbolische“ Teil ist ein logisches, regelbasiertes Gehirn, das die Planung übernimmt, ähnlich wie ein Schachspieler, der vorausdenkt.

In traditionellen Systemen baut das logische Gehirn eine perfekte Karte der Welt auf, bevor der Roboter mit der Bewegung beginnt. Es ist, als würde man versuchen, die gesamte U-Bahn-Karte von London auswendig zu lernen, bevor man das Haus verlässt. Wenn eine Zuglinie gesperrt ist oder eine neue Station eröffnet wird, ist Ihre Karte nutzlos, bis Sie von vorne beginnen. Die Autoren argumentieren, dass dies ineffizient ist. Stattdessen nutzt ihr Roboter Incremental Knowledge (InK). Er beginnt mit einem leeren Blatt oder einer groben Vermutung. Während der „Arbeiter“-Roboter versucht sich zu bewegen und gegen eine Wand stößt, sagt er dem „Chef“: „Hey, hier ist eine Wand!“ Der Chef aktualisiert sofort seine Karte und berechnet den besten Pfad neu. Es ist wie ein GPS, das Ihre Route in dem Moment aktualisiert, in dem Sie im Stau stehen, anstatt darauf zu warten, dass eine neue Karte gedruckt wird.

Die „Belief World“ und die Baumsuche

Das Paper führt einen cleveren Trick ein, um mit Unsicherheit umzugehen. Stellen Sie sich vor, Sie sind in einem dunklen Raum und wissen, dass sich genau eine Wand irgendwo befindet, aber Sie wissen nicht, wo. Sie könnten raten, dass sie links, rechts oder in der Mitte ist. Der Roboter wählt nicht einfach eine Vermutung; er behält eine „Belief Set“ bei – eine mentale Liste aller möglichen Welten, in denen die Wand sein könnte.

Um Entscheidungen in diesem Nebel der Unsicherheit zu treffen, haben die Autoren einen Algorithmus namens Belief World Tree Search (BWTS) entwickelt. Stellen Sie sich einen riesigen Baum vor, der in Ihrem Geist wächst. Der Stamm ist Ihr aktueller Standort. Jedes Mal, wenn Sie eine Richtung wählen müssen, verzweigt sich der Baum. Aber hier ist der Clou: Anstatt nur einen Pfad zu raten, simuliert BWTS tausende möglicher Zukünfte gleichzeitig. Es fragt: „Wenn die Wand hier ist, was ist der beste Zug? Wenn die Wand dort ist, was ist der beste Zug?“ Dann wählt es den Zug, der über all diese Möglichkeiten hinweg im Durchschnitt am besten funktioniert.

Das Paper argumentiert explizit gegen die Verwendung von Standard-„Zufalls“-Ratemetoden (wie einige ältere Algorithmen, die einfach Würfel werfen, um zu sehen, was passiert). Die Autoren fanden heraus, dass zufälliges Raten in einem Labyrinth oft dazu führt, dass der Roboter im Kreis läuft und Zeit verschwendet. Stattdessen nutzt BWTS „strategische Rollouts“ – es simuliert Pfade unter Verwendung intelligenter, vorgeplanter Strategien (wie „scanne immer nach links, wenn du gegen eine Wand stöst“), um schnell die beste Route zu finden, ohne sich zu verirren.

Was sie herausgefunden haben: Geschwindigkeit und Intelligenz

Das Team testete ihre Idee in Computersimulationen von Labyrinthen, die von einfachen Gittern bis hin zu komplexen 3D-Umgebungen mit einem virtuellen „Ameisen“-Roboter mit vielen Gelenken reichten.

Massive Geschwindigkeitsgewinne: Im Vergleich zur alten „Baue zuerst die Karte“-Methode (im Paper als RGL bezeichnet) war die neue InK-Methode unglaublich schneller im Lernen. In einem „Four Rooms“-Labyrinth benötigte die alte Methode etwa 2.080 Schritte, um das Ziel zum ersten Mal von Null an zu erreichen. Die neue InK-Methode benötigte nur 64,9 Schritte. Das sind etwa 30- bis 100-mal weniger Versuche.
Zeitersparnis: Der Zeitunterschied war noch drastischer. Die alte Methode dauerte über 96 Sekunden, nur um den ersten Pfad zu finden. Die neue Methode erledigte dies in 0,02 Sekunden.
Die Kraft des Vorwissens: Als der Roboter einen Hinweis über die Welt erhielt (wie „da ist eine Wand irgendwo, aber ich weiß nicht wo“), glänzte der BWTS-Algorithmus. In diesen Fällen nutzte er die halbe Anzahl an Samples (Versuchen) im Vergleich zum Standard-Planer, obwohl er etwas mehr Rechenzeit für die komplexe Mathematik benötigte.
Komplexe Umgebungen: Das System funktionierte selbst im „Ant-Maze U-Room“, einer hochdimensionalen Herausforderung mit 29 Dimensionen der Bewegung. Die alte Methode benötigte etwa 10.000 Schritte, um ihre Karte aufzubauen, während die neue Methode das Ziel in etwa 1.507 Schritten (oder sogar 1.134 Schritten mit dem BWTS-Planer) erreichte.

Was sie nicht fanden (und was sie ablehnten)

Das Paper ist vorsichtig dabei, zu sagen, was in diesem speziellen Setup nicht gut funktioniert. Sie testeten einen populären Algorithmus namens BAMCP, der versucht, Unsicherheit zu handhaben, indem er davon ausgeht, dass jeder Teil des Labyrinths unabhängig ist (wie die Annahme, dass die Wand in der Küche nichts mit der Wand im Schlafzimmer zu tun hat). Die Autoren fanden heraus, dass dieser Ansatz in ihren Labyrinth-Tests kläglich scheiterte. Da die Wände strukturell miteinander verknüpft waren (wenn dort eine Wand ist, kann dort keine andere sein), führte die Annahme der Unabhängigkeit zu schlechten Entscheidungen und Zeitverschwendung. BAMCP benötigte im Durchschnitt 28 bis 40 Schritte, während die neue Methode 21 bis 23 benötigte, und sie lief viel langsamer.

Die Autoren merken auch an, dass obwohl ihre Methode schneller ist, der BWTS-Algorithmus rechenintensiv ist. Wenn Sie über keinerlei Vorwissen über die Welt verfügen, ist der einfachere „D*“-Planner (ein Standard-inkrementeller Planer) tatsächlich schneller und ausreichend. Man benötigt erst den schicken BWTS-Baum-Suchalgorithmus, wenn man spezifische strukturelle Hinweise über die Welt auszunutzen hat.

Das Fazit

Dieses Paper legt nahe, dass Roboter durch die Kombination eines flexiblen lernenden Gehirns mit einem logischen Planer, der seine Karte in Echtzeit aktualisiert, komplexe, unbekannte Welten viel schneller lernen können als bisher. Sie haben nicht nur einen Roboter simuliert; sie haben gezeigt, dass die neue Methode in diesen spezifischen Labyrinth-Szenarien die alte „Lerne erst alles“-Methode konsequent übertrifft und massive Mengen an Zeit und Aufwand spart. Es ist ein Schritt hin zu Robotern, die ein neues Haus erkunden, lernen, wo die Möbel stehen, und die Küche finden können, ohne ein Handbuch für jedes einzelne Zimmer zu benötigen.

Technisches Resümee: Neurosymbolische Argumentation mit inkrementellem Wissen für sample-effizientes hierarchisches Reinforcement Learning

1. Problemstellung

Deep-Reinforcement-Learning-Agenten (DRL) haben Schwierigkeiten in Umgebungen, die durch spärliche Belohnungen (sparse rewards) und langfristige Planung (long-horizon reasoning) gekennzeichnet sind, und leiden oft unter einer prohibitiven Stichprobenkomplexität (sample complexity). Während Hierarchisches Reinforcement Learning (HRL) dies durch die Zerlegung von Aufgaben über Abstraktionsebenen hinweg mildert, verlassen sich Standardansätze typischerweise auf Paradigmen mit nicht-inkrementellem Wissen (non-InK). Bei diesen Methoden, wie etwa SoRB und RGL, erfordert der hochgradige symbolische Planer ein vollständiges, statisches abstraktes Weltmodell, das durch exhaustive Exploration konstruiert werden muss, bevor jegliches zielgerichtete Verhalten beginnen kann. Dies schafft eine fundamentale Ineffizienz: Der Agent muss die gesamte Umgebung explorieren, unabhängig vom spezifischen Ziel.

Darüber hinaus besteht in neurosymbolischem HRL oft eine semantische Lücke zwischen dem hochgradigen symbolischen Planer und dem niedergradigen neuronalen Controller. Der hochgradige Planer setzt voraus, dass bestimmte Aktionen ausführbar sind, aber der niedergradige neuronale Policy (der oft unabhängig oder in einer anderen Umgebung trainiert wurde) kann diese aufgrund dynamischer Beschränkungen, Stochastik oder nicht modellierter Hindernisse möglicherweise nicht ausführen. Bestehende neurosymbolische Ansätze lassen Mechanismen vermissen, um das hochgradige Weltmodell basierend auf dem Feedback der Ausführung im Niedergrad zu aktualisieren. Umgekehrt aktualisieren klassische Ansätze mit inkrementellem Wissen (InK) in der Robotik (z. B. Active SLAM, D*) zwar Weltmodelle während der Ausführung, setzen jedoch typischerweise symbolische Komponenten auf beiden Ebenen voraus und versäumen es, die policy-abhängige Dynamik neuronaler Niedergrad-Controller zu adressen.

Schließlich sind aktuelle Planungsalgorithmen wie D* oder Bayesian Adaptive MDP Solver (BAMCP) suboptimal, wenn strukturelles Vorwissen existiert (z. B. „es befindet sich genau eine Wand an einem unbekannten Ort“). D* plant basierend auf aktuellen Beobachtungen neu, ignoriert aber die Menge der möglichen Welten (Belief Set), um die durchschnittliche Performance zu optimieren. BAMCP setzt Unabhängigkeit zwischen Zustands-Aktions-Übergängen voraus, was die Erfassung struktureller Beschränkungen, bei denen der Ort eines Hindernisses die Möglichkeiten anderer einschränkt, nicht leisten kann.

2. Methodik

Die Autoren schlagen Neurosymbolisches HRL mit inkrementellem Wissen (InK) vor, ein Framework, das symbolische Planung mit neuronaler Steuerung integriert und gleichzeitig das Weltmodell basierend auf Ausführungspfaden aktualisiert.

2.1 Neurosymbolisches HRL mit InK

Das Framework verwendet eine zwei-stufige Hierarchie:

Hochgradig (Symbolisch): Unterhält ein aktualisierbares abstraktes Weltmodell ( $M$ ), das die Umgebung als eine Menge von symbolischen Zuständen und Aktionen darstellt. Es führt die Planung mittels eines inkrementellen Planers (z. B. D*) durch, um Subziele zu generieren. Entscheidend ist, dass dieses Modell in Echtzeit basierend auf dem Feedback der Ausführung im Niedergrad aktualisiert wird.
Niedriggradig (Neuronal): Ein zielgerichteter neuronaler Policy ( $\pi_l$ ) führt die kontinuierliche Bewegungssteuerung aus, um die vom Hochgrad vorgegebenen Subziele zu erreichen. Er fungiert als Sensor; seine Erfolge und Misserfolge liefern die Ausführungspfade ( $\rho$ ), die zur Aktualisierung des hochgradigen Modells notwendig sind.
Koordination: Der hochgradige Planer leitet den niedergradigen Agenten zu einem Subziel. Wenn der niedergradige Agent scheitert (z. B. gegen eine unerwartete Wand stößt), erkennt der Monitor dies, und das hochgradige Modell wird aktualisiert, um die neue Beschränkung widerzuspiegeln. Der Planer plant daraufhin neu. Dies eliminiert die Notwendigkeit einer vorherigen exhaustiven Exploration und ermöglicht zielgerichtetes Verhalten ab der allerersten Episode.

2.2 Belief World Tree Search (BWTS)

Um die Einschränkung von Standard-inkrementellen Planern (wie D*), die kein strukturelles Vorwissen über eine Menge möglicher Welten ( $W_0$ ) nutzen, adressieren, führen die Autoren die Belief World Tree Search (BWTS) ein.

Problemformulierung: Der Agent operiert in einer wahren Welt $W_{true} \in W_0$ , wobei $W_0$ eine endliche Menge möglicher Welten ist, die strukturelle Priors kodiert (z. B. „eine Wand existiert, der Ort ist unbekannt“). Das Ziel ist es, eine Policy $\pi$ zu finden, die die durchschnittlichen Kosten über alle Welten in $W_0$ minimiert.
Baumstruktur: BWTS konstruiert einen Suchbaum mit zwei Knotentypen:
- Entscheidungsknoten (Decision Nodes): Repräsentieren die Wahl des Agenten bezüglich einer Aktion.
- Zufallsknoten (Chance Nodes): Repräsentieren das Ergebnis einer Aktion (z. B. ob ein Pfad durch eine Wand blockiert ist oder nicht), wodurch das Belief Set $W$ in Teilmengen aufgeteilt wird ( $W^-$ wo die Wand existiert, $W^+$ wo sie nicht existiert).
Strategische Rollouts: Im Gegensatz zu Standard-Monte-Carlo-Tree-Search (MCTS), das Zufalls-Rollouts verwendet, nutzt BWTS strategische Rollouts. Es evaluiert feste, deterministische Strategien (z. B. „nach links fegen“, „nach rechts fegen“, „zum Ziel bewegen“) über alle Welten im aktuellen Belief Set, um Knotenwerte zu schätzen. Dies reduziert die Varianz und vermeidet die Schleifen, die bei stochastischen Rollouts üblich sind.
Selektion und Expansion: Der Algorithmus verwendet eine UCB-ähnliche Formel, um die Balance zwischen Exploration und Exploitation zu halten. Er priorisiert die Expansion von Zweigen mit größeren Belief Sets, da diese mehr Exploration erfordern, um die Unsicherheit aufzulösen.
Konvergenz: Theoretisch konvergiert BWTS gegen die optimale Policy für das InK-Problem, wenn die Anzahl der Iterationen steigt, vorausgesetzt, der Baum ist vollständig expandiert.

3. Kernbeiträge

Neurosymbolisches HRL mit InK: Der Vorschlag eines hierarchischen Frameworks, bei dem ein hochgradiger symbolischer Planer ein aktualisierbares Weltmodell unter Verwendung eines neuronalen Niedergrad-Controllers unterhält. Dieser Ansatz schließt die semantische Lücke, indem er das Feedback der Ausführung im Niedergrad nutzt, um hochgradige Abstraktionen zu verfeinern, was ein sample-effizientes Lernen ohne vorherige exhaustive Exploration ermöglicht.
Belief World Tree Search (BWTS): Die Entwicklung eines Planungsalgorithmus, der die durchschnittliche Performance über eine Menge möglicher Welten mit strukturellen Abhängigkeiten optimiert. BWTS passt MCTS an, um mit vollständig beobachtbaren, aber unbekannten Dynamiken mit strukturellen Priors umzugehen, und überwindet damit die Unabhängigkeitsannahmen von BAMCP sowie das Fehlen der Nutzung von Belief Sets bei D*.
Empirische Validierung: Demonstration, dass InK HRL gegenüber non-InK-Baselines (speziell RGL) eine signifikante Überlegenheit in der Sample-Effizienz bei verschiedenen Navigationsaufgaben, einschließlich hochdimensionaler kontinuierlicher Steuerung (Ant-Maze), aufweist.

4. Experimentelle Ergebnisse

Die Autoren evaluierten ihren Ansatz in Navigationsaufgaben unter Verwendung von Point-Maze-Umgebungen (Four Rooms, Medium Maze, Hard Maze) und einem hochdimensionalen Ant-Maze U-Room.

InK vs. Non-InK (RGL):
- Sample-Effizienz: InK benötigte 30- bis 100-mal weniger Samples als RGL, um ein Ziel von Grund auf zu erreichen (ohne Vorwissen). Beispielsweise erreichte InK in der Hard Maze das Ziel in ~209 Schritten, verglichen mit ~17.456 Schritten bei RGL.
- Trainingseffizienz: Selbst nachdem RGL seine umfangreiche Trainingsphase (100k+ Samples) abgeschlossen hatte, blieb InK (nach nur 75 erreichten Zielen zum Aufbau seines Wissens) effizienter und benötigte 18 % weniger Samples und 20-mal weniger Zeit pro Ziel.
- Hochdimensionale Steuerung: Im Ant-Maze (29 Dimensionen) erreichte InK das Ziel in ~1.500 Schritten (mit D*) oder ~1.134 Schritten (mit BWTS), während der non-InK-Baseline ~10.000 Schritte benötigt wurden, um ein vollständiges abstraktes Modell aufzubauen.
Vergleich der symbolischen Planer (D vs. BWTS vs. BAMCP):*
- BWTS vs. D:* In synthetischen Grid-Welten mit strukturellen Priors (z. B. eine einzelne horizontale Wand) erzielte BWTS geringere erwartete Kosten (z. B. eine Verbesserung von 15,7 % gegenüber D* in horizontalen Wand-Szenarien), indem es das Belief Set nutzte, um kostspieliges Backtracking zu vermeiden. In komplexen Szenarien ohne klare strukturelle Vorteile (z. B. gemischte Wandtypen) war der Laufzeit-Overhead von BWTS jedoch erheblich für marginale Gewinne.
- BWTS vs. BAMCP: BAMCP schnitt schlecht ab (oft >28 Schritte gegenüber ~24 Schritten bei D*) und war instabil, da es auf stochastischen Rollouts beruhte und die Unfähigkeit besaß, strukturelle Abhängigkeiten zu modellieren (z. B. „wenn Wand bei A, dann keine Wand bei B“). Die strategischen Rollouts und die explizite Modellierung struktureller Beschränkungen von BWTS lieferten eine überlegene Performance.
- Vorwissen: Wenn Vorwissen verfügbar war (z. B. eine Menge von drei bekannten Maze-Typen), halbierte InK-BWTS die Sample-Anzahl im Vergleich zu InK-D*, wenngleich dies eine höhere Rechenlaufzeit während der Planungsphase verursachte.

5. Bedeutung und Behauptungen

Das Paper behauptet, dass Neurosymbolisches HRL mit InK einen praktischen Ansatz für sample-effizientes Lernen in komplexen, belohnungsarmen Umgebungen bietet. Durch die Kombination der strukturellen Argumentation symbolischer Planer mit der Anpassungsfähigkeit neuronaler Controller ermöglicht das Framework es Agenten, mit unvollständigem Wissen zu agieren und ihre Entscheidungen zu verfeinern, während sie neue Informationen gewinnen, was das menschliche Denken widerspiegelt.

Die Autoren betonen:

Sample-Effizienz: Der Ansatz erzielt Gewinne von über 100.000 Umgebungsschritten gegenüber modernsten non-InK-Methoden in Point-Maze-Umgebungen.
Optimalität unter Unsicherheit: BWTS bietet eine Methode, um optimal auf durchschnittliche Weise über Belief-Welten zu planen, und adresset damit eine Lücke, die sowohl inkrementelle Replanner (die Priors ignorieren) als auch Bayesianische Planer (die Unabhängigkeit annehmen) hinterlassen.
Vielseitigkeit: Das Framework ist sowohl für niedrigdimensionale als auch für hochdimensionale kontinuierliche Steuerungsprobleme anwendbar, sofern ein zielgerichteter Niedergrad-Policy vortrainiert oder gelernt werden kann.

Die Arbeit kommt zu dem Schluss, dass der Overhead von BWTS gerechtfertigt ist, wenn strukturelles Vorwissen vorhanden ist, und dass das InK-Framework selbst auch ohne solche Priors erhebliche Effizienzgewinne gegenüber traditionellem HRL bietet. Als zukünftige Arbeit wird vorgeschlagen, InK auf Manipulationsaufgaben auszuweiten und strukturelle sowie probabilistische Priors in einem einzigen Algorithmus zu vereinheitlichen.