A single algorithm for both restless and rested rotting bandits

1. Problématique

L'article s'intéresse au problème des Bandits Multi-Armes (MAB) dans des environnements non stationnaires où les récompenses des actions (les "bras") ont tendance à décroître au fil du temps. Ce phénomène, appelé "rotting" (pourriture), est courant dans des applications réelles comme les systèmes de recommandation (l'utilisateur se lasse des mêmes contenus) ou les tutoriels intelligents (la difficulté perçue augmente).

Le papier distingue deux modèles de décroissance :

• Rested Rotting Bandits : La valeur d'un bras ne diminue que lorsqu'il est sélectionné (ex: fatigue de l'utilisateur sur un article spécifique).
• Restless Rotting Bandits : La valeur d'un bras diminue avec le temps, indépendamment du fait qu'il soit sélectionné ou non (ex: obsolescence d'une nouvelle).

Le défi principal :
Jusqu'à présent, ces deux régimes étaient considérés comme fondamentalement différents. Les algorithmes performants pour les bandits "restless" (comme ceux basés sur la détection de changements ou l'exploration active) échouaient souvent dans le régime "rested", et vice-versa. De plus, il a été démontré que si les récompenses pouvaient augmenter, aucun algorithme ne pouvait atteindre un regret sous-linéaire optimal dans un mélange des deux régimes. L'objectif de l'article est de concevoir un algorithme unique capable d'atteindre des garanties de regret quasi-optimales dans les deux cas, sans connaissance a priori du type de non-stationnarité ni des paramètres de décroissance.

2. Méthodologie : RAW-UCB

Les auteurs proposent un nouvel algorithme appelé RAW-UCB (Rotting Adaptive Window Upper Confidence Bound).

Principes Fondamentaux

Contrairement aux approches classiques qui utilisent des mécanismes complexes de détection de changements ou d'exploration forcée, RAW-UCB repose sur une stratégie d'index pure (type UCB) adaptée à la décroissance.

1. Fenêtres Adaptatives : Pour chaque bras $i$, l'algorithme calcule l'UCB (Upper Confidence Bound) sur plusieurs fenêtres temporelles (ou historiques) de tailles différentes $h$.
   • Une petite fenêtre $h$ offre une faible variance mais un biais élevé (car les données sont très récentes et potentiellement très dégradées).
   • Une grande fenêtre $h$ réduit le biais (moyenne sur une période plus longue) mais augmente la variance.
2. Sélection de la Meilleure Fenêtre : RAW-UCB calcule l'index UCB pour toutes les fenêtres possibles incluant le dernier tirage du bras et sélectionne le bras ayant l'index minimum (le plus pessimiste/le plus serré) parmi toutes les fenêtres.
   $$\text{ind}(i, t) = \min_{h \le N_{i,t-1}} \left( \hat{\mu}^h_i(t) + c(h, \delta_t) \right)$$
   où $\hat{\mu}^h_i$ est la moyenne des $h$ dernières observations et $c(h, \delta_t)$ est le terme de confiance.
3. Logique sous-jacente : Dans un contexte de décroissance, les index calculés sur des fenêtres plus anciennes sont des bornes supérieures conservatrices de la valeur future. En prenant le minimum de ces bornes, l'algorithme s'adapte automatiquement à la vitesse de décroissance sans avoir besoin de la connaître.

Complexité et Version Efficace

L'algorithme de base a une complexité $O(K \cdot t)$ par round. Les auteurs proposent également une version efficace, EFF-RAW-UCB, qui utilise une grille géométrique de fenêtres (paramètre $m$) pour réduire la complexité à $O(K \log_m t)$, rendant l'algorithme applicable à de grands horizons temporels.

3. Contributions Clés

1. Impossibilité du cas général décroissant : Les auteurs prouvent qu'il est impossible d'atteindre un regret sous-linéaire ($o(T)$) si l'on autorise simultanément des bras "rested" et "restless" avec des décroissances arbitraires. Cela justifie la nécessité de traiter les deux cas séparément ou de faire des hypothèses structurelles.
2. Un algorithme universel : RAW-UCB est le premier algorithme à atteindre des taux de regret minimax optimaux (à des facteurs poly-logarithmiques près) à la fois pour les bandits rotting "rested" et "restless", sans connaître :
   • Le type de décroissance (rested vs restless).
   • Le budget de variation ($V_T$) ou le nombre de changements ($\Upsilon_T$).
   • L'horizon temporel $T$.
3. Borneres dépendantes du problème : L'algorithme récupère également des bornes de regret en $O(\log T)$ dans les cas stationnaires ou par morceaux stationnaires, ce qui est un résultat fort car, dans le cas général non-stationnaire (sans hypothèse de décroissance), de telles bornes sont souvent incompatibles avec l'optimalité minimax.
4. Validation Expérimentale : Des expériences sur des données synthétiques et réelles (Yahoo! Front Page) montrent que RAW-UCB surpasse systématiquement les algorithmes de référence (FEWA, Exp3.S, GLR-UCB) dans les deux régimes.

4. Résultats Théoriques

Les auteurs établissent des bornes supérieures de regret pour RAW-UCB :

• Cas Restless (Budget de variation $V_T$) :
  Le regret est borné par $O((V_T K T^2 \log T)^{1/3})$, ce qui correspond au taux minimax connu pour les bandits non-stationnaires avec budget de variation, obtenu ici sans connaissance de $V_T$.
• Cas Restless (Stationnarité par morceaux $\Upsilon_T$) :
  Le regret est borné par $O(\sqrt{\Upsilon_T K T \log T})$, correspondant au taux minimax pour les bandits par morceaux.
• Cas Rested :
  Le regret est borné par $O(\sqrt{K T \log T} + K L)$, où $L$ est la borne de la décroissance. Cela correspond au taux minimax pour les bandits rotting rested.

Point crucial : L'hypothèse de décroissance (Assumption 1) est essentielle. Elle permet d'éviter les pièges où un bras "restless" pourrait augmenter sa valeur, rendant le problème intraitable. Sous cette hypothèse, RAW-UCB parvient à des performances optimales là où les algorithmes adversariaux classiques échouent ou sont trop conservateurs.

5. Résultats Expérimentaux

Les expériences ont été menées sur :

1. Données synthétiques : Pour valider les bornes théoriques sur différents niveaux de décroissance ($L$).
2. Données réelles (Yahoo! Front Page) : Un jeu de données de clics sur des articles de news.
   • Scénario : Les auteurs ont identifié une tendance naturelle de décroissance des clics le soir (les utilisateurs lisent moins).
   • Comparaison : RAW-UCB a été comparé à FEWA (l'algorithme précédent pour le cas rested), Exp3.S (adversarial) et GLR-UCB (détection de changement).
   • Résultats :
     • RAW-UCB surpasse FEWA de manière constante, avec un regret plus faible et une variance réduite.
     • Contrairement à FEWA, RAW-UCB fonctionne bien dans le régime "restless" (Yahoo! est un bon proxy pour le restless car les articles vieillissent même sans être cliqués).
     • Exp3.S et GLR-UCB montrent des performances inférieures ou nécessitent un réglage complexe (connaissance de $T$).
     • RAW-UCB est également plus rapide à exécuter que FEWA grâce à sa simplicité structurelle.

6. Signification et Impact

Ce travail est significatif car il unifie deux sous-domaines des bandits non-stationnaires qui étaient auparavant traités par des algorithmes distincts et souvent incompatibles.

• Simplicité et Efficacité : Il démontre qu'une approche basée sur l'UCB adaptatif, sans mécanismes complexes de détection de changements ou d'exploration active, suffit à atteindre l'optimalité théorique dans des environnements dégradants.
• Robustesse : L'algorithme est "agnostique" : il fonctionne bien sans paramétrage fin préalable, ce qui est crucial pour les applications réelles où les paramètres de décroissance sont inconnus.
• Limites théoriques clarifiées : En prouvant l'impossibilité de résoudre le cas mixte (rested + restless sans hypothèse de décroissance stricte), l'article pose des limites claires sur ce qui est apprenable, tout en montrant que l'hypothèse de décroissance est une condition suffisante pour l'efficacité.

En résumé, RAW-UCB représente une avancée majeure pour la conception de systèmes de recommandation et d'apprentissage séquentiel dans des environnements dynamiques où la valeur des options s'effrite avec le temps.