Résumé Technique : L'Apprentissage de Graphes est Sous-optimal dans les Bandits Causaux

Énoncé du Problème

Ce papier examine le problème de la minimisation du regret dans les bandits causaux sous l'hypothèse de suffisance causale (absence de confondants non observés), où la structure du graphe causal sous-jacent est inconnue de l'agent. Dans ce cadre, un agent sélectionne séquentiellement des actions définies par des interventions sur des sous-ensembles de variables (de taille au plus $m$) afin de maximiser la récompense cumulative. La récompense est déterminée par un nœud spécifique $Y$ dans un graphe acyclique dirigé (DAG) sur $n$ variables.

La littérature antérieure a largement opéré sous l'hypothèse que l'identification de l'ensemble des parents du nœud de récompense ($Pa_Y$) est un prérequis nécessaire à un apprentissage efficace. Les stratégies impliquent généralement une approche en deux phases : d'abord découvrir l'ensemble des parents (souvent via l'apprentissage structurel ou une recherche séquentielle), puis appliquer des algorithmes de bandits standards (comme UCB) restreints aux interventions sur ces parents. Alternativement, certains travaux tentent d'apprendre les parents et de minimiser le regret simultanément.

La question centrale abordée par ce travail est : L'identification de l'ensemble des parents du nœud de récompense est-elle une stratégie nécessaire ou optimale pour minimiser le regret cumulatif ?

Méthodologie et Cadre Théorique

1. Le Compromis entre Identification et Regret

Les auteurs établissent d'abord un conflit théorique fondamental entre les objectifs de l'identification des parents et de la minimisation du regret.

• Construction de Contre-Exemples : Ils construisent une sous-classe spécifique d'instances ($\mathcal{E}_0$) où l'ensemble des actions à haute récompense est disjoint de l'ensemble des actions fournissant des informations sur l'ensemble des parents.
• Théorème 3.2 (Compromis Identification-Regret) : Le papier démontre que pour toute politique atteignant des taux d'erreur exponentiellement faibles dans l'identification de l'ensemble des parents (c'est-à-dire $\delta_T \in O(\exp(-T^\alpha))$), le regret cumulatif doit croître comme $\Omega(T^\alpha)$. Inversement, atteindre des taux de regret optimaux exclut l'identification de l'ensemble des parents avec une forte probabilité.
• Implication : Dans les scénarios du pire cas, un agent ne peut pas simultanément apprendre la structure causale et minimiser le regret efficacement. Les actions « informatives » requises pour distinguer le véritable ensemble des parents entraînent souvent un regret élevé, tandis que les actions « optimales » ne fournissent aucune information structurelle.

2. Bornes Inférieures du Regret

Les auteurs dérivent de nouvelles bornes inférieures informationnelles sur le regret du pire cas, qui valent même si l'agent possède une connaissance complète du graphe causal sur les variables non liées à la récompense ($G$). Cela démontre que la connaissance de la structure du graphe (à l'exception de l'ensemble spécifique des parents de la récompense) n'améliore pas les garanties de regret du pire cas.

• Taille des Parents Connue ($k$) :
  • Cas $m \ge k$ : La borne inférieure est $\Omega\left(\sqrt{T \max\left(\frac{(\ell-1)^k \binom{n}{k}}{\binom{m}{k}}, \ell^k\right)}\right)$.
  • Cas $m < k$ : La borne inférieure est $\Omega\left(\sqrt{T \max\left((\ell-1)^m \binom{n}{m}, \ell^m\right)}\right)$.
  • Ces bornes capturent la complexité combinatoire de l'espace d'actions et montrent que la difficulté provient de l'incertitude quant à quel sous-ensemble de taille $k$ constitue les parents, et non de la topologie du graphe elle-même.
• Taille des Parents Inconnue ($k$) :
  • Le papier établit une borne inférieure sur le produit des regrets pour différentes tailles de parents ($k_1$ et $k_2$), prouvant qu'aucun algorithme unique ne peut uniformément atteindre les taux de regret optimaux pour toutes les valeurs possibles de $k$. Cela nécessite un compromis dans la performance à travers différentes instances de problèmes.

3. Algorithmes Proposés

Contournant le besoin d'une récupération explicite du graphe, les auteurs proposent deux algorithmes qui atteignent des bornes de regret quasi-optimales :

