Causal Bandit Over Unknown Graphs: Upper Confidence Bounds With Backdoor Adjustment

1. Problématique

Le problème du bandit causal (Causal Bandit) vise à identifier, par une expérimentation séquentielle, une intervention (ou "bras") qui maximise le gain espéré dans un système causal modélisé par un graphe acyclique dirigé (DAG).

• Limites des méthodes existantes : La plupart des approches actuelles supposent que la structure du graphe causal est connue ou imposent des hypothèses structurelles restrictives. Dans la pratique, le DAG sous-jacent est rarement connu.
• Défis spécifiques :
  • Dans les domaines à variables continues (modèles gaussiens), l'intervention optimale n'est pas nécessairement un parent direct de la variable de récompense, ce qui rend difficile la réduction de l'espace d'action.
  • L'acquisition de données expérimentales (interventions) est coûteuse, tandis que les données observationnelles sont souvent abondantes et peu coûteuses.
  • La présence de confondants latents (variables non observées) peut rendre l'identification causale impossible pour certaines interventions via des ajustements standards.

L'objectif de l'article est de concevoir un algorithme capable de fonctionner sans connaissance préalable du graphe causal, en intégrant efficacement les données observationnelles et expérimentales pour minimiser le regret cumulatif.

2. Méthodologie : L'algorithme BA-UCB

Les auteurs proposent l'algorithme Backdoor-Adjustment Upper Confidence Bound (BA-UCB). Contrairement aux méthodes qui tentent de reconstruire le DAG complet, BA-UCB se concentre sur l'identification dynamique d'ensembles d'ajustement valides pour chaque bras.

A. Hypothèses et Modèle

• Modèle : Variables observées suivant un modèle d'équations structurelles linéaires (SEM) gaussien (DAG sans confondants latents dans la première partie, puis étendu aux graphes mixtes dirigés acycliques - ADMG - avec confondants).
• Données :
  • $n_0$ : Taille de l'échantillon observationnel initial.
  • $n$ : Nombre de données observationnelles collectées à chaque tour.
  • $m$ : Nombre de données expérimentales collectées à chaque tour.

B. Étapes Clés de l'Algorithme

1. Identification des voisins de régression : À partir des données observationnelles, l'algorithme estime le "voisinage de régression" $\hat{M}_i$ de chaque variable $X_i$ (l'ensemble des variables corrélées conditionnellement). Pour un DAG gaussien, les parents directs de $X_i$ sont contenus dans ce voisinage.
2. Sélection des ensembles d'ajustement candidats : Pour chaque bras (intervention sur $X_i$), l'algorithme cherche un sous-ensemble $S \subseteq \hat{M}_i$ qui satisfait le critère de porte arrière (backdoor criterion).
   • Il compare l'estimateur du causal effect obtenu par ajustement observationnel ($\hat{\mu}_{i,obs}$) avec l'estimateur expérimental ($\hat{\mu}_{i,int}$).
   • Un ensemble $S$ est considéré comme candidat si l'intervalle de confiance de la différence $\hat{\mu}_{i,obs}(S) - \hat{\mu}_{i,int}$ contient zéro.
3. Construction des bornes de confiance (UCB) :
   • Au lieu de traiter les données séparément, BA-UCB combine les estimations observationnelles et expérimentales via une moyenne pondérée pour construire l'estimateur du gain $\hat{\mu}_i(t)$ et sa variance.
   • La décision de sélection du bras au tour $t+1$ suit la règle UCB classique : choisir le bras maximisant $\hat{\mu}_i(t) + \hat{\sigma}_i(t) \sqrt{\log t}$.
4. Gestion des confondants latents (Extension) :
   • Dans le cas d'ADMG (présence de confondants), si aucun ensemble d'ajustement valide n'est trouvé (intervalle de confiance ne contenant pas zéro), l'algorithme bascule automatiquement vers une estimation purement expérimentale pour ce bras, garantissant ainsi l'absence de biais.

3. Contributions Clés

1. Algorithme sans connaissance du graphe : BA-UCB ne nécessite pas de connaître le DAG ni de le reconstruire entièrement. Il apprend dynamiquement les ensembles d'ajustement nécessaires.
2. Intégration des données observationnelles : L'algorithme exploite les données observationnelles pour réduire la variance des estimateurs de l'effet causal, permettant une exploration plus efficace.
3. Théorie du regret :
   • Cas sans confondants : Les auteurs établissent une borne supérieure de regret cumulatif de l'ordre de $O(\sqrt{T \log T / (m+n)})$.
   • Avantage majeur : Cette borne ne dépend pas du nombre de bras $K$ (contrairement au regret classique $O(\sqrt{KT \log T})$), à condition d'avoir suffisamment de données observationnelles. Cela signifie que l'efficacité de l'algorithme ne se dégrade pas avec la taille de l'espace d'action.
   • Cas avec confondants : La borne de regret est décomposée en deux parties : une partie dépendant de $(m+n)$ pour les bras identifiables et une partie dépendant de $m$ pour les bras non identifiables.
4. Efficacité computationnelle : Contrairement aux approches bayésiennes (comme BBB-UCB) qui nécessitent de mettre à jour des probabilités sur tous les graphes possibles (coût exponentiel), BA-UCB est polynomial et scalable.

4. Résultats Expérimentaux

Les auteurs ont évalué BA-UCB via des simulations sur des graphes aléatoires de tailles variées ($p=10$ à $50$).

• Comparaison avec UCB standard : BA-UCB atteint un regret cumulatif nettement inférieur, surtout lorsque la taille du graphe augmente. L'avantage provient du partage d'information via les données observationnelles.
• Comparaison avec CN-UCB (Central Node UCB) :
  • CN-UCB suppose que l'intervention optimale est un parent de la récompense.
  • Les résultats montrent que lorsque l'intervention optimale n'est pas un parent (cas fréquent en domaines continus), CN-UCB échoue et son regret croît linéairement. BA-UCB reste robuste dans ces scénarios.
• Comparaison avec BBB-UCB (Bayesian Backdoor Bandit) :
  • BBB-UCB offre de bonnes performances mais est computationnellement prohibitif pour $p \ge 20$ (complexité exponentielle).
  • BA-UCB offre des performances comparables ou supérieures avec une complexité bien inférieure, rendant l'approche applicable à des graphes de grande taille.
• Robustesse aux confondants : Dans les simulations avec confondants latents, la version modifiée de BA-UCB maintient un regret inférieur à l'UCB standard, démontrant sa capacité à identifier les cas où l'ajustement est possible et à éviter les biais sinon.

5. Signification et Impact

Ce travail représente une avancée significative dans le domaine de l'apprentissage par renforcement causal :

• Praticité : Il rend le bandit causal applicable à des situations réelles où le modèle causal est inconnu et où les données observationnelles sont disponibles.
• Efficacité des ressources : En réduisant la dépendance au nombre d'actions $K$ et en valorisant les données observationnelles (moins coûteuses), l'algorithme permet de prendre de meilleures décisions avec moins d'expérimentations coûteuses.
• Généralité : L'extension aux graphes avec confondants latents élargit la portée de l'application à des systèmes complexes où l'omission de variables est inévitable.

En résumé, BA-UCB propose un cadre théorique et algorithmique robuste pour l'optimisation séquentielle dans des systèmes causaux complexes et partiellement observés, surpassant les méthodes existantes en termes de regret et d'efficacité computationnelle.