Robust Counterfactual Inference in Markov Decision Processes

Each language version is independently generated for its own context, not a direct translation.

🕵️‍♂️ Le Détective et le "Et Si ?"

Imaginez que vous êtes un détective privé. Vous avez observé un agent (un robot, un médecin, ou même vous-même) prendre une décision dans un environnement incertain (comme naviguer dans une tempête ou soigner un patient). L'agent a pris une action, et le résultat a été... disons, moyen.

La question classique est : "Et si l'agent avait pris une autre décision ?" C'est ce qu'on appelle l'inférence contrefactuelle. C'est comme regarder une photo d'un accident de voiture et se demander : "Si le conducteur avait tourné à gauche au lieu de droite, aurait-il évité le choc ?"

🧱 Le Problème : Le Miroir Brisé

Jusqu'à présent, pour répondre à cette question, les chercheurs utilisaient une seule "règle du jeu" (un modèle causal) pour simuler le passé. C'était comme si le détective utilisait un seul type de miroir pour voir le passé.

Le problème : Dans la vraie vie, il existe des millions de façons dont les événements pourraient s'être déroulés, tous compatibles avec ce que nous avons vu. En utilisant un seul miroir, on risque de se tromper. Si le miroir est déformé, notre hypothèse sur "ce qui aurait pu se passer" est fausse. Dans des domaines critiques (comme la santé), se tromper peut être dangereux.

💡 La Solution : La "Boîte de Prudence"

L'équipe de ce papier (Jessica Lally, Milad Kazemi et Nicola Paoletti) a eu une idée brillante. Au lieu de choisir un seul miroir, ils ont décidé de construire une boîte qui contient TOUS les miroirs possibles qui pourraient être vrais.

Les Bornes (Les Limites) : Au lieu de dire "Si vous aviez tourné à gauche, vous auriez gagné 10 points", ils disent : "Si vous aviez tourné à gauche, vous auriez gagné entre 5 et 15 points, selon la façon dont la réalité fonctionne vraiment."
La Formule Magique : Leurs plus grandes trouvailles sont :
- Ils ont prouvé qu'on peut calculer ces limites (le 5 et le 15) instantanément, avec une formule mathématique simple, sans avoir besoin de faire des millions de simulations lentes. C'est comme passer de la marche à pied à un avion supersonique (ils sont 4 à 250 fois plus rapides que les anciennes méthodes).
- Ils ont ajouté deux règles de bon sens pour rendre la boîte plus petite et plus utile :
  - Stabilité : Si une action était très probable de réussir, elle le restera probablement dans le passé.
  - Monotonie : Si un résultat n'est pas arrivé dans la réalité, il ne devrait pas devenir plus probable dans l'hypothèse alternative (on ne peut pas inventer de la chance là où il n'y en avait pas).

🛡️ L'Agent Robuste : Le "Pessimiste Intelligent"

Une fois qu'ils ont cette "boîte de prudence" (appelée MDP contrefactuel par intervalles), ils créent un nouveau type d'agent.

L'ancien agent : Cherchait le meilleur scénario possible. S'il se trompait sur le modèle, il pouvait être catastrophique.
Leur nouvel agent : Est un pessimiste intelligent. Il se demande : "Quelle est la PIRE chose qui puisse arriver dans cette boîte de possibilités ?" Il choisit alors la stratégie qui garantit le meilleur résultat possible dans le pire des cas.

C'est comme si un capitaine de navire, au lieu de viser le port le plus rapide mais risqué, choisissait le chemin qui garantit qu'il arrivera à bon port même si la tempête est la pire possible.

🎯 Pourquoi c'est important ?

Imaginez un médecin qui utilise un algorithme pour décider d'un traitement.

L'ancienne méthode : "Si on avait donné le médicament B, le patient serait guéri à 90%." (Mais si le modèle est faux, c'est peut-être 10% !).
La nouvelle méthode : "Si on avait donné le médicament B, le patient aurait eu entre 40% et 95% de chances de guérison. Donc, pour être sûr, choisissons le médicament qui assure au moins 40% de chances, même dans le pire scénario."

🏁 En Résumé

Cette recherche est comme passer d'une devinette hasardeuse à une stratégie de sécurité inébranlable.

Ils ont remplacé la certitude fragile ("Je sais ce qui s'est passé") par une certitude robuste ("Je sais ce qui est possible et je me prépare au pire").
Ils l'ont fait énormément plus vite, ce qui permet de l'appliquer à de gros problèmes (comme piloter un avion ou gérer un hôpital).

C'est une victoire pour la sécurité : on ne parie plus sur une seule version de la réalité, on se prépare à toutes les versions possibles, et on gagne quand même.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique

L'article aborde une limitation fondamentale des méthodes existantes d'inférence contrefactuelle appliquées aux Processus de Décision Markoviens (MDP).

Le défi de l'identifiabilité : Pour calculer des probabilités contrefactuelles (c'est-à-dire : "quel aurait été le résultat si nous avions pris une action différente ?"), les approches classiques doivent supposer un modèle causal spécifique du système (par exemple, le modèle SCM Gumbel-max). Cependant, étant donné une observation et les distributions interventionnelles d'un MDP, il existe souvent de nombreux modèles causaux compatibles avec ces données. Chaque modèle peut produire des probabilités contrefactuelles différentes.
Les risques : Se fier à un seul modèle causal (comme le Gumbel-max) peut conduire à des inférences inexactes, ce qui est particulièrement critique dans des domaines sensibles (santé, contrôle aérien) où la sécurité est primordiale.
Limites des méthodes partielles existantes : Les méthodes d'inférence contrefactuelle partielle tentent de résoudre ce problème en calculant des bornes (intervalles) sur les probabilités plutôt que des valeurs ponctuelles. Cependant, la méthode canonique de Zhang et al. [42], bien qu'exacte, repose sur un problème d'optimisation dont la complexité croît exponentiellement avec la taille de l'espace d'états et d'actions, la rendant inutilisable pour des MDP de grande taille.

2. Méthodologie

Les auteurs proposent une approche non-paramétrique novatrice qui permet de calculer des bornes exactes et serrées sur les probabilités de transition contrefactuelles sans résoudre de problèmes d'optimisation complexes.

A. Cadre Théorique et Hypothèses

L'approche utilise le cadre des Modèles Causaux Structurels (SCM) canoniques. Pour rendre les bornes informatives (et non triviales comme $[0, 1]$ ), deux hypothèses raisonnables sont intégrées dans le problème d'optimisation :

Stabilité Contrefactuelle (Counterfactual Stability) : Si la probabilité de l'outcome observé augmente par rapport à un autre outcome sous une intervention contrefactuelle, alors l'outcome observé reste le plus probable.
Monotonie Contrefactuelle (Counterfactual Monotonicity) :
- Si un outcome a été observé, sa probabilité contrefactuelle ne peut pas diminuer par rapport à sa probabilité nominale.
- Si un outcome possible n'a pas été observé, sa probabilité contrefactuelle ne peut pas augmenter.

B. Réduction Analytique (Le Cœur de l'Innovation)

La contribution majeure est la démonstration que, dans le contexte des MDP (sans confondants non observés), le problème d'optimisation linéaire complexe de Zhang et al. se réduit à des formules analytiques fermées (closed-form expressions).

Au lieu de résoudre un programme linéaire, les bornes inférieures ( $P^{LB}$ ) et supérieures ( $P^{UB}$ ) sont calculées directement en fonction des probabilités de transition observées et interventionnelles.
Ces formules distinguent trois cas pour une paire état-action contrefactuelle $(\tilde{s}, \tilde{a})$ $(\tilde{s}, \tilde{a})$ par rapport à l'observation $(s_t, a_t)$ $(s_{t}, a_{t})$ :
1. La paire est identique à l'observation.
2. La paire a un support disjoint (aucun état suivant commun).
3. La paire a un support partiellement chevauchant.

C. Construction du MDP Contrefactuel par Intervalles (ICFMDP)

En utilisant ces bornes analytiques, les auteurs construisent un ICFMDP (Interval Counterfactual MDP). C'est un MDP où les probabilités de transition sont des intervalles $[P^{LB}, P^{UB}]$ plutôt que des valeurs ponctuelles.

Pour dériver une politique robuste, ils appliquent l'itération de valeur pessimiste (pessimistic value iteration).
L'objectif est d'optimiser la récompense dans le pire des cas parmi tous les MDP contrefactuels compatibles avec les données et les hypothèses. Cela garantit que la politique obtenue est robuste face à l'incertitude du modèle causal sous-jacent.

3. Contributions Clés

Réduction de complexité : Transformation d'un problème d'optimisation exponentiel en solutions analytiques fermées, permettant une mise à l'échelle vers des MDP de grande taille.
Robustesse accrue : Développement de politiques qui optimisent le pire des cas sur l'ensemble des modèles causaux compatibles, offrant une garantie de performance supérieure à celle des méthodes basées sur un modèle unique (comme Gumbel-max).
Flexibilité des hypothèses : La méthode est modulaire ; les hypothèses de stabilité et de monotonie peuvent être activées ou désactivées selon le domaine d'application, sans changer la procédure d'inférence de base.
Validation empirique : Démonstration sur plusieurs benchmarks (GridWorld, Sepsis, Frozen Lake, Aircraft) montrant une amélioration significative de la robustesse et une accélération massive du temps de calcul.

4. Résultats Expérimentaux

Les expériences ont été menées sur quatre environnements avec différents niveaux de stochasticité et de complexité.

Performance et Robustesse :
- Les politiques dérivées de l'ICFMDP (méthode proposée) surpassent systématiquement les politiques basées sur le SCM Gumbel-max en termes de récompense dans le pire des cas.
- Dans des environnements très stochastiques (ex: Sepsis, GridWorld avec $p=0.4$ ), la méthode Gumbel-max produit des politiques très instables (écarts-types larges), tandis que la méthode proposée maintient des performances stables et conservatrices.
- Pour les trajectoires "catastrophiques", la méthode proposée parvient souvent à améliorer la situation tout en restant robuste, là où Gumbel-max échoue ou devient imprévisible.
Efficacité Computationnelle :
- Grâce aux bornes analytiques, la génération du MDP contrefactuel est 4 à 251 fois plus rapide que la méthode Gumbel-max (qui nécessite un échantillonnage coûteux).
- Exemple : Sur le problème Sepsis, la méthode proposée prend ~688 ms contre ~2940 ms pour Gumbel-max.
Impact des hypothèses :
- L'ajout des hypothèses de stabilité et de monotonie resserre légèrement les bornes (réduisant la largeur moyenne des intervalles de ~10 à 15% selon les environnements) mais élimine les contrefactuels "impossibles" ou contre-intuitifs.
- Même sans ces hypothèses, la méthode proposée reste plus robuste que l'approche Gumbel-max.

5. Signification et Conclusion

Cet article représente une avancée significative pour l'inférence causale dans les systèmes de décision séquentiels.

Pour la sécurité (Safety-Critical AI) : En fournissant des garanties de robustesse face à l'incertitude du modèle causal, cette méthode est cruciale pour des applications comme la santé (traitements de sepsis) ou le contrôle aérien, où une erreur d'inférence peut avoir des conséquences graves.
Passage à l'échelle : La capacité à calculer des bornes exactes sans optimisation lourde ouvre la voie à l'application de l'inférence contrefactuelle sur des problèmes réels de grande dimension, auparavant inaccessibles aux méthodes partielles exactes.
Interprétabilité : Les politiques robustes générées offrent des explications contrefactuelles plus fiables sur la façon d'améliorer une politique observée, car elles ne dépendent pas d'un choix arbitraire de modèle causal.

En résumé, les auteurs ont réussi à transformer un problème d'inférence causale complexe et coûteux en une procédure analytique efficace, permettant de prendre des décisions robustes même lorsque la vérité causale sous-jacente n'est pas parfaitement connue.