🤖 machine learning

From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs

Diese Arbeit charakterisiert die Identifizierbarkeit von Übergangskernen in diskontierten Markov-Entscheidungsprozessen allein aus optimalen Aktionen und zeigt auf, dass während Zustands-Aktions-Belohnungen eine hochdimensionale Familie ununterscheidbarer Dynamiken hinterlassen, Belohnungen, die vom nächsten Zustand abhängen, typischerweise die vollständige Rekonstruktion des Übergangskerns ermöglichen, wohingegen reine Zustandsbelohnungen noch weniger Informationen liefern.

Ursprüngliche Autoren: Neal Batra

Veröffentlicht 2026-08-10

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Neal Batra

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, wie man ein Labyrinth durchquert. Sie zeigen ihm nicht die Karte; stattdessen beobachten Sie einfach, was er tut, wenn Sie ihm verschiedene Ziele vorgeben. Vielleicht sagen Sie ihm: „Finde den Käse“, und er läuft nach links. Dann sagen Sie: „Finde die Batterie“, und er läuft nach rechts. Dies ist die Welt des Bestärkenden Lernens (Reinforcement Learning), eines Zweigs der künstlichen Intelligenz, in dem Agenten durch Versuch und Irrtum lernen, eine „Belohnung“ zu maximieren.

In dieser Welt gibt es zwei wesentliche Dinge, die ein Agent wissen muss: was zu tun ist (die Strategie) und was als Nächstes passieren wird (die Physik der Welt). Der Teil „was zu tun ist“ ist leicht zu beobachten: Man sieht einfach den Entscheidungen des Roboters zu. Der Teil „was als Nächstes passieren wird“ ist das Transitionsmodell – eine geheime Karte von Wahrscheinlichkeiten, die besagt: „Wenn ich hier diesen Knopf drücke, besteht eine Wahrscheinlichkeit von 70 %, in eine Grube zu fallen, und eine Wahrscheinlichkeit von 30 %, einen Schatz zu finden.“ Normalerweise gehen wir davon aus, dass wir die geheime Karte rekonstruieren können, wenn wir die perfekte Strategie des Roboters für jedes mögliche Ziel kennen. Aber was, wenn der Roboter so gut in seinem Job ist, dass er die Karte vor uns verbirgt? Was, wenn zwei völlig unterschiedliche Karten zu exakt denselben perfekten Entscheidungen führen? Dieses Paper stellt eine knifflige Frage: Können wir jemals die wahren Regeln des Spiels kennen, indem wir nur die Züge des Gewinners beobachten?

Das große Kartenrätsel

Stellen Sie sich vor, Sie sind ein Detektiv, der versucht herauszufinden, wie ein Videospiel funktioniert, aber Sie können nicht in den Code schauen. Sie können nur beobachten, wie ein Speedrunner das Spiel perfekt spielt. Der Speedrunner weiß genau, welchen Knopf er in jedem Moment drücken muss, um die höchste Punktzahl zu erreichen.

Das Paper fragt: Wenn Sie diesen Speedrunner für jedes mögliche Belohnungsszenario beobachten (einen Münze sammeln, Lava vermeiden, einen Schlüssel einsammen), können Sie dann die Physik des Spiels bestimmen? Können Sie sicher wissen, ob das Drücken von „Springen“ den Charakter 1,5 Meter oder 3 Meter hoch katapultiert?

Die Antwort lautet laut dieser Forschung auf überraschende Weise: „Nein, nicht immer.“

Der Autor, Neal Batra, beweist, dass man zwei völlig unterschiedliche Game-Engines (zwei verschiedene „Transitionskerne“ oder Karten darüber, wie die Welt funktioniert) haben kann, die für jede erdenkliche Belohnung exakt dieselben perfekten Züge hervorbringen. Es ist, als hätte man zwei verschiedene Labyrinthe, in denen der Pfad zum Ausgang identisch aussieht, obwohl Wände und Fallen unterschiedlich angeordnet sind.

