Title :

Non-Asymptotic Sequential Tests for Overlapping Hypotheses and application to near optimal arm identification in bandit models

Author(s) :

Garivier, Aurélien [Auteur]
Unité de Mathématiques Pures et Appliquées [UMPA-ENSL]
Modèles de calcul, Complexité, Combinatoire [MC2]
Kaufmann, Emilie [Auteur]
Scool [Scool]
Centre National de la Recherche Scientifique [CNRS]

Journal title :

Sequential Analysis

Pages :

61-96

Publisher :

Taylor & Francis

Publication date :

2021-03

ISSN :

0747-4946

English keyword(s) :

Sequential statistics
bandit models
tests
Best arm identification
Generalized Likelihood Ratio test
Multi-armed bandits
Sequential testing

HAL domain(s) :

Mathématiques [math]/Statistiques [math.ST]
Statistiques [stat]/Machine Learning [stat.ML]

English abstract : [en]

In this paper, we study sequential testing problems with overlapping hypotheses. We first focus on the simple problem of assessing if the mean µ of a Gaussian distribution is $≥ ε− or ≤ε; if µ ∈ (−ε,ε)$, both answers are ...
Show more >In this paper, we study sequential testing problems with overlapping hypotheses. We first focus on the simple problem of assessing if the mean µ of a Gaussian distribution is $≥ ε− or ≤ε; if µ ∈ (−ε,ε)$, both answers are considered to be correct. Then, we consider PAC-best arm identification in a bandit model: given K probability distributions on R with means $µ_1,. .. , µ_K$ , we derive the asymptotic complexity of identifying, with risk at most $δ$, an index $I ∈ {1,. .. , K}$ such that $µ_I ≥ max_i µ_i −ε$. We provide non asymptotic bounds on the error of a parallel General Likelihood Ratio Test, which can also be used for more general testing problems. We further propose lower bound on the number of observation needed to identify a correct hypothesis. Those lower bounds rely on information-theoretic arguments, and specifically on two versions of a change of measure lemma (a high-level form, and a low-level form) whose relative merits are discussed.Show less >

Language :

Anglais

Popular science :

Non

ANR Project :

BANDITS MANCHOTS POUR SIGNAUX NON-STATIONNAIRES ET STRUCTURES
IDEXLYON
Au delà de l'apprentissage séquentiel pour de meilleures prises de décisions

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL