Bandits: explore or exploit
Learning from rewards with no labels: a running estimate for each option, why the greedy choice gets stuck, epsilon-greedy and an optimism bonus.
What it covers6
Why it matters
Everything in this phase so far has learned from a table of examples with the right answers attached. A great deal of the world doesn't come that way. A site choosing which headline to show, a doctor choosing between treatments, a program learning a game: each has to act first and only then finds out how that one choice turned out. Nobody says what the best choice would have been. Learning this way is called reinforcement learning, and it is how language models are taught to prefer better answers (RLHF). Its smallest version, one decision repeated many times, already holds its central problem.
What you'll be able to do
- Describe learning from rewards: act, see what happens, and adjust, with no table of right answers
- Keep a running estimate of each option's value, updated one reward at a time
- Explain the trade-off between exploring and exploiting, and why always taking the best-looking option fails
- Compare three strategies, greedy, epsilon-greedy and an optimism bonus, by the reward they give up
Show the answer
It shows the first headline forever and never tries the other four
After one click the first headline has a click rate above zero and the other four, never shown, still stand at zero. "Always show the best so far" then picks the first headline every time. Its rate may fall, but it stays above zero, so nothing else ever gets a turn. The lesson's first cell runs exactly this.
The idea: act, see what happens, update one estimate
Purpose. Learn which option is best when the only feedback is how the option you chose turned out.
Here is the problem in full. There are five headlines. Each has a true click rate that nobody knows. For every visitor you pick one headline to show, and you see one thing: click or no click. You want as many clicks as possible over a thousand visitors.
The names come from slot machines, once called one-armed bandits: a row of machines with different payouts and a player deciding which arm to pull. So this is a multi-armed bandit. Each option is an arm, a choice is an action, and what comes back, 1 for a click and 0 for none, is the reward.
What makes it different from everything in this phase so far:
- No labels. No row ever says "the right headline was number 4". You learn only about the arm you pulled.
- Your choices decide your data. An arm you never pull is an arm you never learn about.
Here is the strategy from the opening question, played for a thousand visitors. true_rates is hidden from the player and used only to produce clicks.
Setup (runs before every cell) · 25 lines
The lesson runs this once, before its first cell, and every cell, drill and example starts with what it defines. A cell that changes a setup object changes it for the cells after it, until the page reloads.
import numpy as np true_rates = np.array([0.20, 0.50, 0.35, 0.65, 0.45]) def play(policy, setting, steps=1000, players=500, seed=0): """500 players at once: mean reward per step and share on the best arm.""" rng = np.random.default_rng(seed) arms, rows = len(true_rates), np.arange(players) counts, values = np.zeros((players, arms)), np.zeros((players, arms)) rewards, best = np.zeros(steps), np.zeros(steps) for t in range(steps): if policy == "ucb" and t < arms: choice = np.full(players, t) elif policy == "ucb": choice = (values + setting * np.sqrt(np.log(t) / counts)).argmax(axis=1) else: greedy = (values + rng.random((players, arms)) * 1e-9).argmax(axis=1) choice = np.where(rng.random(players) < setting, rng.integers(arms, size=players), greedy) reward = (rng.random(players) < true_rates[choice]).astype(float) counts[rows, choice] += 1 values[rows, choice] += (reward - values[rows, choice]) / counts[rows, choice] rewards[t], best[t] = reward.mean(), (choice == true_rates.argmax()).mean() return rewards, best
import numpy as np # each headline's real click rate, unknown to the player true_rates = [0.20, 0.50, 0.35, 0.65, 0.45] rng = np.random.default_rng(1) # how often each headline has been shown counts = [0] * 5 # the click rate seen so far for each values = [0.0] * 5 clicks = 0 for visitor in range(1000): arm = values.index(max(values)) # always the best-looking headline reward = 1 if rng.random() < true_rates[arm] else 0 counts[arm] += 1 values[arm] += (reward - values[arm]) / counts[arm] clicks += reward print("shown: ", counts) print("estimates:", [round(v, 2) for v in values]) print("clicks: ", clicks, "of 1000 | the best headline alone would average", round(1000 * max(true_rates)))
A thousand visitors, and every one saw the first headline, the worst of the five. Its estimate, 0.19, is accurate. The other four estimates are 0.0, which isn't a measurement at all: they were never tried. The player collected 188 clicks where the best headline would have brought about 650.
Taking the option that looks best right now is called being greedy, or exploiting. Trying something else to learn about it is exploring. This player only ever exploited, so what it knew never improved.
Show the answer
The headline was never shown, so there is no evidence about it at all
The counts show the fourth headline was shown 0 times. Its 0.0 is the starting value, untouched. An estimate tells you about an option only once the option has been tried, and a greedy player has no reason to try something that looks worse.
A running estimate
The player kept an estimate for each arm with one short line. It deserves a closer look, because every method in this track is built on it.
The natural estimate of an arm's value is the mean of the rewards it has given. You could store every reward and average them each time. You don't have to. When the th reward arrives, the old mean becomes:
In plain words: the arrow means "is replaced by". Take the gap between what you just got, , and what you expected, . Move the estimate a fraction of the way toward the new reward: a full step for the first reward, half a step for the second, a third for the third.
Uses the setup above, 25 lines.
rewards = [1, 0, 0, 1, 1] value, n = 0.0, 0 for r in rewards: n += 1 value += (r - value) / n print("reward", r, "| after", n, "the estimate is", round(value, 3)) print("the plain mean:", sum(rewards) / len(rewards))
The last estimate equals the plain mean, 0.6, and at no point was the list of past rewards needed: just the current estimate and a count.
The piece in brackets, , is the error: reward minus expectation. A reward above the estimate pulls it up and one below pulls it down. "New estimate = old estimate + step size × error" is the shape of every update in reinforcement learning. Only what counts as the reward and the size of the step will change.
value, n = 0.5, 4 reward = 1 n += 1 value += (reward - value) / n print(n, round(value, 2))
Show the answer
5 0.6
The error is 1 - 0.5 = 0.5, and the fifth reward moves the estimate a fifth of the way: 0.5 + 0.5 ÷ 5 = 0.6. That matches the plain mean: four pulls averaging 0.5 total 2, plus 1 is 3, over 5 pulls.
Update an estimate with one reward
Write update(value, count, reward). value is an arm's estimate after count pulls. Return a tuple (new_value, new_count) after one more pull that paid reward: the count goes up by one, and the estimate moves toward the reward by the error divided by the new count.
Uses the setup above, 25 lines.
def update(value, count, reward): return value, count value, count = 0.0, 0 for reward in [1, 0, 0, 1, 1]: value, count = update(value, count, reward) print(round(value, 3), count)
The picture. One arm's estimate, after each reward in the list 1, 0, 0, 1, 1. Each new reward moves the estimate a fraction of the way toward it: all the way for the first, a half for the second, a third for the third. The numbers are the ones the cell above prints.
Each step is smaller than the last, because each new reward is a smaller share of what has been counted.
Write a sentence or two, then compare it with a good answer in the lesson.
In code: explore a little, then explore where unsure
Purpose. Run three strategies on the same five headlines, and measure each by the reward it gives up.
Explore a little
The greedy player failed because it never tried anything else. The simplest repair: most of the time take the best-looking arm, but with a small probability (epsilon) pick an arm completely at random. This is epsilon-greedy.
How much should it explore? Too little and it stays stuck. Too much and it wastes visitors on headlines it already knows are poor. One run can't compare settings fairly, since any single player can be lucky, so play runs 500 independent players at once and averages them.
Uses the setup above, 25 lines.
import numpy as np true_rates = np.array([0.20, 0.50, 0.35, 0.65, 0.45]) def play(epsilon, steps=1000, players=500, seed=0): """500 players, each with their own estimates. Returns mean reward per step, and how often the best arm was chosen.""" rng = np.random.default_rng(seed) arms, rows = len(true_rates), np.arange(players) counts, values = np.zeros((players, arms)), np.zeros((players, arms)) rewards, best = np.zeros(steps), np.zeros(steps) for t in range(steps): # best-looking arm, ties broken at random greedy = (values + rng.random((players, arms)) * 1e-9).argmax(axis=1) explore = rng.random(players) < epsilon choice = np.where(explore, rng.integers(arms, size=players), greedy) reward = (rng.random(players) < true_rates[choice]).astype(float) # for each player, the arm they chose counts[rows, choice] += 1 values[rows, choice] += (reward - values[rows, choice]) / counts[rows, choice] rewards[t], best[t] = reward.mean(), (choice == true_rates.argmax()).mean() return rewards, best for epsilon in (0.0, 0.01, 0.1, 0.3, 1.0): rewards, best = play(epsilon) print("epsilon", epsilon, "| clicks per 1000:", round(float(rewards.sum())), "| regret:", round(650 - float(rewards.sum())), "| best headline shown, last 200 visitors:", round(float(best[-200:].mean()), 2))
Each row of values is one player's five estimates, and values[rows, choice] picks out, for every player, the estimate of the arm that player just pulled. The update is the same running mean as before.
The regret column is the measure to watch: the clicks given up compared with showing the best headline every time, which would bring 650.
- With no exploring (and ties broken at random, a little kinder than the first cell), the players average 483 clicks and are on the best headline only 29% of the time at the end. Most are stuck on a worse one.
- Exploring 1 time in 100 helps: 542. But it's slow to find the best arm.
- Exploring 1 time in 10 is the best of these: 602 clicks, a regret of 48, with 88% on the best headline.
- Exploring 3 times in 10 finds the best arm and then keeps throwing visitors away: 573.
- Always exploring is choosing at random: 429, the average of the five click rates.
Regret comes from two sources, and epsilon trades one for the other. Explore too little and you lose clicks by not knowing. Explore too much and you lose them by not using what you know.
import numpy as np rng = np.random.default_rng(0) draws = rng.random(10000) print([round(float((draws < epsilon).mean()), 2) for epsilon in (0.0, 0.1, 1.0)])
Show the answer
[0.0, 0.1, 1.0]
rng.random() is spread evenly between 0 and 1, so it falls below epsilon in a share epsilon of the draws: never for 0, about a tenth of the time for 0.1, always for 1. That is how one line of code turns epsilon into "explore this often".
Choose an arm, epsilon-greedy
Write choose(values, epsilon, rng). First draw rng.random(). If the draw is below epsilon, explore: return int(rng.integers(len(values))). Otherwise exploit: return the index of the largest value, the first one if several tie. Make exactly those calls to rng, in that order, so the checks can follow them.
Uses the setup above, 25 lines.
import numpy as np def choose(values, epsilon, rng): return 0 rng = np.random.default_rng(0) print([choose([0.2, 0.6, 0.4], 0.5, rng) for i in range(12)])
Explore where you're unsure
Epsilon-greedy explores blindly. A headline shown 400 times with a steady 20% click rate gets as many exploring visitors as one shown twice. A better idea: give each arm the benefit of the doubt in proportion to how little you know about it. Score every arm by its estimate plus a bonus that shrinks as the arm is tried, and pull the arm with the highest score. This is the upper confidence bound method, UCB.
In plain words: is the estimate for arm , is how many times it has been pulled, and is how many pulls have been made in all. The bonus is large when is small, an arm you barely know, and it grows slowly with , so an arm left alone for a long time gets another look. sets how generous the benefit of the doubt is.
An arm gets pulled for one of two reasons: its estimate is high, or its bonus is. Either it is good or you don't yet know that it's bad. This idea has a name worth remembering: optimism in the face of uncertainty.
Uses the setup above, 25 lines.
import numpy as np true_rates = np.array([0.20, 0.50, 0.35, 0.65, 0.45]) def play_ucb(c, steps=1000, players=500, seed=0): rng = np.random.default_rng(seed) arms, rows = len(true_rates), np.arange(players) counts, values = np.zeros((players, arms)), np.zeros((players, arms)) rewards, best = np.zeros(steps), np.zeros(steps) for t in range(steps): if t < arms: # show each headline once to begin choice = np.full(players, t) else: # large for a headline shown rarely bonus = c * np.sqrt(np.log(t) / counts) choice = (values + bonus).argmax(axis=1) reward = (rng.random(players) < true_rates[choice]).astype(float) counts[rows, choice] += 1 values[rows, choice] += (reward - values[rows, choice]) / counts[rows, choice] rewards[t], best[t] = reward.mean(), (choice == true_rates.argmax()).mean() return rewards, best for c in (0.5, 1.0, 2.0): rewards, best = play_ucb(c) print("c", c, "| clicks per 1000:", round(float(rewards.sum())), "| regret:", round(650 - float(rewards.sum())), "| best headline shown, last 200 visitors:", round(float(best[-200:].mean()), 2))
With the players collect 627 clicks, a regret of 23, less than half of the best epsilon-greedy setting's 48, and they are on the best headline 97% of the time by the end. There is no random exploring anywhere in this code. Every pull went to the arm with the best case for being pulled.
The setting still matters. With the bonus is so generous that poor arms keep earning visits: 535 clicks, worse than epsilon-greedy at 0.1. Optimism is a better way to explore, and it still has a dial.
Go deeper A third way: sample from your belief
The lesson on Bayesian rates kept a Beta distribution for an unknown rate. Thompson sampling uses one per arm: draw one sample from each arm's distribution and pull the arm whose sample is highest. An arm you know little about has a wide distribution and sometimes draws a high sample, so it gets explored; as evidence arrives its distribution narrows. It is widely used in practice for problems like the headline one, and it has no dial to set.
Show the answer
The first is far less certain: its error shrinks only with more pulls
The standard error of an average shrinks with the square root of the number of values. Four pulls leave a wide range of rates the arm could really have. UCB's bonus is that uncertainty turned into a number: large after 4 pulls, small after 400.
import math t, c = 100, 1.0 arms = {"A": (0.60, 80), "B": (0.50, 20)} # estimate, times pulled print([round(value + c * math.sqrt(math.log(t) / pulls), 2) for value, pulls in arms.values()])
Show the answer
[0.84, 0.98]
A's bonus is √(ln 100 ÷ 80) ≈ 0.24, giving 0.84. B has been pulled a quarter as often, so its bonus is twice as big, about 0.48, giving 0.98. UCB pulls B next: its estimate is lower, but not yet low enough to be sure.
Worked example: three players, one problem
Put the three strategies side by side on the same five headlines, and watch how the share of visitors seeing the best headline grows over time.
Uses the setup above, 25 lines.
import numpy as np true_rates = np.array([0.20, 0.50, 0.35, 0.65, 0.45]) def play(policy, setting, steps=1000, players=500, seed=0): rng = np.random.default_rng(seed) arms, rows = len(true_rates), np.arange(players) counts, values = np.zeros((players, arms)), np.zeros((players, arms)) rewards, best = np.zeros(steps), np.zeros(steps) for t in range(steps): if policy == "ucb" and t < arms: choice = np.full(players, t) elif policy == "ucb": choice = (values + setting * np.sqrt(np.log(t) / counts)).argmax(axis=1) else: greedy = (values + rng.random((players, arms)) * 1e-9).argmax(axis=1) choice = np.where(rng.random(players) < setting, rng.integers(arms, size=players), greedy) reward = (rng.random(players) < true_rates[choice]).astype(float) counts[rows, choice] += 1 values[rows, choice] += (reward - values[rows, choice]) / counts[rows, choice] rewards[t], best[t] = reward.mean(), (choice == true_rates.argmax()).mean() return rewards, best for name, policy, setting in (("greedy ", "eps", 0.0), ("epsilon-greedy 0.1", "eps", 0.1), ("UCB, c = 0.5 ", "ucb", 0.5)): rewards, best = play(policy, setting) shares = [round(float(best[a:a + 250].mean()), 2) for a in (0, 250, 500, 750)] print(name, "| regret", round(650 - float(rewards.sum())), "| best headline shown, by quarter:", shares)
Read each list left to right: it is the share of visitors shown the best headline in each quarter of the run. The greedy players barely move, because most of them locked on to whichever headline paid first. The epsilon-greedy players climb and then level off below 0.9, since a tenth of their visitors are always sent somewhere at random. The UCB players climb highest and keep climbing, because their exploring fades as the evidence comes in. The regret column is the total price each strategy paid for what it learned.
Code flow. The greedy player's trap, in six lines. Step through three visitors: the player always shows the arm with the highest value, and the pays are decided in advance so the run is the same every time.
The three strategies as a picture. The share of visitors shown the best headline over the run, smoothed over 25 visitors. The setup above holds the play function that the worked example uses:
Uses the setup above, 25 lines.
import matplotlib.pyplot as plt runs = [("greedy", "eps", 0.0), ("epsilon-greedy 0.1", "eps", 0.1), ("UCB, c = 0.5", "ucb", 0.5)] for label, policy, setting in runs: rewards, best = play(policy, setting) plt.plot(np.convolve(best, np.ones(25) / 25, mode="valid"), label=label) plt.xlabel("visitor") plt.ylabel("share shown the best headline") plt.legend() plt.show()
Greedy is flat at 0.29: most players locked on to a poor headline. Epsilon-greedy climbs and levels out below 0.9. UCB climbs fastest and highest, because its exploring fades as the evidence comes in.
Write a sentence or two, then compare it with a good answer in the lesson.
In practice: sampling from belief, and where bandits run
Purpose. Meet the strategy most production systems use, and know what changes when rewards arrive late, drift, or cost something real.
clicks, misses = 3, 7 a, b = 1 + clicks, 1 + misses print(a, b, round(a / (a + b), 3))
Show the answer
4 8 0.333
Each click adds 1 to the first number and each miss adds 1 to the second. The mean of Beta(4, 8) is 4 / 12 = 0.333. Thompson sampling keeps one such belief per arm, and draws from it instead of using the mean.
Where this turns up in an engineer's week. Headline and button tests that shift traffic toward the winner while they run; ad and recommendation slots; choosing among several models or prompts for each request, where each arm is a model and the reward is a quality score minus a cost. Three things change in practice. Rewards often arrive late: a purchase comes days after the page view, so the estimates lag. Click rates drift with seasons and news, so old pulls should count for less, which a fixed step size does and the running mean does not. And some experiments can't explore freely: a medical or financial decision needs a limit on how bad an exploring choice can be.
On the job: log which arm was chosen, with what probability, for every decision. Without that record you can't measure the strategy later, or learn from the choices it made.
Goes deeper in
- Decisions in sequence: when a choice changes what you can choose next, a bandit becomes a full decision process.
- Policy gradients: learning probabilities of actions directly.
- RLHF: how language models are tuned from rewards.
Write a sentence or two, then compare it with a good answer in the lesson.
Practice what you just read
- 6 code examples you can edit and run
- a practice exercise that checks your code
- a 5-question quiz
- 11 review cards for spaced repetition
Try a quiz question
What is the explore-exploit trade-off?
Before this lesson
Where this lesson leads.
575 lessons in thirteen phases. 176 are free without an account, and a free account opens the rest. See every lesson.
Phase 3 · about 39 hours of study
Machine learning
Learning from data, and knowing when it worked
50 lessons 1 free
- What machine learning is FreePrograms that learn rules from examples instead of being told them.30 min
- Features and labelsSupervised learning: inputs, targets and predictions.30 min
- Train, validation and test setsHold data back so you can trust your results.38 min
- Preparing dataClean, encode and scale data before a model sees it.40 min
- Linear regressionFit a line, and predict numbers from features.42 min
- Loss functionsOne number that says how wrong the model is.35 min
- Training with gradient descentAdjust weights step by step to reduce the loss.42 min
- Learning rateStep size, convergence and divergence.35 min
- Logistic regressionPredict probabilities for yes/no outcomes.42 min
- Multiclass classificationSoftmax and cross-entropy for more than two classes.42 min
- The same three models in PyTorchA line, logistic regression and softmax regression fitted both ways: the loss, the gradient and the update opened up, with weight decay and mini-batches.35 min
- Precision, recall and F1Accuracy lies; these don't.42 min
- ROC curves and AUCJudge a classifier across every threshold.30 min
- Calibration: can the probability be trusted?Bands of predicted risk against what happened, the Brier score, why naive Bayes is over-confident, and fixing it on rows the model did not fit.30 min
- Overfitting and underfittingMemorizing versus learning.30 min
- RegularizationPenalize complexity so models generalize.40 min
- Bias and varianceThe two ways a model can be wrong.30 min
- Cross-validationReuse limited data for more reliable estimates.42 min
- Imbalanced classes in depthRare classes measured: why rebalancing mostly moves the threshold, correcting inflated probabilities, average precision against AUC, why the count of rare cases matters, and thresholds from costs.45 min
- Naive Bayes: classifying with countsA classifier trained by counting: Bayes' rule over words, the naive assumption, log scores, smoothing for unseen words, why it is overconfident, and when it beats logistic regression.45 min
- Nearest neighborsPredict from the most similar examples.35 min
- Decision treesLearn a flowchart of yes/no questions.42 min
- Random forests and boostingMany weak models voting beat one strong one.42 min
- Gradient boosting in depthBoosting built from scratch: trees fit to the gradient of the loss, depth and interactions, learning rate against number of trees, early stopping, and what XGBoost and LightGBM add.45 min
- Support vector machinesThe widest margin, support vectors, the hinge loss and C, kernels for curved boundaries, and when an SVM fits.40 min
- Recommender systemsShrunk averages, item-to-item collaborative filtering, matrix factorization, and cold start.40 min
- Project: a price modelMultiple regression on log prices, one-hot categories, percentage effects and an extrapolation flag.45 min
- Feature engineeringTurn raw data into signals a model can use.35 min
- The scikit-learn workflowFit, predict and evaluate with the standard ML library.45 min
- Explaining a model: what it uses, and why this predictionPermutation importance on held-back rows, a linear model's contributions for one customer, partial dependence, and what none of them can say.35 min
- Capstone: churn predictionPredict which customers will leave, and measure it properly.45 min
- ClusteringGroup similar items without labels (k-means).35 min
- Clusters of any shape: DBSCAN and hierarchiesWhy k-means needs round clusters, DBSCAN's core points and noise, and hierarchical clustering with its linkages.40 min
- Anomaly detectionMasking, robust scores with the median and MAD, baselines from the past, isolation forests and thresholds from a review budget.40 min
- Dimensionality reductionVisualize and compress high-dimensional data.35 min
- Cleaning messy dataDuplicates, junk rows, text numbers, mixed dates and missing values that mean something.45 min
- Grouping, pivoting and reshapingNamed aggregation, pivot tables, transform, running totals and groups too small to rank.45 min
- Data in pieces: partitions and mergeable summariesSplit, summarize and combine; which statistics merge exactly, merging variances, sketches for the rest, and partitioning well.30 min
- Combining tables with mergeJoin on keys safely, stack tables, and divide by the right denominator.44 min
- Time series with pandasResample, smooth, compare across years, and test whether one series leads another.45 min
- Forecasting: baselines, lag features and backtestsThree baselines, lag features that never see their own future, a walk-forward backtest, and a range around the number.40 min
- Text mining: TF-IDF, search and labelsBag of words and TF-IDF, similarity search and its blind spots, text classifiers and topics, and when LLM labels are worth it.35 min
- Location dataHaversine distances, nearest places, GeoJSON, point in polygon and simple maps.40 min
- Comparing groups: t-testsWelch's t-test, pooled vs average rates, and a control group for before-and-after changes.40 min
- More tests: groups, categories, relationshipsChoose a test, ANOVA by hand, chi-square on counts, Pearson vs Spearman, one-sided tests.40 min
- Project: an exploratory analysis reportFive business questions answered with cleaning, joins, charts and a test, then written up.45 min
- Bandits: explore or exploitLearning from rewards with no labels: a running estimate for each option, why the greedy choice gets stuck, epsilon-greedy and an optimism bonus.35 min
- Decisions in sequence: states, rewards and valueA Markov decision process on a grid world: discounted return, the value of a state, the Bellman equation, and value iteration to the best policy.40 min
- Q-learning: learning values by doingA value for every action, learned from experience with no rules given: the update, a grid world you can watch, and why optimism explores better than chance.40 min
- Policy gradients: learning what to do directlyA policy as probabilities you can nudge: turn up what worked, measure it against a baseline, and see how the same update trains a language model.40 min
Never trained an AI? Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account. Teach it to write