# Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits

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

## Key facts

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

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [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)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)

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

- [Best Arm Identification in Batched Multi-armed Bandit Problems](https://mlsanity.com/paper/2312.13875/) (2023)
- [Increasing Students' Engagement to Reminder Emails Through Multi-Armed Bandits](https://mlsanity.com/paper/2208.05090/) (2022)
- [Batched Online Contextual Sparse Bandits with Sequential Inclusion of Features](https://mlsanity.com/paper/2409.09199/) (2024)

## Abstract (arXiv)

We study the asymptotic performance of the Thompson sampling algorithm in the batched multi-armed bandit setting where the time horizon T is divided into batches, and the agent is not able to observe the rewards of her actions until the end of each batch. We show that in this batched setting, Thompson sampling achieves the same asymptotic performance as in the case where instantaneous feedback is available after each action, provided that the batch sizes increase subexponentially. This result implies that Thompson sampling can maintain its performance even if it receives delayed feedback in ω(log T) batches. We further propose an adaptive batching scheme that reduces the number of batches to Theta(log T) while maintaining the same performance. Although the batched multi-armed bandit setting has been considered in several recent works, previous results rely on tailored algorithms for the batched setting, which optimize the batch structure and prioritize exploration in the beginning of the experiment to eliminate suboptimal actions. We show that Thompson sampling, on the other hand, is able to achieve a similar asymptotic performance in the batched setting without any modifications.