The True Sample Complexity of Identifying Good Arms
This work addresses the sample efficiency of bandit algorithms for practitioners, offering more practical and intuitive sample complexities, though it is incremental in refining existing theoretical frameworks.
The paper tackles the problem of identifying good arms in multi-armed bandits, arguing that existing PAC definitions lead to overly pessimistic sample complexities of Ω(n), and instead provides new definitions and algorithms that achieve nearly matching upper bounds with sample complexities like Θ(n/m) for ε-optimal arms, where m is the number of near-optimal arms.
We consider two multi-armed bandit problems with $n$ arms: (i) given an $ε> 0$, identify an arm with mean that is within $ε$ of the largest mean and (ii) given a threshold $μ_0$ and integer $k$, identify $k$ arms with means larger than $μ_0$. Existing lower bounds and algorithms for the PAC framework suggest that both of these problems require $Ω(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 $Θ(\frac{n}{m})$ samples where $m = |\{ i : μ_i > \max_{i \in [n]} μ_i - ε\}|$ and (ii) requires $Θ(\frac{n}{m}k)$ samples where $m = |\{ i : μ_i > μ_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.