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.

考虑在 $[0,1]$ 区间上的 $K$ 个臂构成的随机赌博机下，使用有限的轮次 $T$ 定位最佳赌博机的问题，证明了在该问题中误判率的最低下界。同时，该结论证明了基于臂的连续拒绝（Successive Rejection）的算法是最优的，填补了固定预算下最佳臂定位问题的上下限差距。

固定预算最佳臂识别赌博机问题的严格（下界）界限