Batched bandit problems

Abstract

Motivated by practical applications, chiefly clinical trials, we study the regret achievable for stochastic bandits under the constraint that the employed policy must split trials into a small number of batches. We propose a simple policy, and show that a very small number of batches gives close to minimax optimal regret bounds. As a byproduct, we derive optimal policies with low switching cost for stochastic bandits.

Published at http://dx.doi.org/10.1214/15-AOS1381 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Batched bandit problems
• Bounded regret in stochastic multi-armed bandits
• Asymptotically optimal multistage tests of simple hypotheses

Cited by in corpus (33)

• Batched bandit problems
• Batched Multi-armed Bandits Problem
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• Provably Efficient Q-Learning with Low Switching Cost
• Beyond Ads: Sequential Decision-Making Algorithms in Law and Public Policy
• Inference for Batched Bandits
• SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits
• Federated Linear Contextual Bandits
• Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization
• MOTS: Minimax Optimal Thompson Sampling
• Double Explore-then-Commit: Asymptotic Optimality and Beyond
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Online Learning of Energy Consumption for Navigation of Electric Vehicles
• Learning the distribution with largest mean: two bandit frameworks
• Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Parallelizing Thompson Sampling
• A Practical Guide of Off-Policy Evaluation for Bandit Problems
• Phase Transitions in Bandits with Switching Constraints
• Blind Network Revenue Management and Bandits with Knapsacks under Limited Switches
• Off-Policy Evaluation of Bandit Algorithm from Dependent Samples under Batch Update Policy
• Online Batch Decision-Making with High-Dimensional Covariates
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits
• Maximal Objectives in the Multi-armed Bandit with Applications
• Smooth Sequential Optimisation with Delayed Feedback
• Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits
• Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect
• Parallel Contextual Bandits in Wireless Handover Optimization
• The Impact of Batch Learning in Stochastic Bandits
• Understanding Uncertainty of Edge Computing: New Principle and Design Approach
• Bandits with Temporal Stochastic Constraints
• Batched Thompson Sampling for Multi-Armed Bandits
• Batched Bandits with Crowd Externalities