Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis
TL
TL;DR
The question of the optimality of Thompson Sampling for solving the stochastic multi-armed bandit problem is answered 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.
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.
References14 items
1
On Bayesian Upper Confidence Bounds for Bandit Problems
2
An Empirical Evaluation of Thompson Sampling
3
Deviations of Stochastic Bandit Regret
4
A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
5