Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models. Issue 1 (15th January 2021)

• Record Type: Journal Article
• Authors: Garivier, Aurélien; Kaufmann, Emilie
• Is Part Of: Sequential analysis. Volume 40:Issue 1(2021)
• Page Start: 61
• Page End: 96
• Publication Date: 2021-01-15
• Subjects: Best arm identification -- generalized likelihood ratio test -- multi-armed bandits -- sequential testing; 62L10; Sequential analysis -- Periodicals; 519.54
• DOI: 10.1080/07474946.2021.1847965
• Languages: English
• ISSNs: 0747-4946

Abstract

Abstract: In this article, 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 smaller or larger than a fixed ϵ > 0 ; if μ ∈ ( − ϵ, ϵ ), both answers are considered to be correct. Then, we consider probably approximately correct 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 nonasymptotic bounds on the error of a parallel general likelihood ratio test, which can also be used for more general testing problems. We further propose a lower bound on the number of observations 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.