Exploration adaptative dans le bandit linéaire contextuel

Résumé

Les bandits contextuels servent de modèle fondamental pour de nombreuses tâches de prise de décision séquentielle. Les approches théoriquement justifiées les plus populaires sont basées sur le principe d'optimisme. Bien que ces algorithmes puissent être pratiques, ils sont connus pour être asymptotiquement sous-optimaux. D'autre part, les algorithmes asymptotiquement optimaux existants pour ce problème n'exploitent pas la structure linéaire de manière optimale et souffrent de termes d'ordre inférieur qui dominent le regret dans tous les régimes pratiquement intéressants. Nous commençons à combler cette lacune en concevant un algorithme qui est asymptotiquement optimal et qui présente de bonnes performances empiriques en temps fini. En même temps, nous établissons des liens avec la littérature récente sur les cas où les méthodes sans exploration sont efficaces. En effet, si la distribution des contextes se comporte bien, alors notre algorithme agit surtout avec avidité et a un regret sub-logarithmique. De plus, notre approche est adaptative dans le sens où elle détecte automatiquement le cas agréable. Les résultats numériques démontrent des réductions significatives du regret par notre méthode par rapport à plusieurs lignes de base.