On the Complexity of Best Arm Identification in Multi-Armed Bandit Models

Abstract

The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of regret minimization is now well known, our aim is to contribute to a better understanding of the performance in terms of identifying the m best arms. We introduce generic notions of complexity for the two dominant frameworks considered in the literature: fixed-budget and fixed-confidence settings. In the fixed-confidence setting, we provide the first known distribution-dependent lower bound on the complexity that involves information-theoretic quantities and holds when m is larger than 1 under general assumptions. In the specific case of two armed-bandits, we derive refined lower bounds in both the fixed-confidence and fixed-budget settings, along with matching algorithms for Gaussian and Bernoulli bandit models. These results show in particular that the complexity of the fixed-budget setting may be smaller than the complexity of the fixed-confidence setting, contradicting the familiar behavior observed when testing fully specified alternatives. In addition, we also provide improved sequential stopping rules that have guaranteed error probabilities and shorter average running times. The proofs rely on two technical results that are of independent interest : a deviation lemma for self-normalized sums (Lemma 19) and a novel change of measure inequality for bandit models (Lemma 1).

arXiv admin note: text overlap with arXiv:1405.3224

References in corpus (7)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Further Optimal Regret Bounds for Thompson Sampling
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
• Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
• Bounded regret in stochastic multi-armed bandits
• Multiple Identifications in Multi-Armed Bandits

