Résumé technique : Algorithmes basés sur la moyenne : une borne inférieure et un regret

Énoncé du problème

L'article étudie les algorithmes basés sur la moyenne dans le contexte de l'apprentissage en ligne, en se concentrant spécifiquement sur le cadre des bandits multi-bras (MAB) avec un retour de type bandit et un horizon temporel inconnu.

Les algorithmes basés sur la moyenne sont définis par le principe selon lequel un agent doit sélectionner des actions ayant de faibles récompenses moyennes passées avec une faible probabilité dans le futur. Bien que la littérature récente suggère que ces algorithmes convergent favorablement vers des actions sériellement non dominées (approximant les équilibres de Nash dans les jeux économiques), des études empiriques indiquent qu'ils souffrent d'une convergence plus lente par rapport aux algorithmes établis dans les scénarios à retour de type bandit. De plus, il existe une tension entre l'« exploitabilité » de ces algorithmes dans les jeux principal-agent et leurs garanties de convergence théoriques.

Les défis spécifiques abordés sont :

1. Définir les algorithmes basés sur la moyenne pour le cadre à horizon inconnu (où le nombre total de tours $T$ n'est pas connu à l'avance).
2. Déterminer les limites théoriques de la séquence de taux de l'algorithme, $\gamma_t$, qui contrôle le seuil pour éviter les actions « dominées ».
3. Clarifier la relation entre les algorithmes basés sur la moyenne et les algorithmes à pas de regret externe (no-external-regret), notamment si un algorithme peut posséder les deux propriétés simultanément sous un retour de type bandit.

Méthodologie

1. Définitions et préliminaires

Les auteurs formalisent deux définitions d'algorithmes basés sur la moyenne :

