Regret Bounds for Batched Bandits

Abstract

We present simple and efficient algorithms for the batched stochastic multi-armed bandit and batched stochastic linear bandit problems. We prove bounds for their expected regrets that improve over the best-known regret bounds for any number of batches. In particular, our algorithms in both settings achieve the optimal expected regrets by using only a logarithmic number of batches. We also study the batched adversarial multi-armed bandit problem for the first time and find the optimal regret, up to logarithmic factors, of any algorithm with predetermined batch sizes.

Cited by in corpus (7)

• Differentially Private Multi-Armed Bandits in the Shuffle Model
• Parallelizing Thompson Sampling
• Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design
• Design of Experiments for Stochastic Contextual Linear Bandits
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits
• Gaussian Process Bandit Optimization with Few Batches
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs