Source-linked AI summary
Prior-free and prior-dependent regret bounds for Thompson Sampling
Sébastien Bubeck, Che-Yu Liu
TL;DR
The paper asks how Thompson Sampling performs under priors on reward distributions, especially when dependent priors make optimal Bayesian strategies hard to compute. It analyzes posterior sampling and proves improved prior-free and BPR-setting regret guarantees. Under the BPR assumptions, its regret is uniformly bounded over time.
Problem
With non-product priors, finding the optimal Bayesian strategy can be computationally impractical, motivating evaluation through Bayesian regret.
Source: §1 · p. 2Method
Thompson Sampling draws a parameter from the posterior given observed history and chooses an arm with the highest mean under that draw.
Source: §1 · p. 2Results
Thompson Sampling removes the extraneous logarithmic factor in prior-free Bayesian-regret bounds and, in the BPR setting, has regret uniformly bounded over time without the BPR policy’s log-log factor.
Source: §1 · p. 3Takeaways & Limitations
In the BPR setting, Thompson Sampling can use known best-arm value and a lower bound on the smallest gap to attain a time-uniform regret bound.
Source: §1 · p. 3Extending the prior-dependent results to arbitrary priors is a challenging open problem beyond the paper’s current techniques.
Source: §1 · p. 3
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames Bayesian regret as a way to assess Thompson Sampling when informative, dependent priors make optimal Bayesian strategies hard to compute. It previews a prior-free improvement and uniformly bounded regret for Thompson Sampling under the BPR setting’s prior information.
1 Introduction
- The Bayesian bandit model places a known prior on reward distributions, and Bayesian regret averages performance over the parameter, rewards, and algorithmic randomness.Arms yield rewards in [0, 1] that are independent and identically distributed conditionally on the parameter.Source: §1 · pp. 1–2
- For non-product priors, the optimal Bayesian strategy may be computationally impractical, so the paper evaluates Thompson Sampling through Bayesian regret.Such priors can represent shared information across arms, including known arm distributions up to a permutation.Source: §1 · p. 2
- Thompson Sampling draws a parameter from the posterior given past history, then selects an arm with the highest mean under that draw.The paper studies this strategy with potentially hand-tuned priors rather than restricting attention to a Beta prior.Source: §1 · p. 2
- The paper removes the extraneous logarithmic factor in prior-free Bayesian-regret bounds for Thompson Sampling, using ideas reminiscent of MOSS.The earlier bound discussed is Russo and Roy [2013].Source: §1 · pp. 2–3
- In the BPR setting, Thompson Sampling achieves regret uniformly bounded over time and removes the BPR policy’s extraneous log-log factor.The setting assumes a known best-arm value and a non-trivial lower bound on the gap to other arms.Source: §1 · p. 3
2 Optimal prior-free regret bound for Thompson Sampling
Thompson Sampling is shown to achieve a prior-free Bayesian-regret guarantee, and a prior-specific lower bound establishes that this guarantee cannot be improved.
2 Optimal prior-free regret bound for Thompson Sampling
- For every prior over reward distributions in [0, 1], Thompson Sampling satisfies the theorem’s prior-free Bayesian-regret guarantee.The supplied theorem passage does not expose the bound’s value.Source: §2 · p. 3
- A prior exists under which every algorithm incurs a Bayesian-regret lower bound, making the prior-free guarantee unimprovable.The lower-bound statement is supported across the split passages p31 and p32.Source: §2 · p. 3
- The proof rewrites Bayesian regret through upper-confidence bounds and uses a MOSS-inspired choice to control deviations.The proof outline attributes the regret rewriting to Russo and Roy [2013] and describes the choice as inspired by Audibert and Bubeck [2009].Source: §2 · p. 4
3 Thompson Sampling in the two-armed BPR setting
The paper analyzes Thompson Sampling in the two-armed BPR setting, where the optimal mean and gap are known. Its policy has a regret bound uniform over time, with a limited simulation suggesting an advantage over Bubeck et al.’s policy.
3 Thompson Sampling in the two-armed BPR setting
- The setting has two arms with means µ* and µ*−∆, where the largest mean and gap are known.The analysis considers sub-Gaussian reward distributions.Source: §3 · p. 6
- Thompson Sampling draws an environment from the posterior and pulls that environment’s best arm.The policy is derived for two possible assignments of the optimal arm, with a uniform prior and Gaussian rewards of variance 1.Source: §3 · p. 6
- For the two-armed BPR setting with any sub-Gaussian reward distribution (not necessarily Gaussian), Figure 1’s policy has regret R_n ≤ Δ + 578/Δ, uniformly in n.Source: §3 · p. 6
- A limited simulation suggests the policy outperforms Bubeck et al. [2013]’s Policy 1 on Gaussian rewards with variance 1.The passage notes that Policy 1 has a regret bound of order 16/∆.Source: §3 · p. 6, Figure 2 · p. 8
4 Optimal strategy for the BPR setting inspired by Thompson Sampling
This section adapts a Thompson-inspired policy to the general BPR setting, where rewards are sub-Gaussian and the optimal mean and gap lower bound are known. The policy is reported to improve the BPR policy’s regret bound by a log-log term, with a bound uniform in n.
4 Optimal strategy for the BPR setting inspired by Thompson Sampling
- The general BPR setting assumes sub-Gaussian rewards, a known optimal mean µ*, and a known ε separating the best arm from the others.The optimal arm is unique, and all other means are below µ*−ε.Source: §4 · p. 9
- Gaussian rewards with variance 1 derive the sampling rule, but the analysis does not require Gaussian rewards and applies to sub-Gaussian distributions.Source: §4 · p. 10
- The policy samples each arm once in the first K rounds, then randomizes from p_t; its construction uses a slightly larger variance for the proof.The policy draws on Thompson Sampling, and the increased variance is stated as necessary for the proof.Source: §4 · p. 10, Figure 3 · p. 10
- The Figure 3 policy is reported to attain the best-known BPR performance, shaving a log-log term from the BPR policy’s regret bound, uniformly in n.The theorem passage gives no recoverable numerical bound.Source: §4 · p. 10