Sur la complexité de l'identification du meilleur bras sous contrainte de risque dans un modèle de bandits

Nous considérons un modèle d'optimisation discrète où, à chaque instant, le choix d'une option donne accès à une observation bruitée de la valeur associée. Nous donnons une estimation précise du nombre de tirages nécessaires pour identifier avec un risque $\delta$ donné l'option ayant la plus grande valeur moyenne associée : nous donnons une borne inférieure précise (qui implique elle-même un problème d'optimisation), et nous décrivons un algorithme (appelé "Track-and-Stop") qui atteint asymptotiquement cette borne inférieure quand le risque $\delta$ tend vers $0$.