# Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2015.

## Built on by (most cited first, 30 of 38)

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Doubly-Robust Estimation for Correcting Position-Bias in Click Feedback for Unbiased Learning to Rank](https://mlsanity.com/paper/2203.17118/) (2022)
- [Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2402.01845/) (2024)
- [Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits](https://mlsanity.com/paper/2306.02208/) (2023)
- [Online Experimental Design With Estimation-Regret Trade-off Under Network Interference](https://mlsanity.com/paper/2412.03727/) (2024)
- [Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits](https://mlsanity.com/paper/2107.11419/) (2021)
- [The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle](https://mlsanity.com/paper/2111.04295/) (2021)
- [Bandits with Preference Feedback: A Stackelberg Game Perspective](https://mlsanity.com/paper/2406.16745/) (2024)
- [Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Arms](https://mlsanity.com/paper/2206.08776/) (2022)
- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints](https://mlsanity.com/paper/2301.10230/) (2023)
- [Censored Semi-Bandits for Resource Allocation](https://mlsanity.com/paper/2104.05781/) (2021)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [Regret Analysis of Retry-Based Bandits](https://mlsanity.com/paper/2605.20854/) (2026)
- [LITE: Efficiently Estimating Gaussian Probability of Maximality](https://mlsanity.com/paper/2501.13535/) (2025)
- [A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information](https://mlsanity.com/paper/2102.10200/) (2021)
- [Risk-Aware Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2112.01141/) (2021)
- [Autonomous Drug Design with Multi-Armed Bandits](https://mlsanity.com/paper/2207.01393/) (2022)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identification](https://mlsanity.com/paper/2202.05193/) (2022)
- [Adversarial Sleeping Bandit Problems with Multiple Plays: Algorithm and Ranking Application](https://mlsanity.com/paper/2307.14549/) (2023)
- [Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delays](https://mlsanity.com/paper/2407.15439/) (2024)
- [Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox](https://mlsanity.com/paper/2410.05441/) (2024)
- [A Control Function Framework for Mitigating Position Bias in Learning to Rank Systems](https://mlsanity.com/paper/2506.06989/) (2025)
- [Blind Exploration and Exploitation of Stochastic Experts](https://mlsanity.com/paper/2104.01078/) (2021)
- [Multi-armed Bandit Algorithms on System-on-Chip: Go Frequentist or Bayesian?](https://mlsanity.com/paper/2106.02855/) (2021)
- [Adapting Bandit Algorithms for Settings with Sequentially Available Arms](https://mlsanity.com/paper/2109.15228/) (2021)
- [Adversarial Online Learning with Variable Plays in the Pursuit-Evasion Game: Theoretical Foundations and Application in Connected and Automated Vehicle Cybersecurity](https://mlsanity.com/paper/2110.14078/) (2021)
- [UniRank: Unimodal Bandit Algorithm for Online Ranking](https://mlsanity.com/paper/2208.01515/) (2022)
- [Constant or logarithmic regret in asynchronous multiplayer bandits](https://mlsanity.com/paper/2305.19691/) (2023)

## Abstract (arXiv)

We discuss a multiple-play multi-armed bandit (MAB) problem in which several arms are selected at each round. Recently, Thompson sampling (TS), a randomized algorithm with a Bayesian spirit, has attracted much attention for its empirically excellent performance, and it is revealed to have an optimal regret bound in the standard single-play MAB problem. In this paper, we propose the multiple-play Thompson sampling (MP-TS) algorithm, an extension of TS to the multiple-play MAB problem, and discuss its regret analysis. We prove that MP-TS for binary rewards has the optimal regret upper bound that matches the regret lower bound provided by Anantharam et al. (1987). Therefore, MP-TS is the first computationally efficient algorithm with optimal regret. A set of computer simulations was also conducted, which compared MP-TS with state-of-the-art algorithms. We also propose a modification of MP-TS, which is shown to have better empirical performance.