Parameter-Free Heavy-Tailed Bandits

Résumé Technique : Bandits à queue lourde sans paramètres

Énoncé du Problème

L'article traite du problème des bandits multi-bras stochastiques (MAB) sous des distributions de récompenses à queue lourde. Dans ce cadre, les récompenses $X$ satisfont une condition de moment fini $\mathbb{E}[|X|^{1+\epsilon}] \leq u$ pour un exposant de queue $\epsilon \in (0, 1]$ et une borne de moment $u < +\infty$. Bien que des estimateurs robustes puissent atteindre des taux de regret optimaux lorsque $\epsilon$ et $u$ sont connus, les applications réelles (par exemple, la finance, la publicité) manquent souvent d'estimations fiables de ces paramètres.

Le problème central, posé comme une question ouverte par Genalti et Metelli (COLT 2025), est de déterminer les meilleurs garanties de regret possibles pour des algorithmes qui sont sans hypothèse concernant $u$ et $\epsilon$. Plus précisément, l'article étudie :

1. Les compromis fondamentaux entre le regret indépendant de la distribution (pire cas) et le regret dépendant de la distribution (spécifique à l'instance) lorsque $u$ est inconnu.
2. Le coût supplémentaire encouru lorsque $\epsilon$ est également inconnu.
3. Si un algorithme unique peut atteindre un regret sous-linéaire uniformément pour tout $\epsilon \in (0, 1]$.

Méthodologie

Les auteurs emploient une approche analytique en deux étapes :

1. Adaptativité à $u$ ( $\epsilon$ fixé) : Ils analysent d'abord le scénario où $\epsilon$ est connu mais $u$ est inconnu. Ils définissent deux taux de regret :

   • $\Phi_{free}(K, T)$ : une borne de regret sans distribution (distribution-free) liée au moment.
   • $\Phi_{dep}(K, T)$ : un regret dépendant de l'instance normalisé par la somme des écarts (gap-sum-normalized).
     En utilisant un argument de changement de mesure combiné à des constructions d'instances spécifiques, ils dérivent une borne inférieure sur le produit de ces taux, établissant une « frontière » de performance réalisable.

2. Conception d'Algorithme (AdaR-ETC) : Pour égaler les bornes inférieures dérivées, les auteurs proposent l'Adaptive Robust ETC (AdaR-ETC). Il s'agit d'une stratégie Explore-Then-Commit utilisant :

   • Estimateur de la Médiane des Moyennes (MoM) : Pour estimer robustement les moyennes des bras sans nécessiter la connaissance de $u$ ou $\epsilon$.
   • Exploration Programmée : Le budget d'exploration $L_T$ est ajusté via les paramètres $\alpha$ (contrôlant la dépendance à l'horizon) et $q$ (contrôlant la dépendance aux bras). Dans le cadre d'adaptativité à $u$ (où $\epsilon$ est connu), ces paramètres sont explicitement définis en fonction de $\epsilon$. Cependant, l'algorithme peut devenir entièrement sans paramètre (ignorant à la fois $u$ et $\epsilon$) en calibrant le programme d'exploration sur le point final de variance finie $\epsilon = 1$.

3. Adaptativité $(\epsilon, u)$ ( $\epsilon$ inconnu) : Les auteurs étendent l'analyse au cas où les deux paramètres sont inconnus. Ils calibrent l'algorithme AdaR-ETC sur le point final de variance finie $\epsilon = 1$ (en fixant $q=1/3$ et $\alpha=2/3$) pour créer une stratégie unique et sans paramètre. Ils prouvent ensuite une borne inférieure par paire pour montrer que cette calibration produit un profil optimal parmi les stratégies qui conservent la garantie optimale à $\epsilon=1$.

Contributions Clés et Résultats

1. La Frontière de Compromis pour $u$ Inconnu
L'article prouve que pour toute stratégie ignorant $u$, il existe un compromis net entre les garanties indépendantes de la distribution et les garanties dépendantes de la distribution. Spécifiquement, pour un $\epsilon$ fixé :
$$\Phi_{dep}(K, T) \cdot \Phi_{free}(K, T)^{\frac{1+\epsilon}{\epsilon}} = \Omega\left(T^{\frac{1+\epsilon}{\epsilon}}\right)$$
Cela implique que l'amélioration du taux dans le pire cas (indépendant de la distribution) dégrade nécessairement le taux dépendant de l'instance. Les auteurs caractérisent la « frontière-K » et la « frontière-T », montrant qu'aucun algorithme unique ne peut optimiser simultanément les deux.

2. L'Algorithme AdaR-ETC
L'algorithme AdaR-ETC proposé atteint des bornes de regret qui correspondent à la frontière théorique à des facteurs logarithmiques près. En ajustant les paramètres $\alpha$ et $q$, l'algorithme peut sélectionner n'importe quel point de fonctionnement sur la frontière de compromis.

• Borne indépendante de la distribution : $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+\epsilon}(1-q)} T^{\alpha}\right)$
• Borne dépendante de la distribution : $\tilde{O}\left(K^{q-1} T^{\beta_\alpha}\right)$
  où $\beta_\alpha = (1-\alpha)(1+\epsilon)/\epsilon$.
  Le point « équilibré » (dépendance égale vis-à-vis de $K$ et $T$) produit un taux de $\tilde{O}\left(u^{\frac{1}{1+\epsilon}} K^{\frac{\epsilon}{1+2\epsilon}} T^{\frac{1+\epsilon}{1+2\epsilon}}\right)$. Pour le cas de la variance finie ($\epsilon=1$), cela donne un taux de $\tilde{O}(T^{2/3})$, ce qui est strictement inférieur au taux de $\tilde{O}(\sqrt{T})$ atteignable lorsque $u$ est connu, quantifiant ainsi le « prix de l'adaptativité ».

3. Limites de l'Adaptativité Simultanée $(\epsilon, u)$
Lorsque $\epsilon$ est également inconnu, les auteurs proposent de calibrer AdaR-ETC sur $\epsilon=1$.

• Sous-linéarité Ponctuelle : Pour tout $\epsilon > 0$ fixé, l'algorithme calibré atteint un regret sous-linéaire.
• Impossibilité de l'Uniformité : L'article prouve qu'aucune stratégie unique ne peut garantir un regret sous-linéaire uniformément sur tout $\epsilon \in (0, 1]$. À mesure que $\epsilon \to 0$, l'exposant de $T$ tend vers 1, ce qui signifie que le regret devient linéaire.
• Optimalité de la Calibration : Parmi les stratégies qui maintiennent la garantie $\tilde{O}(K^{1/3}T^{2/3})$ à $\epsilon=1$, l'algorithme AdaR-ETC calibré pour $\epsilon=1$ est montré comme étant optimal au sens de la frontière pour tous les autres $\epsilon$.

Signification et Revendications

L'article affirme résoudre le problème ouvert de COLT 2025 concernant les bandits à queue lourde sans hypothèse. Sa principale signification réside dans :

• Caractérisation du Coût Statistique : Il fournit une caractérisation précise du coût statistique de l'adaptation à des queues lourdes inconnues, démontrant que l'adaptation à une échelle inconnue ($u$) et un ordre inconnu ($\epsilon$) introduit des compromis fondamentaux plutôt que de simples facteurs constants.
• Frontière vs Oracle : Il établit qu'il n'existe pas de « courbe oracle » qui soit optimale pour tous les ordres de moments ; l'adaptation est plutôt décrite par une frontière.
• Solution Algorithmique : Il fournit un algorithme simple et sans paramètre (AdaR-ETC) qui atteint ces compromis optimaux sans nécessiter de connaissance préalable des propriétés de la queue de la distribution.

Les auteurs déclarent explicitement que leurs résultats ne récupèrent pas les taux oracle sans hypothèses structurelles supplémentaires, confirmant que le « prix de l'adaptativité » est inhérent au cadre des queues lourdes. Ils identifient les limites du regret sous-linéaire uniforme et suggèrent que les travaux futurs devraient se concentrer sur la conception de versions « anytime » de l'algorithme et sur l'identification des hypothèses supplémentaires les plus faibles requises pour récupérer les taux oracle.