The True Sample Complexity of Identifying Good 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 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(fracnm) samples where m = | i : μi > maxi ∈ [n] μi - ε| and (ii) requires Theta(fracnmk) 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.