Non-Asymptotic Sequential Tests for Overlapping Hypotheses and application to near optimal arm identification in bandit models
Non-Asymptotic Sequential Tests for Overlapping Hypotheses and application to near optimal arm identification in bandit models
复制标题
重叠假设的非渐近序贯检验及其在强盗模型中近最优臂识别中的应用
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
E. Kaufmann
中科院分区：
文献类型：
--
作者：
Aurélien Garivier;E. Kaufmann
本文研究了具有重叠假设的序贯检验问题。我们首先关注一个简单的问题，即评估高斯分布的均值μ是否为$≥ e−或≤e;如果μ ∈（−e，e）$，则两个答案都被认为是正确的。然后，我们考虑在强盗模型中的PAC-最佳手臂识别：给定R上的K个概率分布，平均值为$µ_1，. ..，μ_K$，我们得到了在风险不超过$δ$的情况下，识别指数$I ∈ {1，. ..，K}$使得$µ_I ≥ max_i µ_i −e$。我们提供了一个并行的一般似然比检验的误差的非渐近界，这也可以用于更一般的测试问题。我们进一步提出了确定一个正确假设所需的观测数的下限。这些下限依赖于信息理论的参数，特别是在两个版本的测量引理的变化（高层次的形式，和低层次的形式），其相对优点进行了讨论。
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 $≥ e− or ≤e; if µ ∈ (−e,e)$, 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 −e$. 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.