skip to content

Thompson Sampling

4 roadmaps5 questions

Draw once from each arm's posterior, play the winner, then update: exploration falls out of the uncertainty itself, so bandits cut regret versus a fixed split. Interviewers ask when not to use one.

on this pageshow

explore

questions

5

In Thompson sampling, how is the arm to serve chosen on a single request?

level: middleimportance: must knowfreq 72%

answer

  1. randomness replaces a tuned knob
  2. each arm carries a full posterior
  3. sample it, do not summarise it
  4. one draw per arm, per request
  5. compare draws, not posterior means

basics

~20 s

Thompson sampling draws one random value from each arm's posterior over its reward rate, then serves the arm whose draw came out largest. Every request repeats the draw, so allocation follows the posteriors on its own.

solid answer

~40 s

On every request you take a single sample from each arm's posterior over its true reward rate — one number per arm — and serve whichever arm's sample is largest. The reward you observe then updates that arm's posterior, and the next request draws a fresh set of numbers. Because the draw is random, an arm ends up served with probability equal to the posterior probability that it is the best arm: arms that are still plausibly best keep getting traffic, arms that are almost certainly worse stop getting it. There is no exploration rate to tune and no schedule to decay — the randomness of the draw *is* the exploration mechanism. With three headline variants live, traffic drifts toward the leader over hours without anyone touching a split.

code

python · 17 lines
python
import random

true_rate = [0.04, 0.05]   # unknown to the sampler
alpha = [1, 1]             # posterior parameters, one pair per arm
beta = [1, 1]
plays = [0, 0]

for _ in range(20000):
    # one draw per arm from its own posterior, then serve the largest
    draws = [random.betavariate(alpha[i], beta[i]) for i in range(2)]
    arm = draws.index(max(draws))
    reward = 1 if random.random() < true_rate[arm] else 0
    alpha[arm] += reward
    beta[arm] += 1 - reward
    plays[arm] += 1

print(plays)  # e.g. [~1200, ~18800] - the worse arm is squeezed out

go deeper

for a junior

Be ready to state the loop in order: one random draw per arm from its posterior, serve the largest draw, record the outcome, repeat. Knowing that the choice is random rather than a fixed split is most of what is expected.

for a middle

You are expected to explain the mechanics and why they work: sampling preserves uncertainty that the posterior mean discards, so an arm still plausibly best keeps winning draws. Be able to contrast it with always serving the current leader.

for a senior

Show you have run one. Talk about how often draws are refreshed at real traffic volumes, what the served-share curve looks like over the first hours, and what happens when reward updates lag the decisions that produced them.

for a principal

Own the tradeoff of shipping an allocation rule with no knobs. It is trivial to deploy and impossible to hand-tune, so the only lever is the prior; be ready to say how you would explain a moving traffic split to stakeholders and what guardrails you would put around an automated allocator.

