# Parallelizing Thompson Sampling

arXiv: https://arxiv.org/abs/2106.01420 · HTML: https://mlsanity.com/paper/2106.01420/

## Key facts

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

## Builds on (most cited first, 22 of 22)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups](https://mlsanity.com/paper/1802.07028/) (2018)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Batched Gaussian Process Bandit Optimization via Determinantal Point Processes](https://mlsanity.com/paper/1611.04088/) (2016)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [MOTS: Minimax Optimal Thompson Sampling](https://mlsanity.com/paper/2003.01803/) (2020)
- [Prior-free and prior-dependent regret bounds for Thompson Sampling](https://mlsanity.com/paper/1304.5758/) (2013)
- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition](https://mlsanity.com/paper/1910.10873/) (2019)
- [Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity](https://mlsanity.com/paper/1807.07889/) (2018)
- [Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization](https://mlsanity.com/paper/1808.03880/) (2018)
- [Unconstrained Submodular Maximization with Constant Adaptive Complexity](https://mlsanity.com/paper/1811.06603/) (2018)
- [Stochastic Submodular Cover with Limited Adaptivity](https://mlsanity.com/paper/1810.13351/) (2018)

## Built on by (most cited first, 20 of 20)

- [Batched Thompson Sampling](https://mlsanity.com/paper/2110.00202/) (2021)
- [Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning](https://mlsanity.com/paper/2306.08803/) (2023)
- [Approximate Function Evaluation via Multi-Armed Bandits](https://mlsanity.com/paper/2203.10124/) (2022)
- [Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits](https://mlsanity.com/paper/2301.11442/) (2023)
- [Batched Nonparametric Contextual Bandits](https://mlsanity.com/paper/2402.17732/) (2024)
- [Batched Thompson Sampling for Multi-Armed Bandits](https://mlsanity.com/paper/2108.06812/) (2021)
- [One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning](https://mlsanity.com/paper/2205.15891/) (2022)
- [Adaptive Experimentation at Scale: A Computational Framework for Flexible Batches](https://mlsanity.com/paper/2303.11582/) (2023)
- [Batched Energy-Entropy acquisition for Bayesian Optimization](https://mlsanity.com/paper/2410.08804/) (2024)
- [Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates](https://mlsanity.com/paper/2606.00984/) (2026)
- [Anonymous Bandits for Multi-User Systems](https://mlsanity.com/paper/2210.12198/) (2022)
- [Best Arm Identification in Batched Multi-armed Bandit Problems](https://mlsanity.com/paper/2312.13875/) (2023)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [A Batch Sequential Halving Algorithm without Performance Degradation](https://mlsanity.com/paper/2406.00424/) (2024)
- [Optimization of Epsilon-Greedy Exploration](https://mlsanity.com/paper/2506.03324/) (2025)
- [Zero-Inflated Bandits](https://mlsanity.com/paper/2312.15595/) (2023)
- [Breaking the log(1/Delta2) Barrier: Better Batched Best Arm Identification with Adaptive Grids](https://mlsanity.com/paper/2501.17370/) (2025)
- [The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margin](https://mlsanity.com/paper/2511.03708/) (2025)
- [Meta-Learning Multi-armed Bandits for Beam Tracking in 5G and 6G Networks](https://mlsanity.com/paper/2512.05680/) (2025)
- [Risk-Aware Adaptive Evaluation: Finding High-Impact Failures Under Limited Budgets](https://mlsanity.com/paper/2609.38914/) (2026)

## 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.