Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

Résumé Technique : Suivi du Leader Perturbé pour les Bandits Découplés

Cadre du Problème
Ce papier aborde le problème des bandits multi-bras (MAB) découplés, un cadre où l'apprenant sélectionne deux bras distincts à chaque round $t$ : un bras $i_t$ pour l'exploitation (encaissant la perte $\ell_{t, i_t}$ sans l'observer) et un bras $j_t$ pour l'exploration (observant la perte $\ell_{t, j_t}$ sans l'encaisser). Ce cadre modélise des scénarios tels que les systèmes de communication à bande ultra-large (capteur d'un canal différent du canal de transmission) et le transfert sim-to-real en robotique. L'objectif est de minimiser le pseudo-regret, défini comme la différence entre la perte cumulative encourue par les choix d'exploitation de l'apprenant et la perte cumulative du meilleur bras fixe a posteriori.

Le papier vise des garanties Meilleur des Deux Mondes (BOBW), cherchant à atteindre :

1. Un regret optimal de $O(\sqrt{KT})$ dans le régime adversaire (où les pertes sont déterminées par un adversaire adaptatif).
2. Un regret presque optimal et indépendant du temps de $O(K/\Delta_{\min})$ dans le régime adversaire stochastiquement contraint (SCA) (qui inclut le cadre stochastique standard), où $\Delta_{\min}$ est le plus petit écart de sous-optimalité.

Méthodologie
Les auteurs proposent une nouvelle politique basée sur le cadre Suivi du Leader Perturbé (FTPL), spécifiquement conçue pour surmonter les goulots d'étranglement computationnels des politiques BOBW existantes dans les contextes découplés.

• Stratégie d'Exploitation : L'apprenant sélectionne le bras d'exploitation $i_t$ en minimisant une estimation de perte cumulative perturbée :
  $$i_t = \arg\min_{i \in [K]} \left\{ \hat{L}_{t,i} - \frac{r_{t,i}}{\eta_t} \right\}$$
  où $\hat{L}_{t,i}$ est la perte cumulative estimée, $\eta_t$ est le taux d'apprentissage, et $r_{t,i}$ sont des perturbations aléatoires i.i.d. échantillonnées selon une distribution de Pareto $P_\alpha$ avec un paramètre de forme $\alpha > 1$. Ce type de perturbation correspond à la politique $\beta$-Tsallis-INF (avec $\alpha = 1/(1-\beta)$), connue pour atteindre des garanties BOBW.

• Stratégie d'Exploration (Innovation Clé) : Dans les algorithmes de bandits FTPL standards, la construction d'un estimateur de perte pondéré par l'importance (IW) sans biais nécessite généralement de connaître la probabilité exacte $w_{t,i}$ de sélection du bras $i$. Dans les bandits découplés, la probabilité d'exploration $p_{t,i}$ doit être définie en fonction de $w_{t,i}$. Cependant, FTPL ne fournit pas d'expression fermée pour $w_{t,i}$ (contrairement à FTRL), et estimer le vecteur complet par rééchantillonnage géométrique est coûteux en calcul ($O(K^2)$ ou plus).
  Pour résoudre cela, les auteurs introduisent une probabilité de substitution $q_{t,i}$ qui peut être calculée directement à partir des estimations de pertes actuelles, sans rééchantillonnage ni optimisation convexe :
  $$q_{t,i} = \left( \frac{1}{1 + \eta_t \hat{L}_{t,i}} \wedge \frac{1}{\sigma_{t,i}^{1/\alpha}} \right)^{\frac{\alpha+1}{2}}$$
  où $\sigma_{t,i}$ est le rang de $\hat{L}_{t,i}$ parmi tous les bras. Le bras d'exploration $j_t$ est ensuite sélectionné selon la distribution normalisée $p_{t,i} = q_{t,i} / \sum_j q_{t,j}$. Cette approche évite le besoin de valeurs explicites $w_{t,i}$ tout en maintenant les propriétés théoriques requises pour les garanties BOBW.

Contributions Clés

1. Première politique BOBW basée sur FTPL pour les Bandits Découplés : Le papier présente la première politique atteignant des garanties BOBW dans les bandits découplés sans résoudre de problèmes d'optimisation convexe (nécessaires aux approches basées sur FTRL comme Decoupled-Tsallis-INF) ni employer de procédures de rééchantillonnage (généralement requises pour l'estimation de probabilité FTPL).
2. Efficacité Computationnelle : En remplaçant le calcul complet du vecteur de probabilité par la substitution $q_{t,i}$ efficacement calculable, la politique proposée réduit la complexité computationnelle par étape. Bien que le tri des estimations de perte prenne $O(K \log K)$, les auteurs notent qu'une implémentation optimisée peut atteindre des mises à jour en $O(K)$ en suivant les changements de rang de manière incrémentale. Cela contraste avec les politiques FTRL qui nécessitent une optimisation convexe itérative (par exemple, la méthode de Newton) à chaque étape.
3. Garanties Théoriques :
   • Régime Adversaire : La politique atteint une borne de regret de $O(\sqrt{KT})$, correspondant à la borne inférieure connue pour les bandits découplés.
   • Régime Stochastique/SCA : La politique atteint une borne de regret de $O(K/\Delta_{\min})$ (spécifiquement $O(\sqrt{K/\Delta_{\min}} \sum_{i \neq i^*} 1/\Delta_i + K/\Delta_{\min})$ pour $\alpha=3$), ce qui est presque optimal et améliore les bornes dépendantes du temps des bandits stochastiques standards.

Résultats

• Théoriques : Le papier fournit des preuves rigoureuses (via une décomposition du regret en termes de stabilité et de pénalité) montrant que la probabilité de substitution $q_{t,i}$ est suffisamment proche de la vraie probabilité d'exploitation pour maintenir les bornes de regret nécessaires.
• Empiriques : Des expériences sur des données synthétiques (régimes adversaire et stochastique) et une simulation réelle utilisant le jeu de données MovieLens 100K démontrent que la politique FTPL proposée :
  • Atteint un regret cumulatif inférieur par rapport aux politiques BOBW existantes (Decoupled-Tsallis-INF/FTRL et EXP3).
  • Démontre une efficacité computationnelle supérieure. Dans le régime adversaire, la politique proposée s'exécute significativement plus vite que les bases de référence FTRL. Pour $K=64$, le ratio de temps d'exécution de FTRL par rapport à FTPL a été observé comme étant environ 1363 fois plus lent.
  • S'adapte efficacement au nombre de bras $K$, maintenant une robustesse face à des tailles d'écart $\Delta$ variables.

Signification et Revendications
Le papier revendique que sa contribution principale est de combler le fossé entre l'optimalité théorique des politiques BOBW basées sur FTRL et l'efficacité computationnelle de FTPL dans le contexte des bandits découplés. En éliminant le besoin d'optimisation convexe et de rééchantillonnage, la méthode proposée permet à FTPL de réaliser pleinement ses avantages d'efficacité sans sacrifier la performance en regret. Les auteurs suggèrent que la technique d'utilisation de probabilités de substitution facilement calculables à la place de vecteurs de probabilité exacts pourrait être applicable à d'autres cadres algorithmiques (tels que la famille Prod) au-delà de FTPL, permettant potentiellement une efficacité computationnelle améliorée dans des contextes de bandits plus larges. Ce travail est motivé par des applications pratiques dans les systèmes de communication et la robotique où la latence computationnelle par étape est critique.