mlsanityData to 7 Oct 2026

Batched Multi-armed Bandits Problem

arXiv 1904.01763 ↗First posted 3 Apr 2019stat.ML cs.IT cs.LGcited by 97

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in citeperchet2016batched, the effect of the number of arms on the regret for the multi-armed case is still open. Moreover, the question whether adaptively chosen batch sizes will help to reduce the regret also remains underexplored. In this paper, we propose the BaSE (batched successive elimination) policy to achieve the rate-optimal regrets (within logarithmic factors) for batched multi-armed bandits, with matching lower bounds even if the batch sizes are determined in an adaptive manner.

Key facts. Cited by 97 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Apr 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 19; 2022: 17; 2023: 17; 2024: 16; 2025: 17; 2026: 11.

97 papers.

Sort:

By area:

  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  3. 2021Federated Linear Contextual Banditscited by 61
  4. 2024Feedback Efficient Online Fine-Tuning of Diffusion Modelscited by 52
  5. 2022The Sample Complexity of Online Contract Designcited by 35
  6. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  7. 2025FOCUS: Efficient Keyframe Selection for Long Video Understandingcited by 30
  8. 2021Differentially Private Multi-Armed Bandits in the Shuffle Modelcited by 24
  9. 2021Batched Neural Banditscited by 22
  10. 2022Replicable Banditscited by 22
  11. 2024Generalized Linear Bandits with Limited Adaptivitycited by 22
  12. 2021Lipschitz Bandits with Batched Feedbackcited by 21
38 more
  1. 2021Parallelizing Thompson Samplingcited by 20
  2. 2021Batched Thompson Samplingcited by 19
  3. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  4. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  5. 2022Distributed Contextual Linear Bandits with Minimax Optimal Communication Costcited by 13
  6. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  7. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  8. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  9. 2021Diffusion Approximations for Thompson Sampling in the Small Gap Regimecited by 12
  10. 2022A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Banditscited by 12
  11. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  12. 2022Batched Dueling Banditscited by 10
  13. 2021Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Banditscited by 9
  14. 2023A Lipschitz Bandits Approach for Continuous Hyperparameter Optimizationcited by 9
  15. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 8
  16. 2023Optimal Batched Best Arm Identificationcited by 8
  17. 2023An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Banditscited by 8
  18. 2021Online Learning of Energy Consumption for Navigation of Electric Vehiclescited by 7
  19. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  20. 2024Optimal Batched Linear Banditscited by 7
  21. 2024Infrequent Resolving Algorithm for Online Linear Programmingcited by 7
  22. 2022Bandits for Online Calibration: An Application to Content Moderation on Social Media Platformscited by 6
  23. 2023On-Demand Communication for Asynchronous Multi-Agent Banditscited by 6
  24. 2023Sequential Counterfactual Risk Minimizationcited by 6
  25. 2024Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Banditscited by 6
  26. 2025Nightjar: Dynamic Adaptive Speculative Decoding for Large Language Models Servingcited by 6
  27. 2022Reward Imputation with Sketching for Contextual Batched Banditscited by 5
  28. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  29. 2024Stochastic contextual bandits with graph feedback: from independence number to MAS numbercited by 5
  30. 2021Parallelizing Contextual Banditscited by 4
  31. 2021Safe Data Collection for Offline and Online Policy Learningcited by 4
  32. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  33. 2021Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Banditscited by 3
  34. 2022The Impact of Batch Learning in Stochastic Linear Banditscited by 3
  35. 2023Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costscited by 3
  36. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  37. 2024Batched Nonparametric Contextual Banditscited by 3
  38. 2024Adversarial Online Learning with Temporal Feedback Graphscited by 3

50 most cited of 97 All 97 (JSON)