Titre :

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

Auteur(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]

Titre de la revue :

Sequential Analysis

Pagination :

61-96

Éditeur :

Taylor & Francis

Date de publication :

2021-03

ISSN :

0747-4946

Mot(s)-clé(s) en anglais :

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

Discipline(s) HAL :

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

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Projet ANR :

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