🤖 AI

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

Dit artikel introduceert missingness-MDP's, een nieuwe subklasse van POMDP's die onwaarneembaarheid van toestandskenmerken modelleert via theorie over ontbrekende gegevens, en stelt PAC-algoritmen voor om de onderliggende missingness-functie te leren uit trajectgegevens teneinde epsilon-optimale beleidslijnen af te leiden.

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

Gepubliceerd 2026-05-13

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

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

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een robot te leren een doolhof te navigeren, maar de sensoren van de robot zijn defect. Soms ziet het de hele kamer duidelijk; op andere momenten verdwijnen delen van de kamer uit zijn zicht. Misschien verdwijnt een muur, of is een deur onzichtbaar. De robot kent nog steeds de regels van het doolhof (hoe hij van de ene plek naar de andere beweegt), maar hij weet niet waarom of wanneer de sensoren falen.

Dit artikel introduceert een nieuwe manier om de robot te helpen perfect te handelen, zelfs wanneer zijn zicht onbetrouwbaar is. Hier is de uitleg met eenvoudige analogieën:

1. Het Probleem: De "Defecte Brillen"

In de echte wereld is data vaak incompleet. Denk aan een arts die een patiënt controleert. De arts weet hoe een ziekte meestal verloopt (de regels), maar soms gaat de thermometer stuk, of verliest de hartslagmonitor het signaal. De arts moet beslissingen nemen op basis van onvolledige informatie.

In de informatica wordt dit meestal gemodelleerd als een POMDP (Partially Observable Markov Decision Process). Het probleem is dat standaard AI-modellen moeite hebben om te leren waarom de data ontbreekt. Het is alsof je probeert de regels van een kaartspel te leren waarbij de dealer soms kaarten verbergt, maar je niet weet of ze ze willekeurig verbergen, omdat ze slecht zijn in delen, of omdat ze bedriegen op basis van welke kaarten jij hebt.

2. De Oplossing: "Ontbrekendheids-MDP's" (miss-MDP's)

De auteurs hebben een nieuwe, gespecialiseerde versie van deze modellen ontwikkeld, genaamd miss-MDP's. In plaats van ontbrekende data te behandelen als een vaag "mist", behandelen ze het als een specifiek type "defect" met drie verschillende persoonlijkheidskenmerken:

MCAR (Missing Completely At Random): Alsof een gloeilamp willekeurig knippert. De data ontbreekt, maar het heeft niets te maken met de gezondheid van de patiënt of de locatie van de robot. Het is gewoon pech.
MAR (Missing At Random): Alsof een camera alleen faalt wanneer het te donker is. De data ontbreekt, maar het hangt af van iets anders dat je wel kunt zien (bijvoorbeeld: de hartslagmonitor faalt alleen wanneer de temperatuur hoog is, wat je wel kunt zien).
MNAR (Missing Not At Random): De lastige. Alsof een camera weigert een foto te maken als het onderwerp iets verlegen doet. De data ontbreekt omdat van de waarde van de data zelf (bijvoorbeeld: de hartslagmonitor faalt specifiek wanneer de hartslag levensgevaarlijk hoog is).

3. De Strategie: Het "Defectpatroon" Leren

De grote doorbraak van het artikel is het uitzoeken hoe je de AI kunt leren deze "defectpatronen" te herkennen uit de geschiedenis.

De Oude Manier: Meestal is het onmogelijk om te leren waarom data ontbreekt. Het is alsof je probeert de regels van een goocheltruc te raden door alleen naar de handen van de goochelaar te kijken zonder het deck te zien.
De Nieuwe Manier: De auteurs realiseerden zich dat als het "defect" één van de drie bovenstaande patronen volgt (MCAR, MAR, of een specifiek type MNAR), je het patroon wel kunt leren.
- Ze gebruiken een dataset van eerdere acties en waarnemingen (zoals een logboek van de reis van de robot).
- Ze draaien een statistisch algoritme om te tellen hoe vaak dingen onder verschillende omstandigheden ontbreken.
- Ze bouwen een "kaart" van de ontbrekendheid.

4. Het Resultaat: Een "Superplanner"

Zodra de AI het "defectpatroon" (de ontbrekendheidsfunctie) heeft geleerd, kan deze kennis invoeren in een standaard planningstool.

De Garantie: Het artikel bewijst wiskundig dat als je de AI genoeg data geeft, het het defectpatroon nauwkeurig genoeg zal leren om beslissingen te nemen die bijna net zo goed zijn als de perfecte, theoretisch beste beslissing.
Het Bewijs: Ze hebben dit getest op twee scenario's:
1. ICU: Een simulatie van een arts die een patiënt behandelt met ontbrekende vitale functies.
2. Predator: Een simulatie van een leeuw die een everzwijn achtervolgt, waarbij het everzwijn zich soms verbergt.

In beide gevallen presteerde hun methode (eerst het defectpatroon leren) aanzienlijk beter dan standaard AI-methoden die proberen het antwoord direct te raden zonder de ontbrekende data te begrijpen.

5. De Haken

De methode werkt uitstekend als het "defect" de regels volgt (MCAR, MAR, of specifiek MNAR). Als de ontbrekendheid chaotisch is en geen van deze patronen volgt (zoals de "niet-identificeerbare" MNAR in hun tests), kan de AI het patroon niet perfect leren en daalt de prestatie.

Kortom: Het artikel zegt: "Raad niet zomaar hoe je moet handelen wanneer data ontbreekt. Bepaal eerst hoe de data ontbreekt door naar de geschiedenis te kijken. Zodra je het patroon van de ontbrekende stukken begrijpt, kun je de puzzel perfect oplossen."

Technische Samenvatting: Missingness-MDPs (miss-MDPs)

Probleemstelling

Het artikel behandelt de uitdaging van sequentiële besluitvorming onder onzekerheid wanneer statiefuncties dynamisch ontbreken. Waar Markov-beslissingsprocessen (MDP's) volledige waarneembaarheid veronderstellen, omvatten realistische scenario's (bijvoorbeeld medische diagnostiek met onvolledige sensordata) vaak ontbrekende functies. Standaard Gedeeltelijk Waarneembare Markov-beslissingsprocessen (POMDP's) kunnen dit modelleren via een waarnemingsfunctie; het leren van deze functie uit actiewaarnemingsgeschiedenissen is echter over het algemeen niet identificeerbaar en computationeel onbeheersbaar.

De auteurs definiëren een specifieke probleemstelling: gegeven een miss-MDP met een bekende onderliggende MDP (overgangsfunctie $T$ ) maar een onbekende ontbrekendheidsfunctie $M$ , en een dataset van actiewaarnemingstrajecten, is het doel om een beleid $\pi^*$ te berekenen dat $\epsilon$ -optimaal is. De kernmoeilijkheid ligt in het leren van $M$ uit data om planning mogelijk te maken, een taak die onmogelijk is voor algemene POMDP's maar potentieel haalbaar voor specifieke subklassen.

Methodologie

1. Definitie van Miss-MDP's

De auteurs introduceren Missingness-MDPs (miss-MDPs) als een geschikte subklasse van POMDP's.

Structuur: Een miss-MDP is een tuple $(S, A, T, b_0, \varrho, Z, M, \gamma)$ .
Waarnemingsruimte: $Z = \times_{i \in I} (S_i \cup \{\perp\})$ , waarbij $\perp$ een ontbrekende functie aanduidt.
Ontbrekendheidsfunctie ( $M$ ): Een stochastische functie $M: S \to \Delta(Z)$ die de waarschijnlijkheid bepaalt dat functies worden waargenomen of ontbreken.
Typen Ontbrekendheid: Het kader adopteert de canonieke taxonomie voor ontbrekende data (Rubin, 1976):
- MCAR (Missing Completely at Random): Ontbrekendheid is onafhankelijk van statiewaarden.
- MAR (Missing at Random): Ontbrekendheid hangt alleen af van waargenomen functies. De auteurs onderscheiden tussen Eenvoudige MAR (hangt alleen af van altijd-waargenomen functies) en algemene MAR.
- MNAR (Missing Not at Random): Ontbrekendheid hangt af van niet-waargenomen (ontbrekende) functiewaarden.

2. Leeralgoritmen (PAC-garanties)

Het artikel stelt Probably Approximately Correct (PAC) leeralgoritmen voor om de onbekende ontbrekendheidsfunctie $\hat{M}$ te benaderen uit een dataset $D$ . De aanpak berust op de identificeerbaarheid van specifieke ontbrekendheidstypen.

Algoritme $A_{sMAR}$ (voor Eenvoudige MAR):
- Partitioneert functies in altijd-waargenomen ( $\hat{I}_{always}$ ) en potentieel ontbrekende.
- Schat de waarschijnlijkheid van ontbrekendheidsindicatoren op basis van de waarden van altijd-waargenomen functies.
- Stelling 1: Bewijst dat voor Eenvoudige MAR, $\hat{M}$ convergeert naar de ware $M$ met hoge waarschijnlijkheid naarmate de datasetgrootte toeneemt.
Algoritme $A_{IMI}$ (voor Onafhankelijke Ontbrekendheidsindicatoren):
- Toepasbaar op MCAR, Eenvoudige MAR en een subset van identificeerbare MNAR.
- Veronderstelt: (1) Onafhankelijkheid van ontbrekendheidsindicatoren over functies, (2) Geen zelfcensuur (de waarde van een functie beïnvloedt niet zijn eigen ontbrekendheid), en (3) Positiviteit (functies hebben een niet-nul waarschijnlijkheid om te worden waargenomen).
- Schat ontbrekendheidswaarschijnlijkheden voor elke functie onafhankelijk op basis van andere waargenomen functies.
- Stelling 2: Bewijst PAC-garanties voor $\hat{M}$ onder deze veronderstellingen.
Berekening van Beleid:
- Zodra $\hat{M}$ is benaderd, construeren de auteurs een volledig gespecificeerde miss-MDP $\hat{P}$ .
- Zij gebruiken kant-en-klare POMDP-oplossers (bijvoorbeeld SARSOP) om een $\epsilon$ -optimaal beleid voor $\hat{P}$ te berekenen.
- Stelling 3: Bewijst dat als $\hat{M}$ voldoende nauwkeurig is, het resulterende beleid $\epsilon$ -optimaal is voor de ware miss-MDP $P$ .

3. Theoretische Inzichten

Verwaarloosbaarheid: De auteurs bewijzen (Opmerking 1) dat voor MAR (inclusief MCAR) de specifieke waarschijnlijkheden van de ontbrekendheidsfunctie "verwaarloosbaar" zijn voor geloofsupdates (het handhaven van de huidige statieverdeling) omdat ze in de regel van Bayes tegen elkaar wegvallen. De functie is echter nog steeds vereist om het beleid zelf te berekenen, aangezien de overgangswaarschijnlijkheden tussen geloof afhankelijk zijn van $M$ .

Belangrijkste Bijdragen

Formalisering: Introductie van miss-MDP's, waarbij theorie over ontbrekende data (MCAR, MAR, MNAR) wordt geïntegreerd in het POMDP-kader om een beheersbare subklasse te definiëren waarin de waarnemingsfunctie leerbaar is.
Identificeerbaarheidsanalyse: Identificatie van specifieke voorwaarden (Eenvoudige MAR, Onafhankelijke/MNAR zonder zelfcensuur) waaronder de ontbrekendheidsfunctie leerbaar is uit geschiedenissen, in contrast met de algemene niet-identificeerbaarheid van POMDP-waarnemingsfuncties.
PAC-algoritmen: Ontwikkeling van algoritmen ( $A_{sMAR}$ , $A_{IMI}$ ) met formele PAC-garanties voor het leren van de ontbrekendheidsfunctie.
Optimaliteitsgaranties: Bewijs dat het leren van $\hat{M}$ met voldoende precisie toelaat om $\epsilon$ -optimale beleidslijnen te berekenen voor het ware systeem.

Experimentele Resultaten

De auteurs evalueerden hun aanpak op twee benchmarks:

ICU: Een medisch besluitvormingsmodel (arts die een patiënt behandelt) met 800 staten.
Predator: Een achtervolgings-ontwijkspel (Tag-variant) met tot 1.765 staten.

Vondsten:

Benoaderingskwaliteit: Onder correcte veronderstellingen convergeert de Totale Variatie (TV) afstand tussen de geleerde $\hat{M}$ en ware $M$ naar nul naarmate de datasetgrootte toeneemt.
Beleidsprestaties: Beleid afgeleid van de geleerde miss-MDP convergeert naar de optimale beleidswaarde ( $\pi^*$ ) naarmate de benadering verbetert.
Veronderstellingsgevoeligheid: Onjuiste veronderstellingen (bijvoorbeeld MAR aannemen terwijl de data MNAR is met zelfcensuur) leiden tot slechte benadering en suboptimale beleidslijnen.
Vergelijking met Baselines: De voorgestelde modelgebaseerde aanpak presteerde aanzienlijk beter dan modelvrije baselines (PPO met/zonder geheugen, POMCP) op beide benchmarks. De auteurs schrijven het falen van modelvrije methoden toe aan hun onvermogen om de specifieke gedeeltelijke waarneembaarheidsstructuur van miss-MDP's effectief te hanteren, en merken op dat deze methoden wel slaagden toen ontbrekendheid werd verwijderd.

Betekenis en Beweringen

Het artikel claimt de kloof te overbruggen tussen theorie over ontbrekende data en sequentiële besluitvorming. De primaire betekenis ligt in het bieden van een principiële, modelgebaseerde aanpak voor het hanteren van ontbrekende data in POMDP's met statistische garanties (PAC).

In tegenstelling tot eerdere werken die ontbrekendheid als incidenteel behandelen of vertrouwen op imputatie zonder garanties, doet dit werk het volgende:

Modelleert expliciet het ontbrekendheidsproces.
Leert de ontbrekendheidsfunctie uit data met theoretische foutgrenzen.
Gebruikt dit geleerde model om de near-optimale aard van het resulterende beleid te garanderen.

De auteurs merken bescheiden op dat hun huidige aanpak veronderstelt dat de onderliggende MDP-overgangsfunctie bekend is. Zij identificeren het opheffen van deze veronderstelling en het uitbreiden van het kader naar algemene miss-POMDP's als richtingen voor toekomstig werk. De empirische resultaten bevestigen dat hun aanpak superieur is aan directe POMDP-formuleringen (zoals POMCP) en methoden voor diepe versterkingsleer (zoals PPO) in situaties waar het ontbrekendheidsmechanisme identificeerbare patronen volgt.