Complexité de l'information dans la sélection de sous-ensembles de Bandit.

Nous considérons le problème de l'exploration efficace des bras d'un bandit stochastique pour identifier le meilleur sous-ensemble d'une taille spécifiée. Sous les formulations PAC et à budget fixe, nous dérivons des bornes améliorées en utilisant des intervalles de confiance basés sur la divergence KL. Alors que l'application d'une idée similaire dans le cadre du regret a donné des limites en termes de divergence KL entre les bras, nos limites dans le cadre de l'exploration pure impliquent l'"information de Chernoff" entre les bras. En plus d'introduire cette nouvelle quantité dans la littérature sur les bandits, nous contribuons à une comparaison entre les stratégies basées sur l'échantillonnage uniforme et adaptatif pour les problèmes d'exploration pure, trouvant des preuves en faveur de la seconde.