Variance-Dependent Best Arm Identification

We study the problem of identifying the best arm in a stochastic multi-armed bandit game. Given a set of n arms indexed from 1 to n, each arm i is associated with an unknown reward distribution supported on [0,1] with mean θi and variance σi2. Assume θ1 > θ2 ≥ cdots ≥θn. We propose an adaptive algorithm which explores the gaps and variances of the rewards of the arms and makes future decisions based on the gathered information using a novel approach called textitgrouped median elimination. The proposed algorithm guarantees to output the best arm with probability (1-δ) and uses at most O left(sumi = 1n left(fracσi2Deltai2 + frac1Deltairight)(ln δ-1 + ln ln Deltai-1)right) samples, where Deltai (i ≥ 2) denotes the reward gap between arm i and the best arm and we define Delta1 = Delta2. This achieves a significant advantage over the variance-independent algorithms in some favorable scenarios and is the first result that removes the extra ln n factor on the best arm compared with the state-of-the-art. We further show that Omega left( sumi = 1n left( fracσi2Deltai2 + frac1Deltai right) ln δ-1 right) samples are necessary for an algorithm to achieve the same goal, thereby illustrating that our algorithm is optimal up to doubly logarithmic terms.