Thompson Sampling: Why Randomised Exploration Beats Greedy Optimisation

Imagine you run an online experiment with several versions of a webpage, several drug doses, or several ad creatives. Each option pays off at an unknown rate, and every trial costs you a chance to earn from the best option you already know. Play it safe and you may lock in a mediocre choice forever. Explore forever and you waste trials on options you already suspect are weak. This is the multi-armed bandit problem, and Thompson sampling is the Bayesian answer that has quietly become a default in industry experimentation, recommender systems, and adaptive trials.

The idea is disarmingly simple: keep a posterior belief about each option, sample one plausible world from that belief, and act as if the sample were true. Options that might be best get played often. Options that are almost certainly poor get played rarely, but never with probability exactly zero while doubt remains. Exploration is not bolted on as a random coin flip. It emerges from uncertainty itself.

The bandit problem, stated precisely

At each round t = 1, 2, ..., T, an agent chooses an arm a_{t} from K arms and observes a reward r_{t}. In the simplest stochastic setting, arm k has an unknown mean reward:

$$\mu_{k} = \mathbb{E}[r \mid a = k]$$

The regret after T rounds measures what was lost by not always playing the best arm:

$$R_{T} = T \cdot \max_{k} \mu_{k} - \sum_{t=1}^{T} \mathbb{E}[r_{t}]$$

A good algorithm keeps regret growing slowly, ideally logarithmically in T for a fixed set of arms. Greedy play, which always picks the arm with the highest observed average so far, fails this test badly. If an early unlucky run makes the best arm look poor, greedy play may never return to it, and regret grows linearly. That failure is not a quirk of small samples. It is structural: greedy play confuses "has not been observed to be good" with "is not good".

Thompson sampling in one paragraph

Thompson sampling, proposed by William Thompson in 1933 and revived by the modern bandit literature, maintains a posterior distribution over each arm's mean. At each round it draws one sample from each posterior, plays the arm with the largest sampled value, observes the reward, and updates that arm's posterior. That is the whole algorithm. The sampling step does two jobs at once: it exploits what is known, because arms with high posterior means usually produce high samples, and it explores what is uncertain, because arms with wide posteriors sometimes produce high samples even when their means are modest.

Formally, let H_{t-1} denote the history before round t, and let P_{t-1} be the posterior over the vector of means given that history. Thompson sampling plays arm k with probability equal to its posterior probability of being optimal:

$$\mathbb{P}(a_{t} = k \mid H_{t-1}) = \mathbb{P}(\mu_{k} = \max_{j} \mu_{j} \mid H_{t-1})$$

This property is called probability matching. It is why the method feels so natural: the frequency with which you try an option matches your current belief that it is the best one.

A worked case: Beta-Bernoulli bandits

The cleanest case is binary rewards, such as clicks or conversions. Suppose arm k succeeds with unknown probability theta_{k}. Put a Beta prior on each theta_{k}:

$$\theta_{k} \sim \mathrm{Beta}(\alpha_{k}, \beta_{k})$$

A uniform prior corresponds to alpha_{k} = 1 and beta_{k} = 1. After observing s successes and f failures on arm k, conjugacy gives a posterior that is again Beta:

$$\theta_{k} \mid \text{data} \sim \mathrm{Beta}(\alpha_{k} + s, \beta_{k} + f)$$

Each round, sample theta_{k} from its posterior for every k, play the arm with the largest sample, and increment s or f for the arm played. No optimisation, no confidence bound to tune, no exploration rate to schedule. The posterior width does the scheduling for you: early on, when s and f are small, samples vary wildly and exploration is heavy; later, posteriors concentrate and play concentrates on the winner.

A short implementation makes the point concrete:

import numpy as np

class BetaThompson:
    def __init__(self, n_arms):
        self.alpha = np.ones(n_arms)
        self.beta = np.ones(n_arms)

    def choose(self):
        samples = np.random.beta(self.alpha, self.beta)
        return int(np.argmax(samples))

    def update(self, arm, reward):
        if reward == 1:
            self.alpha[arm] += 1
        else:
            self.beta[arm] += 1

Notice what is absent: there is no epsilon to decay, no bonus term to calibrate, and no separate exploration phase. If you add a new arm mid-experiment, give it a wide prior and Thompson sampling will try it automatically, in proportion to how plausible it is that the new arm is best.

Beyond binary rewards: Gaussian Thompson sampling

Binary rewards are not the only tractable case. For rewards that are roughly continuous, a common model puts a Gaussian prior on each mean and assumes Gaussian observation noise with known variance sigma^{2}. After n_{k} observations on arm k with sample mean m_{k}, the posterior for mu_{k} is Gaussian with a mean that is a precision-weighted average of the prior mean and m_{k}, and a variance that shrinks as n_{k} grows. Sampling from those Gaussians and playing the argmax gives Gaussian Thompson sampling, and the same probability-matching intuition carries over.

