Sur la complexité de l'identification du meilleur bras dans les modèles de bandits à plusieurs bras.

Résumé Le modèle de bandit stochastique à plusieurs bras est une abstraction simple qui s'est avérée utile dans de nombreux contextes différents en statistique et en apprentissage automatique. Alors que la limite réalisable en termes de minimisation du regret est maintenant bien connue, notre objectif est de contribuer à une meilleure compréhension de la performance en termes d'identification des m meilleurs bras. Nous introduisons des notions génériques de complexité pour les deux cadres dominants considérés dans la littérature : les cadres à budget fixe et à confiance fixe. Dans le cadre de la confiance fixe, nous fournissons la première limite inférieure connue de la complexité en fonction de la distribution qui implique des quantités théoriques de l'information et qui tient lorsque m est supérieur à 1 sous des hypothèses générales. Dans le cas spécifique de deux bandits armés, nous dérivons des limites inférieures raffinées à la fois dans le cadre de la confiance fixe et du budget fixe, ainsi que des algorithmes de correspondance pour les modèles de bandits gaussiens et de Bernoulli. Ces résultats montrent en particulier que la complexité du cadre à budget fixe peut être plus petite que la complexité du cadre à confiance fixe, ce qui contredit le comportement familier observé lors du test d'alternatives entièrement spécifiées. En outre, nous fournissons également des règles d'arrêt séquentielles améliorées qui ont des probabilités d'erreur garanties et des temps d'exécution moyens plus courts. Les preuves reposent sur deux résultats techniques qui présentent un intérêt indépendant : un lemme de déviation pour les sommes auto-normalisées (Lemma 19) et une nouvelle inégalité de changement de mesure pour les modèles de bandits (Lemma 1).