Cited by in corpus (139)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Quantifying total uncertainty in physics-informed neural networks for solving forward and inverse stochastic problems
• Global rates of convergence for nonconvex optimization on manifolds
• "What is Relevant in a Text Document?": An Interpretable Machine Learning Approach
• A Survey of Reinforcement Learning Algorithms for Dynamically Varying Environments
• Frequentist Consistency of Variational Bayes
• Sparse graphs using exchangeable random measures
• Cosmology constraints from shear peak statistics in Dark Energy Survey Science Verification data
• Cumulative effects of triadic closure and homophily in social networks
• Time-uniform, nonparametric, nonasymptotic confidence sequences
• Machine Learning Testing: Survey, Landscapes and Horizons
• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• Calibrating general posterior credible regions
• Optimal Best Arm Identification with Fixed Confidence
• Turning Optical Complex Media into Universal Reconfigurable Linear Operators by Wavefront Shaping
• Online Censoring for Large-Scale Regressions with Application to Streaming Big Data
• A hybrid supervised/unsupervised machine learning approach to solar flare prediction
• Minimal Exploration in Structured Stochastic Bandits
• Bayesian optimisation for likelihood-free cosmological inference
• Accelerating Nuclear Configuration Interaction Calculations through a Preconditioned Block Iterative Eigensolver
• Improper Learning for Non-Stochastic Control
• A near-stationary subspace for ridge approximation
• Random Forest identification of the thin disk, thick disk and halo Gaia-DR2 white dwarf population
• Gym-ANM: Reinforcement Learning Environments for Active Network Management Tasks in Electricity Distribution Systems
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• Improving the Expected Improvement Algorithm
• Kernel-Based Emulator for the 3D Matter Power Spectrum from CLASS
• Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
• Exploration in Structured Reinforcement Learning
• A Novel Online Stacked Ensemble for Multi-Label Stream Classification
• The Recycling Gibbs Sampler for Efficient Learning
• On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits
• A new class of accelerated regularization methods, with application to bioluminescence tomography
• Conservative Bandits
• Reward-Free Exploration for Reinforcement Learning
• Safe Option-Critic: Learning Safety in the Option-Critic Architecture
• Multiple-Play Bandits in the Position-Based Model
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• A study of the morphology, dynamics, and folding pathways of ring polymers with supramolecular topological constraints using molecular simulation and nonlinear manifold learning
• Preference-based Online Learning with Dueling Bandits: A Survey
• Trend Filtering -- I. A Modern Statistical Tool for Time-Domain Astronomy and Astronomical Spectroscopy
• A unified framework for 21cm tomography sample generation and parameter inference with Progressively Growing GANs
• Prepaid parameter estimation without likelihoods
• Predictive Online Convex Optimization
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Identifying Best Interventions through Online Importance Sampling
• Optimal Best-arm Identification in Linear Bandits
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• On the bias, risk and consistency of sample means in multi-armed bandits
• Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization
• Machine Learning Accelerated Likelihood-Free Event Reconstruction in Dark Matter Direct Detection
• From self-tuning regulators to reinforcement learning and back again
• A Convex Approximation for the Tertiary Control of Unbalanced Microgrids
• Matrix Completion under Interval Uncertainty
• COHORT: Coordination of Heterogeneous Thermostatically Controlled Loads for Demand Flexibility
• Locally Differentially Private (Contextual) Bandits Learning
• Loss-Aversively Fair Classification
• Accounting for Model Uncertainty in Algorithmic Discrimination
• Pure Exploration with Multiple Correct Answers
• To Infinity and Beyond: Some ODE and PDE Case Studies
• Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
• Gradient Ascent for Active Exploration in Bandit Problems
• On high-dimensional modifications of some graph-based two-sample tests
• Stochastic Rank-1 Bandits
• Dictionary learning for clustering on hyperspectral images
• Online Learning with Gaussian Payoffs and Side Observations
• Learning to detect an oddball target with observations from an exponential family
• A Bandit Approach to Multiple Testing with False Discovery Control
• Sequential Experimental Design for Transductive Linear Bandits
• Accelerated iterative regularization via dual diagonal descent
• Selecting the best system and multi-armed bandits
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes
• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Stopping criterion for active learning based on deterministic generalization bounds
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
• Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
• Best Arm Identification for Contaminated Bandits
• Swapped Face Detection using Deep Learning and Subjective Assessment
• Stochastic Bandits with Linear Constraints
• Maximin Action Identification: A New Bandit Framework for Games
• The True Sample Complexity of Identifying Good Arms
• Towards Optimal and Efficient Best Arm Identification in Linear Bandits
• Finding All ε-Good Arms in Stochastic Bandits
• Stability analysis of ground states in a one-dimensional trapped spin-1 Bose gas
• Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
• Quantum secure learning with classical samples
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Navigating to the Best Policy in Markov Decision Processes
• Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors
• Collaborative Top Distribution Identifications with Limited Interaction
• MERLiN: Mixture Effect Recovery in Linear Networks
• Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback
• Structured Best Arm Identification with Fixed Confidence
• Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces
• Generic Outlier Detection in Multi-Armed Bandit
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Learning to Detect an Odd Restless Markov Arm with a Trembling Hand
• The Role of Contextual Information in Best Arm Identification
• Fixed Inducing Points Online Bayesian Calibration for Computer Models with an Application to a Scale-Resolving CFD Simulation
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
• Non-Asymptotic Pure Exploration by Solving Games
• Sparse Stochastic Bandits
• Active Tolerant Testing
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs
• Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits
• Best Arm Identification with Safety Constraints
• Task-Optimal Exploration in Linear Dynamical Systems
• Combinatorial Pure Exploration with Bottleneck Reward Function
• Pair-Matching: Links Prediction with Adaptive Queries
• K-NN active learning under local smoothness assumption
• A Decentralized Policy with Logarithmic Regret for a Class of Multi-Agent Multi-Armed Bandit Problems with Option Unavailability Constraints and Stochastic Communication Protocols
• Detecting an Odd Restless Markov Arm with a Trembling Hand
• A PAC algorithm in relative precision for bandit problem with costly sampling
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism
• Transfer Learning in Bandits with Latent Continuity
• From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model
• Pure Exploration in Kernel and Neural Bandits
• PAC Best Arm Identification Under a Deadline
• Experimental Design for Regret Minimization in Linear Bandits
• High-resolution reconstruction of cellular traction-force distributions: the role of physically motivated constraints and compressive regularization
• Collaborative Pure Exploration in Kernel Bandit
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits
• Active Information Acquisition for Linear Optimization
• Targeted Active Learning for Bayesian Decision-Making
• A KL-LUCB Bandit Algorithm for Large-Scale Crowdsourcing
• Sequential ranking under random semi-bandit feedback
• Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
• Learning to Detect an Odd Markov Arm
• Online Model Selection: a Rested Bandit Formulation
• An Index-based Deterministic Asymptotically Optimal Algorithm for Constrained Multi-armed Bandit Problems
• Best-item Learning in Random Utility Models with Subset Choices
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
• Diffusion Approximations for a Class of Sequential Testing Problems
• A Bad Arm Existence Checking Problem
• Chernoff Sampling for Active Testing and Extension to Active Regression
• Adaptive Double-Exploration Tradeoff for Outlier Detection
• Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits