Abstract
We consider the stochastic multi-armed bandit problem with a prior distribution on the reward distributions. We are interested in studying prior-free and prior-dependent regret bounds, very much in the same spirit as the usual distribution-free and distribution-dependent bounds for the non-bayesian stochastic bandit. Building on the techniques of Audibert and Bubeck [2009] and Russo and Roy [2013] we first show that Thompson Sampling attains an optimal prior-free bound in the sense that for any prior distribution its Bayesian regret is bounded from above by $14 \sqrt{n K}$. This result is unimprovable in the sense that there exists a prior distribution such that any algorithm has a Bayesian regret bounded from below by $\frac{1}{20} \sqrt{n K}$. We also study the case of priors for the setting of Bubeck et al. [2013] (where the optimal mean is known as well as a lower bound on the smallest gap) and we show that in this case the regret of Thompson Sampling is in fact uniformly bounded over time, thus showing that Thompson Sampling can greatly take advantage of the nice properties of these priors.
Introduction
The multi-armed bandit (MAB) problem serves as the fundamental framework for studying the exploration-exploitation trade-off. Thompson Sampling (TS), introduced in 1933, offers a Bayesian solution by maintaining a prior distribution over arm rewards and sampling from it to guide action selection. Despite its long history and strong empirical performance, theoretical guarantees for TS have historically lagged behind frequentist methods like Upper Confidence Bound (UCB) algorithms. Previous bounds often contained suboptimal logarithmic factors or were restricted to specific reward distributions.
This work addresses two critical questions:
- Can Thompson Sampling achieve minimax optimal "prior-free" regret?
- Can TS effectively exploit informative priors to achieve superior "prior-dependent" performance?
Methodology
The authors employ a theoretical framework that bridges Bayesian and frequentist analysis. Key methodological contributions include:
- Regret Decomposition via UCBs: By expressing Bayesian regret in terms of UCBs, the authors leverage established frequentist tools to analyze the Bayesian TS algorithm.
- MOSS-style Analysis: To eliminate the $\sqrt{\log n}$ factor present in earlier proofs, the authors adapt techniques from the Minimax Optimal Strategy in the Stochastic case (MOSS) algorithm. This involves a refined analysis of the tail probabilities of reward distributions.
- Analysis in the BPR Setting: The paper examines the setting proposed by Bubeck, Perchet, and Rigollet (BPR), where the agent possesses structural knowledge, specifically the value of the optimal mean ($\mu^*$) and a lower bound on the gap ($\Delta$) between the best and sub-optimal arms.
Theoretical Results
The paper establishes two primary theoretical milestones:
Minimax Optimality (Prior-Free)
The authors prove that for any prior distribution on rewards supported in $[0, 1]$, the Bayesian regret ($BR_n$) of Thompson Sampling is bounded by: $$BR_n \leq 14\sqrt{nK}$$ This result matches the known lower bound for any bandit algorithm, establishing TS as a minimax optimal strategy without the logarithmic overhead found in previous analyses (e.g., $5\sqrt{nK \log n}$).
Bounded Regret (Prior-Dependent)
In the BPR setting, TS demonstrates the ability to achieve uniformly bounded regret. For a two-armed bandit, the regret is bounded by $\Delta + \frac{578}{\Delta}$, a value independent of the time horizon $n$. For the $K$-armed case, the bound is $O\left(\sum_{i:\Delta_i>0} \left(\Delta_i + \frac{\log(\Delta_i/\epsilon)}{\Delta_i}\right)\right)$. This implies that with sufficient structural information, the total error of TS stops growing as time approaches infinity.
Empirical Evaluation
The authors conducted synthetic simulations using Gaussian reward distributions (variance 1) to compare the TS-based policy against the specialized BPR algorithm. The results validate the theoretical findings, showing that the TS-inspired policy not only achieves bounded regret but also converges to its regret ceiling faster and at a lower absolute value than the previous state-of-the-art.
Conclusion
This research confirms that Thompson Sampling is not merely a heuristic but a theoretically robust algorithm. It achieves minimax optimality across arbitrary priors and can naturally exploit structural information to reach bounded regret. While the bounded regret results currently rely on specific assumptions (the BPR setting), extending these findings to more general informative priors remains a significant area for future research.
Summary updated