🤖 AI

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

Cet article introduit les MDP à données manquantes, une nouvelle sous-classe de MDP partiellement observables qui modélise l'inobservabilité des caractéristiques d'état par la théorie des données manquantes, et propose des algorithmes PAC pour apprendre la fonction de données manquantes sous-jacente à partir de données de trajectoire afin de dériver des politiques epsilon-optimales.

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

Publié 2026-05-13

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

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

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'enseigner à un robot comment naviguer dans un labyrinthe, mais que les capteurs du robot sont défectueux. Parfois, il voit toute la pièce clairement ; d'autres fois, des parties de la pièce disparaissent simplement de son champ de vision. Peut-être qu'un mur disparaît, ou qu'une porte devient invisible. Le robot connaît toujours les règles du labyrinthe (comment il se déplace d'un endroit à l'autre), mais il ne sait pas pourquoi ni quand les capteurs échouent.

Ce papier présente une nouvelle méthode pour aider le robot à apprendre à agir parfaitement, même lorsque sa vision est peu fiable. Voici le détail utilisant des analogies simples :

1. Le Problème : Les « Lunettes Défectueuses »

Dans le monde réel, les données sont souvent incomplètes. Pensez à un médecin examinant un patient. Le médecin sait comment une maladie évolue généralement (les règles), mais parfois le thermomètre tombe en panne, ou le moniteur cardiaque perd le signal. Le médecin doit prendre des décisions basées sur des informations incomplètes.

En informatique, cela est généralement modélisé comme un POMDP (Processus de Décision Markovien Partiellement Observable). Le problème est que les modèles d'IA standards peinent à apprendre pourquoi les données manquent. C'est comme essayer d'apprendre les règles d'un jeu de cartes où le donneur cache parfois des cartes, mais vous ne savez pas s'il les cache au hasard, parce qu'il est mauvais donneur, ou parce qu'il triche en fonction des cartes que vous tenez.

2. La Solution : Les « MDP de Manque » (miss-MDPs)

Les auteurs ont créé une nouvelle version spécialisée de ces modèles appelée miss-MDPs. Au lieu de traiter les données manquantes comme un « brouillard » vague, ils les traitent comme un type spécifique de « glitch » avec trois personnalités distinctes :

MCAR (Manquant Complètement Au Hasard) : Comme un ampoule qui clignote au hasard. Les données manquent, mais cela n'a rien à voir avec la santé du patient ou la position du robot. C'est simplement de la malchance.
MAR (Manquant Au Hasard) : Comme un appareil photo qui ne fonctionne que lorsqu'il fait trop sombre. Les données manquent, mais cela dépend de quelque chose d'autre que vous pouvez voir (par exemple, le moniteur cardiaque échoue uniquement lorsque la température est élevée, ce que vous pouvez voir).
MNAR (Manquant Pas Au Hasard) : Le plus difficile. Comme un appareil photo qui refuse de prendre une photo si le sujet fait quelque chose de gênant. Les données manquent à cause de la valeur des données elles-mêmes (par exemple, le moniteur cardiaque échoue spécifiquement lorsque la fréquence cardiaque est dangereusement élevée).

3. La Stratégie : Apprendre le « Motif du Glitch »

La grande percée de ce papier réside dans la découverte de la façon d'enseigner à l'IA à apprendre ces « motifs de glitch » à partir de l'historique.

L'Ancienne Façon : Habituellement, essayer d'apprendre pourquoi les données manquent est impossible. C'est comme essayer de deviner les règles d'un tour de magie en regardant seulement les mains du magicien sans voir le jeu de cartes.
La Nouvelle Façon : Les auteurs ont réalisé que si le « glitch » suit l'un des trois motifs ci-dessus (MCAR, MAR, ou un type spécifique de MNAR), vous pouvez apprendre le motif.
- Ils utilisent un ensemble de données d'actions et d'observations passées (comme un journal de bord du voyage du robot).
- Ils exécutent un algorithme statistique pour compter à quelle fréquence les choses disparaissent dans différentes conditions.
- Ils construisent une « carte » du manque.

4. Le Résultat : Un « Super-Planificateur »

Une fois que l'IA a appris le « motif du glitch » (la fonction de manque), elle peut intégrer cette connaissance dans un outil de planification standard.

La Garantie : Le papier prouve mathématiquement que si vous donnez suffisamment de données à l'IA, elle apprendra le motif du glitch avec assez de précision pour prendre des décisions presque aussi bonnes que la décision parfaite, théoriquement optimale.
La Preuve : Ils ont testé cela sur deux scénarios :
1. ICU : Une simulation d'un médecin traitant un patient avec des signes vitaux manquants.
2. Predator : Une simulation d'un lion poursuivant un sanglier où le sanglier se cache parfois.

Dans les deux cas, leur méthode (apprendre d'abord le motif du glitch) a nettement surpassé les méthodes d'IA standard qui tentent de deviner directement la réponse sans comprendre les données manquantes.

5. L'Inconvénient

La méthode fonctionne très bien si le « glitch » suit les règles (MCAR, MAR, ou MNAR spécifique). Si le manque est chaotique et ne suit aucun de ces motifs (comme le MNAR « non identifiable » dans leurs tests), l'IA ne peut pas apprendre le motif parfaitement, et les performances chutent.

En bref : Le papier dit : « Ne devinez pas simplement comment agir lorsque les données manquent. D'abord, déterminez comment les données manquent en examinant l'historique. Une fois que vous comprenez le motif des pièces manquantes, vous pouvez résoudre l'énigme parfaitement. »

Résumé Technique : MDPs à Données Manquantes (miss-MDPs)

Énoncé du Problème

L'article aborde le défi de la prise de décision séquentielle sous incertitude lorsque les caractéristiques d'état sont dynamiquement manquantes. Alors que les Processus de Décision Markoviens (MDP) supposent une observabilité complète, des scénarios réels (par exemple, des diagnostics médicaux avec des données de capteurs incomplètes) impliquent souvent des caractéristiques manquantes. Les Processus de Décision Markoviens Partiellement Observables (POMDP) standards peuvent modéliser cela via une fonction d'observation ; cependant, apprendre cette fonction à partir d'historiques d'actions et d'observations est généralement non identifiable et computationnellement intraitable.

Les auteurs définissent un cadre de problème spécifique : Étant donné un miss-MDP avec un MDP sous-jacent connu (fonction de transition $T$ ) mais une fonction de manquance $M$ inconnue, et un ensemble de données de trajectoires d'actions-observations, l'objectif est de calculer une politique $\pi^*$ qui soit $\epsilon$ -optimale. La difficulté centrale réside dans l'apprentissage de $M$ à partir des données pour permettre la planification, une tâche impossible pour les POMDPs généraux mais potentiellement réalisable pour des sous-classes spécifiques.

Méthodologie

1. Définition des miss-MDPs

Les auteurs introduisent les MDPs à Données Manquantes (miss-MDPs) comme une sous-classe propre des POMDPs.

Structure : Un miss-MDP est un tuple $(S, A, T, b_0, \varrho, Z, M, \gamma)$ .
Espace d'Observation : $Z = \times_{i \in I} (S_i \cup \{\perp\})$ , où $\perp$ désigne une caractéristique manquante.
Fonction de Manquance ( $M$ ) : Une fonction stochastique $M: S \to \Delta(Z)$ qui détermine la probabilité que les caractéristiques soient observées ou manquantes.
Types de Manquance : Le cadre adopte la taxonomie canonique des données manquantes (Rubin, 1976) :
- MCAR (Manquant Complètement au Hasard) : La manquance est indépendante des valeurs d'état.
- MAR (Manquant au Hasard) : La manquance dépend uniquement des caractéristiques observées. Les auteurs distinguent le MAR Simple (dépend uniquement des caractéristiques toujours observées) du MAR général.
- MNAR (Manquant Non au Hasard) : La manquance dépend des valeurs de caractéristiques non observées (manquantes).

2. Algorithmes d'Apprentissage (Garanties PAC)

L'article propose des algorithmes d'apprentissage Probablement Approximativement Corrects (PAC) pour approximer la fonction de manquance inconnue $\hat{M}$ à partir d'un ensemble de données $D$ . L'approche repose sur l'identifiabilité de types spécifiques de manquance.

Algorithme $A_{sMAR}$ (pour MAR Simple) :
- Partitionne les caractéristiques en toujours-observées ( $\hat{I}_{always}$ ) et potentiellement manquantes.
- Estime la probabilité des indicateurs de manquance basée sur les valeurs des caractéristiques toujours-observées.
- Théorème 1 : Prouve que pour le MAR Simple, $\hat{M}$ converge vers la vraie $M$ avec une forte probabilité à mesure que la taille de l'ensemble de données augmente.
Algorithme $A_{IMI}$ (pour Indicateurs de Manquance Indépendants) :
- Applicable aux MCAR, MAR Simple, et à un sous-ensemble de MNAR identifiables.
- Suppose : (1) l'indépendance des indicateurs de manquance entre les caractéristiques, (2) l'absence d'autocensure (la valeur d'une caractéristique n'influence pas sa propre manquance), et (3) la positivité (les caractéristiques ont une probabilité non nulle d'être observées).
- Estime les probabilités de manquance pour chaque caractéristique indépendamment, en se basant sur les autres caractéristiques observées.
- Théorème 2 : Prouve les garanties PAC pour $\hat{M}$ sous ces hypothèses.
Calcul de la Politique :
- Une fois $\hat{M}$ approximée, les auteurs construisent un miss-MDP entièrement spécifié $\hat{P}$ .
- Ils utilisent des solveurs POMDP standards (par exemple, SARSOP) pour calculer une politique $\epsilon$ -optimale pour $\hat{P}$ .
- Théorème 3 : Prouve que si $\hat{M}$ est suffisamment précise, la politique résultante est $\epsilon$ -optimale pour le vrai miss-MDP $P$ .

