On the Prior Sensitivity of Thompson Sampling
arXiv:1506.03378
Abstract
The empirically successful Thompson Sampling algorithm for stochastic bandits has drawn much interest in understanding its theoretical properties. One important benefit of the algorithm is that it allows domain knowledge to be conveniently encoded as a prior distribution to balance exploration and exploitation more effectively. While it is generally believed that the algorithm's regret is low (high) when the prior is good (bad), little is known about the exact dependence. In this paper, we fully characterize the algorithm's worst-case dependence of regret on the choice of prior, focusing on a special yet representative case. These results also provide insights into the general sensitivity of the algorithm to the choice of priors. In particular, with being the prior probability mass of the true reward-generating model, we prove and regret upper bounds for the bad- and good-prior cases, respectively, as well as \emph{matching} lower bounds. Our proofs rely on the discovery of a fundamental property of Thompson Sampling and make heavy use of martingale theory, both of which appear novel in the literature, to the best of our knowledge.
arXiv commentAppears in the 27th International Conference on Algorithmic Learning Theory (ALT), 2016
References in corpus (9)
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Further Optimal Regret Bounds for Thompson Sampling
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays
- Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors
- Thompson Sampling for Budgeted Multi-armed Bandits
- Generalized Thompson Sampling for Contextual Bandits
- Approximation Algorithms for Bayesian Multi-Armed Bandit Problems