mlsanityData to 7 Oct 2026

Parallelizing Thompson Sampling

arXiv 2106.01420 ↗First posted 2 Jun 2021cs.LG cs.AI math.OCcited by 20

Not on the map. Why?

Abstract (arXiv)

How can we make use of information parallelism in online decision making problems while efficiently balancing the exploration-exploitation trade-off? In this paper, we introduce a batch Thompson Sampling framework for two canonical online decision making problems, namely, stochastic multi-arm bandit and linear contextual bandit with finitely many arms. Over a time horizon T, our textitbatch Thompson Sampling policy achieves the same (asymptotic) regret bound of a fully sequential one while carrying out only O(log T) batch queries. To achieve this exponential reduction, i.e., reducing the number of interactions from T to O(log T), our batch policy dynamically determines the duration of each batch in order to balance the exploration-exploitation trade-off. We also demonstrate experimentally that dynamic batch allocation dramatically outperforms natural baselines such as static batch allocations.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 22 of its 71 references that are in the map. First posted on arXiv 2 Jun 2021.

Builds on

22 of 71 references.

References · 22

  1. 2019Introduction to Multi-Armed Banditscited by 475
  2. 2017A Tutorial on Thompson Samplingcited by 420
  3. 2013Learning to Optimize Via Posterior Samplingcited by 253
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2017Batched Large-scale Bayesian Optimization in High-dimensional Spacescited by 116
  6. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 113
  7. 2019Batched Multi-armed Bandits Problemcited by 97
  8. 2019Sequential Experimental Design for Transductive Linear Banditscited by 88
  9. 2018High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groupscited by 58
  10. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  11. 2013Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Explorationcited by 50
  12. 2019Regret Bounds for Batched Banditscited by 49
10 more
  1. 2016Batched Gaussian Process Bandit Optimization via Determinantal Point Processescited by 33
  2. 2020Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Banditscited by 31
  3. 2020MOTS: Minimax Optimal Thompson Samplingcited by 28
  4. 2013Prior-free and prior-dependent regret bounds for Thompson Samplingcited by 25
  5. 2019Adaptivity in Adaptive Submodularitycited by 22
  6. 2019Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transitioncited by 17
  7. 2018Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexitycited by 14
  8. 2018Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimizationcited by 11
  9. 2018Unconstrained Submodular Maximization with Constant Adaptive Complexitycited by 8
  10. 2018Stochastic Submodular Cover with Limited Adaptivitycited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 3; 2023: 6; 2024: 3; 2025: 4; 2026: 2.

20 papers.

Sort:

  1. 2021Batched Thompson Samplingcited by 19
  2. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  3. 2022Approximate Function Evaluation via Multi-Armed Banditscited by 4
  4. 2024Batched Nonparametric Contextual Banditscited by 3
  5. 2021Batched Thompson Sampling for Multi-Armed Banditscited by 2
  6. 2022One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learningcited by 2
  7. 2023Communication-Efficient Collaborative Regret Minimization in Multi-Armed Banditscited by 2
  8. 2023Adaptive Experimentation at Scale: A Computational Framework for Flexible Batchescited by 2
  9. 2022Anonymous Bandits for Multi-User Systemscited by 1
  10. 2023Best Arm Identification in Batched Multi-armed Bandit Problemscited by 1
  11. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  12. 2024A Batch Sequential Halving Algorithm without Performance Degradationcited by 1
8 more
  1. 2024Batched Energy-Entropy acquisition for Bayesian Optimizationcited by 1
  2. 2025Optimization of Epsilon-Greedy Explorationcited by 1
  3. 2026Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updatescited by 1
  4. 2023Zero-Inflated Banditscited by 0
  5. 2025Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Gridscited by 0
  6. 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margincited by 0
  7. 2025Meta-Learning Multi-armed Bandits for Beam Tracking in 5G and 6G Networkscited by 0
  8. 2026Risk-Aware Adaptive Evaluation: Finding High-Impact Failures Under Limited Budgetscited by 0