On the Prior Sensitivity of Thompson Sampling
This provides theoretical insights into the sensitivity of Thompson Sampling to priors, which is incremental but important for practitioners in bandit algorithms who rely on domain knowledge.
The paper tackles the problem of understanding how Thompson Sampling's regret depends on the choice of prior distribution in stochastic bandits, proving matching upper and lower bounds of O(√(T/p)) for bad priors and O(√((1-p)T)) for good priors, where p is the prior probability mass of the true model.
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 $p$ being the prior probability mass of the true reward-generating model, we prove $O(\sqrt{T/p})$ and $O(\sqrt{(1-p)T})$ 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.