Title :

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

Author(s) :

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

Scool [Scool]

Journal title :

Sequential Analysis

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

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL