Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
复制标题
DOI：
--
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
A. Carpentier;A. Locatelli
中科院分区：
文献类型：
--
作者：
A. Carpentier;A. Locatelli
我们考虑了在$K$-armed随机bandit环境下，具有固定预算$T$的最佳臂识别问题，其中武器分布定义在$[0，1]$上。我们证明，任何强盗策略，至少有一个强盗问题的特点是复杂性$H$，将错误识别的最佳武器的概率下界为$$\exp\Big（-\frac{T}{\log（K）H}\Big），$$其中$H$是所有次优武器的平方差距的倒数之和。我们的结果正式反驳的一般信念-来自结果在固定的置信度设置-必须存在一个算法，这个问题的错误概率是上界的$\exp（-T/H）$。这也证明了一些现有的策略的基础上逐次拒绝的武器是最佳的，因此，目前的差距上限和下限之间的固定预算的最佳武器识别问题。
We consider the problem of \textit{best arm identification} with a \textit{fixed budget $T$}, in the $K$-armed stochastic bandit setting, with arms distribution defined on $[0,1]$. We prove that any bandit strategy, for at least one bandit problem characterized by a complexity $H$, will misidentify the best arm with probability lower bounded by $$\exp\Big(-\frac{T}{\log(K)H}\Big),$$ where $H$ is the sum for all sub-optimal arms of the inverse of the squared gaps. Our result disproves formally the general belief - coming from results in the fixed confidence setting - that there must exist an algorithm for this problem whose probability of error is upper bounded by $\exp(-T/H)$. This also proves that some existing strategies based on the Successive Rejection of the arms are optimal - closing therefore the current gap between upper and lower bounds for the fixed budget best arm identification problem.