• Algorithme 1 ($k$ connu) :

  • Mécanisme : Au lieu d'apprendre le graphe, l'algorithme échantillonne aléatoirement un sous-ensemble d'actions ($A'$) depuis l'espace de toutes les interventions de taille $m$. La taille de ce sous-ensemble est soigneusement choisie pour garantir, avec une forte probabilité, qu'il contient au moins une action optimale.
  • Exécution : Il exécute ensuite un algorithme standard de borne supérieure de confiance (UCB) exclusivement sur ce sous-ensemble réduit $A'$.
  • Performance : Il atteint un regret correspondant aux bornes inférieures dérivées, à des facteurs logarithmiques près, sans nécessiter la connaissance du graphe $G$ ni de l'ensemble spécifique des parents.

• Algorithme 2 ($k$ inconnu) :

  • Mécanisme : Conçu pour s'adapter à un nombre inconnu de parents, cet algorithme fonctionne par phases. À chaque phase, il échantillonne un sous-ensemble aléatoire d'actions, exécute UCB, et construit un « bras mixte » (une action randomisée basée sur la distribution empirique de la phase).
  • Adaptativité : La longueur de la phase et la taille de l'échantillon sont ajustées dynamiquement (en divisant par deux la taille de l'échantillon, en doublant la longueur de la phase) pour équilibrer l'exploration à travers différentes tailles potentielles d'ensembles de parents.
  • Performance : L'algorithme s'avère Pareto-optimal en taux. Cela signifie que son vecteur de regret (performance à travers tous les $k$ possibles) ne peut être strictement dominé par aucune autre politique ; il atteint le meilleur compromis possible entre la performance sur les instances avec un petit $k$ et un grand $k$.

Résultats Clés et Contributions

1. Sous-optimalité de l'Apprentissage de Graphes : Le papier démontre rigoureusement que l'apprentissage de l'ensemble des parents est sous-optimal pour la minimisation du regret dans le cadre du pire cas. Il existe des instances où les objectifs de l'apprentissage structurel et de la minimisation du regret sont fondamentalement conflictuels.
2. Nouvelles Bornes Inférieures : Les auteurs fournissent les premières bornes inférieures pour les bandits causaux avec graphes inconnus qui prennent explicitement en compte la structure combinatoire de l'espace d'actions. Crucialement, ces bornes s'appliquent même lorsque l'agent connaît le graphe complet $G$ (à l'exception des parents de la récompense), prouvant que la connaissance structurelle seule est insuffisante pour contourner la difficulté du problème.
3. Algorithmes Quasi-Optimaux :
   • Pour $k$ connu, l'algorithme proposé atteint un regret $\tilde{O}\left(\sqrt{T \ell^k \binom{n}{k} / \binom{m}{k}}\right)$, ce qui correspond à la borne inférieure.
   • Pour $k$ inconnu, l'algorithme adaptatif atteint un vecteur de regret Pareto-optimal, gérant efficacement l'incertitude de $k$ sans connaissance préalable.
4. Validation Empirique : Les expériences sur des graphes synthétiques d'Erdős–Rényi démontrent que les méthodes proposées (EmpKnownUCB+ et EmpUnknownUCB+) surpassent significativement les bases de référence existantes, notamment :
   • RAPS : Une méthode de l'état de l'art qui apprend explicitement les parents avant de minimiser le regret.
   • UCB Standard : Appliqué à l'espace d'actions complet.
   • Les méthodes proposées réduisent le regret d'un facteur allant jusqu'à 20 par rapport aux bases de référence, en particulier dans les configurations où la phase d'identification des parents de RAPS consommerait des ressources excessives.

Importance et Revendications

Le papier revendique un changement de paradigme dans l'approche des bandits causaux avec structures inconnues. Il soutient que la découverte causale explicite est inutile pour atteindre des taux de regret optimaux. En démontrant que l'apprentissage structurel et la minimisation du regret peuvent être des objectifs conflictuels, le travail suggère que les algorithmes doivent se concentrer directement sur le paysage des récompenses plutôt que d'essayer de reconstruire le graphe causal sous-jacent.

Les auteurs soulignent que leurs résultats valident sous aucune hypothèse distributionnelle (par exemple, linéarité) et pour des interventions dures. Ils notent que bien que l'information structurelle (le graphe $G$) n'améliore pas les bornes de regret du pire cas, les algorithmes proposés atteignent ces bornes sans avoir besoin d'une telle information. Le travail conclut que pour la minimisation du regret du pire cas, « contourner la récupération du graphe et des parents » n'est pas seulement viable, mais supérieur aux approches traditionnelles en deux étapes.

Les travaux futurs, tels que suggérés par les auteurs, consistent à caractériser les configurations où ces objectifs pourraient s'aligner, ou à investiguer des hypothèses distributionnelles spécifiques qui pourraient permettre une optimisation simultanée de l'apprentissage structurel et du regret.