• $\gamma_t$-basé sur la moyenne : Basé sur les récompenses moyennes actuelles $\alpha_t(a)$. Si $\alpha_t(a') - \alpha_t(a) > \gamma_t$, la probabilité de choisir $a$ à $t+1$ est au plus $\gamma_t$.
• Prédictif $\gamma_t$-basé sur la moyenne : Basé sur les récompenses moyennes de l'étape suivante $\alpha_{t+1}$.

L'article étabffiche que ces définitions sont mutuellement convertibles et se concentre sur la variante non prédictive pour le cadre bandit.

2. Algorithmes proposés

Les auteurs proposent deux algorithmes adaptés au retour de type bandit et aux horizons inconnus :

• $\epsilon$-Greedy généralisé : Une variante où les actions sont considérées comme « dominées » si leur récompense cumulative estimée est significativement plus faible que celle des autres. L'algorithme assigne une faible probabilité $\epsilon_t$ aux actions dominées et distribue la probabilité restante parmi les actions non dominées.
• Exp3 basé sur la moyenne : Une variante de l'algorithme Exp3 (Exponential-weight algorithm for Exploration and Exploitation). Il utilise des poids multiplicatifs basés sur les récompenses cumulatives estimées, avec une composante d'exploration $\epsilon_t$ pour assurer un échantillonnage suffisant.

Les deux algorithmes utilisent des estimateurs pondérés par l'importance pour gérer l'absence de retour complet.

3. Dérivation de la borne inférieure théorique

Pour déterminer la limite fondamentale de la vitesse à laquelle ces algorithmes peuvent apprendre, les auteurs dérivent une borne inférieure sur la séquence de taux $\gamma_t$.

• Construction adversaire : Ils construisent deux environnements adverses spécifiques ($x'_t$ et $x''_t$) qui exploitent le dilemme exploration-exploitation. Dans ces environnements, un algorithme doit distinguer deux actions qui semblent initialement similaires mais divergent plus tard.
• Argument d'indistinguabilité : En raison du retour de type bandit, si l'algorithme joue une action spécifique trop rarement (pour satisfaire un petit $\gamma_t$), il ne peut pas distinguer les deux environnements.
• Dérivation de l'inégalité : En analysant la probabilité de sélectionner une action dominée dans ces environnements construits, ils dérivent une inégalité nécessaire : $\sum_{t=t_1}^{t_c-1} \gamma_t + k \cdot \gamma_{t_c} \geq 1$.
• Analyse asymptotique : Ils approchent cette somme par des intégrales pour montrer que toute séquence de taux décroissant plus vite que $O(1/\sqrt{t})$ (spécifiquement, toute séquence où $\gamma_t \in o(1/\sqrt{t})$) viole la condition requise pour qu'un algorithme soit basé sur la moyenne dans le cadre bandit.

4. Analyse du regret

Les auteurs analysent l'intersection des algorithmes basés sur la moyenne et des algorithmes à pas de regret externe. Ils démontrent que, bien que les algorithmes basés sur la moyenne ne garantissent pas automatiquement l'absence de regret (et peuvent souffrir d'un regret linéaire dans des configurations adverses spécifiques avec un $\gamma_t$ très petit), il existe des configurations (spécifiquement certaines paramétrisations d'Exp3) qui satisfont à la fois la propriété basée sur la moyenne et la propriété de pas de regret externe.

Principales contributions

1. Première borne inférieure sur $\gamma_t$ : L'article fournit la première borne inférieure formelle pour la séquence de taux $\gamma_t$ des algorithmes basés sur la moyenne dans le cadre de retour de type bandit. Il établit que $\gamma_t$ ne peut pas décroître plus vite que $O(1/\sqrt{t})$. Spécifiquement, toute séquence $\gamma_t \in o(1/\sqrt{t})$ est invalide pour les algorithmes basés sur la moyenne dans ce cadre.
2. Algorithmes à horizon inconnu : Les auteurs proposent deux algorithmes concrets basés sur la moyenne ( $\epsilon$-greedy généralisé et Exp3 basé sur la moyenne) qui fonctionnent efficacement sans connaissance préalable de l'horizon temporel $T$.
3. Réconciliation des définitions : Le travail clarifie la relation entre les définitions prédictives et non prédictives basées sur la moyenne, montrant leur convertibilité.
4. Chevauchement Regret-Basé sur la moyenne : L'article prouve que l'ensemble des algorithmes basés sur la moyenne et l'ensemble des algorithmes à pas de regret externe ne sont pas disjoints. Il construit une variante spécifique d'Exp3 qui est à la fois basée sur la moyenne et à pas de regret.
5. Validation empirique : Par des expériences numériques, les auteurs montrent que bien que les algorithmes basés sur la moyenne puissent converger légèrement plus lentement que leurs homologues standards, ils peuvent atteindre des performances compétitives tant dans les cadres de MAB stochastiques que dans les jeux économiques (oligopole de Bertrand).

Résultats

Résultats théoriques

• Borne inférieure : La séquence $\gamma_t = \frac{1}{2\sqrt{t}+1}$ est identifiée comme un seuil critique. Toute séquence décroissant strictement plus vite que celle-ci (par exemple, $\gamma_t = 1/t^{0.51}$ ou $\gamma_t = 1/t$) est prouvée comme étant invalide pour les algorithmes basés sur la moyenne sous retour de type bandit.
• Regret : L'article confirme que les algorithmes basés sur la moyenne ne sont pas intrinsèquement « exploitables » d'une manière qui exclut les garanties de pas de regret ; il existe des algorithmes qui sont à la fois basés sur la moyenne et à pas de regret.

Résultats empiriques

• MAB stochastique : Dans une expérience de bandit à 10 bras, l'Exp3 basé sur la moyenne (avec $\alpha=1/2$) a montré une convergence légèrement plus lente vers l'action optimale par rapport à une configuration Exp3 standard, mais la différence était marginale. Les variantes $\epsilon$-greedy ont montré des performances dépendantes du taux d'exploration.
• Oligopole de Bertrand : Dans un jeu de prix répété, l'algorithme Exp3 basé sur la moyenne a convergé vers l'équilibre de Nash de manière nettement plus rapide que ce qui avait été observé précédemment dans la littérature similaire (par exemple, Bichler et al., 2025). Les algorithmes $\epsilon$-greedy basés sur la moyenne étaient plus lents, ce qui est attribué à une exploration excessive lorsque le seuil de domination était élevé.

Signification et affirmations

L'article affirme fournir une limite fondamentale sur la performance des algorithmes basés sur la moyenne. La borne inférieure dérivée sur $\gamma_t$ explique pourquoi ces algorithmes apprennent souvent lentement : pour satisfaire la condition basée sur la moyenne (éviter les actions dominées) sans retour complet, l'algorithme doit maintenir un certain niveau d'exploration. Si le taux d'exploration chute trop rapidement (c'est-à-dire si $\gamma_t$ devient trop petit), l'algorithme ne peut pas distinguer les environnements et est contraint de jouer des actions dominées, violant ainsi la définition basée sur la moyenne.

Les auteurs positionnent leur travail comme une étape nécessaire pour réconcilier les préoccupations d'« exploitabilité » des jeux principal-agent avec les garanties de convergence en théorie des jeux. En montant que les propriétés basées sur la moyenne et de pas de regret peuvent coexister, ils suggèrent que les algorithmes basés sur la moyenne sont une alternative viable pour les scénarios d'apprentissage économique, à condition que le taux $\gamma_t$ soit choisi avec soin pour respecter la borne inférieure dérivée.

L'article conclut que, bien que les algorithmes basés sur la moyenne ne soient pas universellement plus rapides que les algorithmes standards à pas de regret, ils offrent une classe distincte de dynamiques d'apprentissage qui peuvent être compétitives, particulièrement dans les contextes où la convergence vers des stratégies sériellement non dominées est l'objectif principal. Le travail laisse ouverte la question de savoir si un algorithme peut être construit pour correspondre exactement à la borne inférieure théorique $\gamma_t \approx 1/\sqrt{t}$ tout en maintenant un regret optimal.