Multi-Agent Lipschitz Bandits

Résumé Technique : Bandits Lipschitz Multi-Agents

Énoncé du Problème
Cet article traite du problème des bandits stochastiques multi-joueurs décentralisés et coopératifs sur un espace d'actions continu à structure Lipschitzienne. Le cadre implique $N$ agents opérant dans un environnement partagé $X = [0, 1]^d$ sans communication directe. La fonction de récompense moyenne $\mu: X \to [0, 1]$ est inconnue mais supposée être $L$-Lipschitzienne.

Une contrainte critique est le modèle de « collision dure » (hard collision) : si deux agents ou plus sélectionnent des actions au sein de la même région (cellule) simultanément, tous les agents en collision reçoivent une récompense nulle et aucune observation. L'objectif est de maximiser la récompense cumulative collective sur un horizon de temps $T$. Le défi réside dans la confluence de trois facteurs : l'espace d'actions continu (qui rend une discrétisation naïve intraitable), la contrainte de collision dure (nécessitant une coordination) et l'absence de canaux de communication.

Méthodologie
Les auteurs proposent un protocole modulaire, sans communication, en quatre phases, conçu pour découpler le problème de coordination du problème d'apprentissage. La stratégie repose sur un modèle de partition par cellules où l'espace d'action est discrétisé en $K$ cellules hypercubiques de côté $h$.

1. Phase I : Identification Grossière :
   Tous les agents effectuent un échantillonnage aléatoire uniforme des centres de cellules pendant une durée fixe $T_0$. Malgré une probabilité élevée de collisions, cette phase garantit que, avec une probabilité élevée, chaque agent obtient suffisamment d'observations non-collidées pour construire des bornes de confiance grossières sur la valeur maximale de chaque cellule. Cette phase sert à élaguer l'espace de recherche en éliminant les cellules sous-optimales.

2. Phase II : Raffinement Dirigé par les Maxima (« Local Peek ») :
   Pour traiter la pathologie « centre-vs-maximum » — où la valeur du centre d'une cellule est un mauvais indicateur de son véritable supremum en raison de pics aigus près des frontières — les agents effectuent une exploration localisée à l'intérieur des cellules candidates. Ils échantillonnent à partir d'une grille fine ($\eta$-réseau) à l'intérieur des cellules candidates restantes pour construire des intervalles de confiance à haute résolution sur les véritables maxima de cellules $\mu^*(C)$. Cela permet aux agents d'identifier les $N$ meilleures cellules basées sur leurs véritables suprema plutôt que sur leurs centres.

3. Phase II 1/2 : Attribution Décentralisée (« Musical Chairs ») :
   Une fois que les agents s'accordent sur un ensemble de $N$ cellules cibles (soit par une condition d'$\epsilon$-unicité, soit par un ordonnancement public), ils doivent s'assigner à ces cellules sans conflit. Les auteurs analysent une version pratique du protocole « Musical Chairs » où les agents ne savent pas quelles cellules sont occupées. Les agents non assis échantillonnent de manière répétée à partir de l'ensemble cible jusqu'à ce qu'ils atterrissent sur une cellule inoccupée. L'analyse montre que ce processus se termine en un temps attendu de $O(N)$.

4. Phase III : Optimisation Intra-Cellulaire :
   Une fois installés, le problème se factorise en $N$ problèmes de bandits Lipschitziens à joueur unique indépendants. Chaque agent exécute un algorithme standard quasi-optimal (par exemple, Zooming) confiné à sa cellule assignée pour le reste de l'horizon.

Principales Contributions

• Première Solution de Bout en Bout : Ce travail fournit la première solution fondée sur des principes pour les bandits multi-joueurs décentralisés dans des domaines continus avec des collisions dures.
• Identification Dirigée par les Maxima : Les auteurs introduisent une phase d'identification novatrice qui effectue un « regard local » (local peek) pour encadrer les véritables suprema des cellules, évitant ainsi de manière prouvée les biais inhérents aux stratégies de classement basées sur les centres.
• Découplage de la Coordination et de l'Apprentissage : Le protocole sépare le coût de coordination du coût d'apprentissage. Les phases de coordination (I, II et attribution) engendrent un coût indépendant de l'horizon de temps $T$ (pour une confiance fixée) ou seulement polylogarithmique en $T$ (en regret attendu).
• Garanties Sans Écart (Gap-Free) : Sous une hypothèse de couverture/ordonnancement public et une condition de dimension de quasi-optimalité, les auteurs dérivent une borne de regret sans écart, assurant la robustesse même lorsque les écarts de récompense entre les cellules sont nuls.
• Extension aux Modèles de Seuil de Distance : Le cadre est étendu aux modèles de collision par seuil de distance généraux en mappant le problème sur un ensemble de « balles sûres » dérivées d'un $r$-empilement, assurant la séparation entre les agents.

Résultats et Bornes de Regret
Le papier établit les garanties de regret suivantes, où $d$ est la dimension de l'espace d'action :

• Régime de Consensus : Sous une condition d'$\epsilon$-unicité (un écart suffisant entre la $N$-ième et la $(N+1)$-ième meilleure cellule), le regret cumulé attendu est borné par :
  $$\mathbb{E}[R(T)] \leq \underbrace{O(N(T_0 + T_1) + N^2)}_{\text{Coût de Coordination}} + \underbrace{\tilde{O}\left(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}}\right)}_{\text{Coût d'Apprentissage}}$$
  Le terme d'apprentissage dominant correspond au taux optimal du joueur unique Lipschitzien de $\tilde{O}(T^{(d+1)/(d+2)})$. Le coût de coordination est indépendant de l'horizon pour une confiance fixée.

• Régime Sans Écart (Gap-Free) : Sans supposer d'écart de récompense, l'algorithme atteint un regret attendu de $\tilde{O}(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}})$ en exécutant le protocole par époques avec une précision ajustée dynamiquement.

• Borne Inférieure : Les auteurs prouvent une borne inférieure minimax correspondante de $\Omega(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}})$, démontrant que la dépendance en $T^{(d+1)/(d+2)}$ ne peut être améliorée dans ces régimes. Cela confirme que la décentralisation et les collisions ne dégradent pas la difficulté statistique fondamentale par rapport au cas à joueur unique.

Signification
L'article affirme fournir les premières garanties de bout en bout pour les bandits multi-joueurs dans des domaines continus. Sa principale importance réside dans la démonstration que la surcharge de coordination dans un cadre décentralisé peut être isolée et rendue indépendante de l'horizon de temps, permettant au système collectif d'atteindre le même taux d'apprentissage asymptotique qu'un agent optimal unique. Le travail souligne qu'avec une stratégie de recherche dirigée par les maxima, les défis subtils des espaces d'action continus (spécifiquement le biais centre-vs-maximum) peuvent être résolus sans communication, permettant une exploration coopérative efficace dans des environaux de contention de ressources.