Abstract
The empirically successful Thompson Sampling (TS) 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 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.
Introduction
Thompson Sampling (TS) is a cornerstone of modern reinforcement learning and multi-armed bandit research. Its elegance lies in its Bayesian nature: by maintaining a posterior distribution over possible models, the algorithm naturally balances the need to explore uncertain actions with the desire to exploit known rewards. A primary advantage of TS is the ability to incorporate "domain knowledge" through a prior distribution.
Intuitively, a practitioner expects that a "good" prior—one that assigns high probability to the true state of the world—will lead to lower regret, while a "bad" prior will hinder performance. However, until recently, the exact mathematical relationship between prior quality and frequentist regret remained poorly understood. This paper provides the first rigorous characterization of this sensitivity, quantifying exactly how much Thompson Sampling helps or hurts based on the accuracy of the initial belief.
The Sensitivity Question
In a standard multi-armed bandit problem, an agent seeks to minimize cumulative regret over $T$ time steps. Thompson Sampling approaches this by sampling a model from the current posterior and acting optimally according to that sample. The central question addressed here is: If an agent assigns a prior probability $p$ to the true model, how does the expected regret scale with $p$ and $T$?
Previous theoretical bounds were often loose or included extraneous logarithmic factors that obscured the fundamental relationship. To isolate the effect of the prior, the authors focus on a minimalist yet representative "2-Actions-And-2-Models" setting. This simplification allows for a precise analysis of how the agent's belief evolves as it gathers data.
Methodology: The Martingale Innovation
The core technical contribution of this work is the application of Martingale Theory to the evolution of posterior beliefs. The authors identify a fundamental property of Thompson Sampling: the inverse of the posterior probability of the true model, $1/p_t(\theta^*)$, is a martingale.
By treating the agent's belief as a stochastic process, the analysis utilizes "hitting time" calculations—determining how long it takes for a belief to drift far enough to correct an initial error. Using Doob’s optional stopping theorem and other martingale tools, the authors bound the regret without relying on the standard information-theoretic or confidence-bound techniques that often lead to looser results. This approach provides a cleaner, more direct path to understanding the algorithm's dynamics.
Key Results
The paper establishes tight frequentist regret bounds, showing that the sensitivity to the prior is symmetric yet impactful:
- The Price of Skepticism (Poor Prior): When the prior probability $p$ of the true model is small, the regret scales as $\Theta\left(\sqrt{\frac{T}{p}}\right)$. This indicates that if the prior is poorly specified, regret does not just increase linearly; it explodes at a rate proportional to $1/\sqrt{p}$.
- The Reward of Accuracy (Good Prior): When the prior is high, the benefit scales as $\Theta\left(\sqrt{(1-p)T}\right)$. This quantifies the reduction in exploration needed when the agent starts with a strong, correct belief.
These bounds are "tight," meaning the upper and lower bounds match, leaving no hidden gaps. This confirms that the square-root scaling is a fundamental limit of the Thompson Sampling algorithm in this setting.
Empirical Validation
To complement the theoretical proofs, the authors conducted simulations using synthetic Bernoulli bandit instances. By running thousands of independent trials across varying values of $p$, they observed that the empirical regret curves matched the predicted $1/\sqrt{p}$ and $\sqrt{1-p}$ relationships with remarkable precision. These experiments verify that the martingale-based analysis captures the actual behavior of the algorithm in practice.
Discussion and Future Work
While the results provide a definitive answer for the 2-model case, they also open new avenues for research:
- Scaling to Many Models: While the authors provide corollaries for general cases, extending the tightest bounds to high-dimensional model spaces remains a conjecture.
- Structural Geometry: In many real-world applications, such as linear bandits, models are related. Future work is needed to determine how prior sensitivity changes when the model space has an underlying geometric structure.
- Algorithmic Robustness: The finding that TS is highly sensitive to bad priors suggests that modifications may be necessary for safety-critical applications. Techniques like "prior-averaging" or hybrid exploration strategies could potentially mitigate the $1/\sqrt{p}$ regret explosion while retaining the benefits of a good prior.
In summary, this work provides a rigorous mathematical foundation for what practitioners have long suspected: Thompson Sampling is a powerful tool for leveraging domain knowledge, but it carries a significant "price" if that knowledge is misplaced.
Summary updated