Exploration vs Exploitation
Showing the best-known item earns the most today and learns the least. Some exploration is the price of data you can trust — and in some domains that price cannot be paid.
The problem, the obvious approach, and why it breaks
Every lesson starts where the work starts: someone has a problem, and the first model that comes to mind looks fine offline.
How much should a recommender show things it is unsure about, how do bandit strategies decide, and where is exploration unacceptable?
A homepage has one hero slot and a rotating set of campaigns. The marketing lead says: "we always run the campaign that performed best last week. Every week it is the same one. Are we sure the others are worse, or have we just stopped finding out?"
Show the option with the highest observed success rate. It has the most data and the best number; anything else is deliberately showing something worse.
An option tried thirty times with a slightly lower rate than the incumbent's thousands of trials may actually be better; the difference is inside the noise, and the greedy rule never collects the trials that would resolve it.
- An option tried thirty times with a slightly lower rate than the incumbent's thousands of trials may actually be better; the difference is inside the noise, and the greedy rule never collects the trials that would resolve it.
- The incumbent's advantage is partly that it was shown at the best times to the best users; the challengers' numbers came from the leftover traffic. Greedy selection turns that exposure difference into a permanent verdict.
- The world changes — the incumbent campaign goes stale — and the greedy rule has no mechanism to notice, because the challengers' last observations are months old and it never refreshes them.
- Offline, greedy looks optimal: on the logged data the incumbent has the best rate. The cost of not learning is not in the log, because it is the absence of data.
What is being predicted, and from what data
This domain leads with these two. A target nobody defined precisely is a label nobody can trust, and a dataset nobody can describe is a model nobody can debug.
- Maximise cumulative engagement over a horizon, not engagement today — which means the value of information about an under-shown option is part of the objective.
- The label for a shown option is its outcome; the label for an unshown option does not exist, and the strategy decides how much to pay to obtain one.
- For each option, the count of times shown and the count of successes. For the incumbent, thousands of observations; for the others, a few dozen from the week they were last tried.
- Context about the user and the moment, which turns the problem from a fixed set of arms into a contextual one where the best option differs by user.
- No observation of the counterfactual: what the user would have done with the option not shown.
How it actually works
Precisely enough to predict its behaviour — not a framework API.
- A bandit chooses among options with uncertain rewards and updates its estimates from the outcomes it observes. Regret is the gap between what was earned and what the best option would have earned; a good strategy has regret that grows slowly as it learns.
- ε-greedy shows the best-known option most of the time and a random one a small fraction of the time. Simple, and it explores uniformly forever, including options that have been clearly ruled out.
- Upper confidence bound (UCB) scores each option by its estimate plus a bonus for uncertainty, so an option with few trials gets a chance in proportion to how little is known about it; the bonus shrinks as trials accumulate.
- Thompson sampling keeps a posterior over each option's rate, draws one sample from each, and shows the highest draw. Options with wide posteriors are chosen sometimes because a draw lands high; the exploration is proportional to the plausibility that the option is best.
Three ways to decide how much to not know
ε-greedy is a fixed budget: explore a set fraction of the time, uniformly. UCB is an optimism rule: score each option by its estimate plus an uncertainty bonus. Thompson sampling is a probability rule: show each option as often as it is plausibly the best.
The difference that matters in production is what happens to an option that has been shown enough to be clearly worse. ε-greedy keeps showing it; UCB and Thompson sampling stop, because its uncertainty has shrunk. That is why uniform exploration is expensive on large option sets.
1import random2 3class Arm:4 def __init__(self):5 self.successes = 1 # Beta(1, 1) prior: everything equally plausible6 self.failures = 17 8def choose(arms):9 # one draw from each posterior; the widest posteriors land high10 # often enough to be shown, and narrow low ones almost never11 draws = {name: random.betavariate(a.successes, a.failures) for name, a in arms.items()}12 return max(draws, key=draws.get)13 14def update(arm, reward, forget=0.99):15 # a forgetting factor keeps the posterior from freezing when the16 # world moves; its value is a guess about how fast that happens17 arm.successes = arm.successes * forget + reward18 arm.failures = arm.failures * forget + (1 - reward)The forgetting factor is the part that gets omitted in the textbook version and matters most in production. Without it the posterior of a long-running option becomes so narrow that a change in the world is never detected.
Regret is the cost of not knowing, and it is not in the log
Regret is the reward the best option would have earned minus the reward actually earned. A greedy policy has low regret on the logged data — it chose the option with the best number — and unknown regret in reality, because the option that might have been better was never shown and the log cannot say.
That is the offline/online gap in its purest form: the greedy policy is optimal on the log and the log is missing the data that would show it is not.
On every weekly report the incumbent campaign had the highest observed conversion rate and was selected again.
A bandit introduced on a fraction of traffic found that two of the retired campaigns outperformed the incumbent for a large user segment, and the incumbent's rate had been sliding for months.
- 1The challengers' rates were estimated from a few dozen leftover impressions on unfavourable traffic and were never refreshed.
- 2The incumbent's rate was a blend across segments; per segment it was best for one and worst for two, which the surface-level number could not show.
- 3The incumbent went stale and the greedy rule had no mechanism to notice, since no alternative was ever measured against it again.
Where exploration is unacceptable
An exploratory decision is a decision made partly to learn. On a marketing slot the learner's cost is a slightly worse impression for one user. In a fraud model the cost is a fraudulent transaction allowed through and charged to a cardholder; in triage it is a patient routed to a slower queue to see what happens.
The rule is about who bears the cost. Where the cost of a wrong decision falls on the individual it is made about, exploration needs the justification of a clinical trial — consent, a bound on harm, an ethics review — or it is confined to decisions where either choice is acceptable. The bandit library does not know this; the surface configuration has to.
Any option the bandit can choose is acceptable to show to any user it might be shown to; the only cost of exploration is forgone reward.
holds when The option set is pre-filtered for policy, safety and legality; the decision is a presentation choice with no direct consequence for the individual beyond a worse impression.
breaks when The bandit is attached to a decision with individual consequences — credit, fraud, medical, safety — or the option set includes items that were never reviewed because the bandit was expected to learn they are bad.
respond Confine exploration to a filtered option set or remove it from the surface; do not tune ε down and call the problem solved.
| Option | Quality | Latency | Cost | Interpretability | Data needed | Operational | Note |
|---|---|---|---|---|---|---|---|
| Greedy (always the best-known) | Optimal on the log, blind in the world; regret unknown and growing when the world moves. | ||||||
| ε-greedy | A fixed exploration budget; wastes it on options already ruled out. | ||||||
| UCB | Uncertainty-directed; deterministic given the counts, so easy to audit and to game. | ||||||
| Thompson sampling | Uncertainty-directed and randomised; natural with a posterior, needs a forgetting rule in practice. |
caveat The quality column assumes a stationary world and cheap exploration, which is the case in which the differences are smallest. With delayed rewards, non-stationarity or a real cost per exploratory decision the ranking changes and the safest answer may be not to explore at all, which no row expresses.
How to build it
Most important first.
- Decide the horizon and the cost of a bad impression first; the right amount of exploration is a function of both and neither is a modelling parameter.
- Prefer uncertainty-directed exploration (UCB, Thompson sampling) over uniform ε-greedy when the option set is large or when clearly bad options should stop being shown.
- Make the exploration contextual: the best option per user segment, not per surface, and let the bandit learn the difference.
- Log the propensity of every decision so the exploration also produces the data that feedback-loop correction and counterfactual evaluation need (Feedback Loops).
- Bound exploration with guardrails in domains where a bad decision has a real cost — never explore into a decision that would be unacceptable if wrong.
What to measure
Which number actually maps to the decision — and which numbers look relevant and are not.
- Cumulative reward against a fixed policy over the horizon, on an A/B test — the number that says whether the exploration paid for itself.
- Posterior width per option over time: exploration is working if uncertainty shrinks where it was widest.
- Do not measure the success rate of exploratory impressions and call exploration expensive. Their job is information; their rate is expected to be lower.
What must stay true after deployment
The field this whole domain exists for. A model is a set of assumptions with weights attached; these are the ones a monitor or a test should be checking.
- The reward for an option is stationary over the window the bandit's posterior covers, or the forgetting rate matches how fast it actually moves.
- The exploratory impressions are logged with their propensities and are not filtered out of the data downstream as anomalies.
- Every option the bandit can choose is acceptable to show; the option set has been filtered for safety before the bandit sees it.
- Offline: replay the bandit against the logged randomised slice with a counterfactual estimator to compare strategies before deploying; check regret curves on a simulator with the real reward delay.
- Online: an A/B test of the bandit against the greedy incumbent on cumulative reward over the full horizon, not on the first week.
- Over time: the distribution of impressions across options; a bandit that has collapsed to one option with a stale posterior is greedy with extra steps.
What can go wrong
- Non-stationarity: the bandit converges on an option, the world moves, and the converged posterior is so narrow that the bandit never re-explores. A forgetting factor or a sliding window is needed and its length is a guess.
- Delayed rewards: the outcome arrives days later and the bandit keeps choosing on stale posteriors, over-exploring or over-exploiting depending on which way the delay biases the estimate (Ground-Truth Delay).
- Exploration is applied to a decision it should not touch — a fraud block, a medical triage — because the bandit was a library and the surface was a config.
- The bandit is tuned by someone who measures its exploratory impressions' rate and turns exploration down until it is greedy.
- Exploration is a real, continuous cost in the metric everyone watches, paid for information that appears as better decisions later and is attributed to nobody.
- Uncertainty-directed strategies need a model of the uncertainty, which is a posterior to maintain, a prior to choose, and a forgetting rate to guess.
- A contextual bandit is a model with all of a model's problems — features, skew, drift — plus the exploration policy on top.
- "Exploration means showing worse things on purpose." It means showing things whose quality is unknown, on purpose. The alternative is never finding out, which is a decision too.
- "Thompson sampling is the best bandit." It is the most natural for many problems; with delayed rewards, non-stationarity or hard safety constraints each strategy needs modification, and the choice depends on the reward structure, not on a ranking of algorithms.
- "We can explore in the fraud model — just let a small fraction of suspicious transactions through." Each of those is a real loss to a real cardholder. Exploration where the cost of a bad decision is borne by an individual needs a different justification than a marketing slot.
Where this applies
ML advice is stated as universal far more often than it is. These labels say what each claim is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- DOMAIN-SPECIFICOn a marketing slot or a feed, an exploratory impression costs a little engagement and exploration is cheap; in medical triage, fraud, credit or safety-critical routing, an exploratory decision can harm the person it is made about and exploration is unacceptable or must be confined to decisions that are safe either way.
- SIMPLIFIEDThe strategies are described at the level of ideas: real deployments add contextual features, delayed-reward handling, non-stationarity corrections and constraints, and the regret guarantees quoted in the literature assume conditions — stationary, independent rewards — that production rarely meets.
- CONTESTEDA serious position holds that a bandit is over-engineering for most product decisions and that periodic A/B tests with a fixed exploration budget are more legible, easier to govern and nearly as efficient. The counter is that A/B tests explore uniformly and stop, so they waste traffic on options already ruled out and never re-explore when the world moves, which is exactly the failure the bandit's uncertainty bookkeeping prevents.
Where the depth lives
This domain teaches the model and hands the rest off by name.
- — Experimentation and statistics — the regret bounds, the variance of counterfactual estimators and the design of an A/B test against a bandit are a statistics discipline this lesson names but does not teach.