3. Insights Théoriques

Ignorabilité : Les auteurs prouvent (Remarque 1) que pour le MAR (incluant le MCAR), les probabilités spécifiques de la fonction de manquance sont "ignorables" pour les mises à jour de croyance (maintenir la distribution d'état actuelle) car elles s'annulent dans la règle de Bayes. Cependant, la fonction est toujours requise pour calculer la politique elle-même, car les probabilités de transition entre les croyances dépendent de $M$ .

Contributions Clés

Formalisation : Introduction des miss-MDPs, intégrant la théorie des données manquantes (MCAR, MAR, MNAR) dans le cadre des POMDPs pour définir une sous-classe traitable où la fonction d'observation est apprenable.
Analyse d'Identifiabilité : Identification de conditions spécifiques (MAR Simple, Indépendance/MNAR sans autocensure) sous lesquelles la fonction de manquance est apprenable à partir des historiques, en contraste avec l'non-identifiabilité générale des fonctions d'observation des POMDPs.
Algorithmes PAC : Développement d'algorithmes ( $A_{sMAR}$ , $A_{IMI}$ ) avec des garanties PAC formelles pour apprendre la fonction de manquance.
Garanties d'Optimalité : Preuve que l'apprentissage de $\hat{M}$ avec une précision suffisante permet le calcul de politiques $\epsilon-optimales$ pour le système réel.

Résultats Expérimentaux

Les auteurs ont évalué leur approche sur deux benchmarks :

ICU : Un modèle de prise de décision médicale (médecin traitant un patient) avec 800 états.
Predator : Un jeu de poursuite-évasion (variante de Tag) avec jusqu'à 1 765 états.

Constats :

Qualité de l'Approximation : Sous des hypothèses correctes, la distance de Variation Totale (TV) entre le $\hat{M}$ appris et le vrai $M$ converge vers zéro à mesure que la taille de l'ensemble de données augmente.
Performance de la Politique : Les politiques dérivées du miss-MDP appris convergent vers la valeur de la politique optimale ( $\pi^*$ ) à mesure que l'approximation s'améliore.
Sensibilité aux Hypothèses : Des hypothèses incorrectes (par exemple, supposer MAR lorsque les données sont MNAR avec autocensure) conduisent à une mauvaise approximation et à des politiques sous-optimales.
Comparaison avec les Baselines : L'approche basée sur modèle proposée a considérablement surpassé les baselines sans modèle (PPO avec/sans mémoire, POMCP) sur les deux benchmarks. Les auteurs attribuent l'échec des méthodes sans modèle à leur incapacité à gérer efficacement la structure spécifique d'observabilité partielle des miss-MDPs, notant que ces méthodes ont réussi lorsque la manquance a été supprimée.

Signification et Revendications

L'article prétend combler le fossé entre la théorie des données manquantes et la prise de décision séquentielle. Sa signification principale réside dans la fourniture d'une approche basée sur modèle et principielle pour gérer les données manquantes dans les POMDPs avec des garanties statistiques (PAC).

Contrairement aux travaux antérieurs qui traitent la manquance comme incidente ou reposent sur l'imputation sans garanties, ce travail :

Modélise explicitement le processus de manquance.
Apprend la fonction de manquance à partir des données avec des bornes théoriques sur l'erreur.
Exploite ce modèle appris pour garantir la quasi-optimalité de la politique résultante.

Les auteurs notent modestement que leur approche actuelle suppose que la fonction de transition du MDP sous-jacent est connue. Ils identifient le levage de cette hypothèse et l'extension du cadre aux miss-POMDPs généraux comme des pistes de travail futur. Les résultats empiriques confirment que leur approche est supérieure aux formulations POMDP directes (comme POMCP) et aux méthodes d'apprentissage par renforcement profond (comme PPO) dans des contextes où le mécanisme de manquance suit des motifs identifiables.