Résumé Technique : Bandits Multi-Bras Scintillants (Flickering Multi-Armed Bandits)

1. Formulation du Problème

Le papier introduit le cadre des Bandits Multi-Bras Scintillants (Flickering Multi-Armed Bandits - FMAB) pour traiter la prise de décision séquentielle dans des environnements où la disponibilité des actions est dynamique, restreinte et dépend de l'état actuel de l'agent. Contrairement aux problèmes classiques de Bandits Multi-Bras (MAB), qui supposent un accès sans restriction à un ensemble fixe de bras, le FMAB modélise des scénarios où un agent ne peut sélectionner qu'un sous-ensemble de bras défini par sa position actuelle dans un graphe évoluant de manière stochastique.

Contraintes Fondamentales :

• Accessibilité Locale : À chaque tour $t$, l'agent réside à l'arm $a_{t-1}$. L'ensemble des bras disponibles $L_t(a_{t-1})$ est restreint au voisinage de $a_{t-1}$ dans le graphe actuel $G_t$, plus le bras actuel lui-même.
• Évolution Stochastique : Le graphe $G_t$ évolue au fil du temps. L'agent ne peut pas sauter arbitrairement vers n'importe quel bras ; il doit naviguer à travers la structure du graphe pour atteindre des bras non visités ou prometteurs.
• Double Défi : L'agent fait face à une tension entre l'acquisition d'informations statistiques (explorer les bras pour identifier le meilleur) et les coûts de navigation physique (le coût de mouvement à travers le graphe pour atteindre ces bras).

Modèles de Graphes :
Les auteurs formalisent l'évolution de la disponibilité des actions à travers deux processus de graphes aléatoires primaires :

1. Erdős–Rényi (ER) i.i.d. : À chaque tour, un nouveau graphe est échantillonné indépendamment. Les arêtes existent avec une probabilité $p$ (homogène) ou des probabilités spécifiques aux arêtes $p_{ij}$ (hétérogène).
2. Édition-Markovienne (Edge-Markovian) : Le graphe évolue à partir de son état précédent. Les arêtes apparaissent avec une probabilité $\alpha$ et disparaissent avec une probabilité $\beta$. Cela modélise une connectivité "collante" où la topologie change graduellement plutôt que de se réinitialiser complètement.

L'objectif est de minimiser le regret cumulé $R(T) = \sum_{t=1}^T (\mu(a^*) - r_t(a_t))$, où $a^*$ est le bras optimal, sous réserve de ces contraintes de mouvement local.

2. Méthodologie

La solution proposée est un Algorithme à Deux Phases qui utilise une Marche Aléatoire Paresseuse (Lazy Random Walk) pour l'exploration.

Phase I : Identification du Meilleur Bras (Exploration)

• Politique : L'agent effectue une marche aléatoire paresseuse. À chaque étape, étant donné le bras actuel $a_{t-1}$ et le graphe réalisé $G_t$, l'agent sélectionne le bras suivant $a_t$ uniformément au hasard dans l'ensemble disponible $L_t(a_{t-1})$.
• Durée : Cette phase dure un temps prédéterminé $T_0$.
• Objectif : Collecter suffisamment d'échantillons de tous les bras pour estimer précisément leurs espérances de récompense $\hat{\mu}(a)$.
• Terminaison : À la fin de la Phase I, l'agent identifie le bras optimal candidat $\hat{a}^* = \arg\max_a \hat{\mu}(a)$.

Phase II : Navigation et Engagement (Exploitation)

• Politique : L'agent continue la marche aléatoire paresseuse jusqu'à ce qu'il atteigne avec succès la cible identifiée $\hat{a}^*$.
• Engagement : Une fois que l'agent arrive sur $\hat{a}^*$, il s'engage sur ce bras pour tous les tours suivants. Puisque l'agent peut toujours rester sur son bras actuel (auto-boucle), il reste à $\hat{a}^*$ indéfiniment.

Techniques d'Analyse Théorique

L'analyse fait le pont entre les techniques spectrales pour les chaînes de Markov évolutives et les inégalités de concentration pour les graphes variant dans le temps :

• Pour les Graphes ER i.i.d. :
  • Cas Homogène : Le noyau de transition attendu est symétrique et doublement stochastique, produisant une distribution stationnaire uniforme. Les auteurs utilisent un argument de régénération pour montrer que la marche se mélange efficacement.
  • Cas Hétérogène : Le noyau n'est pas symétrique. Les auteurs emploient un argument de typicalité uniforme, prouvant que les propriétés réalisées du graphe (degrés, coupes) se concentrent fortement autour de leurs valeurs attendues, permettant des bornes uniformes sur le gap spectral et la distribution stationnaire.
• Pour les Graphes Édition-Markovienne :
  • L'analyse traite le couplage entre la marche de l'agent et l'évolution du graphe.
  • Une condition de "Deux Vitesses" est établie : le graphe doit évoluer suffisamment lentement (condition de collant $\beta \le O(1/n)$) par rapport à la vitesse de mélange de la marche aléatoire.
  • L'algorithme nécessite une période de chauffe (burn-in period) ($T_{burn}$) pour que le processus du graphe atteigne sa distribution stationnaire avant que la phase d'exploration standard ne commence.

3. Résultats Clés

Bornes de Regret

Le papier établit des bornes de regret sous-linéaires de haute probabilité pour les deux modèles de graphes.

Théorème 1 (Graphes ER i.i.d.) :
Pour le modèle ER hétérogène, le regret $R(T)$ satisfait avec une probabilité $1-\delta$ :
$$R(T) \le \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{Coût d'Exploration}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{Coût de Navigation}}$$
où $\Delta_{\min}$ est le minimum de l'écart de sous-optimalité. Le coût d'exploration croît linéairement avec le nombre de bras $n$, et le coût de navigation rend compte du temps pour atteindre le bras optimal.

Théorème 3 (Graphes Édition-Markovienne) :
Sous les conditions de typicalité et de collant, le regret inclut un terme de chauffe supplémentaire :
$$R(T) \le \underbrace{O\left(\frac{\log(nT/\delta)}{\alpha+\beta}\right)}_{\text{Chauffe (Burn-in)}} + \underbrace{O\left(n \log(nT/\delta) + \frac{n \log(n/\delta)}{\Delta_{\min}^2}\right)}_{\text{Exploration}} + \underbrace{O\left(n \log(n/\delta)\right)}_{\text{Navigation}}$$

Regret Attendu et Quasi-Optimalité

En fixant la probabilité d'échec $\delta = 1/T$, les auteurs dérivent la borne du regret attendu :
$$E[R(T)] = O\left(\frac{n \log(nT)}{\Delta_{\min}^2}\right)$$
Le papier prouve que cette borne est quasi-optimale en dérivant une borne inférieure d'information théorique. La borne inférieure montre que tout algorithme doit subir un temps d'identification de $\Omega(n \log(T)/\Delta_{\min}^2)$. L'approche à deux phases proposée correspond à cette borne inférieure à des facteurs logarithmiques près, démontrant que le "coût de navigation" n'augmente pas fondamentalement la difficulté statistique de l'identification.

Simulations

Les conclusions théoriques sont validées par :

1. Expériences Contrôlées : Des simulations sur des graphes ER i.i.d. et Édition-Markovienne confirment que le regret moyen converge vers zéro et que le temps de navigation croît inversement avec la probabilité d'arête $p$ (soit $O(1/p)$).
2. Scénario de Réponse aux Catastrophes Robotique : Une simulation d'un véhicule terrestre explorant des sites de relais de communication dans une zone de catastrophe. Le véhicule opère avec une détection locale (pas de carte globale) et navigue dans un réseau de rues changeant dynamiquement (Édition-Markovienne). Les résultats montrent que l'algorithme identifie avec succès l'emplacement optimal et converge vers celui-ci, validant l'applicabilité pratique du modèle FMAB.

4. Signification et Contributions

Le papier revendique les contributions suivantes :

• Cadre Novateur : Il introduit le modèle FMAB, qui est le premier à coupler explicitement les contraintes de mouvement local (navigation) avec la prise de décision séquentielle sous incertitude. Cela comble une lacune dans la littérature existante où les bandits "Dormants" (Sleeping) ou "Volatiles" supposent que la disponibilité est indépendante des actions de l'agent ou mondialement connue.
• Analyse Unifiée : Il fournit une analyse de regret unifiée pour l'apprentissage sur des graphes aléatoires évolutifs, traitant les dynamiques i.i.d. et Markoviennes.
• Robustesse Algorithmique : La stratégie de marche aléatoire paresseuse proposée est montrée comme robuste à travers divers régimes de connectivité (homogène, hétérogène et temporellement corrélé).
• Limites Fondamentales : En établissant une borne inférieure correspondante, le travail caractérise le coût intrinsèque de l'apprentissage sous des contraintes de mouvement local, prouvant que l'overhead physique de la navigation ne dégrade pas le taux statistique fondamental de l'apprentissage (à des facteurs logarithmiques près).
• Pertinence Pratique : Ce travail fait le pont entre l'apprentissage en ligne théorique et les contraintes physiques, offrant une base rigoureuse pour des applications en robotique, réponse aux catastrophes et systèmes réseaux où les agents ne peuvent pas se téléporter entre les options.

Les auteurs concluent que bien que l'analyse de haute probabilité dépende de paramètres de graphes spécifiques, le regret attendu final dépend uniquement des paramètres fondamentaux du problème ($n, T, \Delta_{\min}$), suggérant que les contraintes structurelles de l'environnement sont efficacement gérées par la stratégie d'exploration proposée.