🤖 AI

Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs

Dieser Beitrag führt Missingness-MDPs ein, eine neue Unterklasse von POMDPs, die die Nichtbeobachtbarkeit von Zustandsmerkmalen mittels der Theorie fehlender Daten modelliert, und schlägt PAC-Algorithmen vor, um die zugrundeliegende Missingness-Funktion aus Trajektoriendaten zu erlernen, um epsilon-optimale Politiken abzuleiten.

Ursprüngliche Autoren: Joshua Wendland, Markel Zubia, Roman Andriushchenko, Maris F. L. Galesloot, Milan Ceska, Henrik von Kleist, Thiago D. Simao, Maximilian Weininger, Nils Jansen

Veröffentlicht 2026-05-13

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Joshua Wendland, Markel Zubia, Roman Andriushchenko, Maris F. L. Galesloot, Milan Ceska, Henrik von Kleist, Thiago D. Simao, Maximilian Weininger, Nils Jansen

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 die Sensoren des Roboters sind fehlerhaft. Manchmal sieht er den ganzen Raum klar; zu anderen Zeiten verschwinden Teile des Raumes einfach aus seinem Sichtfeld. Vielleicht verschwindet eine Wand oder eine Tür ist unsichtbar. Der Roboter kennt zwar die Regeln des Labyrinths (wie er sich von einem Ort zum anderen bewegt), aber er weiß nicht, warum oder wann die Sensoren versagen.

Dieser Artikel stellt eine neue Methode vor, um dem Roboter zu helfen, perfekt zu handeln, selbst wenn seine Vision unzuverlässig ist. Hier ist die Aufschlüsselung mit einfachen Analogien:

1. Das Problem: Die „fehlerhaften Brillen"

In der realen Welt sind Daten oft unvollständig. Denken Sie an einen Arzt, der einen Patienten untersucht. Der Arzt weiß, wie sich eine Krankheit normalerweise entwickelt (die Regeln), aber manchmal geht das Thermometer kaputt oder der Herzfrequenzmonitor verliert das Signal. Der Arzt muss Entscheidungen auf Basis unvollständiger Informationen treffen.

In der Informatik wird dies üblicherweise als POMDP (Partially Observable Markov Decision Process – teilweise beobachtbarer Markov-Entscheidungsprozess) modelliert. Das Problem ist, dass Standard-KI-Modelle Schwierigkeiten haben zu lernen, warum Daten fehlen. Es ist, als würde man versuchen, die Regeln eines Kartenspiels zu lernen, bei dem der Dealer manchmal Karten versteckt, man aber nicht weiß, ob er sie zufällig versteckt, weil er schlecht im Mischen ist, oder weil er betrügt, basierend darauf, welche Karten Sie halten.

2. Die Lösung: „Missingness-MDPs" (miss-MDPs)

Die Autoren haben eine neue, spezialisierte Version dieser Modelle entwickelt, die miss-MDPs genannt werden. Anstatt fehlende Daten als einen vagen „Nebel" zu behandeln, betrachten sie sie als eine spezifische Art von „Fehler" mit drei unterschiedlichen Persönlichkeiten:

MCAR (Missing Completely At Random – vollständig zufällig fehlend): Wie eine Glühbirne, die zufällig flackert. Die Daten fehlen, aber dies hat nichts mit der Gesundheit des Patienten oder dem Standort des Roboters zu tun. Es ist einfach Pech.
MAR (Missing At Random – zufällig fehlend): Wie eine Kamera, die nur ausfällt, wenn es zu dunkel ist. Die Daten fehlen, aber dies hängt von etwas anderem ab, das Sie sehen können (z. B. der Herzfrequenzmonitor fällt nur aus, wenn die Temperatur hoch ist, was Sie sehen können).
MNAR (Missing Not At Random – nicht zufällig fehlend): Der knifflige Fall. Wie eine Kamera, die sich weigert, ein Foto zu machen, wenn das Motiv etwas Peinliches tut. Die Daten fehlen wegen des Wertes der Daten selbst (z. B. fällt der Herzfrequenzmonitor speziell dann aus, wenn die Herzfrequenz gefährlich hoch ist).

3. Die Strategie: Den „Fehlermuster" lernen

Der große Durchbruch dieses Artikels besteht darin, herauszufinden, wie man der KI beibringt, diese „Fehlermuster" aus der Vergangenheit zu lernen.

Der alte Weg: Normalerweise ist es unmöglich zu lernen, warum Daten fehlen. Es ist, als würde man versuchen, die Regeln eines Zaubertricks nur zu erraten, indem man die Hände des Magiers beobachtet, ohne das Deck zu sehen.
Der neue Weg: Die Autoren erkannten, dass man das Muster lernen kann, wenn der „Fehler" einem der drei oben genannten Muster folgt (MCAR, MAR oder eine bestimmte Art von MNAR).
- Sie verwenden einen Datensatz vergangener Aktionen und Beobachtungen (wie ein Logbuch der Reise des Roboters).
- Sie führen einen statistischen Algorithmus aus, um zu zählen, wie oft Dinge unter verschiedenen Bedingungen fehlen.
- Sie erstellen eine „Karte" des Fehlens.

4. Das Ergebnis: Ein „Super-Planer"

Sobald die KI das „Fehlermuster" (die Missingness-Funktion) gelernt hat, kann sie dieses Wissen in ein Standard-Planungstool einfügen.

Die Garantie: Der Artikel beweist mathematisch, dass die KI, wenn man ihr genügend Daten gibt, das Fehlermuster genau genug lernt, um Entscheidungen zu treffen, die fast so gut sind wie die perfekte, theoretisch beste Entscheidung.
Der Beweis: Sie testeten dies an zwei Szenarien:
1. ICU: Eine Simulation eines Arztes, der einen Patienten mit fehlenden Vitalzeichen behandelt.
2. Predator: Eine Simulation eines Löwen, der ein Wildschwein jagt, wobei das Wildschwein sich manchmal versteckt.

In beiden Fällen schnitt ihre Methode (zuerst das Fehlermuster zu lernen) deutlich besser ab als Standard-KI-Methoden, die versuchen, die Antwort direkt zu erraten, ohne die fehlenden Daten zu verstehen.

5. Der Haken

Die Methode funktioniert großartig, wenn der „Fehler" den Regeln folgt (MCAR, MAR oder spezifische MNAR). Wenn das Fehlen chaotisch ist und keinem dieser Muster folgt (wie das „nicht identifizierbare" MNAR in ihren Tests), kann die KI das Muster nicht perfekt lernen, und die Leistung sinkt.

Kurz gesagt: Der Artikel sagt: „Erraten Sie nicht einfach, wie man handelt, wenn Daten fehlen. Ermitteln Sie zuerst, wie die Daten fehlen, indem Sie die Vergangenheit betrachten. Sobald Sie das Muster der fehlenden Teile verstanden haben, können Sie das Rätsel perfekt lösen."

Technische Zusammenfassung: Missingness-MDPs (miss-MDPs)

Problemstellung

Die Arbeit adressiert die Herausforderung der sequenziellen Entscheidungsfindung unter Unsicherheit, wenn Zustandsmerkmale dynamisch fehlen. Während Markov-Entscheidungsprozesse (MDPs) vollständige Beobachtbarkeit voraussetzen, beinhalten reale Szenarien (z. B. medizinische Diagnostik mit unvollständigen Sensordaten) häufig fehlende Merkmale. Standard-Partially Observable Markov Decision Processes (POMDPs) können dies über eine Beobachtungsfunktion modellieren; das Erlernen dieser Funktion aus Aktions-Beobachtungs-Historien ist jedoch im Allgemeinen nicht identifizierbar und rechnerisch unlösbar.

Die Autoren definieren eine spezifische Problemstellung: Gegeben ein miss-MDP mit einer bekannten zugrunde liegenden MDP-Struktur (Übergangsfunktion $T$ ), aber einer unbekannten Missingness-Funktion $M$ , sowie einem Datensatz von Aktions-Beobachtungs-Trajektorien, ist das Ziel, eine Policy $\pi^*$ zu berechnen, die $\epsilon$ -optimal ist. Die Kernschwierigkeit liegt im Erlernen von $M$ aus Daten, um eine Planung zu ermöglichen – eine Aufgabe, die für allgemeine POMDPs unmöglich, für spezifische Unterklassen jedoch potenziell machbar ist.

Methodik

1. Definition von Miss-MDPs

Die Autoren führen Missingness-MDPs (miss-MDPs) als eine echte Unterklasse von POMDPs ein.

Struktur: Ein miss-MDP ist ein Tupel $(S, A, T, b_0, \varrho, Z, M, \gamma)$ .
Beobachtungsraum: $Z = \times_{i \in I} (S_i \cup \{\perp\})$ , wobei $\perp$ ein fehlendes Merkmal bezeichnet.
Missingness-Funktion ( $M$ ): Eine stochastische Funktion $M: S \to \Delta(Z)$ , die die Wahrscheinlichkeit bestimmt, dass Merkmale beobachtet werden oder fehlen.
Typen von Missingness: Das Framework übernimmt die kanonische Taxonomie fehlender Daten (Rubin, 1976):
- MCAR (Missing Completely at Random): Missingness ist unabhängig von Zustandswerten.
- MAR (Missing at Random): Missingness hängt nur von beobachteten Merkmalen ab. Die Autoren unterscheiden zwischen Simple MAR (hängt nur von stets beobachteten Merkmalen ab) und allgemeinem MAR.
- MNAR (Missing Not at Random): Missingness hängt von unbeobachteten (fehlenden) Merkmalswerten ab.

2. Lernalgorithmen (PAC-Garantien)

Die Arbeit schlägt Probably Approximately Correct (PAC) Lernalgorithmen vor, um die unbekannte Missingness-Funktion $\hat{M}$ aus einem Datensatz $D$ zu approximieren. Der Ansatz basiert auf der Identifizierbarkeit spezifischer Missingness-Typen.

Algorithmus $A_{sMAR}$ (für Simple MAR):
- Partitioniert Merkmale in stets beobachtete ( $\hat{I}_{always}$ ) und potenziell fehlende.
- Schätzt die Wahrscheinlichkeit von Missingness-Indikatoren basierend auf den Werten der stets beobachteten Merkmale.
- Satz 1: Beweist, dass für Simple MAR $\hat{M}$ mit hoher Wahrscheinlichkeit gegen die wahre $M$ konvergiert, wenn die Datensatzgröße zunimmt.
Algorithmus $A_{IMI}$ (für Independent Missingness Indicators):
- Anwendbar auf MCAR, Simple MAR und eine Teilmenge identifizierbarer MNAR.
- Nimmt an: (1) Unabhängigkeit der Missingness-Indikatoren über Merkmale hinweg, (2) Kein Selbstzensieren (der Wert eines Merkmals beeinflusst nicht dessen eigenes Fehlen) und (3) Positivität (Merkmale haben eine von Null verschiedene Wahrscheinlichkeit, beobachtet zu werden).
- Schätzt Missingness-Wahrscheinlichkeiten für jedes Merkmal unabhängig basierend auf anderen beobachteten Merkmalen.
- Satz 2: Beweist PAC-Garantien für $\hat{M}$ unter diesen Annahmen.
Berechnung der Policy:
- Sobald $\hat{M}$ approximiert ist, konstruieren die Autoren einen vollständig spezifizierten miss-MDP $\hat{P}$ .
- Sie nutzen handelsübliche POMDP-Löser (z. B. SARSOP), um eine $\epsilon$ -optimale Policy für $\hat{P}$ zu berechnen.
- Satz 3: Beweist, dass, wenn $\hat{M}$ hinreichend genau ist, die resultierende Policy für den wahren miss-MDP $P$ $\epsilon$ -optimal ist.

3. Theoretische Einsichten

Ignorierbarkeit: Die Autoren beweisen (Anmerkung 1), dass für MAR (einschließlich MCAR) die spezifischen Wahrscheinlichkeiten der Missingness-Funktion für Belief-Updates (Aufrechterhaltung der aktuellen Zustandsverteilung) „ignorierbar" sind, da sie sich in der Bayes-Regel herauskürzen. Die Funktion ist jedoch dennoch erforderlich, um die Policy selbst zu berechnen, da die Übergangswahrscheinlichkeiten zwischen Beliefs von $M$ abhängen.

