Thompson Sampling: An Asymptotically Optimal Finite Time Analysis

2012/05/18 by Emilie Kaufmann, Kaufmann, Emilie, Nathaniel Korda +3 · 13 citations
Computer Science · Decision Sciences · Engineering · #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

paper · doi:10.48550/arxiv.1205.4217

openalex publication_date 2012/05/18 · 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 `a Data\n Scientist

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