Thompson Sampling

The algorithm is one line: maintain a posterior over each arm's reward parameter, draw one sample from each, and pull the arm whose sample is highest. It was proposed in 1933, ignored for most of a century, and is now the default in production bandit systems because it is simple, it performs at least as well as UCB empirically, and it has properties that matter in deployment that UCB does not.

Why it explores correctly

The probability of selecting an arm equals the posterior probability that the arm is optimal. That is exactly the right amount of exploration: an arm the data strongly rules out is almost never chosen, one that is plausibly best is chosen in proportion to how plausible it is, and an arm about which nothing is known has a wide posterior and gets sampled often.

No exploration parameter appears anywhere. The uncertainty in the posterior does the work, and it narrows automatically as evidence accumulates. Regret bounds matching the logarithmic lower bound have been established for the Bernoulli and linear cases, so the empirical performance has theoretical backing.

For Bernoulli rewards with a Beta prior the implementation is trivial: keep successes and failures per arm, sample from \(\text{Beta}(\alpha_i + s_i, \beta_i + f_i)\), take the argmax. This is a few lines of code and is what most production systems run.

Why it fits production

Randomisation gives natural parallelism. Every decision draws its own samples, so simultaneous decisions spread across arms rather than concentrating on one. A system making thousands of decisions before any feedback returns behaves sensibly, which UCB does not.

Delayed feedback degrades it gracefully. With outcomes arriving late, the posterior is simply less updated, so the algorithm explores more, which is the correct response to having less information. UCB's bonus depends on total time rather than on observed feedback, so it becomes overconfident under delay.

The propensity is computable. Because selection is probabilistic, the probability of each action can be estimated by sampling, which is exactly what off-policy evaluation needs. A deterministic policy logs no propensities and cannot be evaluated counterfactually, which makes the resulting data far less useful.

When it breaks

Model misspecification is silent. The posterior is only meaningful if the likelihood is right. A Beta-Bernoulli model applied to a reward that is not Bernoulli produces a confident, wrong posterior, and the algorithm explores according to a certainty it has not earned.

Priors matter early and are chosen carelessly. With few observations the prior dominates, so an overconfident prior suppresses exploration exactly when it is most needed. Weakly informative priors are the safe default and an uninformative one is not always available.

Posterior sampling is expensive for complex models. Beta-Bernoulli is closed-form; a neural reward model is not, and approximations such as bootstrapped ensembles, Monte Carlo dropout or Langevin sampling are used instead. Each approximates the posterior badly in its own way, and the exploration behaviour inherits the approximation's failure mode.

Non-stationarity again requires modification. A posterior built from all history is increasingly confident about a world that has changed. Discounting old observations, or inflating the posterior variance, restores adaptivity and reintroduces a parameter encoding the assumed rate of change.