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

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