Résumé Technique : Identification de la Meilleure Action à Confiance Fixe pour l'Analyse de Médiation Causale

1. Définition du Problème

Cet article traite du problème de l'Identification de la Meilleure Action (Best-Arm Identification - BAI) dans un contexte de bandit causal, se concentrant spécifiquement sur l'analyse de médiation causale.

• Contexte : Dans le cadre des bandits causaux standards, l'objectif est généralement de maximiser la moyenne interpersonnelle $E[Y | do(X=x)]$, qui agrège les effets à travers tous les chemins causaux. Cependant, les chercheurs souhaitent souvent isoler l'effet d'un traitement $X$ sur un résultat $Y$ qui ne passe pas par un médiateur spécifique $Z$ (par exemple, pour exclure des mécanismes contraires à l'éthique, un biais de positionnement dans les publicités, ou des réactions intermédiaires indésirables).
• Objectif : L'article vise à identifier l'action $x^*$ qui maximise l'Espérance du Résultat Potentiel Naturel Direct (NDPO - Natural Direct Potential Outcome), définie par $E[Y_{x, Z_{x_0}}]$. Cette quantité représente le résultat attendu si le traitement est fixé à $x$ tandis que le médiateur $Z$ est maintenu à la valeur qu'il aurait prise sous une action de référence $x_0$.
• Cadre : Le problème est formulé dans un cadre à confiance fixe (fixed-confidence). Un apprenant tire séquentiellement des actions (interventions $do(X=x)$), observant des échantillons i.i.d. de la distribution interpersonnelle $P(Z, Y | do(X=x))$. L'objectif est d'identifier l'action optimale avec une probabilité d'au moins $1-\delta$ tout en minimisant le temps d'arrêt attendu (complexité d'échantillonnage).

2. Méthodologie

2.1 Identification au Niveau de la Population

Les auteurs établissent d'abord que l'espérance du NDPO est identifiable à partir des distributions interpersonnelles observables dans un cadre de bandit causal.

• Hypothèse : Ils s'appuient sur l'hypothèse d'identification standard pour les effets directs naturels : $Y_{x,z} \perp\!\!\rightleftharpoons Z_{x'}$ pour tout $x, x', z$. Graphiquement, cela correspond à l'absence de confusion non mesurée entre le médiateur $Z$ et le résultat $Y$ dans le graphe où les flèches sortantes de $X$ et $Z$ sont supprimées.
• Formule d'Identification : Sous cette hypothèse, l'espérance du NDPO $\theta(x)$ est identifiée comme suit :
  $$\theta(x) = \sum_{y,z} y P(Y=y | Z=z, do(X=x)) P(Z=z | do(X=x_0))$$
  Cette formulation permet l'estimation en utilisant uniquement les distributions interpersonnelles conjointes $P(Z, Y | do(X=x))$ et $P(Z | do(X=x_0))$, évitant ainsi le besoin de contre-factuels imbriqués qui ne sont pas directement observables dans le cadre du bandit.

2.2 Borne Inférieure de la Complexité d'Échantillonnage

L'article dérive une borne inférieure dépendante de l'instance pour la complexité d'échantillonnage de tout algorithme $\delta$-correct.

• Différence Clé avec le BAI Standard : Contrairement au BAI standard où l'objectif dépend uniquement de la propre distribution de l'action, le NDPO couple la distribution du résultat sous l'action $x$ avec la distribution du médiateur sous l'action de base $x_0$.
• Structure de Complexité : La borne inférieure implique un problème d'optimisation semi-infini. Le temps caractéristique $T^*(P)$ est défini par :
  $$(T^*(P))^{-1} = \sup_{w \in \Sigma_K} \inf_{Q \in \text{Alt}(P)} \sum_{x \in \mathcal{X}} w_x KL(P_x \| Q_x)$$
  où $\text{Alt}(P)$ est l'ensemble des modèles alternatifs où une action différente est optimale. La contrainte définissant $\text{Alt}(P)$ est non-séparable car la distribution de base du médiateur $Q_{x_0}(Z)$ apparaît dans l'objectif pour chaque action, créant un couplage entre les actions qui n'existe pas dans le BAI classique.

2.3 Algorithme Proposé : TaS-NDPO

Les auteurs proposent TaS-NDPO, un algorithme de type Track-and-Stop (TaS) adapté à cet objectif spécifique. L'algorithme se compose de trois composantes principales :

1. Estimation par Substitution (Plug-in Estimation) : Des estimations empiriques des distributions interpersonnelles sont utilisées pour calculer des estimations par substitution de $\theta(x)$.
2. Règle d'Échantillonnage (D-tracking avec Forçage) :
   • D-tracking : L'algorithme suit les proportions d'échantillonnage optimales $w^*$ dérivées de la borne inférieure.
   • Couverture des Compétiteurs : Pour gérer les contraintes non-séparables, l'algorithme garantit que chaque action est sélectionnée comme "compétiteur" dans le problème d'optimisation suffisamment souvent.
   • Forçage au Niveau de la Cellule : Crucialement, l'algorithme impose l'exploration au niveau de la cellule $(x, z)$ (combinaisons d'action et de valeur du médiateur). Cela est nécessaire car la divergence KL se décompose en termes pondérés par les probabilités du médiateur ; les valeurs rares du médiateur doivent être échantillonnées suffisamment pour assurer une estimation cohérente des probabilités conditionnelles du résultat $P(Y|Z, do(X))$.
3. Règle d'Arrêt (GLRT) : L'algorithme s'arrête lorsque la statistique du Test de Rapport de Vraisemblance Généralisé (GLRT) dépasse un seuil $\beta(t, \delta)$. La statistique mesure la divergence KL minimale vers tout modèle alternatif où une action sous-optimale paraît meilleure que l'actuelle meilleure action empirique.
4. Solveur d'Optimisation : La résolution de l'optimisation intérieure dans la règle d'échantillonnage et la règle d'arrêt implique un problème d'optimisation semi-infini. Les auteurs emploient une méthode de l'ensemble de coupure (cutting-set method) (Mutapcic et Boyd, 2009) combinée à une réduction à trois actions (la base, la meilleure actuelle et un compétiteur) ainsi qu'un schéma de minimisation alternée pour résoudre les sous-problèmes bi-convexes résultants.

3. Contributions Clés

1. Formulation du Problème : L'article définit et étudie formellement le problème de BAI pour maximiser l'espérance du NDPO, une quantité pertinente pour isoler les effets directs causaux en présence de médiateurs.
2. Identification dans les Bandits : Il établit l'identification du NDPO espéré en utilisant uniquement les distributions interpersonnelles disponibles dans un cadre de bandit causal, faisant le pont entre la théorie de l'inférence causale et la prise de décision séquentielle.
3. Bornes Théoriques : Il dérive une nouvelle borne inférieure de la complexité d'échantillonnage qui met en évidence les défis uniques de l'optimisation du NDPO, spécifiquement le couplage des actions via la distribution du médiateur de base et le besoin d'accumulation d'informations au niveau de la cellule.
4. Conception d'Algorithme : Il introduit TaS-NDPO, un nouvel algorithme qui :
   • Utilise une méthode d'ensemble de coupure pour résoudre l'optimisation semi-infinie complexe requise pour les proportions d'échantillonnage optimales.
   • Incorpore un forçage au niveau de la cellule pour garantir la cohérence dans les régimes de médiateurs clairsemés.
   • Prouve la $\delta$-correction (exactitude garantie avec une probabilité de $1-\delta$) et l'optimalité asymptotique (atteindre la borne inférieure de la complexité d'échantillonnage quand $\delta \to 0$).

4. Résultats Expérimentaux

Les auteurs ont évalué TaS-NDPO sur des données synthétiques et sur un jeu de données publicitaires réel à grande échelle (IPinYou).

• Validation sur le Monde Réel (IPinYou) :
  • Le jeu de données impliquait la sélection de créations publicitaires ($X$) pour maximiser les clics ($Y$), la visibilité de l'emplacement ($Z$) servant de médiateur.
  • Divergence de Décision : L'action maximisant la moyenne interpersonnelle standard était différente de celle maximisant le NDPO. La moyenne standard favorisait une création apparaissant fréquemment dans les emplacements de tête (effet médié), tandis que l'action optimale pour le NDPO était différente.
  • Performance : TaS-NDPO a atteint un temps d'arrêt médian de 12 928 échantillons, soit environ 50 % d'efficacité supplémentaire par rapport à la variante au niveau de l'action (25 856 échantillons) et surpasse nettement l'échantillonnage uniforme et une approche privilégiant la base. Toutes les méthodes ont maintenu des taux d'erreur empirique nuls pour $\delta=0.05$.
• Expériences Synthétiques :
  • Échelle de l'Écart (Gap Scaling) : Les résultats ont confirmé l'échelle en $1/\Delta^2$ de la complexité d'échantillonnage prédite par la borne inférieure.
  • Rareté du Médiateur : L'avantage du forçage au niveau de la cellule était le plus marqué dans les contextes avec des cellules médiateur-résultat rares (régimes clairsemés), où le forçage au niveau de l'action échouait à accumuler suffisamment d'informations.
  • Temps d'Exécution : La surcharge de calcul de l'optimisation par ensemble de coupure était modérée (moyenne de 22,5 secondes par exécution pour jusqu'à 100k échantillons), ne constituant pas un goulot d'étranglement par rapport aux gains d'efficacité d'échantillonnage.

5. Signification et Revendications

L'article affirme que TaS-NDPO fournit une solution théoriquement fondée et empiriquement efficace pour identifier les traitements qui maximisent les effets directs causaux tout en excluant les voies médiées.

• Signification Théorique : Il étend le cadre Track-and-Stop aux contextes causaux avec des contre-factuels imbriqués, prouvant que l'optimalité asymptotique est réalisable même lorsque la fonction objectif couple les distributions entre différentes actions (via le médiateur de base).
• Signification Pratique : En isolant les effets directs, la méthode permet une prise de décision qui évite les mécanismes indésirables (ex: clickbait, effets secondaires indésirables ou positionnement contraire à l'éthique) qui pourraient autrement être favorisés par les approches de maximisation de la moyenne standard.
• Modestie : Les auteurs reconnaissent que leur cadre actuel se concentre sur les résultats binaires et une structure de graphe causal spécifique (Médiateur entre Traitement et Résultat). Ils notent que l'extension à des résultats multicatégories est directe, mais que la généralisation à des effets spécifiques de chemin plus complexes dans des structures causales plus larges reste une direction pour les travaux futurs. Ils précisent également que l'identification repose sur la plausibilité du graphe causal sous-jacent (spécifiquement l'absence de confusion non mesurée entre $Z$ et $Y$), ce qui est une hypothèse standard mais non testable en inférence causale.