Sous-échantillonnage pour l'exploration non paramétrique efficace de bandits.

Résumé Dans cet article, nous proposons le premier algorithme de bandit à bras multiples basé sur le rééchantillonnage qui atteint un regret asymptotiquement optimal simultanément pour différentes familles de bras (à savoir les distributions de Bernoulli, Gaussienne et Poisson). Contrairement à l'échantillonnage de Thompson qui nécessite de spécifier un antécédent différent pour être optimal dans chaque cas, notre proposition RB-SDA ne nécessite aucun réglage dépendant de la distribution. RB-SDA appartient à la famille des algorithmes de duel par sous-échantillonnage (SDA) qui combine l'idée de sous-échantillonnage utilisée pour la première fois par les algorithmes BESA [1] et SSMC [2] avec différents schémas de sous-échantillonnage. En particulier, RB-SDA utilise l'échantillonnage par blocs aléatoires. Nous réalisons une étude expérimentale pour évaluer la flexibilité et la robustesse de cette nouvelle approche prometteuse pour l'exploration dans les modèles de bandits.