Tests séquentiels non asymptotiques pour les hypothèses de chevauchement et application à l'identification quasi optimale du bras dans les modèles de bandits.

Résumé Dans cet article, nous étudions les problèmes de tests séquentiels avec des hypothèses qui se chevauchent. Nous nous concentrons d'abord sur le problème simple consistant à évaluer si la moyenne µ d'une distribution gaussienne est $≥ ε- ou ≤ε. Si µ ∈ (-ε,ε)$, les deux réponses sont considérées comme correctes. Ensuite, nous considérons l'identification du meilleur bras PAC dans un modèle de bandit : étant donné K distributions de probabilité sur R avec des moyennes $µ_1,.... , µ_K$ , nous dérivons la complexité asymptotique de l'identification, avec un risque au plus égal à $δ$, d'un indice $I ∈ {1, . , K}$ tel que $µ_I ≥ max_i µ_i -ε$. Nous fournissons des bornes non asymptotiques sur l'erreur d'un test de rapport de vraisemblance général parallèle, qui peut également être utilisé pour des problèmes de test plus généraux. Nous proposons également des bornes inférieures sur le nombre d'observations nécessaires pour identifier une hypothèse correcte. Ces limites inférieures reposent sur des arguments de la théorie de l'information, et plus particulièrement sur deux versions d'un lemme de changement de mesure (une forme de haut niveau et une forme de bas niveau) dont les mérites relatifs sont discutés.