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

2015/06/02 by Junpei Komiyama, Komiyama, Junpei, Junya Honda +3 · 12 citations
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Machine Learning and Algorithms #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1506.00779

Abstract

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

Cited by

• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing
• Multiple-Play Bandits in the Position-Based Model
• Position-Based Multiple-Play Bandits with Thompson Sampling
• Accelerated learning from recommender systems using multi-armed bandit
• Decentralized Asynchronous Multi-player Bandits
• Online Learning with Probing for Sequential User-Centric Selection
• On the Prior Sensitivity of Thompson Sampling
• Constant or logarithmic regret in asynchronous multiplayer bandits
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
• Double Thompson Sampling for Dueling Bandits
• A survey on multi-player bandits
• Correcting for Position Bias in Learning to Rank: A Control Function Approach

Related

• Analysis of Thompson Sampling for the multi-armed bandit problem
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms
• Lenient Regret for Multi-Armed Bandits
• Further Optimal Regret Bounds for Thompson Sampling
• Thompson Sampling for Combinatorial Semi-Bandits