Thompson Sampling: An Asymptotically Optimal Finite Time Analysis

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.

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

References in corpus (2)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

Cited by in corpus (8)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Thompson Sampling for Learning Parameterized Markov Decision Processes
• Learning to Optimize Via Posterior Sampling
• Learning the distribution with largest mean: two bandit frameworks
• Group Fairness in Bandit Arm Selection
• Convolutional Monte Carlo Rollouts in Go
• CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption
• GNU Radio Implementation of MALIN: "Multi-Armed bandits Learning for Internet-of-things Networks"