Die drei Arten von Hinweisen

Das Paper testet drei verschiedene Wege, dem Roboter eine Belohnung zu geben, und jeder Hinweis offenbart einen anderen Grad an Wahrheit.

1. Der „Aktions“-Hinweis (Zustands-Aktions-Belohnungen)
Dies ist das häufigste Szenario. Sie sagen dem Roboter: „Wenn du in der Küche bist und den Löffel aufhebst, bekommst du 10 Punkte.“
Das Paper stellt fest, dass selbst wenn Sie die perfekte Wahl des Roboters für jeden Löffel, Gabel und Messer in jedem Raum kennen, Sie die exakte Karte dennoch nicht festlegen können. Es gibt eine ganze Familie von verschiedenen Karten, die dem Roboter gegenüber identisch aussehen.

Der Zaubertrick: Der Autor zeigt, dass diese verschiedenen Karten durch eine mathematische „magische Linse“ (eine Matrix namens L) miteinander verbunden sind. Wenn man die Welt durch diese Linse betrachtet, ändern sich die Wahrscheinlichkeiten, aber die besten Entscheidungen des Roboters bleiben exakt dieselben.
Das Ausmaß des Rätsels: Wenn der Roboter $n$ verschiedene Orte hat, an denen er sein kann, gibt es eine massive, glatte Familie verborgener Karten – genauer gesagt, eine Familie mit $n(n-1)$ Dimensionen der Freiheit. Es ist, als gäbe es unendlich viele Möglichkeiten, die Wände eines Raumes zu streichen, solange man die Tür an der gleichen Stelle lässt. Je mehr Entscheidungen der Roboter hat (mehr Aktionen), desto schwieriger wird es, die Wahrheit zu verbergen, aber es ist immer noch möglich, sie zu verstecken.

2. Der „Nächster-Schritt“-Hinweis (Transitionsabhängige Belohnungen)
Stellen Sie sich nun vor, Sie können den Roboter basierend darauf belohnen, wo er endet. „Wenn du den Knopf drückst und auf der roten Kachel landest, bekommst du 100 Punkte.“
Dies ist ein viel stärkerer Hinweis. Da Sie das Ziel direkt belohnen können, können Sie die Physik des Spiels wesentlich strenger testen.

Das Ergebnis: Wenn der Roboter mindestens zwei Möglichkeiten hat, eine Entscheidung zu treffen, können Sie die exakte Karte in der Regel bestimmen. Der einzige Fall, in dem dies nicht gelingt, ist, wenn der Robot in einem Raum mit nur einer möglichen Bewegung ist. In diesem Fall hat der Roboter keine Wahl, also können Sie nicht testen, ob die Physik unterschiedlich ist. Sobald es jedoch eine Wahl gibt, offenbaren die „Nächster-Schritt“-Hinweise in der Regel die wahre Karte, es sei denn, das Spiel ist auf eine sehr spezifische, seltene Weise manipuliert.

3. Der „Zustands“-Hinweis (Zustandsbelohnungen)
Stellen Sie sich schließlich vor, Sie können nur sagen: „Wenn du in der Küche bist, bekommst du 10 Punkte“, unabhängig davon, was Sie tun.
Dies ist der schwächste Hinweis. Es ist, als würde man dem Roboter sagen: „Sei glücklich, wenn du in der Küche bist“, ohne zu sagen, welchen Knopf er drücken soll.

Das Ergebnis: Dies offenbart am wenigsten Informationen. Zwei völlig unterschiedliche Karten können unter diesen Regeln identisch aussehen. Das Paper beweist, dass das Wissen über die Entscheidungen des Roboters bei diesen einfachen Belohnungen nicht ausreicht, um zwischen vielen verschiedenen Welten zu unterscheiden.

Die Hierarchie der Wahrheit

Das Paper ordnet diese Erkenntnisse in einer klaren Leiter des Wissens:

Transitionsbelohnungen (Belohnung des Ziels) sind am stärksten. Sie können in der Regel die exakte Karte offenbaren.
Aktionsbelohnungen (Belohnung der Wahl) liegen in der Mitte. Sie zeigen Ihnen, wie Aktionen zueinander stehen, hinterlassen aber einen „Nebel“ aus vielen möglichen Karten.
Zustandsbelohnungen (Belohnung des Ortes) sind am schwächsten. Sie hinterlassen den meisten Nebel, wodurch viele verschiedene Karten gleich aussehen.

Warum das wichtig ist

Sie fragen sich vielleicht: „Und was? Wenn der Roboter die richtigen Züge macht, warum kümmern wir uns dann um die Karte?“

Das Paper argumenttiert, dass die Karte für Dinge wichtig ist, die über das bloße Gewinnen hinausgehen. Wenn Sie vorhersagen wollen, was als Nächstes passiert, eine Katastrophe simulieren wollen oder fragen wollen: „Was wäre passiert, wenn ich etwas anderes getan hätte?“ (Kontrafaktika), dann benötigen Sie die echte Karte, nicht nur diejenige, die für das aktuelle Spiel gut aussieht.

Die Studie beweist, dass das Wissen über die besten Züge nicht garantiert, dass man auch die Regeln der Welt kennt. Man kann einen perfekten Agenten haben, der sich wie ein Genie verhält, während sein internes Verständnis der Realität völlig falsch ist. Es ist eine Erinnerung daran, dass das Richtige zu tun nicht immer bedeutet, dass man versteht, warum es richtig ist oder wie die Welt unter der Oberfläche tatsächlich aussieht.

Der Autor rät nicht nur, sondern liefert einen mathematischen Beweis. Er zeigt exakt auf, wie man diese „falschen“ Karten konstruiert, die den Roboter täuschen, und berechnet exakt, wie viele dieser falschen Karten existieren. Es ist eine fundierte, bewiesene Tatsache: Der Pfad zum Schatz mag derselbe sein, aber das Gelände unter Ihren Füßen könnte alles Mögliche sein.

Technisches Resümee: Identifizierbarkeit von Übergangskernen in diskontierten MDPs

Problemstellung
Diese Arbeit untersucht das inverse Problem der Rekonstruktion der Übergangswahrscheinlichkeiten eines endlichen, diskontierten Markov-Entscheidungsprozesses (MDP), gegeben ausschließlich die Menge der optimalen Aktionen für jede mögliche Belohnungsfunktion innerhalb einer spezifischen Klasse. Während das Übergangsmodell sowohl die optimale Strategie als auch die Dynamik der Umgebung bestimmt, können zwei unterschiedliche Übergangskerne identische optimale Aktionen empfehlen. Die zentrale Frage laet sich wie folgt formulieren: Unter welchen Bedingungen sind zwei Kerne $P$ und $Q$ allein basierend auf den von ihnen induzierten optimalen Aktionen ununterscheidbar?

Die Studie vergleicht drei verschiedene Klassen von Belohnungen, die die Dynamik auf unterschiedliche Weise testen:

