The True Sample Complexity of Identifying Good Arms

Abstract

We consider two multi-armed bandit problems with $n$ arms: (i) given an $\epsilon >0$, identify an arm with mean that is within $\epsilon$ of the largest mean and (ii) given a threshold ${\mu }_0$ and integer $k$, identify $k$ arms with means larger than ${\mu }_0$. Existing lower bounds and algorithms for the PAC framework suggest that both of these problems require $\Omega (n)$ samples. However, we argue that these definitions not only conflict with how these algorithms are used in practice, but also that these results disagree with intuition that says (i) requires only $\Theta (\frac{n}{m})$ samples where $m=|\{i:{\mu }_i>{\max }_{i\in [n]}{\mu }_i-\epsilon \}|$ and (ii) requires $\Theta (\frac{n}{m}k)$ samples where $m=|\{i:{\mu }_i>{\mu }_0\}|$. We provide definitions that formalize these intuitions, obtain lower bounds that match the above sample complexities, and develop explicit, practical algorithms that achieve nearly matching upper bounds.

References in corpus (4)

• Simple regret for infinitely many armed bandits
• Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
• Pure Exploration with Multiple Correct Answers
• PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits