Multi-armed bandits and exploration
Learning what works while serving users: the explore-exploit trade-off, epsilon-greedy, upper confidence bounds and Thompson sampling, contextual bandits, bandits versus A/B tests, uses in ranking, notifications, pricing and creative selection, logging for off-policy evaluation, and pitfalls.
Reading is half of it. See this used in a real interview: walk through Design a News Feed →
A recommendation system that only shows what it already knows works well never learns about new items. An A/B test that splits traffic evenly for two weeks keeps showing the losing variant to half the users. Multi-armed bandits balance learning (exploration) with using what has been learned (exploitation), shifting traffic toward better options as evidence accumulates. They come up in feed, recommendation and notification designs as the answer to cold start and "how do you choose between options automatically?".
The explore-exploit trade-off
Each option (an "arm": a thumbnail, a headline, a notification time, a candidate item) has an unknown reward rate (click, watch, purchase). Every time you choose:
- Exploit: pick the option with the best estimate so far.
- Explore: try something less certain, which might be better.
Pure exploitation gets stuck on early winners; pure exploration wastes traffic. Bandit algorithms manage the balance.
Common algorithms
| Algorithm | How it chooses | Notes |
|---|---|---|
| Epsilon-greedy | best option most of the time, a random one with probability ε | simple; explores blindly; ε often decays over time |
| Upper confidence bound (UCB) | option with the highest optimistic estimate (mean plus uncertainty bonus) | explores options with few observations; deterministic |
| Thompson sampling | sample a plausible reward rate for each option from its posterior, pick the highest sample | explores in proportion to the chance of being best; strong in practice |
For click-style rewards, Thompson sampling with Beta distributions is a few lines of code: keep counts of successes and failures per arm and sample.
Contextual bandits
Rewards often depend on context: user, device, time of day, item features. Contextual bandits learn a model mapping context to expected reward per action and add exploration around it (for example, sampling from model uncertainty, or epsilon exploration). They sit between simple bandits and full recommendation models, and are widely used for personalised choices like which artwork to show for a title. See Design Netflix.
Bandits versus A/B tests
| A/B test | Bandit | |
|---|---|---|
| Goal | measure the effect precisely | maximise reward during learning |
| Traffic split | fixed | adapts toward winners |
| Statistical clarity | high, simple to analyse | harder; biased estimates without care |
| Regret (lost reward while learning) | higher | lower |
| Best for | product decisions, long-term metrics, guardrails | many options, short-lived content, continuous optimisation |
Use A/B tests for decisions you need to understand and defend (a new ranking model, a pricing change), and bandits for ongoing optimisation among many options (headlines, thumbnails, notification templates). See feature flags and A/B testing.
Where they appear
- Cold start: give new items or creators some exposure to learn their quality. See recommendation systems.
- Feed ranking exploration: reserve a small share of slots for uncertain candidates to avoid feedback loops. See Design a News Feed.
- Notifications: choose send time, template and channel per user. See Design a Notification System.
- Dating and marketplaces: give new profiles or providers visibility while learning. See Design Tinder.
- Ads and creatives: choose among ad creatives. See ad serving and auctions.
System design
- Decision service: given context, returns an action and the probability with which it was chosen (the propensity).
- Logging: record context, action, propensity, and later the reward, joined by a decision id. Rewards may arrive late (a purchase days later), so joins use windows. See windowing and watermarks.
- Updating: simple bandits update counters in near real time (in a fast store); contextual models retrain periodically from logs. See feature stores and ML serving.
- Off-policy evaluation: with logged propensities, you can estimate how a new policy would have performed on past data (inverse propensity scoring) before deploying it.
Pitfalls
- Non-stationarity: popularity changes; use decay or sliding windows so old data does not dominate.
- Delayed and noisy rewards: optimising clicks may hurt long-term satisfaction; choose rewards carefully and keep guardrail metrics.
- Too little exploration after the algorithm becomes confident; keep a floor.
- Peeking at results from a bandit as if it were an A/B test gives biased effect sizes.
- Fairness: exploration and exploitation affect creators and sellers; monitor exposure.
In the interview
"For thumbnails we run a Thompson sampling bandit per title and user segment, so traffic shifts to the best artwork within hours; decisions log their propensities so we can evaluate new policies offline. For the ranking model change itself we use a standard A/B test with guardrails." Brief and precise is enough.
Checklist
- Explore-exploit trade-off stated; exploration share bounded.
- Thompson sampling or UCB for simple choices; contextual bandits for personalised ones.
- Bandits for continuous optimisation, A/B tests for measured decisions.
- Propensities and rewards logged for evaluation.
- Decay for changing environments; carefully chosen rewards and guardrails.