Optimal Best Arm Identification with Fixed Confidence

Abstract

We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.

Conference on Learning Theory (COLT), Jun 2016, New York, United States

References in corpus (3)

• Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
• Unimodal Bandits without Smoothness
• On the Complexity of A/B Testing

Cited by in corpus (42)

• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Optimal Best-arm Identification in Linear Bandits
• Simple Regret Minimization for Contextual Bandits
• Gradient Ascent for Active Exploration in Bandit Problems
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes
• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• Double Explore-then-Commit: Asymptotic Optimality and Beyond
• Best Arm Identification for Contaminated Bandits
• Adaptive Exploration in Linear Contextual Bandit
• Towards Optimal and Efficient Best Arm Identification in Linear Bandits
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
• Fixed-Confidence Guarantees for Bayesian Best-Arm Identification
• Collaborative Top Distribution Identifications with Limited Interaction
• Navigating to the Best Policy in Markov Decision Processes
• An Optimal Elimination Algorithm for Learning a Best Arm
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
• The Role of Contextual Information in Best Arm Identification
• Weighted Empirical Risk Minimization: Sample Selection Bias Correction based on Importance Sampling
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Non-Asymptotic Pure Exploration by Solving Games
• Thresholding Bandit with Optimal Aggregate Regret
• (Almost) Free Incentivized Exploration from Decentralized Learning Agents
• Dealing with Unknown Variances in Best-Arm Identification
• Bandit Quickest Changepoint Detection
• Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm
• Pure Exploration in Kernel and Neural Bandits
• Bregman Deviations of Generic Exponential Families
• The Influence of Shape Constraints on the Thresholding Bandit Problem
• PAC Best Arm Identification Under a Deadline
• MaxGap Bandit: Adaptive Algorithms for Approximate Ranking
• Learning to Actively Learn: A Robust Approach
• Sequential anomaly detection with sampling constraints
• Learning to Detect an Odd Markov Arm
• Discriminative Learning via Adaptive Questioning
• Covariance Adaptive Best Arm Identification
• Price of Safety in Linear Best Arm Identification
• Vector Optimization with Stochastic Bandit Feedback
• Guaranteed Fixed-Confidence Best Arm Identification in Multi-Armed Bandits: Simple Sequential Elimination Algorithms
• On Slowly-varying Non-stationary Bandits
• Diffusion Approximations for a Class of Sequential Testing Problems
• Chernoff Sampling for Active Testing and Extension to Active Regression
• Stochastic Bandits with Vector Losses: Minimizing ${\ell }^{\infty }$-Norm of Relative Losses