# Batched Thompson Sampling

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 1 Oct 2021.

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

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2008.11918/) (2020)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [Parallelizing Thompson Sampling](https://mlsanity.com/paper/2106.01420/) (2021)

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

- [Advancing Deep Active Learning & Data Subset Selection: Unifying Principles with Information-Theory Intuitions](https://mlsanity.com/paper/2401.04305/) (2024)
- [Rate-Constrained Remote Contextual Bandits](https://mlsanity.com/paper/2204.12620/) (2022)
- [Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning](https://mlsanity.com/paper/2306.08803/) (2023)
- [Optimal Adaptive Experimental Design for Estimating Treatment Effect](https://mlsanity.com/paper/2410.05552/) (2024)
- [The Impact of Batch Learning in Stochastic Linear Bandits](https://mlsanity.com/paper/2202.06657/) (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)
- [Simulation-Based Inference for Adaptive Experiments](https://mlsanity.com/paper/2506.02881/) (2025)
- [Adaptive Experimentation at Scale: A Computational Framework for Flexible Batches](https://mlsanity.com/paper/2303.11582/) (2023)
- [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)
- [A Batch Sequential Halving Algorithm without Performance Degradation](https://mlsanity.com/paper/2406.00424/) (2024)
- [Batched Nonparametric Bandits via k-Nearest Neighbor UCB](https://mlsanity.com/paper/2505.10498/) (2025)
- [Optimization of Epsilon-Greedy Exploration](https://mlsanity.com/paper/2506.03324/) (2025)
- [Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits](https://mlsanity.com/paper/2603.13742/) (2026)
- [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)
- [Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits](https://mlsanity.com/paper/2609.19709/) (2026)
- [Challenges and Solutions for Bandits in the Wild: Warm-Started Mixture Bandits for Cross-Cohort Slate Recommendation](https://mlsanity.com/paper/2609.37800/) (2026)

## Abstract (arXiv)

We introduce a novel anytime Batched Thompson sampling policy for multi-armed bandits where the agent observes the rewards of her actions and adjusts her policy only at the end of a small number of batches. We show that this policy simultaneously achieves a problem dependent regret of order O(log(T)) and a minimax regret of order O(√Tlog(T)) while the number of batches can be bounded by O(log(T)) independent of the problem instance over a time horizon T. We also show that in expectation the number of batches used by our policy can be bounded by an instance dependent bound of order O(loglog(T)). These results indicate that Thompson sampling maintains the same performance in this batched setting as in the case when instantaneous feedback is available after each action, while requiring minimal feedback. These results also indicate that Thompson sampling performs competitively with recently proposed algorithms tailored for the batched setting. These algorithms optimize the batch structure for a given time horizon T and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. We show that Thompson sampling combined with an adaptive batching strategy can achieve a similar performance without knowing the time horizon T of the problem and without having to carefully optimize the batch structure to achieve a target regret bound (i.e. problem dependent vs minimax regret) for a given T.