Hauptbeiträge

Formalisierung: Einführung von miss-MDPs, die die Theorie fehlender Daten (MCAR, MAR, MNAR) in das POMDP-Framework integrieren, um eine handhabbare Unterklasse zu definieren, in der die Beobachtungsfunktion lernbar ist.
Identifizierbarkeitsanalyse: Identifikation spezifischer Bedingungen (Simple MAR, Unabhängige/MNAR ohne Selbstzensieren), unter denen die Missingness-Funktion aus Historien lernbar ist, im Gegensatz zur allgemeinen Nicht-Identifizierbarkeit von POMDP-Beobachtungsfunktionen.
PAC-Algorithmen: Entwicklung von Algorithmen ( $A_{sMAR}$ , $A_{IMI}$ ) mit formalen PAC-Garantien für das Erlernen der Missingness-Funktion.
Optimalitätsgarantien: Beweis, dass das Erlernen von $\hat{M}$ mit ausreichender Präzision die Berechnung von $\epsilon$ -optimalen Policies für das wahre System ermöglicht.

Experimentelle Ergebnisse

Die Autoren bewerteten ihren Ansatz an zwei Benchmarks:

ICU: Ein medizinisches Entscheidungsmodell (Arzt behandelt einen Patienten) mit 800 Zuständen.
Predator: Ein Verfolgungs-Flucht-Spiel (Variante von „Fangen") mit bis zu 1.765 Zuständen.

Ergebnisse:

Approximationsqualität: Unter korrekten Annahmen konvergiert die Total-Variations-(TV-)Distanz zwischen dem gelernten $\hat{M}$ und dem wahren $M$ gegen Null, wenn die Datensatzgröße zunimmt.
Policy-Leistung: Policies, die aus dem gelernten miss-MDP abgeleitet werden, konvergieren gegen den optimalen Policy-Wert ( $\pi^*$ ), wenn sich die Approximation verbessert.
Annahmensensitivität: Falsche Annahmen (z. B. MAR anzunehmen, wenn die Daten MNAR mit Selbstzensieren sind) führen zu schlechter Approximation und suboptimalen Policies.
Vergleich mit Baselines: Der vorgeschlagene modellbasierte Ansatz übertraf modellfreie Baselines (PPO mit/ohne Speicher, POMCP) auf beiden Benchmarks signifikant. Die Autoren führen das Versagen modellfreier Methoden auf ihre Unfähigkeit zurück, die spezifische partielle Beobachtbarkeitsstruktur von miss-MDPs effektiv zu handhaben, und stellen fest, dass diese Methoden erfolgreich waren, wenn die Missingness entfernt wurde.

Bedeutung und Behauptungen

Die Arbeit behauptet, die Lücke zwischen der Theorie fehlender Daten und der sequenziellen Entscheidungsfindung zu schließen. Ihre primäre Bedeutung liegt in der Bereitstellung eines prinzipiellen, modellbasierten Ansatzes zum Umgang mit fehlenden Daten in POMDPs mit statistischen Garantien (PAC).

Im Gegensatz zu früheren Arbeiten, die Missingness als nebensächlich behandeln oder auf Imputation ohne Garantien zurückgreifen, leistet diese Arbeit Folgendes:

Sie modelliert den Missingness-Prozess explizit.
Sie lernt die Missingness-Funktion aus Daten mit theoretischen Fehlergrenzen.
Sie nutzt dieses gelernte Modell, um die Near-Optimalität der resultierenden Policy zu garantieren.

Die Autoren vermerken bescheiden, dass ihr aktueller Ansatz davon ausgeht, dass die Übergangsfunktion des zugrunde liegenden MDP bekannt ist. Sie identifizieren das Aufheben dieser Annahme und die Erweiterung des Frameworks auf allgemeine miss-POMDPs als Richtungen für zukünftige Arbeiten. Die empirischen Ergebnisse bestätigen, dass ihr Ansatz in Szenarien, in denen der Missingness-Mechanismus identifizierbaren Mustern folgt, überlegener ist als direkte POMDP-Formulierungen (wie POMCP) und Methoden des Deep Reinforcement Learning (wie PPO).