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

摘要

In this article, we study sequential testing problems with 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 mu is an element of (-epsilon, epsilon), 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 mu(1), ... , mu(K), we derive the asymptotic complexity of identifying, with risk at most d, an index I is an element of {1, ..., K} such that mu(I) = max(i mu i) - epsilon: 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.