The pattern generalises. Whenever you can sample from a posterior, you can run Thompson sampling: linear bandits with Gaussian posteriors over weight vectors, logistic models with approximate posteriors, and neural bandits with ensembles or dropout used as a rough posterior sampler. The algorithm is a template, not a single formula, and its quality depends on the quality of the posterior approximation you plug in.

Why not epsilon-greedy or UCB?

Epsilon-greedy explores blindly. With probability epsilon it picks a uniformly random arm, regardless of whether that arm is a plausible winner or a known loser. That wastes trials, and a fixed epsilon never stops exploring at the right rate, while a decaying epsilon schedule must be tuned by hand and can decay too fast.

Upper confidence bound (UCB) methods explore optimistically: they play the arm with the highest value of an estimated mean plus a bonus that shrinks with the number of pulls. UCB is principled and comes with strong regret guarantees, but the bonus is a design choice, and in complex models such as contextual bandits or neural models, constructing a trustworthy bonus is hard. Thompson sampling sidesteps the bonus entirely. Uncertainty enters through the posterior sample, so the same code works wherever a posterior sampler exists.

There is also a practical advantage that matters in production. Thompson sampling is easy to explain to non-technical stakeholders: "we show each variant in proportion to our current belief that it is best." That sentence is almost literally the algorithm, and it makes the exploration-exploitation trade-off legible to product and clinical teams who would rightly distrust a tuned bonus term.

Regret: what theory actually says

For Beta-Bernoulli bandits, Thompson sampling achieves regret that grows like log T, matching the information-theoretic lower bound up to constants. The intuition behind the proof is instructive even without the details. An arm can only be played often if it often looks optimal under posterior samples, and that can only happen while its posterior still assigns substantial mass above the true best mean. As data accumulate, the posterior for a suboptimal arm concentrates below the optimum, its samples stop winning, and its play frequency collapses. Exploration is self-limiting: you explore an arm exactly as long as the data leave room to believe in it.

That said, theory comes with conditions. The logarithmic regret result assumes a well-specified model and a stationary environment. Break those assumptions and the guarantees weaken, which leads directly to the pitfalls below.

Common pitfalls

A bad prior is not harmless. A strongly informative prior that is wrong can suppress a good arm for a long time, because its posterior starts narrow and needs many observations to move. In practice, use weakly informative priors, especially for new arms, and sanity-check prior predictive behaviour before launch.

Nonstationarity breaks the posterior. If arm means drift over time, a posterior that pools all history equally will be slow to adapt. Standard fixes include sliding windows, discounting old observations, or explicitly modelling drift. Running vanilla Thompson sampling on a drifting system and expecting it to track changes is a common production mistake.

Delayed feedback distorts learning. If rewards arrive hours or days after the choice, the posterior lags reality and the algorithm keeps sampling from stale beliefs. Batch updates, or models that account for pending observations, are needed when feedback is slow.

Probability matching is not fairness. Thompson sampling allocates trials in proportion to the probability of being best, not equally. Stakeholders who expect equal exposure during an experiment will be surprised. Agree the allocation rule before launch, and monitor it, rather than discovering the imbalance in a review meeting.

Approximate posteriors can mislead. With neural models, an ensemble or dropout distribution is only a rough posterior. If the approximation is overconfident, exploration collapses and the method degenerates into greedy play with extra steps. Check calibration: do arms that the model calls certain actually behave certainly?

Contextual Thompson sampling

The most useful extension adds context. In a recommender or ad system, the best arm depends on the user, the time of day, or the page. Linear contextual Thompson sampling models the expected reward of arm k in context x as a linear function:

$$\mathbb{E}[r \mid x, a = k] = x^{\top} w_{k}$$

with a Gaussian posterior over each weight vector w_{k}. At each round, sample a weight vector per arm, score each arm in the current context, and play the argmax. The same probability-matching logic now operates conditionally on context, so exploration is targeted: the algorithm explores arms that might be best for this kind of user, not arms that are best on average.

This is where Thompson sampling earns its keep in real systems. Contextual UCB requires a confidence ellipsoid per arm and careful tuning; contextual Thompson sampling requires a posterior sampler, which many Bayesian linear models provide for free.

When to use it, and when not to

Use Thompson sampling when rewards are observed reasonably quickly, the model class is roughly right, and you want an adaptive experiment that balances learning and earning without a hand-tuned exploration schedule. It is a strong default for A/B/n testing, content recommendation, and adaptive allocation.

Avoid it, or adapt it heavily, when the environment drifts fast, when feedback is severely delayed, when a wrong prior could be costly, or when you need guaranteed equal allocation or strict experimental control for a causal claim. In those cases a fixed randomised design, or a bandit variant built for nonstationarity, may be the honest choice.

Takeaway

Greedy play fails because it treats absence of evidence as evidence of absence. Epsilon-greedy patches that failure with blind randomness. Thompson sampling fixes it at the source: it turns uncertainty into a probability, samples a plausible world, and acts optimally in that world. When the posterior is honest, exploration takes care of itself, in exactly the proportion that current belief justifies.

---

Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial