Thompson Sampling: An Asymptotically Optimal Finite Time Analysis

05/18/2012
by   Emilie Kaufmann, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset