lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits

Abstract

The paper proposes a novel upper confidence bound (UCB) procedure for identifying the arm with the largest mean in a multi-armed bandit game in the fixed confidence setting using a small number of total samples. The procedure cannot be improved in the sense that the number of samples required to identify the best arm is within a constant factor of a lower bound based on the law of the iterated logarithm (LIL). Inspired by the LIL, we construct our confidence bounds to explicitly account for the infinite time horizon of the algorithm. In addition, by using a novel stopping time for the algorithm we avoid a union bound over the arms that has been observed in other UCB-type algorithms. We prove that the algorithm is optimal up to constants and also show through simulations that it provides superior performance with respect to the state-of-the-art.

Cited by in corpus (97)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Non-stochastic Best Arm Identification and Hyperparameter Optimization
• Review on Ranking and Selection: A New Perspective
• Optimal Best Arm Identification with Fixed Confidence
• Best-Arm Identification in Linear Bandits
• Causal Bandits: Learning Good Interventions via Causal Inference
• Spectral MLE: Top-$K$ Rank Aggregation from Pairwise Comparisons
• An optimal algorithm for the Thresholding Bandit Problem
• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
• Always Valid Inference: Bringing Sequential Analysis to A/B Testing
• Improving the Expected Improvement Algorithm
• Sequential estimation of quantiles with applications to A/B-testing and best-arm identification
• Simple regret for infinitely many armed bandits
• Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
• On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits
• Conservative Bandits
• Why Adaptively Collected Data Have Negative Bias and How to Correct for It
• Towards Instance Optimal Bounds for Best Arm Identification
• Identifying Best Interventions through Online Importance Sampling
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• Inference for Batched Bandits
• On the bias, risk and consistency of sample means in multi-armed bandits
• Composing Meta-Policies for Autonomous Driving Using Hierarchical Deep Reinforcement Learning
• Unimodal Bandits without Smoothness
• Locally Differentially Private (Contextual) Bandits Learning
• Pure Exploration with Multiple Correct Answers
• Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
• Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
• Sequential Nonparametric Testing with the Law of the Iterated Logarithm
• Comparing Sequential Forecasters
• Confidence sequences for sampling without replacement
• BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed Bandits
• Sequential Experimental Design for Transductive Linear Bandits
• Pure Exploration of Multi-armed Bandit Under Matroid Constraints
• A Bandit Approach to Multiple Testing with False Discovery Control
• Selecting the best system and multi-armed bandits
• Optimal Best-Arm Identification Methods for Tail-Risk Measures
• Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
• Adaptive Multiple-Arm Identification
• Best Arm Identification for Contaminated Bandits
• Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
• The True Sample Complexity of Identifying Good Arms
• Maximin Action Identification: A New Bandit Framework for Games
• Towards Optimal and Efficient Best Arm Identification in Linear Bandits
• Learning the distribution with largest mean: two bandit frameworks
• A Bandit-Based Algorithm for Fairness-Aware Hyperparameter Optimization
• Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
• Optimal Confidence Regions for the Multinomial Parameter
• Finding All ε-Good Arms in Stochastic Bandits
• Feature selection as Monte-Carlo Search in Growing Single Rooted Directed Acyclic Graph by Best Leaf Identification
• Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits
• An Optimal Policy for Dynamic Assortment Planning Under Uncapacitated Multinomial Logit Models
• Fixed-Confidence Guarantees for Bayesian Best-Arm Identification
• Uncertainty quantification using martingales for misspecified Gaussian processes
• Accurate Inference for Adaptive Linear Models
• A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model
• Collaborative Top Distribution Identifications with Limited Interaction
• PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits
• Sublinear Optimal Policy Value Estimation in Contextual Bandits
• Generic Outlier Detection in Multi-Armed Bandit
• An Optimal Elimination Algorithm for Learning a Best Arm
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• The Role of Contextual Information in Best Arm Identification
• Structured Best Arm Identification with Fixed Confidence
• A Successive-Elimination Approach to Adaptive Robotic Sensing
• Bandit Quickest Changepoint Detection
• Near-Optimal Confidence Sequences for Bounded Random Variables
• Understanding the Origin of Information-Seeking Exploration in Probabilistic Objectives for Control
• Bandits with many optimal arms
• On conditional versus marginal bias in multi-armed bandits
• Thresholding Bandit with Optimal Aggregate Regret
• (Almost) Free Incentivized Exploration from Decentralized Learning Agents
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits
• From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model
• MaxGap Bandit: Adaptive Algorithms for Approximate Ranking
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism
• Pure Exploration in Kernel and Neural Bandits
• Variance-Dependent Best Arm Identification
• Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture
• PAC Mode Estimation using PPR Martingale Confidence Sequences
• PAC Best Arm Identification Under a Deadline
• Experimental Design for Regret Minimization in Linear Bandits
• A nonasymptotic law of iterated logarithm for general M-estimators
• Nonparametric iterated-logarithm extensions of the sequential generalized likelihood ratio test
• A KL-LUCB Bandit Algorithm for Large-Scale Crowdsourcing
• Stochastic Bandits with Vector Losses: Minimizing ${\ell }^{\infty }$-Norm of Relative Losses
• Best-item Learning in Random Utility Models with Subset Choices
• Stochastic Multi-armed Bandits in Constant Space
• Active Information Acquisition for Linear Optimization
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
• Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits
• Quick Best Action Identification in Linear Bandit Problems
• Thompson Sampling Guided Stochastic Searching on the Line for Deceptive Environments with Applications to Root-Finding Problems
• Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix