Thompson Sampling and Bayesian Bandits

A trading desk has five variants of an execution algorithm, each with an unknown true fill-rate advantage, and only limited order flow to test them with live. Route everything to the current best-looking variant, and you might lock into a false leader based on early noise, never discovering another variant is actually better. Split traffic evenly forever, and you waste flow testing variants already clearly worse. Thompson sampling navigates this tradeoff automatically, using nothing more exotic than a posterior distribution per option and a random draw.

An analogy: choosing a restaurant among several you're unsure about

Suppose you've tried five restaurants a handful of times each, and you're not fully sure which is genuinely best — some you've visited more (so you're more confident), some only once (so your belief is wide and uncertain). A sensible policy for where to eat tonight isn't "always the best average so far" (overcommits to noisy early impressions) and isn't "rotate evenly" (wastes visits on ones you're already fairly sure are worse). Instead: imagine a plausible "true quality" for each restaurant, drawn according to how confident and where-centered your current belief is, then go wherever looks best in that one imagined draw. An uncertain restaurant occasionally gets a lucky high draw and gets picked, giving it a fair chance to prove itself, while one you're confident is mediocre rarely draws high enough to win. This is Thompson sampling.

The maths, one symbol at a time

For each option (arm) $k = 1,\dots,K$, maintain a posterior distribution $p(\theta_k \mid D_k)$ over its true payoff $\theta_k$, based on data observed from that arm so far. At each decision point:

$$\tilde\theta_k \sim p(\theta_k \mid D_k) \text{ for each } k, \quad \text{then choose } k^* = \arg\max_k \tilde\theta_k$$

In words: draw one random sample from each arm's current posterior belief about its own true payoff, then pick whichever sampled value is highest this round. An arm with a wide, uncertain posterior occasionally produces a high sample purely from that uncertainty, giving it a chance to be explored; an arm with a narrow posterior confidently centered on a mediocre value almost never produces a high enough sample to win. As data accumulates on each arm, its posterior narrows around its true payoff, and the sampled draws increasingly reflect the true ranking rather than noise — exploration tapers off naturally, with no separate schedule to hand-tune.

Worked example 1: two execution variants after limited data

Variant A has been tested 40 times with 28 successes, giving a Beta$(28,12)$ posterior (mean $\approx 0.70$, fairly tight). Variant B has been tested only 5 times with 4 successes, giving a Beta$(4,1)$ posterior (mean $=0.80$, but very wide). On a given round, sample $\tilde\theta_A \sim$ Beta$(28,12)$ and $\tilde\theta_B \sim$ Beta$(4,1)$. Even though B's mean is higher, its wide spread means $\tilde\theta_B$ could easily land as low as $0.4$ or as high as $0.98$; A's tighter posterior usually samples around $0.6$–$0.8$. Some rounds B "wins" and gets tried again (appropriately, since it's underexplored); other rounds A wins, since its solid track record still frequently outdraws B's noisier one. Traffic splits in a data-justified way, with no fixed exploration percentage set by hand.

Worked example 2: convergence as data accumulates

Suppose after 500 more rounds, Variant A's posterior has tightened to Beta$(300,130)$ (mean $\approx 0.698$) and Variant B's to Beta$(250,260)$ (mean $\approx 0.490$) — B's early 4/5 success rate turned out to be mostly luck. Now sampling from each posterior almost always gives A a higher draw, since the two barely overlap anymore; B is essentially never chosen going forward. Through the same sampling rule used from round one, the algorithm has transitioned from heavy exploration to heavy exploitation, with the transition speed set automatically by how quickly each posterior narrows, not a separate schedule.

Each arm in Thompson sampling carries its own posterior like the one shown in the explorer above — a tight, confident posterior mostly loses the "who gets tried next" draw to a wide, uncertain one until enough data narrows it too.

What this means in practice

Thompson sampling and Bayesian bandits are used for A/B testing execution algorithms, market-making quote strategies, or product variants under live traffic, where continuously re-splitting traffic based on updated posteriors captures far more value than a fixed-length A/B test committed to one allocation until a predetermined end date. It's also the standard baseline behind many production recommendation and pricing systems — provably good long-run performance from a rule simple enough to implement around any conjugate posterior update.