Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
By: Researcher
Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).
Please contact us in case of a broken link from here
| Authors | Nathaniel Korda, Rémi Munos, Emilie Kaufmann |
| Journal/Conference Name | arXiv preprint |
| Paper Category | Artificial Intelligence |
| Paper 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. |
| Date of publication | 2012 |
| Code Programming Language | MATLAB |
| Comment |
Copyright Researcher 2022