Analysis of Thompson Sampling for the multi-armed bandit problem

2011/11/08 by Shipra Agrawal, Agrawal, Shipra, Navin Goyal +1 · 8 citations
Computer Science · Decision Sciences · #68Q25 #68W40 #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #F.2.0 #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1111.1797

openalex publication_date 2011/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by W. R. Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In addition, it is efficient to implement and exhibits several desirable properties such as small regret for delayed feedback. However, theoretical understanding of this algorithm was quite limited. In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the multi-armed bandit problem. More precisely, for the two-armed bandit problem, the expected regret in time T is O(\fracln TΔ + (1)/(Δ³)). And, for the N-armed bandit problem, the expected regret in time T is O([(∑_i=2^N (1)/(Δ_i²))²] ln T). Our bounds are optimal but for the dependence on Δ_i and the constant factors in big-Oh.

Cited by

• Simple Algorithms for Dueling Bandits
• Adaptive Combinatorial Allocation
• Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Group Fairness in Bandit Arm Selection
• Stochastic Multi-Armed Bandits with Control Variates
• Simple Regret Minimization for Contextual Bandits
• Causal Bandits with Unknown Graph Structure
• Near-optimal Bayesian Solution For Unknown Discrete Markov Decision Process

Related

• Further Optimal Regret Bounds for Thompson Sampling
• Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed\n Bandit Problem with Multiple Plays
• Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms
• Thompson Sampling for Complex Bandit Problems