






















In this paper, we study sequential testing problems with \emph{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 $μ\in(-ε,ε)$, both answers are considered to be correct. Then, we consider PAC-best arm identification in a bandit model: given $K$ probability distributions on $\mathbb{R}$ with means $μ_1,\dots,μ_K$, we derive the asymptotic complexity of identifying, with risk at most $δ$, an index $I\in\{1,\dots,K\}$ such that $μ_I\geq \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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。