Source-linked AI summary
Thompson Sampling: An Asymptotically Optimal Finite Time Analysis
Emilie Kaufmann, Nathaniel Korda, Rémi Munos
TL;DR
The paper addresses whether Thompson Sampling is optimal for stochastic bandits, focusing on Bernoulli rewards. It develops a finite-time analysis and compares the policy numerically with established alternatives, proving asymptotic optimality and reporting favorable simulations.
Problem
The optimality of Thompson Sampling for stochastic multi-armed bandits remained unresolved for Bernoulli rewards despite earlier weaker or absent theoretical guarantees.
Method
The paper analyzes posterior-sampled arm selection under Thompson Sampling and derives a finite-time regret bound using Beta-Binomial tools and control of optimal-arm sampling tails.
Results
The paper proves the first asymptotic optimality result for Thompson Sampling in Bernoulli bandits and provides simulations comparing it with other known optimal policies.
Takeaways & Limitations
Thompson Sampling achieves the optimal asymptotic regret rate of Lai and Robbins and is presented as an alternative to UCB policies for bounded rewards.
Takeaways & Limitations
The proof is specialized to Bernoulli rewards, and extending it to more complex reward distributions is described as challenging.
Abstract
from arXiv · showhide
The question of the optimality of Thompson Sampling for solving the stochastic multi-armed bandit problem had been open since 1933. In this paper we answer it positively for the case of Bernoulli rewards by providing the first finite-time analysis that matches the asymptotic rate given in the Lai and Robbins lower bound for the cumulative regret. The proof is accompanied by a numerical comparison with other optimal policies, experiments that have been lacking in the literature until now for the Bernoulli case.
1 Introduction
The paper studies Thompson Sampling for Bernoulli stochastic bandits and provides a finite-time regret analysis establishing asymptotic optimality, alongside numerical comparisons with other policies.
- Problem setting: Stochastic bandits require balancing immediate reward exploitation against exploratory actions that may yield future gains.Each action has an unknown reward distribution, and the agent seeks to minimize expected cumulative regret.
- Optimality gap: Lai and Robbins characterize asymptotically optimal policies as achieving their lower-bound regret rate, while earlier efficient UCB-style policies lacked this equality guarantee for Thompson Sampling.KL-UCB and DMED were known to be asymptotically optimal, whereas prior Thompson Sampling analyses supplied weaker or no theoretical guarantees.
- Thompson Sampling: Thompson Sampling samples each arm’s posterior parameter and selects the arm with the highest sampled expected reward.With uniform priors, the policy chooses an action according to the probability that it has the highest posterior expected reward.
- Contributions: The paper provides a finite-time regret bound for Thompson Sampling and proves the bound yields the Lai–Robbins asymptotic rate.The theorem holds for every ϵ > 0, with a problem-dependent constant in the regret bound.
- Experiments: Numerical experiments compare Thompson Sampling with UCB, KL-UCB, and Bayes-UCB, reporting stronger performance for Thompson Sampling at large horizons.The experiments use Bernoulli rewards and horizon T = 10000 across two two-arm problems.
2 Preliminaries
The preliminaries establish notation and distributional tools for the Bernoulli analysis, while assuming a unique optimal action and defining the indices used in comparisons.
- Assumptions: The analysis assumes action 1 is uniquely optimal, with µ1 > µ2 ≥ ... ≥ µK.This ordering is adopted without loss of generality.
- Notation: The paper defines success counts and empirical means for each action, then uses the resulting statistics in the analysis.Sa,t denotes the number of observed successes from action a by time t.
- Posterior distributions: With uniform priors and Bernoulli rewards, each arm’s posterior has an explicit Beta form.This conjugate structure supplies the posterior distributions used by Thompson Sampling.
- Distributional tools: The analysis repeatedly uses a Beta–Binomial relationship connecting Beta distributions with Binomial distribution functions and densities.The paper calls this relationship the “Beta-Binomial trick.”
- Comparison indices: KL-UCB and Bayes-UCB indices are defined using KL-based confidence and posterior quantile constructions, with the paper noting qa,t < ua,t.Q(α, π) denotes the quantile of order α of distribution π.
3 Finite Time Analysis
The analysis bounds suboptimal-arm draws by decomposing their causes and controlling under-estimation of the optimal arm. Proposition 1 enables concentration-based control, yielding a finite-time bound whose leading term establishes asymptotic optimality.
- Initial decomposition: The analysis decomposes a suboptimal-arm draw into optimal-arm under-estimation and suboptimal selection despite no under-estimation.This adapts the standard analysis of frequentist index policies to Thompson Sampling.
- Initial decomposition: Thompson Sampling cannot directly use an optimistic-index argument because its posterior samples are not upper-confidence estimates.When the optimal-arm posterior is concentrated, its sample can still fall below the true mean with substantial probability.
- Bounding the optimal arm: Proposition 1 shows that the probability of observing only a small number of optimal-arm draws is itself small.This permits analysis after the optimal-arm posterior has received enough observations to become well concentrated.
- Final bound: Theorem 2 holds for every ϵ > 0, and its regret bound therefore establishes the asymptotic optimality of Thompson Sampling.The bound includes the leading term K(µa, µ1) together with finite additive constants and D(ϵ, µ1, µa).
- Bounding term B: For term B, posterior samples from saturated suboptimal arms are controlled relative to posterior quantiles, with the remaining sum bounded by a finite constant.A suboptimal arm is saturated after at least Ca ln(t) selections, where Ca = 32(µ1−µa)^2.
- Bounding term A: The proof bounds term A with a self-normalized inequality adapted to Thompson Sampling’s per-round randomization and uses the Beta–Binomial link with concentration inequalities.The decomposition separates large-trial Binomial terms from the event controlled by Proposition 1.
4 Experiments
The experiments compare Thompson Sampling with UCB-based and other asymptotically optimal policies across two-arm and ten-arm Bernoulli bandits. Thompson Sampling performs especially well against the competing optimal policies and is comparatively simple to implement.
- Two-arm experiments: At horizon T = 10000, Thompson Sampling always outperforms KL-UCB and Bayes-UCB at large horizons in the two-arm experiments.The three optimal policies are significantly better than UCB, even for small horizons.
- Ten-arm experiment: Among the algorithms shown in Figure 2, Thompson Sampling has the best mean regret relative to the asymptotic lower bound.The lower bound is only asymptotic, so some algorithms can have mean regret closer to or sometimes smaller than it.
- Implementation: Thompson Sampling is described as the easiest optimal policy to implement because posterior sampling costs less than KL-UCB optimization or Bayes-UCB quantile computation.
- Two-arm experiments: Figure 1 averages cumulative regret over N = 20000 trials for two-arm problems with (µ1, µ2) = (0.2, 0.25) and (0.8, 0.9).
5 Discussion
The paper establishes Thompson Sampling’s asymptotic optimality for Bernoulli bandits through a finite-time proof and supports the result with simulations. It also identifies bounded rewards as an application scope while noting that broader reward-distribution generalizations remain challenging.
- Contributions: The paper provides the first proof of asymptotic optimality for Thompson Sampling in Bernoulli bandits.
- Empirical evidence: Simulations show that Thompson Sampling outperforms currently known optimal policies.
- Proof contribution: Tail control for N1,t yields a stronger result than controlling its expectation alone and supports a simpler finite-time analysis.
- Proof contribution: The finite-time analysis is closer to UCB-like arguments and achieves Lai and Robbins’s optimal asymptotic rate.
- Scope and limitations: Generalizing the proof to complex reward distributions remains challenging because it depends heavily on properties of Beta distributions.A broader result would need prior-dependent finite-time control of posterior-tail probabilities.