Garanties de confiance fixe pour l'identification bayésienne du meilleur bras.

Résumé Nous étudions et fournissons de nouvelles perspectives sur la règle d'échantillonnage appelée Top-Two Thompson Sampling (TTTS). En particulier, nous justifions son utilisation pour l'identification du meilleur bras à confiance fixe. Nous proposons également une variante du TTTS appelée Top-Two Transportation Cost (T3C), qui élimine la charge de calcul du TTTS. Comme contribution principale, nous fournissons la première analyse de complexité d'échantillon de TTTS et T3C lorsqu'ils sont couplés avec une règle d'arrêt bayésienne très naturelle, pour des bandits avec des récompenses gaussiennes, résolvant une des questions ouvertes soulevées par Russo (2016). Nous fournissons également de nouveaux résultats de convergence postérieure pour TTTS sous deux modèles couramment utilisés dans la pratique : bandits avec récompenses gaussiennes et Bernoulli et prieurs conjugués.