## The setting You have K arms — say three headline variants on a landing page. Each arm has an unknown true reward rate: the long-run fraction of impressions that convert. On every incoming request you must pick exactly one arm to serve, you observe the reward for that arm only, and you would like to earn as much reward as possible while still learning which arm is best. ## The rule itself Thompson sampling keeps, for each arm, a **posterior distribution** over that arm's true rate — not a single number, but a full probability distribution describing what the rate could plausibly be given everything observed so far. The allocation rule is then three lines, executed per request: 1. Draw **one** number from each arm's posterior. One draw per arm — not the posterior mean, not an average of many draws. 2. Serve the arm whose draw is largest (the argmax over the draws). 3. Observe the reward and fold it into that arm's posterior. On the next request you draw again, and the numbers come out different. Nothing else is needed: no exploration rate, no decay schedule, no separate "explore now" branch. ## Why the randomness is the whole trick A greedy rule that always serves the arm with the highest posterior mean has a well-known failure: an arm that got lucky in its first few impressions is served forever, and the arm that got unlucky never gets the traffic that would reveal it is actually better. The mean throws away exactly the information that matters — how sure you are. Sampling keeps it. If an arm's posterior still puts real mass above the leader's, a draw from it will sometimes come out on top, and that arm gets served. If an arm's posterior sits clearly and tightly below the leader's, its draws almost never win and it fades out. So the traffic an arm receives is governed by how plausible it is that the arm is best, which is precisely the quantity that should govern exploration. That gives Thompson sampling a property worth naming: it is **probability matching**. The long-run share of traffic an arm receives equals the posterior probability that it is the best arm. Early on, with wide posteriors, that probability is spread across arms and traffic is spread with it. As data accumulates the posteriors separate, the probability concentrates on one arm, and so does the traffic — automatically, with no annealing schedule written by hand. ## What it looks like in operation Suppose the three headlines have true rates near 4%, 5% and 5.2%. In the first few hundred impressions the posteriors overlap heavily and the served shares wobble around a third each. After a few thousand impressions the 4% arm's posterior has separated and its share collapses toward a few percent. The two close arms keep splitting traffic for far longer, because the posterior probability that either is best genuinely stays near a half — and that is correct behaviour, not a bug: serving either of two nearly-identical arms costs almost nothing, so there is no urgency to resolve them. ## Details that separate a good answer from a shallow one **Draw granularity.** The rule specifies a fresh draw per decision. Many production systems draw once and reuse the choice for a batch of requests, or refresh draws every few seconds, because a per-request posterior draw is expensive at high queries-per-second. That is a real and usually acceptable approximation, but it is an approximation: within a batch the allocation is deterministic, and adaptation is coarser than the textbook rule. **Update latency.** The rule assumes the reward is folded in before the next decision. When rewards arrive late relative to decisions, the sampler is choosing against a posterior that does not yet contain the evidence for the impressions it already served, and it will over-serve whichever arm has the most unresolved traffic. **It is a decision rule, not an inference method.** Thompson sampling tells you *where to send the next request*. It does not by itself tell you whether to declare a winner or how precisely each arm's rate is known. **No knobs is a double-edged property.** The absence of an exploration parameter is why the rule is so easy to deploy, and also why it can be hard to explain to a stakeholder who wants to know why yesterday's traffic split moved. The lever you actually have is the prior — everything else follows from the data. ## The one-sentence version Sample one plausible rate per arm from its posterior, serve the arm with the highest sampled rate, update, repeat: exploration falls out of uncertainty rather than being scheduled.

  • What goes wrong if you serve the arm with the highest posterior mean instead of the highest draw?
    You get a purely greedy rule with no exploration. An arm that converted well in its first handful of impressions holds the lead, the arm that started unlucky never receives the traffic that would correct it, and the sampler can stay locked on a worse arm indefinitely. Sampling instead of averaging keeps a non-zero chance of serving any arm that is still plausibly best.
  • What share of traffic does an arm receive in the long run?
    The posterior probability that it is the best arm — Thompson sampling is probability matching. If the posteriors say arm B is best with probability 0.7, roughly 70% of requests go to B. As data accumulates that probability moves toward 0 or 1 and the traffic follows, which is why the split anneals itself with no decay schedule.
  • Does the draw have to be taken fresh for every single request?
    The textbook rule says yes, and that is what gives per-request randomisation. In production it is common to draw once per short batch or refresh draws on a timer, because sampling every posterior on every request is expensive at high throughput. That is a reasonable approximation, but within a batch the allocation is deterministic and adaptation is coarser.

Each arm states one rate it could plausibly be running at, drawn honestly from its own uncertainty, and the request goes to whoever claims the highest number that round. An arm nobody has measured can still make a bold claim; a heavily measured one cannot.

saying these in an interview costs you the question

  • Says it serves the arm with the highest posterior mean
  • Thinks an exploration rate must be tuned by hand
  • Draws once and reuses that choice for all traffic forever
  • Confuses the posterior draw with the arm's observed conversion rate
  • Believes each arm is sampled many times and the samples averaged

context

resolving links…

open as a page

Why does Thompson sampling keep serving an arm with only 1 success in 2 trials?

level: middleimportance: should knowfreq 58%

basics

~20 s

Two trials leave a very wide posterior, so a draw from that arm lands above the leader's draw often enough to win some requests. Uncertainty, not a tuned exploration parameter, is what buys the arm its traffic.

open as a page

How do you keep Thompson sampling responsive when an arm's true rate changes over time?

level: seniorimportance: should knowfreq 45%

basics

~20 s

A long-running Thompson sampler locks in because its posteriors become extremely tight and the changed arm barely gets served. Make it forget on purpose: discount old observations each round, or keep only a sliding window of recent ones.

open as a page

How does Thompson sampling's cumulative regret compare with a fixed 50/50 split?

level: seniorimportance: should knowfreq 50%

basics

~20 s

A fixed 50/50 split's cumulative regret grows linearly with traffic: 50,000 impressions parked on a 4% arm instead of a 5% arm costs about 500 conversions. Thompson sampling's grows sublinearly, roughly like the logarithm of the horizon.

open as a page

How would you run Thompson sampling on a news feed where articles arrive and expire daily?

level: principalimportance: nice to knowfreq 28%

basics

~20 s

Thompson sampling handles arms coming and going without modification: each request draws over whatever arms are live, and a new arm's wide posterior earns it exploration. The real problems are cold-start priors, delayed clicks, and exploration swamping exploitation.

open as a page