On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
summary
Proves that best-arm identification complexities differ between the fixed-budget and fixed-confidence settings, using a new Pinsker-like change-of-measure inequality to get lower bounds and deriving problem-dependent rates in terms of Chernoff-information complexity (not the same KL terms as regret). Constructs matching upper bounds for Gaussians (complexities coincide) and shows for Bernoulli rewards the fixed-confidence complexity is provably larger. Also develops empirical-likelihood UCB ideas for tight regret control.
AI-written summary · about
chapters (5)
- 0:00Introduction to bandits
- 12:23Best arm identification
- 16:01Budget vs confidence
- 19:08Lower bounds and complexity
- 24:24Conclusions and Q&A
related talks
01h 01mStochastic Bandits: Foundations and Current Perspectives
45mBest Of Both Worlds: Stochastic & Adversarial Best-Arm Identification
01h 09mStochastic Bandits: Foundations and Current Perspectives
04mOn gradient-based methods for finding game-theoretic equilibria
01h 21mAdversarial Bandits: Theory and Algorithms
22mOnline Learning and Bandits with Queried Hints
38mBest of Both World Algorithms from I.I.D. to Adversarial Data
48mAdaptivity and Confounding in Multi-armed Bandit Experiments