On Explore-Then-Commit Strategies.

Résumé Nous étudions le problème de la minimisation du regret dans des problèmes de bandit à deux bras avec des récompenses gaussiennes. Notre objectif est d'utiliser ce cadre simple pour illustrer que les stratégies basées sur une phase d'exploration (jusqu'à un temps d'arrêt) suivie d'une exploitation sont nécessairement sous-optimales. Les résultats sont valables que l'on connaisse ou non la différence de moyenne entre les deux bras. Outre le message principal, nous raffinons également les inégalités de déviation existantes, ce qui nous permet de concevoir des stratégies entièrement séquentielles avec des garanties de regret en temps fini qui sont (a) asymptotiquement optimales à mesure que l'horizon croît et (b) optimales par ordre dans le sens minimax. En outre, nous fournissons des preuves empiriques que la théorie est également valable en pratique et nous discutons des extensions au cas non gaussien et à celui des armes multiples.