Thompson Sampling: An Asymptotically Optimal Finite Time Analysis

2012/05/18 by Emilie Kaufmann, Kaufmann, Emilie, Nathaniel Korda +3 · 23 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Smart Grid Energy Management #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1205.4217

15 pages, 2 figures, submitted to ALT (Algorithmic Learning Theory)

openalex publication_date 2012/05/18 · arxiv created 2012/07/19 · arxiv updated 2012/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The question of the optimality of Thompson Sampling for solving the stochastic multi-armed bandit problem had been open since 1933. In this paper we answer it positively for the case of Bernoulli rewards by providing the first finite-time analysis that matches the asymptotic rate given in the Lai and Robbins lower bound for the cumulative regret. The proof is accompanied by a numerical comparison with other optimal policies, experiments that have been lacking in the literature until now for the Bernoulli case.

Cited by

• Information-directed sampling for bandits: a primer
• Bernstein-von Mises for Adaptively Collected Data
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
• Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
• No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes
• The Confusing Instance Principle for Online Linear Quadratic Control
• A Frequency-Domain Analysis of the Multi-Armed Bandit Problem: A New Perspective on the Exploration-Exploitation Trade-off
• Multi-Agent Stage-wise Conservative Linear Bandits
• A Bio-Inspired Minimal Model for Non-Stationary K-Armed Bandits
• CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption
• Asymptotically Optimal Problem-Dependent Bandit Policies for Transfer Learning
• Know When to Explore: Difficulty-Aware Certainty as a Guide for LLM Reinforcement Learning
• Big Data Analytics - Retour vers le Futur 3; De Statisticien à Data Scientist
• Group Fairness in Bandit Arm Selection
• Non-stationary Bandit Convex Optimization: A Comprehensive Study
• Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts
• Q-learning with Posterior Sampling
• Stable Thompson Sampling: Valid Inference via Variance Inflation
• Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
• Balancing Performance and Costs in Best Arm Identification
• Thompson Sampling for Learning Parameterized Markov Decision Processes
• Convolutional Monte Carlo Rollouts in Go
• A Classification View on Meta Learning Bandits

Related

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits
• Prior-free and prior-dependent regret bounds for Thompson Sampling
• Further Optimal Regret Bounds for Thompson Sampling
• MOTS: Minimax Optimal Thompson Sampling