Abstract
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 μ₀ and integer k, identify k arms with means larger than μ₀. 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 Θ(n/m) samples where m = |{ i : μ_i > max_i ∈ [n] μ_i - ε}| and (ii) requires Θ(n/mk) samples where m = |{ i : μ_i > μ₀ }|. 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.