Offline-to-Online Learning in Linear Bandits

Résumé Technique : Apprentissage de l'Offline-to-Online dans les Bandits Linéaires

Énoncé du Problème
Cet article traite du problème de l'apprentissage de l'offline-to-online (de l'hors-ligne vers l'en-ligne) dans le cadre des bandits linéaires stochastiques. Le scénario implique un apprenant qui sélectionne séquentiellement des actions à partir d'un ensemble $\mathcal{A} \subset \mathbb{R}^d$ afin de maximiser les récompenses cumulées sur un horizon $n$, tout en ayant accès à un jeu de données hors-ligne préexistant $\mathcal{D}$. Les données hors-ligne sont collectées via un design fixe et non adaptatif (comptages d'actions déterministes) et suivent un modèle de récompense linéaire avec un bruit sous-gaussien.

Le défi central réside dans l'arbitrage entre deux objectifs concurrents :

1. Regret en ligne ($R_n$) : Minimiser le regret par rapport à l'action optimale $\mu^*$. Les algorithmes en ligne standards (par exemple, LinUCB) reposent sur l'optimisme pour explorer, atteignant un regret sous-linéaire mais pouvant souffrir d'un regret initial élevé si les données hors-ligne sont ignorées.
2. Regret hors-ligne ($R_n^{off}$) : Minimiser le regret par rapport à la récompense moyenne du jeu de données hors-ligne ($\mu_{off}$). Les algorithmes hors-ligne standards (par exemple, LinLCB) reposent sur le pessimisme pour exploiter les données connues, garantissant une performance proche de $\mu_{off}$, mais échouent à explorer, ce qui conduit à un regret linéaire si les données hors-ligne sont sous-optimales ou si l'horizon est long.

Les travaux existants ont largement traité ces régimes séparément ou se sont concentrés sur les bandits multi-bras (MAB) où le regret dépend du nombre d'actions. Cet article cherche à combler le fossé dans les environnements structurés (linéaires), où le regret devrait dépendre de la dimension $d$ plutôt que de la taille de l'espace d'actions.

Méthodologie : L'Algorithme LinOtO
Les auteurs proposent LinOtO (Linear Offline-to-Online), un algorithme qui équilibre dynamiquement l'exploration et l'exploitation en gérant un budget d'exploration. L'algorithme fonctionne en basculant entre deux stratégies basées sur un ensemble de confiance $C_t$ construit à partir des données hors-ligne et en ligne :

1. Ensembles de Confiance : L'algorithme maintient un estimateur des moindres carrés $\hat{\theta}_t$ et un ellipsoïde de confiance $C_t$ autour du paramètre réel $\theta^*$. Le rayon de cet ensemble incorpore l'incertitude provenant à la fois des données hors-ligne ($\beta_{off}$) et des interactions en ligne ($\beta_t$).
2. Actions Optimistes vs Pessimistes :
   • Action UCB ($U_t$) : L'action maximisant la borne supérieure de confiance (Upper Confidence Bound) au sein de $C_t$. Cela favorise l'exploration et réduit $R_n$, mais risque d'augmenter $R_n^{off}$.
   • Action LCB ($L_t$) : L'action maximisant la borne inférieure de confiance (Lower Confidence Bound) (spécifiquement, le maximum des bornes de confiance minimales au fil du temps). Cela favorise l'exploitation des données hors-ligne, réduisant $R_n^{off}$, mais peut augmenter $R_n$.
3. Mécanisme de Budget :
   • L'algorithme définit une récompense de base sûre $r_b$, dérivée d'une borne inférieure sur la récompense d'une action spécifique "sûre" $L_{off}$ (l'action LCB calculée uniquement à partir des données hors-ligne). La Proposition 2 garantit que $L_{off}$ est proche de $\mu_{off}$ avec une haute probabilité.
   • Un budget d'exploration $B(t)$ est maintenu, représentant l'excédent de récompense cumulée de l'algorithme par rapport à la base $r_b$.
   • Règle de Décision : Si $B(t) > 0$, l'algorithme sélectionne l'action optimiste $U_t$ (exploration). Si $B(t) \le 0$, il sélectionne l'action pessimiste $L_t$ (exploitation) pour accumuler du budget.
   • Ce mécanisme garantit que l'algorithme n'explore que lorsqu'il a "mérité" de le faire en restant sûr par rapport à la référence hors-ligne.

Contributions Clés

1. Conception d'Algorithme : L'article présente LinOtO, le premier algorithme spécifiquement conçu pour le cadre des bandits linéaires offline-to-online qui équilibre simultanément les stratégies UCB et LCB via un mécanisme de commutation basé sur un budget.
2. Garanties Théoriques : Les auteurs établissent des bornes de regret à haute probabilité pour les deux mesures :
   • Regret en ligne ($R_n$) : Le Théorème 1 montre que LinOtO atteint un regret sous-linéaire par rapport à l'action optimale. La borne consiste en un terme dépendant de l'horizon $n$ (similaire à LinUCB) et une constante additive dépendant de la qualité des données hors-ligne. Si les données hors-ligne couvrent bien l'espace, la borne s'améliore.
   • Regret hors-ligne ($R_n^{off}$) : Le Théorème 2 démontre que le regret par rapport à la référence hors-ligne croît linéairement avec $n$ mais diminue en $O(1/\sqrt{m})$ avec le nombre d'échantillons hors-ligne $m$. Cela correspond à la performance d'une solution purement hors-ligne (pessimiste).
3. Analyse du Compromis de Pareto : L'analyse révèle un compromis ajustable contrôlé par un paramètre $\alpha$. Augmenter $\alpha$ favorise la performance en ligne (plus proche de LinUCB), tandis que diminuer $\alpha$ favorise la performance hors-ligne (plus proche de LinLCB).

Résultats Expérimentaux
Les évaluations empiriques sur des tâches de bandits linéaires synthétiques (dimension $d=20$, $|A|=100$) démontrent :

• Sensibilité à l'Horizon : Pour des horizons courts, LinOtO suit la base conservatrice de LinLCB. Pour des horizons longs, il transite vers l'exploration, atteignant un regret sous-linéaire comparable à LinUCB.
• Qualité des Données Hors-ligne :
  • Lorsque le jeu de données hors-ligne exclut l'action optimale, LinOtO parvient à s'écarter du préalable hors-ligne sous-optimal pour explorer, finissant par surpasser LinLCB (qui souffre d'un regret linéaire) et approchant la performance de LinUCB à mesure que la taille des données hors-ligne $m$ augmente.
  • Lorsque le jeu de données hors-ligne inclut l'action optimale, LinOtO converge rapidement, performant de manière comparable à LinUCB et LinLCB.
• Robustesse : L'algorithme se situe systématiquement entre les extrêmes de l'exploration pure (LinUCB) et de l'exploitation pure (LinLCB), s'adaptant aux paramètres du problème.

Signification et Revendications
L'article affirme que LinOtO résout efficacement le compromis "mal compris" de l'offline-to-online dans les environnements structurés. Contrairement aux travaux antérieurs dans le cadre des MAB (par exemple, Sentenac et al., 2025), cette approche exploite la structure linéaire pour garantir que le regret dépend de la dimension $d$ plutôt que du nombre d'actions, ce qui la rend scalable pour les problèmes de haute dimension.

Les auteurs notent modestement que leur cadre suppose actuellement des données hors-ligne à design fixe et ne tient pas compte des changements de distribution entre les données hors-ligne et en ligne ou des politiques de journalisation adaptatives. Ils identifient l'extension de ces limites, ainsi que l'extension du cadre aux contextes non linéaires, comme des directions importantes pour la recherche future. Ce travail contribue à la littérature plus large sur l'utilisation des connaissances préal ($\textit{hints}$, données hors-ligne) pour guider les compromis exploration-exploitation dans l'apprentissage en ligne.