Zustandsbelohnungen: $r(s)$ , abhängig nur vom aktuellen Zustand.
Zustands-Aktions-Belohnungen: $r(s, a)$ , abhängig vom aktuellen Zustand und der Aktion.
Übergangsabhängige Belohnungen: $r(s, a, s')$ , abhängig vom Zustand, der Aktion und dem resultierenden nächsten Zustand.

Das Papier definiert drei Konzepte der Äquivalenz: $P \equiv_{tr} Q$ (ununterscheidbar unter Übergangsbelohnungen), $P \equiv_{sa} Q$ (ununterscheidbar unter Zustands-Aktions-Belohnungen) und $P \equiv_{s} Q$ (ununterscheidbar unter Zustandsbelohnungen).

Methodik
Die Analyse stützt sich auf die strukturellen Eigenschaften der Bellman-Optimitätsgleichungen und die Beziehung zwischen Wertfunktionen und Übergangskernen.

Zustands-Aktions-Belohnungen: Der Autor konstruiert eine spezifische Familie von Belohnungen, $r^P_v(s, a) = v(s) - \gamma P_{s,a}v$ , die jede Aktion für einen gegebenen Wertevektor $v$ optimal macht. Durch den Vergleich der Policy-Evaluierungsgleichungen unter den Kernen $P$ und $Q$ für diese Belohnungen leitet das Papier eine notwendige und hinreichende Bedingung für Äquivalenz ab. Dies beinhaltet die Identifizierung einer eindeutigen invertierbaren Matrix $L$ , die die Wertfunktionen der beiden Kerne in Beziehung setzt.
Übergangsabhängige Belohnungen: Die Methodik nutzt die Fähigkeit aus, spezifische Übergangszeilen zu isolieren. Wenn ein Zustand mehrere Aktionen besitzt, kann eine übergangsabhängige Belohnung so gestaltet werden, dass sie unter einer Übergangszeile einen erwarteten Wert von Null und unter einer anderen einen Wert von Nicht-Null aufweist, was sie effektiv unterscheidet. Für Zustände mit einer einzelnen Aktion stützt sich die Analyse darauf, ob die spezifische Übergangszeile die Optimalität von Aktionen an anderen Stellen des Zustandsraums beeinflusst.
Zustandsbelohnungen: Die Analyse charakterisiert Äquivalenz durch die Untersuchung der „Policy-Regionen“ $R_P(\pi)$ , definiert als die Menge der Zustandsbelohnungen, für die eine deterministische Strategie $\pi$ optimal ist. Zwei Kerne sind äquivalent, wenn und nur wenn diese Regionen für alle deterministischen Strategien identisch sind.

Kernergebnisse

Zustands-Aktions-Äquivalenz ( $P \equiv_{sa} Q$ ):
Zwei Kerne $P$ und $Q$ liefern für jede Zustands-Aktions-Belohnung dieselben optimalen Aktionen, wenn und nur wenn es eine eindeutige invertierbare Matrix $L$ (mit $L\mathbf{1} = \mathbf{1}$ ) gibt, sodass:
$Q_{s,a} = \left( P_{s,a} + \frac{1}{\gamma} e_s^T (L - I) \right) L^{-1}$
Dies impliziert, dass der Vorteil jeder Aktion relativ zu einer Strategie unter der Transformation erhalten bleibt. In der Nähe eines Kerns mit strikt positiven Einträgen bildet die Menge der ununterscheidbaren Kerne eine glatte Mannigfaltigkeit der Dimension $n(n-1)$ , wobei $n$ die Anzahl der Zustände ist. Dies ist eine strikte Teilmenge des umgebenden Kernraums, was bedeutet, dass der Übergangskern zwar nicht eindeutig bestimmt ist, die Mehrdeutigkeit jedoch auf eine spezifische, niedrigdimensionale Familie beschränkt ist. Das Ergebnis gilt selbst dann, wenn die Daten auf Belohnungen mit einer eindeutigen optimalen Aktion an jedem Zustand beschränkt sind.
Übergangsabhängige Äquivalenz ( $P \equiv_{tr} Q$ ):
Übergangsabhängige Belohnungen liefern signifikant mehr Informationen.
- An jedem Zustand mit mindestens zwei Aktionen wird die Übergangszeile eindeutig identifiziert.
- An Zuständen mit einer einzelnen Aktion wird die Zeile identifiziert, sofern die spezifische Übergangswahrscheinlichkeit die Optimalität von Aktionen an anderen Zuständen nicht beeinflusst (eine Bedingung, die nur für eine Nullmenge von strikt positiven Kernen gilt).
- Folglich ist fast jeder strikt positive Übergangskern durch übergangsabhängige Belohnungen eindeutig identifiziert, sofern der MDP mindestens einen Zustand mit einer echten Wahl (mehrere Aktionen) enthält.
Zustandsbelohnungs-Äquivalenz ( $P \equiv_{s} Q$ ):
Zustandsbelohnungen liefern die geringsten Informationen. Zwei Kerne sind äquivalent, wenn und nur wenn sie für jede Zustandsbelohnung dieselben optimalen deterministischen Strategien teilen. Diese Bedingung ist äquivalent zur Gleichheit der Policy-Regionen $R_P(\pi) = R_Q(\pi)$ für alle $\pi$ . Diese Äquivalenz ist strikt schwächer als die Zustands-Aktions-Äquivalenz; distinkte Kerne können unter Zustandsbelohnungen ununterscheidbar sein, während sie unter Zustands-Aktions-Belohnungen unterscheidbar sind.
Hierarchie der Identifizierbarkeit:
Das Papier etabliert eine strikte Hierarchie der Äquivalenz:
$P \equiv_{tr} Q \implies P \equiv_{sa} Q \implies P \equiv_{s} Q$
Keine der Implikationen ist umkehrbar. Die Erlaubnis, dass die Belohnung von mehr Komponenten des Übergangs (speziell dem nächsten Zustand) abhängt, erhöht die Fähigkeit zur Unterscheidung zwischen verschiedenen Übergangsmodellen strikt.

Bedeutung und Ansprüche
Das Papier behauptet, die Frage gelöst zu haben, wie viel der Übergangsdynamik allein aus optimalem Verhalten rekonstruiert werden kann. Es demonstriert, dass:

Optimale Aktionen sind für die vollständige Rekonstruktion unzureichend: Selbst mit Kenntnis der optimalen Aktionen für alle Belohnungen ist der Übergangskern im Allgemeinen nicht eindeutig bestimmt, wenn die Belohnungen nur von Zuständen oder Zuständen-Aktionen abhängen.
Strukturelle Beschränkungen existieren: Für Zustands-Aktions-Belohnungen ist die Mehrdeutigkeit nicht willkürlich; sie ist präzise durch eine Matrixtransformation charakterisiert, die den Vergleich von Aktionen (Advantages) über alle Strategien hinweg bewahrt.
Die Belohnungsstruktur bestimmt die Rekuperierbarkeit: Die Form der Belohnung ist entscheidend. Übergangsabhängige Belohnungen können den Kern fast vollständig rekonstruieren, während Zustandsbelohnungen erhebliche strukturelle Unterschiede verborgen lassen können.
Unterscheidung zwischen Entscheidungsfindung und Vorhersage: Die Ergebnisse verdeutlichen, dass ein Modell ausreichen kann, um optimale Entscheidungen zu reproduzieren (Policy-Reproduktion), ohne jedoch ausreichend zu sein, um Übergänge vorherzusagen, Kontrafaktuale zu simulieren oder auf ungesehene Belohnungsklassen zu transferieren.

Die Arbeit erweitert die bisherige Literatur (z. B. Letcher et al.), indem sie den Fokus von der Rekonstruktion von Kernen aus numerischen Q-Werten auf die Rekonstruktion aus der diskreten Menge optimaler Aktionen verschiebt und gleichzeitig den Umfang der betrachteten Belohnungsklasse erweitert. Das Papier kommt zu dem Schluss, dass optimale Aktionen zwar signifikante Strukturen über die Dynamik offenbaren, die Dynamik selbst jedoch im Allgemeinen nicht enthüllen, es sei denn, die Belohnungsfunktion ist ausreichend reichhaltig (d. h. sie hängt vom nächsten Zustand ab).

Das große Kartenrätsel

Die drei Arten von Hinweisen

Die Hierarchie der Wahrheit

Warum das wichtig ist

Technisches Resümee: Identifizierbarkeit von Übergangskernen in diskontierten MDPs

Mehr davon