Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models

DOI10.1080/07474946.2021.1847965MaRDI QIDQ4987192zbMATH OpenOpenAlexFDO

Authors Emilie Kaufmann, Aurélien Garivier

Publication date 29 April 2021

Published in Sequential Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.03495

zbMATH Keywords

generalized likelihood ratio testmulti-armed banditssequential testingbest arm identification

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Sequential statistical analysis (62L10)

Abstract: In this paper, we study sequential testing problems with emph{overlapping} hypotheses. We first focus on the simple problem of assessing if the mean $mu$ of a Gaussian distribution is smaller or larger than a fixed $epsilon>0$; if $muin(-epsilon,epsilon)$, both answers are considered to be correct. Then, we consider PAC-best arm identification in a bandit model: given $K$ probability distributions on $mathbbR$ with means $m{u}_1,dots,m{u}_K$, we derive the asymptotic complexity of identifying, with risk at most $delta$, an index $Iin1,dots,K$ such that $m{u}_{I}geqma{x}_{i}m{u}_i-epsilon$. 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.

Recommendations

• On the complexity of best-arm identification in multi-armed bandit models
• scientific article; zbMATH DE number 20652
• Nonparametric bandit methods
• Learning the distribution with largest mean: two bandit frameworks
• Pure exploration in infinitely-armed bandit models with fixed-confidence

Cites work

• A fully sequential procedure for indifference-zone selection in simulation
• Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
• Asymptotically efficient adaptive allocation rules
• Boundary crossing problems for sample means
• Explore first, exploit next: the true shape of regret in bandit problems
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Sequential Design of Experiments
• Sequential Tests of Statistical Hypotheses
• Some aspects of the sequential design of experiments
• The Large-Sample Distribution of the Likelihood Ratio for Testing Composite Hypotheses
• The expected sample size of some tests of power one
• The sample complexity of exploration in the multi-armed bandit problem

Cited in

(3)

• Policy space identification in configurable environments
• Certified multifidelity zeroth-order optimization
• scientific article; zbMATH DE number 7626761 (Why is no real title available?)

This page was built for publication: Nonasymptotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987192)