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

Abstract

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.

Appeared in ICML2015. Fixed the evaluation of term (B) in Lemma 3. Replaced \tildeμ->θ

Cited by in corpus (16)

• Multiple-Play Bandits in the Position-Based Model
• Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
• Beyond the Click-Through Rate: Web Link Selection with Multi-level Feedback
• Adversarial Online Learning with Variable Plays in the Pursuit-Evasion Game: Theoretical Foundations and Application in Connected and Automated Vehicle Cybersecurity
• On the Prior Sensitivity of Thompson Sampling
• Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits
• Position-Based Multiple-Play Bandits with Thompson Sampling
• A survey on multi-player bandits
• On Thompson Sampling for Smoother-than-Lipschitz Bandits
• Accelerated learning from recommender systems using multi-armed bandit
• Bounded Regret for Finitely Parameterized Multi-Armed Bandits
• Sequential ranking under random semi-bandit feedback
• Constant or logarithmic regret in asynchronous multiplayer bandits
• Multi-level Feedback Web Links Selection Problem: Learning and Optimization
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation