Thompson Sampling Explained: The Bayesian Approach to Optimization

Why Thompson Sampling?

Among the many multi-armed bandit algorithms, Thompson Sampling consistently delivers the best empirical performance. It was originally proposed in 1933 by William R. Thompson, but it took decades for the theoretical community to prove what practitioners already knew: it works remarkably well.

The core idea is elegant. Instead of using fixed rules (like epsilon-greedy's random exploration) or optimistic heuristics (like UCB1's confidence bounds), Thompson Sampling uses probability matching: it selects each arm with a probability equal to the probability that arm is the best.

The Beta Distribution

For binary outcomes (convert or don't convert), Thompson Sampling uses the Beta distribution to model uncertainty about each arm's true conversion rate.

A Beta distribution is defined by two parameters:

• alpha (α): number of successes plus 1
• beta (β): number of failures plus 1

Starting from Beta(1, 1) (uniform, since we know nothing), the distribution updates as we observe outcomes:

• Success → Beta(α + 1, β)
• Failure → Beta(α, β + 1)

Use the explorer below to see how the distributions evolve. Add successes and failures to each arm and watch the posteriors narrow and separate.

How the Algorithm Works

At each step, Thompson Sampling:

1. Samples a random value from each arm's Beta distribution
2. Selects the arm with the highest sampled value
3. Observes the outcome (success or failure)
4. Updates the selected arm's distribution

That's it. No tuning parameters. No epsilon values. No confidence bounds to compute.

Why This Works

The magic is in the sampling step. Consider two arms:

• Arm A: Beta(20, 80), observed 20% conversion rate, fairly certain
• Arm B: Beta(3, 7), observed 30% conversion rate, very uncertain

Arm B has a higher observed rate, but we're much less certain about it. When we sample from these distributions:

• Arm A's samples cluster tightly around 0.20
• Arm B's samples spread widely, sometimes above 0.40, sometimes below 0.10

Arm B gets explored because we're uncertain about it. Once we gather more data and its distribution tightens, it will either prove itself (and get exploited) or fall behind (and get abandoned). The uncertainty itself drives exploration.

Posterior Convergence

As data accumulates, Beta distributions narrow. After enough observations, the distributions separate clearly and the algorithm spends almost all its time exploiting the best arm.

The convergence rate depends on the separation between the true rates:

• Large separation (e.g., 20% vs 80%): converges in ~50 trials
• Moderate separation (e.g., 40% vs 60%): converges in ~200 trials
• Small separation (e.g., 48% vs 52%): converges in ~2,000+ trials

This is actually optimal. The algorithm spends exploration budget proportional to how hard the problem is.

Thompson Sampling vs Other Algorithms

vs Epsilon-Greedy

Epsilon-Greedy explores uniformly at a fixed rate. It wastes exploration on arms that are clearly bad. Thompson Sampling focuses exploration on arms whose performance is uncertain, making every exploratory pull more informative.

vs UCB1

UCB1 is deterministic: given the same data, it always picks the same arm. Thompson Sampling is stochastic, so the random sampling means it occasionally tries suboptimal arms even when it's fairly confident. That randomness makes it more robust to non-stationary environments where the best arm can change over time.

Empirical Comparison

In benchmarks across thousands of simulated scenarios:

Thompson Sampling wins on both median and worst-case regret.

The Conjugate Prior Advantage

For binary outcomes, the Beta-Bernoulli model is a conjugate pair: the posterior has the same functional form as the prior. This means:

• No approximation needed (exact Bayesian inference)
• Updates are O(1): just increment two counters
• Sampling from Beta distributions is computationally cheap
• No iterative algorithms, no convergence issues

This is why Thompson Sampling is so practical for production systems. The per-request computation is negligible: sample from a Beta distribution and compare.

Beyond Binary Outcomes

Thompson Sampling extends to continuous outcomes (revenue, time on page) using different distribution families:

• Binary outcomes → Beta-Bernoulli
• Count data → Gamma-Poisson
• Continuous outcomes → Normal-Normal (Gaussian)
• Contextual features → Linear models with Gaussian priors

The Bandit platform currently supports Beta-Bernoulli Thompson Sampling for conversion optimization, which covers the majority of web optimization use cases.

Implementation Details

In the Bandit platform, Thompson Sampling state is maintained per experiment:

For each arm:
  α = number of conversions + 1
  β = number of non-conversions + 1

When an assignment is requested:

1. Sample θ_i ~ Beta(α_i, β_i) for each arm
2. Select arg max θ_i
3. Return the corresponding treatment

When a conversion is tracked:

1. Identify the arm from the assignment
2. Increment α for that arm

The entire operation runs in sub-millisecond time with in-memory state, making it suitable for high-traffic applications.

Key Takeaways

• Thompson Sampling is the recommended default algorithm for most optimization scenarios
• It uses Beta distributions to model uncertainty about conversion rates
• Exploration emerges naturally from uncertainty, with no tuning required
• It achieves the lowest empirical regret among standard bandit algorithms
• The computation is trivial: sample, compare, update two counters
• It works best for binary outcomes but extends to other outcome types

When in doubt, use Thompson Sampling. It's the algorithm that combines theoretical elegance with practical performance.