Towards Instance Optimal Bounds for Best Arm Identification

Lijie Chen, Jian Li, Mingda Qiao

Published 2016-08-22Version 1

In the best arm identification (Best-1-Arm) problem, we are given $n$ stochastic bandit arms, each associated with a reward distribution with an unknown mean. We would like to identify the arm with the largest mean with probability $1-\delta$, using as few samples as possible. Understanding the sample complexity of Best-1-Arm has attracted significant attention since the last decade. However, the optimal sample complexity is still unknown. Recently, Chen and Li made an interesting conjecture, called gap-entropy conjecture, concerning the instance optimal sample complexity of Best-1-Arm. Given a Best-1-Arm instance, let $\mu_{[i]}$ denote the $i$th largest mean and $\Delta_{[i]}=\mu_{[1]}-\mu_{[i]}$ denote the corresponding gap. $H(I)=\sum_{i=2}^{n}\Delta_{[i]}^{-2}$ denotes the complexity of the instance. The gap-entropy conjecture states that for any instance $I$, $\Omega(H(I)\cdot(\log\delta^{-1}+\mathsf{Ent}(I)))$ is an instance lower bound, where $\mathsf{Ent}(I)$ is an entropy-like term completely determined by $\Delta_{[i]}$s, and there is a $\delta$-correct algorithm for Best-1-Arm with sample complexity $O(H(I)\cdot(\log\delta^{-1}+\mathsf{Ent}(I))+\Delta_{[2]}^{-2}\log\log\Delta_{[2]}^{-1})$. If the conjecture is true, we would have a complete understanding of the instance-wise sample complexity of Best-1-Arm. We make significant progress towards the resolution of the gap-entropy conjecture. For the upper bound, we provide a highly nontrivial $\delta$-correct algorithm which requires $$O(H(I)\cdot(\log\delta^{-1}+\mathsf{Ent}(I))+\Delta_{[2]}^{-2}\log\log \Delta_{[2]}^{-1}\operatorname*{polylog}(n,\delta^{-1}))$$ samples. For the lower bound, we show that for any Best-1-Arm instance with all gaps of the form $2^{-k}$, any $\delta$-correct monotone algorithm requires at least $\Omega(H(I)\cdot(\log\delta^{-1}+\mathsf{Ent}(I)))$ samples in expectation.