Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem

Abstract

We consider the problem of \textit{best arm identification} with a \textit{fixed budget $T$}, in the $K$-armed stochastic bandit setting, with arms distribution defined on $[0,1]$. We prove that any bandit strategy, for at least one bandit problem characterized by a complexity $H$, will misidentify the best arm with probability lower bounded by $$\exp (-\frac{T}{\log (K)H}),$$ where $H$ is the sum for all sub-optimal arms of the inverse of the squared gaps. Our result disproves formally the general belief - coming from results in the fixed confidence setting - that there must exist an algorithm for this problem whose probability of error is upper bounded by $\exp (-T/H)$. This also proves that some existing strategies based on the Successive Rejection of the arms are optimal - closing therefore the current gap between upper and lower bounds for the fixed budget best arm identification problem.

arXiv commentCOLT 2016

Cited by in corpus (17)

• On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits
• On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials
• Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
• Collaborative Top Distribution Identifications with Limited Interaction
• Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Sampling
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions
• Bandit Pareto Set Identification: the Fixed Budget Setting
• Bandits with many optimal arms
• Rate-optimal Bayesian Simple Regret in Best Arm Identification
• Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm
• The Influence of Shape Constraints on the Thresholding Bandit Problem
• Learning to Actively Learn: A Robust Approach
• Covariance Adaptive Best Arm Identification
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
• Stochastic Bandits with Vector Losses: Minimizing ${\ell }^{\infty }$-Norm of Relative Losses
• Price of Safety in Linear Best Arm Identification
• Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits