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 (9)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Simple regret for infinitely many armed bandits
• Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
• Thresholding Bandits with Augmented UCB
• Pure Exploration with Multiple Correct Answers
• A Bandit Approach to Multiple Testing with False Discovery Control
• PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits

Cited by in corpus (7)

• An Optimal Elimination Algorithm for Learning a Best Arm
• My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits
• On Regret with Multiple Best Arms
• Bandits with many optimal arms
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits
• Pure Exploration in Kernel and Neural Bandits
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits