Recognition: unknown
Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Spectral bandits
Spectral bandits achieve scalable regret in graph-structured recommendation by using an effective dimension to learn good policies from few node evaluations.
-
Budgeted Online Influence Maximization
A new algorithm for online influence maximization under a total budget constraint using the independent cascade model and edge-level semi-bandit feedback, with improved regret bounds for both budgeted and cardinality ...
-
Covariance-adapting algorithm for semi-bandits with application to sparse rewards
A covariance-adapting algorithm for semi-bandits achieves asymptotically tight regret bounds under a new sub-exponential distribution family, with direct application to sparse rewards.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.