• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Non-Asymptotic Sequential Tests for ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Article dans une revue scientifique
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] refId

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
Files
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-02123833v2/document
  • Open access
  • Access the document
Thumbnail
  • http://arxiv.org/pdf/1905.03495
  • Open access
  • Access the document
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-02123833v2/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-02123833v2/document
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017