Résumé technique : Échantillonnage dirigé par l'information pour les bandits causaux

Formulation du problème

Cet article traite du problème des bandits causaux contextuels dans des environnements contenant des variables non manipulables. Dans les problèmes de bandits multi-bras standard, les actions sont sélectionnées pour maximiser les récompenses avec des distributions inconnues. Dans les bandits causaux, les actions correspondent à des interventions ($do(X=x)$) sur un modèle causal structurel (SCM), où les récompenses sont couplées par des mécanismes causaux partagés.

Le défi spécifique abordé ici provient du fait que certaines variables dans le graphe causal influencent la récompense mais ne peuvent pas être directement manipulées (par exemple, les attributs démographiques, les caractéristiques génétiques ou les conditions macroéconomiques). Bien que ces variables ne puissent pas faire l'objet d'une intervention, elles servent de variables de contexte observées avant la sélection de l'action et de variables observées après l'intervention. L'objectif est de sélectionner une intervention réalisable parmi un ensemble d'armes candidates pour maximiser la récompense attendue dépendante du contexte, $\mu_x(c) = E[Y | do(x), C=c]$, tout en partageant efficacement l'information entre différentes interventions.

Les auteurs supposent :

1. Un graphe causal $G$ connu sans variables de confusion latentes.
2. Un ensemble de variables non manipulables $N \subseteq V \setminus \{Y\}$.
3. Les variables de contexte $C$ sont observées avant la sélection de l'action et sont closes sous l'ascendance (c'est-à-dire $An(C)=C$).
4. La distribution observationnelle est inconnue, paramétrée par des tables de probabilités conditionnelles (CPT).

Méthodologie

1. Formulation bayésienne et paramétrage

Les auteurs adoptent un cadre bayésien où le paramètre inconnu $\theta$ consiste en les tables de probabilités conditionnelles de la distribution observationnelle. Sous l'hypothression de l'absence de facteurs de confusion latents, les distributions interventionnelles sont identifiables à partir de la distribution observationnelle via la formule de factorisation tronquée.

• Indépendance des paramètres : Le vecteur de paramètres $\theta$ est décomposé en vecteurs locaux $\theta_{ij}$ correspondant aux CPT de chaque variable étant donné les configurations de ses parents.
• Mises à jour de la distribution a posteriori : En supposant des a priori de Dirichlet conjugués, la distribution a posteriori sur $\theta$ est mise à jour de manière analytique sur la base des données observées. Cela permet aux échantillons collectés sous une intervention de mettre à jour les estimations pour d'autres interventions en affinant les CPT partagées.

2. Identification des bras candidats

Pour gérer les variables non manipulables, l'article utilise le concept d'ensembles d'interventions minimales potentiellement optimales (POMISs) dérivés de Lee et Bareinboim [2019].

• Projection : Le graphe original est projeté sur un graphe $H$ ne contenant que des variables manipulables. La confusion latente induite par les variables non manipulables est représentée par des arêtes bidirectionnelles dans $H$.
• Sélection des bras : L'ensemble des bras candidats $\mathcal{A}$ est généré en énumérant les POMISs du graphe projeté $H$. Cela garantit que l'algorithme ne considère que les interventions qui sont théoriquement optimales sous les contraintes de manipulabilité.

3. Algorithmes proposés

L'article propose deux variantes causales d'algorithmes de bandits standards :

A. Thompson Sampling Causal (TS)

• Mécanisme : À chaque tour $t$, étant donné le contexte $C_t=c_t$, l'algorithme échantillonne un paramètre $\theta_t$ à partir de la distribution a posteriori conditionnée par le contexte $P(\theta | F_t, C_t=c_t)$. Il sélectionne ensuite l'action $a_t$ qui maximise la récompense attendue sous le paramètre échantillonné : $a_t = \arg\max_{a \in \mathcal{A}} E[Y_a | \theta_t, c_t]$.
• Analyse du regret : Les auteurs établissent une borne de regret bayésien sous-linéaire dépendant de l'entropie de la correspondance de l'action optimale, $H(\Pi^*)$. La borne s'établit comme $O(\sqrt{T |A| |C| \log |A|})$.

B. Échantillonnage dirigé par l'information causal (IDS)

• Mécanisme : L'IDS sélectionne une distribution sur les actions qui minimise le ratio d'information, défini comme le carré du regret instantané attendu divisé par le gain d'information attendu sur l'action optimale.
  • Terme de regret : $\Delta_t(\pi | c_t) = \sum \pi(a) E[Y_{\Pi^*(c_t)} - Y_a]$.
  • Terme de gain d'information : $g_t(\pi | c_t) = \sum \pi(a) D_{KL}(P(\Pi^*, Y_a) || P(\Pi^*)P(Y_a))$.
• Approximation de Monte Carlo : Puisque les espérances a posteriori requises pour calculer le ratio d'information sont analytiquement intraitables dans les espaces de paramètres continus, l'algorithme les approxime en utilisant $N$ échantillons de Monte Carlo provenant de la distribution a posteriori.
• Contrôle de l'erreur : Les auteurs dérivent des bornes de concentration à haute probabilité (Lemmes 3 et 4) pour les estimations de Monte Carlo du regret attendu et du gain d'information. Ces bornes quantifient explicitement l'erreur supplémentaire introduite par l'approximation.

Contributions clés

1. Cadre bayésien pour les variables non manipulables : L'article formule des bandits causaux contextuels avec des variables non manipulables en traitant les CPT observationnelles comme le paramètre inconnu. Cette formulation permet le partage d'information entre les interventions via les mécanismes causaux partagés, même lorsque certaines variables ne peuvent pas être manipulées.
2. Thompson Sampling causal avec garanties de regret : Les auteurs proposent un algorithme de TS causal et prouvent une borne de regret bayésien sous-linéaire dépendant de l'entropie. Cela étend les garanties de TS aux contextes avec des contraintes structurelles et de contexte.
3. IDS causal avec analyse d'approximation : L'article développe un algorithme IDS causal qui équilibre la minimisation du regret et l'acquisition d'information. Crucialement, il dérive une borne de regret qui sépare explicitement le terme informationnel standard de l'erreur introduite par l'approximation de Monte Carlo. Lorsque le ratio d'information est calculé exactement (version oracle), le taux standard de l'IDS sous-linéaire est récupéré.
4. Bornes de concentration pour les estimations de Monte Carlo : Les auteurs fournissent des bornes de confiance à haute probabilité pour les estimations de Monte Carlo du regret instantané attendu et du gain d'information contextuel. Ces résultats quantifient l'impact de l'erreur d'échantillonnage de la distribution a posteriori sur les garanties de performance de l'algorithme.

Résultats et évaluation

Les méthodes proposées ont été évaluées sur plusieurs tâches de bandits causaux synthétiques, incluant des exemples structurés et des graphes causaux générés aléatoirement.

• Performance : Les expériences démontrent que les algorithmes Causal TS et Causal IDS proposés surpassent à la fois les bases causales et non causales.
• Mécanisme : La performance supérieure est attribuée à la capacité des algorithmes à exploiter plus efficacement l'information partagée entre différentes interventions via la structure causale partagée, particulièrement en présence de variables non manipulables.

Signification

L'article affirme sa pertinence en fournissant un cadre principled pour la prise de décision dans des environnements causaux où le contrôle total sur les variables est impossible. En intégrant les variables non manipulables dans le cadre des bandits causaux et en offrant des algorithmes avec des bornes de regret rigoureuses (incluant l'analyse des erreurs d'approximation), ce travail comble le fossé entre l'inférence causale théorique et la prise de décision séquentielle pratique. La gestion explicite des erreurs d'approximation de Monte Carlo dans l'IDS est mise en avant comme une avancée théorique clé, garantissant que les bénéfices de l'échantillonnage dirigé par l'information sont préservés même lorsque le calcul exact est irréalisable.