Learning from Local Walks on Dynamic Graphs with Bandit Feedback

Résumé Technique : Apprentissage par marches locales sur des graphes dynamiques avec rétroaction de type bandit

Formulation du problème
Cet article traite du problème des bandits multi-bras (MAB) stochastiques dans un cadre où l'apprenant est contraint à un mouvement local sur un graphe dynamique. Contrairement aux modèles de bandits classiques où n'importe quel bras est disponible à chaque tour, ou aux modèles de rétroaction par graphe où des observations latérales sont disponibles, ici l'apprenant ne peut choisir que son nœud actuel ou un voisin immédiat en fonction de la connectivité du graphe à cet instant précis.

• Cadre : Les bras correspondent aux sommets $A = \{1, \dots, n\}$ d'un graphe non orienté variant dans le temps $G_t = (A, E_t)$.
• Contraintes : À chaque tour $t$, l'apprenant n'observe que le voisinage local $L_t(a_{t-1})$ et doit choisir $a_t \in L_t(a_{t-1})$. Le processus de graphe est "oblivious" (indépendant des actions de l'apprenant).
• Défi central : Ce cadre découple l'identification du meilleur bras de l'exploitation. Dans les bandits classiques, identifier le bras optimal $a^\star$ permet une exploitation immédiate. Dans ce cadre dynamique, même après l'identification de $a^\star$, l'apprenant peut être structurellement isolé de celui-ci en raison de la topologie évolutive. La capacité d'apprentissage nécessite que l'environnement fournisse de manière cohérente des voies de navigation, et pas seulement que l'union de tous les graphes sur l'horizon soit connexe.

Méthodologie et conditions structurelles
Les auteurs adoptent un cadre "explore-then-commit" (explorer puis s'engager), séparant le problème en exploration (collecte d'échantillons) et navigation (atteindre la cible identifiée). Pour garantir l'apprentissage, ils introduisent une condition structurelle agnostique au processus basée sur la marche canonique (une marche aléatoire simple où l'apprenant reste ou se déplace uniformément vers un voisin).

• Mélange par fenêtre glissante à distribution stationnaire commune (Définition 1) : L'article rejette les conditions de connectivité sur l'ensemble de l'horizon (par exemple, l'union de tous les graphes étant connexe) comme étant insuffisantes, car elles ne garantissent pas la joignabilité à des instants d'arrêt arbitraires. Au lieu de cela, ils imposent une condition sur la marche aléatoire induite :
  1. Distribution stationnaire commune : Chaque instant du graphe $G_t$ induit un noyau réversible $U_t$ possédant une distribution stationnaire commune $\pi$ (obtenue par exemple par des séquences de degrés fixes).
  2. Mélange par fenêtre glissante : Dans chaque fenêtre de temps de longueur $W$, au moins une fraction $\rho$ des tours doit présenter un gap spectral $\ge \gamma$.
     Cette condition garantit que la marche converge vers $\pi$ de manière uniforme dans le temps, empêissant l'apprenant d'être piégé indéfiniment dans des sous-graphes locaux, quel que soit le moment où l'exploration se termine.

Algorithmes
L'article analyse une famille d'algorithmes opérant sous ce régime :

1. LEX (Exploration paresseuse à budget fixe) : Utilise la marche canonique pour l'exploration pendant un budget fixe $T_{exp}$ déterminé par les paramètres de mélange et les écarts de récompense. Il s'engage sur le leader empirique et navigue en utilisant la marche canonique si la cible n'est pas immédiatement accessible.
2. CB-LEX (Arrêt basé sur la confiance) : Remplace le budget fixe par une règle d'arrêt dépendante des données. Il se termine lorsque la borne inférieure de confiance (LCB) du leader empirique domine les bornes supérieures de confiance (UCB) de tous les autres bras (pas seulement du second), assurant ainsi une robustesse contre l'échantillonnage inégal.
3. RALEX (Exploration sensible aux récompenses) : Introduit un noyau biaisé par la récompense qui mélange la marche canonique avec une proposition optimiste (softmax sur les récompenses estimées). Crucialement, il maintient un "plancher canonique" ($\epsilon_0$) pour garantir que les propriétés de mélange structurel de la marche canonique soient préservées, garantissant la sécurité dans le pire des cas.

Résultats clés et bornes de regret
Sous la condition de mélange $(W, \rho, \gamma, \pi)$, les auteurs établissent un regret espéré sous-linéaire ($o(T)$) pour tous les algorithmes proposés. Les bornes de regret se décomposent en deux composantes distinctes :

1. Regret d'apprentissage : Évolue avec la difficulté statistique (inverse des écarts $\Delta^{-2}$) et le surcoût de mélange ($\tau_0$), représentant le coût de l'identification du meilleur bras.
2. Regret de navigation : Un coût structurel indépendant de l'horizon $T$, représentant le temps attendu pour atteindre le bras optimal identifié à partir du point d'arrêt.

• LEX/CB-LEX : Atteignent un regret de l'ordre de $O(\tau_0 \cdot \Psi \cdot \log T)$, où $\Psi$ capture la complexité des écarts et des masses stationnaires.
• RALEX : Prouve que le biais sensible aux récompenses est compatible avec un regret sous-linéaire. Bien que la borne du pire cas soit conservatrice (en raison du plancher canonique), l'article fournit un théorème distinct (Théorème 4) montrant que si le biais sensible aux récompenses augmente avec succès la probabilité de visitation des bras "proches des goulots d'étranglement", un gain de performance prouvable (amélioration multiplicative du terme d'apprentissage) est obtenu.

Signification et affirmations
L'article se positionne comme une caractérisation structurelle de l'apprentissage pour les bandits à contrainte locale sur des graphes dynamiques, plutôt que comme une proposition de minimisation du regret quasi-optimal sur des familles de graphes spécifiques (comme les graphes complets).

• Invariance par décalage : La principale contribution est la condition de mélange par fenêtre glissante invariante par décalage. Cela garantit que les hypothèses structurelles requises pour la navigation tiennent après le temps d'arrêt aléatoire de l'exploration, une exigence que les conditions sur l'horizon complet ne satisfont pas.
• Découplage : Ce travail sépare explicitement le coût statistique de l'apprentissage du coût structurel de la navigation, fournissant un cadre théorique clair pour les environnements dynamiques.
• Agnosticisme vis-à-vis du processus : Contrairement aux travaux antérieurs reposant sur des processus de graphes spécifiques (par exemple, i.i.d. Erdős–Rényen ou Markovien sur les arêtes), cet article fournit un théorème qui est valable pour toute séquence de graphes satisfaisant la condition de mélange centrée sur la marche.
• Sécurité vs Gain : L'analyse de RALEX distingue un "théorème de sécurité" (garantissant un regret sous-linéaire avec tout paramètre de biais) et un "théorème de gain" (certifiant l'amélioration des performances sous des conditions spécifiques sur la proposition sensible aux récompenses).

Les auteurs concluent que leur travail établit un "régime positif" où la marche canonique intrinsèque est suffisante pour l'apprentissage, offrant une base pour de futures extensions vers des noyaux plus complexes comme les marches de type Metropolis.