Multi-Armed Bandits: Epsilon-Greedy, UCB and Thompson Sampling

Multi-armed and contextual bandits: the explore-exploit trade-off, epsilon-greedy, UCB, Thompson sampling, logging propensities and bandits vs A/B tests.

Advanced 3 min read · Updated 29 October 2026

A multi-armed bandit chooses between options ("arms") again and again, learning which pays off best while still trying the others now and then. It's the formal version of the explore-exploit trade-off: show what you know works, or try something that might work better. Bandits appear in ML system design for headline and thumbnail selection, new-item exploration, ad creative choice, notification timing and anywhere an A/B test would be too slow or would waste too much traffic.

Explore vs exploit

Always exploiting (showing the current best) means you never discover a better option and never learn about new items. Always exploring wastes traffic on bad options. A bandit algorithm decides, request by request, how much to explore, and shifts traffic towards winners as evidence accumulates.

The bandit loop: choose an arm, observe a reward, update the estimate for that arm. Logging the probability of each choice makes the data reusable for offline evaluation later.

The main algorithms

Algorithm	How it explores	Pros	Cons
Epsilon-greedy	With probability ε pick a random arm; otherwise the best so far	Trivial to implement and explain	Explores blindly, even arms known to be bad
Upper confidence bound (UCB)	Pick the arm with the highest optimistic estimate (mean + uncertainty bonus)	Explores uncertain arms on purpose; deterministic	Needs tuning; deterministic choice is hard with delayed rewards
Thompson sampling	Sample a plausible reward rate for each arm from its posterior; pick the highest sample	Strong in practice; naturally handles delay and batching	Needs a probabilistic model of rewards
Contextual bandits	Model reward as a function of context (user, time), e.g. linear UCB or a neural model	Personalised choices	More data and modelling; needs careful logging

# Thompson sampling for click-through (Beta-Bernoulli)
import random
arms = {"A": [1, 1], "B": [1, 1], "C": [1, 1]}   # [clicks + 1, non-clicks + 1]

def choose():
    samples = {arm: random.betavariate(a, b) for arm, (a, b) in arms.items()}
    return max(samples, key=samples.get)

def update(arm, clicked):
    arms[arm][0 if clicked else 1] += 1

Early on every arm's posterior is wide, so all get traffic; as clicks accumulate, the posteriors narrow and the best arm wins most samples. An arm that's clearly worse is rarely chosen, which is where bandits save traffic over a fixed split.

Bandits vs A/B tests

	A/B test	Bandit
Goal	Learn the true effect with statistical confidence	Maximise reward during the experiment
Traffic split	Fixed (for example 50/50)	Shifts towards winners
Best for	Launch decisions, long-term and guardrail metrics	Short-lived choices: headlines, creatives, new items
Weakness	Wastes traffic on losers	Biased effect estimates; poor for slow, long-term metrics

Use an A/B test to decide whether a new ranking model ships. Use a bandit to pick which of five thumbnails a video shows this afternoon.

System design concerns

Log propensities: record the probability the policy gave each chosen arm. With it you can evaluate a new policy offline from old logs (inverse propensity scoring) instead of running it live.
Delayed rewards: a purchase may arrive hours later. Update in batches and prefer Thompson sampling, which tolerates stale parameters.
State storage: per-arm counts or posteriors live in a fast store; updates come from a stream job joining choices to rewards.
Non-stationarity: click rates change over the day; decay old observations or use a sliding window.
Guardrails: cap exploration on risky surfaces, and never explore with content that breaks policy.

A production bandit service: the policy reads arm state from a fast store; a stream job joins logged choices with delayed rewards and updates that state.

Where it’s used

News and media

Headline and thumbnail testing, where the best option changes daily and waiting for a full A/B test is too slow.

Recommendations

Exploration slots that give new items impressions, a standard cold start technique.

Marketing and notifications

Choosing send times or message variants per user with contextual bandits.

In an interview

Explain explore vs exploit and why pure exploitation starves new items.
Pick Thompson sampling or UCB and explain how it explores.
Say when you'd use a bandit instead of an A/B test, and when you wouldn't.
Mention logging propensities for offline policy evaluation.

Frequently asked questions

What is a multi-armed bandit?

An algorithm that repeatedly chooses between options while learning which pays off best, balancing exploiting the current best option with exploring others. It shifts traffic towards winners during the experiment.

When should I use a bandit instead of an A/B test?

For short-lived choices where maximising reward during the test matters, such as headlines, thumbnails or new-item exploration. Use A/B tests for launch decisions that need unbiased effect estimates and long-term metrics.