An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

Résumé Technique : Un Algorithme Amélioré pour les Bandits Contextuels Linéaires Adversaires via une Réduction

Définition du Problème

L'article traite du problème des bandits contextuels linéaires adverses. Dans ce cadre, un adversaire de type « oblivious » (sans mémoire) sélectionne une séquence de vecteurs de perte cachés $\theta_t \in \mathbb{R}^d$ avant le début de l'interaction. À chaque tour $t$, un ensemble d'actions $A_t \subset \mathbb{R}^d$ est tiré de manière i.i.d. selon une distribution $\mathcal{D}$ fixe mais inconnue, et révélé à l'apprenant. L'apprenant doit sélectionner une action $a_t \in A_t$ et subit une perte $\ell_t$ dont l'espérance est $\mathbb{E}[\ell_t] = a_t^\top \theta_t$. L'objectif est de minimiser le regret par rapport à la meilleure politique fixe $\pi$, où une politique associe tout ensemble d'actions observé $A$ à un point de son enveloppe convexe $\text{conv}(A)$.

Ce cadre généralise les bandits linéaires classiques en permettant aux ensembles d'actions (contextes) de varier de manière stochastique au fil du temps, tandis que les pertes restent adverses. Un défi critique est que la distribution $\mathcal{D}$ est inconnue, et l'apprenant n'a pas accès à un simulateur capable de générer des échantillons gratuits de $\mathcal{D}$. De plus, le nombre d'actions possibles $K$ peut être exponentiellement grand par rapport à la dimension $d$ (par exemple, dans des problèmes combinatoires comme le plus court chemin), rendant les algorithmes dont la complexité est polynomiale en $K$ infaisables.

Méthodologie

La contribution centrale est une réduction efficace sur le plan computationnel qui transforme le problème du bandit contextuel linéaire adverse en un problème de bandit linéaire adverse robuste à la spécification erronée avec un ensemble d'actions fixe.

1. Réduction aux Ensembles d'Actions Fixes :
   Les auteurs définissent une application $\Psi(\pi) = \mathbb{E}_{A \sim \mathcal{D}}[\pi(A)]$, qui associe une politique $\pi$ à son action moyenne. Puisque $\mathcal{D}$ est inconnue, l'ensemble réel des actions moyennes $\Omega = \{\Psi(\pi) \mid \pi \in \Pi\}$ ne peut pas être accédé directement. Au lieu de cela, l'algorithme construit une approximation empirique $\hat{\Omega}$ en utilisant $N$ échantillons i.i.d. d'ensembles d'actions tirés de $\mathcal{D}$.

   • $\hat{\Omega}$ est défini comme la somme de Minkowski des enveloppes convexes des ensembles d'actions échantillonnés : $\hat{\Omega} = \frac{1}{N} \sum_{i=1}^N \text{conv}(A_i)$.
   • La réduction repose sur le fait que pour les politiques de classifieurs linéaires, la différence entre la perte espérée sur la distribution réelle et la distribution empirique est faible (convergence uniforme), à condition que $N$ soit suffisamment grand.

2. Gestion de l'Écart via la Robustesse à la Spécification Erronée :
   Parce que l'apprenant opère sur $\hat{\Omega}$ plutôt que sur $\Omega$, le retour d'information reçu par l'algorithme de bandit linéaire sous-jacent est « mal spécifié ». Plus précisément, la perte espérée observée par l'algorithme de bandit linéaire diffère de la véritable perte espérée par un terme d'erreur borné $\epsilon$.

   • Les auteurs utilisent un algorithme de bandit linéaire adverse $\alpha$-robuste à la spécification erronée comme une boîte noire. Cet algorithme garantit un regret faible même lorsque le retour d'information satisfait $|\mathbb{E}[c_t] - \langle y_t, \theta_t \rangle| \le \epsilon$.
   • Pour exécuter un point $y_t \in \hat{\Omega}$ suggéré par l'algorithme de bandit linéaire, l'apprenant utilise une décomposition basée sur Frank-Wolfe (Algorithme 2) pour exprimer $y_t$ comme une combinaison convexe de points sur la frontière de $\hat{\Omega}$. Ces points de frontière correspondent à des politiques de classifieurs linéaires $\pi_\phi$, qui peuvent être exécutées à l'aide d'un oracle d'optimisation linéaire pour les ensembles d'actions individuels $A_t$.

3. Composants Algorithmiques :

   • Algorithme 1 : Le cadre principal qui interagit avec l'environnement, décompose la suggestion du bandit linéaire en un mélange de politiques linéaires, et renvoie la perte résultante à l'algorithme de bandit linéaire.
   • Algorithme 3 (Continuous Exponential Weights Robuste à la Spécification Erronée) : Une instanciation spécifique de l'algorithme de bandit linéaire robuste. Il adapte la méthode des poids exponentiels continus tronqués (Ito et al., 2020) en ajoutant un « terme de bonus » $b_t$ à l'estimateur de perte. Ce bonus encourage l'exploration et compense le surcoût de regret causé par la spécification erronée.
   • Truc de Doublement (Doubling Trick) : Pour gérer la taille d'échantillon optimale $N$ inconnue, l'algorithme utilise un truc de doublement, redémarrant le processus aux époques $2, 4, 8, \dots$ et utilisant tous les échantillons de contexte accumulés pour affiner $\hat{\Omega}$.

Contributions Clés

• Algorithme Efficace par Oracle : L'article présente le premier algorithme pour les bandits contextuels linéaires adverses avec des ensembles d'actions stochastiques qui atteint des bornes de regret indépendantes du nombre d'actions $K$ dans sa complexité computationnelle. Il nécessite uniquement un oracle d'optimisation linéaire pour les ensembles d'actions individuels à chaque tour.
• Applicabilité Combinatoire : La méthode est la première à atteindre un regret de $\text{poly}(d)\sqrt{T}$ en temps polynomial pour les bandits combinatoires avec des ensembles d'actions stochastiques et des pertes adverses. Les algorithmes précédents nécessitaient soit un retour d'information de type semi-bandit, soit avaient une complexité computationnelle croissant polynomialement avec $K$ (ce qui est exponentiel en $d$ pour de nombreux problèmes).
• Nouvelle Réduction : Le travail établit une réduction en temps polynomial d'un bandit contextuel linéaire adverse vers des bandits linéaires robustes à la spécification erronée. Contrairement aux réductions précédentes (ex. Hanna et al., 2023) qui se concentraient sur des contextes stochastiques ou manquaient d'implémentations en temps polynomial, cette réduction opère sous des pertes adverses et est efficace sur le plan computationnel.

Résultats

L'algorithme atteint les bornes de regret suivantes (en ignorant les facteurs logarithmiques) :

• Sans Simulateur : $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3 T \log K}\})$.
  • Cela résout une question ouverte de Liu et al. (2023) concernant la possibilité d'atteindre un regret de $\text{poly}(d)\sqrt{T}$ en temps polynomial indépendamment de $K$.
  • La complexité computationnelle est de $\text{poly}(d, T)$ plus $\text{poly}(d, T)$ appels à l'oracle d'optimisation linéaire.
• Avec Simulateur : Si l'apprenant a accès à un simulateur capable de générer des contextes gratuits, la borne de regret s'améliore pour devenir $\tilde{O}(d\sqrt{L^*})$, où $L^*$ est la perte cumulée de la meilleure politique. Il s'agit d'une borne de premier ordre qui s'adapte à la difficulté de l'instance du problème.

Signification et Revendications

Les auteurs affirment que ce travail fournit un cadre général qui élargit considérablement l'applicabilité des bandits contextuels linéaires adverses à des problèmes ayant des espaces d'actions exponentiellement grands (ex. : plus court chemin, flux, appariement bipartite) sans nécessiter la connaissance de la distribution du contexte ou d'un simulateur.

L'article note explicitement que, bien que la borne $\tilde{O}(d^2\sqrt{T})$ soit une amélioration par rapport aux résultats précédents en temps polynomial dépendant de $K$, il reste une question ouverte de savoir si la borne quasi-optimale $\tilde{O}(d\sqrt{T})$ peut être atteinte sans simulateur en temps polynomial. Les auteurs soulignent également que leur approche élimine l'hypothèse irréaliste de distributions de contextes log-concaves requise par certains travaux antérieurs (Olkhovskaya et al., 2023) lorsqu'ils sont spécialisés à certaines formulations. Enfin, ils suggèrent que le cadre de réduction peut être applicable à d'autres contextes, tels que les MDP linéaires avec des transitions fixes et des pertes adverses.