mlsanityData to 14 Oct 2026

Regret Bounds for Batched Bandits

arXiv 1910.04959 ↗First posted 11 Oct 2019cs.DS cs.LGcited by 49

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 49 papers in the map (data through 14 Oct 2026). First posted on arXiv 11 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 12; 2023: 7; 2024: 7; 2025: 6; 2026: 6.

49 papers.

Sort:

By area:

  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  3. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  4. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  5. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  6. 2022Replicable Banditscited by 22
  7. 2021Lipschitz Bandits with Batched Feedbackcited by 21
  8. 2021Parallelizing Thompson Samplingcited by 20
  9. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 19
  10. 2021Batched Thompson Samplingcited by 19
  11. 2022Differentially Private Stochastic Linear Bandits: (Almost) for Freecited by 19
  12. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
37 more
  1. 2021Solving Multi-Arm Bandit Using a Few Bits of Communicationcited by 16
  2. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  3. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  4. 2022Batched Dueling Banditscited by 10
  5. 2021Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Banditscited by 9
  6. 2023A Lipschitz Bandits Approach for Continuous Hyperparameter Optimizationcited by 9
  7. 2022Synthetically Controlled Banditscited by 8
  8. 2024Optimal Batched Linear Banditscited by 7
  9. 2024Falcon: Fair Active Learning using Multi-armed Banditscited by 6
  10. 2022Reward Imputation with Sketching for Contextual Batched Banditscited by 5
  11. 2024Experiment Planning with Function Approximationcited by 5
  12. 2026Multi-Drafter Speculative Decoding with Alignment Feedbackcited by 4
  13. 2022The Impact of Batch Learning in Stochastic Linear Banditscited by 3
  14. 2023Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costscited by 3
  15. 2024Adversarial Online Learning with Temporal Feedback Graphscited by 3
  16. 2026Batched Kernelized Bandits: Refinements and Extensionscited by 3
  17. 2022An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problemcited by 2
  18. 2023Adaptive Experimentation at Scale: A Computational Framework for Flexible Batchescited by 2
  19. 2023Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platformscited by 2
  20. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  21. 2024Replicability is Asymptotically Free in Multi-armed Banditscited by 2
  22. 2024Batched Stochastic Bandit for Nondegenerate Functionscited by 2
  23. 2025Optimal and Practical Batched Linear Bandit Algorithmcited by 2
  24. 2026Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updatescited by 2
  25. 2021The Impact of Batch Learning in Stochastic Banditscited by 1
  26. 2022Anonymous Bandits for Multi-User Systemscited by 1
  27. 2023Best Arm Identification in Batched Multi-armed Bandit Problemscited by 1
  28. 2024A Batch Sequential Halving Algorithm without Performance Degradationcited by 1
  29. 2025Batched Nonparametric Bandits via k-Nearest Neighbor UCBcited by 1
  30. 2025Optimization of Epsilon-Greedy Explorationcited by 1
  31. 2025On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-ballscited by 1
  32. 2026Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Banditscited by 1
  33. 2023Robust and differentially private stochastic linear banditscited by 0
  34. 2025A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyondcited by 0
  35. 2025Batched Bandits with Heavy-Tailed Rewardscited by 0
  36. 2026Learning in Markovian bandits with non-observable states and constrained decision epochscited by 0
  37. 2026Memory--Batch Tradeoffs in Lipschitz Banditscited by 0