Ce que les astuces de doublage peuvent et ne peuvent pas faire pour les bandits à plusieurs bras.

Résumé Un algorithme d'apprentissage par renforcement en ligne est dit "anytime" s'il n'a pas besoin de connaître à l'avance l'horizon T de l'expérience. Une technique bien connue pour obtenir un algorithme anytime à partir de n'importe quel algorithme non-anytime est le "Doubling Trick". Dans le contexte des bandits à bras multiples adversaires ou stochastiques, la performance d'un algorithme est mesurée par son regret, et nous étudions deux familles de séquences d'horizons croissants (géométrique et exponentielle) pour généraliser des résultats précédemment connus selon lesquels certaines astuces de doublement peuvent être utilisées pour conserver certaines limites de regret. Dans un cadre général, nous prouvons qu'une astuce de doublement géométrique peut être utilisée pour conserver les limites (minimax) dans $R_T = O(\sqrt{T})$ mais ne peut pas conserver les limites (dépendantes de la distribution) dans $R_T = O(\log T)$. Nous expliquons pourquoi les astuces de doublement exponentiel peuvent être meilleures, car elles conservent les bornes dans $R_T = O(\log T)$, et sont proches de la conservation des bornes dans $R_T = O(\sqrt{T})$.