The cleanest possible version of the explore–exploit problem: no states, no transitions, just actions. From regret — the right way to keep score — to the three great strategies (ε-greedy, UCB, Thompson), then to learning from which option a human preferred rather than a number, the foundation under RLHF.
You walk into a casino and find a row of slot machines — "one-armed bandits," in the old slang. They look identical, but they are not: each one pays out at a different secret rate. One is generous, one is stingy, the rest are somewhere in between. You have a fixed evening and a fixed stack of coins. Which machine should you keep pulling?
Here is the cruel part. The only way to learn a machine's payout rate is to pull it and see what falls out. You never get to peek inside. And every coin you spend probing a machine that turns out to be bad is a coin you did not spend on the one that turns out to be good. The machines you don't pull tell you nothing at all.
This is the whole game, and it has a precise name: the multi-armed bandit problem. It is the simplest reinforcement-learning problem there is — and, as the lecture says, still has many open questions. Strip RL of everything fancy — no states, no transitions, no dynamics — and the irreducible core that remains is this single dilemma: spend your next pull on what already looks best, or on something you haven't tried enough to be sure about?
It is not a toy. Drop the casino story and the same structure appears everywhere. Which ad do I show this visitor? — arms are ads, reward is a click. Which news topic should the feed recommend? — arms are topics, reward is a "like." Which of two treatments do I give the next patient in a trial? — arms are treatments, reward is recovery, and a wasted pull is a patient who got the worse drug. Each is the same loop: choose an action, observe only its outcome, update, repeat.
Five machines with secret payout rates. Pull a machine and you see only that machine's reward (a coin or nothing) and its running average. The other machines stay grey question-marks — you learn nothing about an arm you don't pull. Try a few pulls. How sure are you which is best? Reveal shows the hidden truth.
Notice the discomfort already. After a handful of pulls you have a guess about each machine, but each guess rests on a tiny, noisy sample. The machine that looks best so far might just have been lucky. If you commit to it now you might be locking onto a fluke; if you keep probing you are burning coins. That tension — nothing more — is the engine of this entire lecture.
Let us turn the casino story into something we can reason about. The setup is deliberately minimal — this is the simplest reinforcement-learning problem, and we keep it that way.
The defining limitation, repeated from Chapter 0 because it controls everything: the algorithm only receives feedback on the chosen arm. Pull arm 3, you observe a reward sampled around μ3. You learn nothing about μ1, μ2, μ4, μ5. This is called bandit feedback (as opposed to "full feedback," where you'd see what every arm would have paid). It is why bandit problems demand counterfactual reasoning: to act well you must reason about outcomes you will never directly observe.
Since μ(a) is the expected reward of arm a, the natural estimate is the sample average of the rewards we've actually gotten from a. Call the estimate Q(a) and let N(a) be the number of times we've pulled a so far:
This is just a running mean. By the law of large numbers, as N(a) grows, Q(a) converges to the true μ(a). Two facts that will matter for everything that follows: an arm pulled many times has a Q(a) we can trust (large N, tight estimate); an arm pulled rarely has a Q(a) that might be wildly off (small N, loose estimate). The number of pulls N(a) is not bookkeeping — it is our confidence.
One arm with a true mean of 0.60 (dashed line). Each pull draws a noisy reward; the warm curve is the running sample-average Q(a). Slide the noise up and watch how many pulls it takes before Q(a) settles near the truth — that delay is exactly why you can't trust an arm you've barely tried.
How do we judge a bandit algorithm? "Total reward earned" is tempting but unfair — it depends on how generous the machines happen to be. The lecture uses a cleaner scoreboard that subtracts out the luck of the draw: regret.
Imagine a genie who knew every arm's true mean from the start. The genie would pull the best arm, the one with mean μ1, every single round — collecting an expected T × μ1 over T rounds. That is the unbeatable ideal, the OPT (optimal-in-hindsight) reward. Your algorithm, ignorant at first, scatters its pulls across arms while it learns and earns less. The shortfall is the regret:
Read it term by term. The first piece, T·μ1, is what the genie earns — the best arm pulled T times. The bracket sums the expected reward of whatever arms you actually chose on rounds 1 through T. The difference is the opportunity cost of not knowing the answer from the start. Every time you pull a sub-optimal arm a, you add a little chunk μ1 − μ(a) — the per-pull gap — to your regret.
Here is the subtle, beautiful part. A learner that always pulled some fixed bad arm would rack up regret growing like c·T — linear in T, a constant loss every round forever. We want to do dramatically better. We call an algorithm no-regret (or sublinear-regret) if its average regret per round vanishes as T grows:
That happens whenever the total regret grows slower than T — for example like the square root of T, or like the logarithm of T. The lecture's examples are exactly these: Regret(T) on the order of the square-root-of-T, or the even better log-T. If your total regret is only log T after a million rounds, then your per-round mistake has shrunk to almost nothing — asymptotically the mistakes are negligible. You have, in effect, found the best arm and are mostly playing it.
Cumulative regret over T rounds. The red line is a fixed-exploration learner: regret grows straight up, linearly — a constant loss every round. The teal curve grows like the square root of T, and the warm curve like log T — both bend over and flatten. Drag the slider to extend the horizon and watch the gap explode.
The most obvious strategy is greedy: estimate each arm's mean by its sample average Q(a), then always pull the arm with the highest Q. Pure exploitation. It sounds reasonable. It is a trap.
Suppose early on, by bad luck, the truly-best arm pays out poorly on its first pull while a mediocre arm pays well. Greedy now believes the mediocre arm is best, and — because it only ever pulls the current best — it never pulls the good arm again to discover its mistake. It has locked into a local optimum and stays there forever. On the 10-armed testbed in the lecture, the pure-greedy curve flattens early at a clearly sub-optimal reward. Greedy is not optimal, because it never gathers the information that would correct it.
ε-greedy (epsilon-greedy) bolts a pinch of randomness onto greedy. With probability 1 − ε it exploits (pulls the current-best arm); with probability ε it explores (pulls a uniformly random arm):
That small ε guarantees every arm keeps getting tried, so Q(a) eventually converges for all arms and greedy's "lock-in" disaster can't happen. On the testbed, ε = 0.1 and ε = 0.01 both beat pure greedy comfortably — the price of a little exploration buys you out of the local-optimum trap.
It works, but it is crude, in two ways the next chapters will fix:
Arm 2 (teal) is best, but the agent must find it. Left (ε→0): nearly pure greed — sometimes it locks onto a worse arm and never recovers. Right (ε→1): pure exploration — it finds the winner but keeps throwing pulls away on losers. Grey = true payoff, colored = how often each arm got pulled over 600 rounds.
ε-greedy's sin was exploring blindly. Upper Confidence Bound (UCB) fixes it with one of the most elegant ideas in all of learning: be optimistic about the arms you haven't tried much. Don't explore at random — explore wherever you have the most to gain from being wrong in your favor.
Start from Chapter 1's insight: an arm pulled N(a) times has an estimate Q(a) whose uncertainty shrinks as N(a) grows. We can make that precise. Suppose each arm's rewards come from a distribution with some spread σ. A concentration inequality — the lecture names Hoeffding's inequality — says: with high probability, the true mean μ(a) lies within a window around the estimate Q(a), and that window has half-width
where t is the total number of pulls so far and c is a tunable constant controlling how much you value exploration. Don't memorize the exact form — read its shape, because the shape is the whole idea:
Now the magic. Instead of acting on the estimate Q(a), UCB acts on the optimistic top of the window — the upper confidence bound — and pulls whichever arm has the largest one:
This is the principle of optimism in the face of uncertainty (OFU): when unsure about an arm, assume the best plausible truth about it. An arm gets pulled for one of two good reasons — either its estimate Q(a) is high (it really is good: exploitation), or its bonus is high (we're very unsure and it could be good: exploration). UCB fuses explore and exploit into a single number. There is no separate coin flip.
Three arms. Each dot is the estimate Q(a); the bracket above it is the confidence window (its upper tip is the UCB). Pull the arm UCB chooses and watch its bracket shrink (more data). Notice UCB often picks an arm whose estimate is lower but whose window is wider — that is optimism choosing exploration. Over time every bracket narrows onto the truth (dashed).
The bonus formula stays abstract until you push real counts and means through it. Let's compute UCB scores for three arms with actual data and watch optimism pick the surprising one.
We are at total time t = 100 pulls. Use the exploration constant c = 2. Three arms, with these running statistics:
| Arm | Estimate Q(a) | Pulls N(a) |
|---|---|---|
| Arm A | 0.60 | 80 |
| Arm B | 0.55 | 10 |
| Arm C | 0.40 | 10 |
Arm A looks best by raw estimate (0.60), and we've pulled it 80 times — we trust that number. Arms B and C have been tried only 10 times each, so their estimates are shaky. Which does UCB choose? Compute the bonus c · √((ln t)/N(a)) for each. Note ln(100) ≈ 4.605, so √(ln 100) ≈ 2.146.
Now you write the rule that is UCB — the bonus and the argmax — and confirm it picks Arm B on exactly this data.
UCB explores by being optimistic: take the top of each confidence window. Thompson sampling (also called posterior sampling) explores a completely different, almost playful way: maintain a full belief about each arm, then act as if a single random draw from those beliefs were the truth. It is an old idea — from 1933 — that for decades had no theory, yet works extremely well in practice (the proper analysis only arrived around 2012).
Here is the clean contrast the lecture draws. UCB keeps, for each arm, a range the mean probably lies in. Thompson keeps something richer: a full posterior distribution over each arm's mean — a probability curve saying "I think this arm's mean is most likely around here, but it could plausibly be anywhere under this curve." More data makes the curve narrower and sharper, just like the shrinking UCB window, but it carries the whole shape of our uncertainty, not just its width.
Why does sampling explore automatically? Because the width of a posterior is the chance of a surprising draw. An arm we've barely tried has a wide, flat posterior, so its random sample is often large — it gets picked, gathering data. An arm we've pulled a thousand times has a needle-thin posterior, so its sample is essentially its true mean every time. Uncertainty buys the arm extra chances exactly in proportion to how unsure we are — no explicit bonus, no coin flip, just the geometry of the beliefs.
Two arms after some play. Arm X: 8 successes, 2 failures, so its posterior is Beta(9, 3) — a fairly confident bump near 8/10 = 0.80. Arm Y: 1 success, 1 failure, posterior Beta(2, 2) — a wide, flat hump centered at 0.50 but spreading from near 0 to near 1. On this round we draw one sample from each: say X draws 0.78 (close to its mean — it's confident) and Y draws 0.83 (a high draw from its wide belief — entirely plausible). We pull Arm Y, because its sample 0.83 beat X's 0.78. Y got chosen not because we think it's better — we don't — but because we're unsure enough about it that an optimistic draw was possible. That is exploration, emerging for free from the randomness of the draw.
Two arms' Beta posteriors over their success-rate. Feed a reward to an arm and watch its curve grow taller and narrower — belief concentrating. The warm arm's true rate is 0.7, the teal arm's is 0.4. Early curves are wide (a random sample could pick either); after enough data they're needles, and the sampled values almost always favor the true winner.
Now implement Thompson sampling on a 3-arm Bernoulli bandit and confirm it homes in on the best arm — the proof is in the pull counts.
Three strategies, one bandit, side by side. This is the payoff: let ε-greedy, UCB, and Thompson sampling all attack the same 6-armed bandit, and watch their cumulative regret diverge as the rounds tick by. Regret is the scoreboard from Chapter 2 — lower is better, and the shape of each curve tells you everything.
What to look for as it runs:
Press Race. Six arms, one clearly best. Three agents run the same horizon; each line is its cumulative regret (lower = better). Watch ε-greedy (red) keep climbing while UCB (teal) and Thompson (warm) bend over and flatten. Slide the horizon to stretch the race; the gap widens with time.
Re-run it a few times. Because rewards are random, the exact ordering of UCB vs Thompson can swap from run to run — both are no-regret, both excellent. But the qualitative story is rock-solid: the two adaptive methods flatten, fixed ε-greedy does not. That gap is the difference between sublinear and linear regret, and it is why nobody ships a fixed-ε bandit in production when UCB or Thompson is a few lines away.
So far every round looked identical: the same arms, the same hidden means, every time. But most real problems hand you a clue before you choose. The visitor on your site has an age and a country; the patient has a chart; the user has a watch history. The best arm depends on that clue. This is the contextual bandit.
In a plain bandit, the reward of arm a is just r(a), and we estimate a single number Q(a) per arm. In a contextual bandit, the reward depends on a context s that you observe at the start of each round: the reward is r(s, a) and we estimate Q(s, a). Same explore–exploit machinery — ε-greedy, UCB, Thompson all carry over — but now the value is a function of both the context and the action.
Practically, contextual bandits are the workhorse of real recommendation and ad systems precisely because they capture "personalize the choice to who's in front of me" without paying the full cost of planning over a future. They are also the natural home of the personalization example from lecture: each user-topic pair is a context-action, and a "like" is the reward.
Every algorithm so far assumed a reward number falls out of each pull — a click, a payout, a 0/1 success. But the lecture's last move asks a deeper question: what if there is no reliable number? In many real applications rewards aren't directly measurable, or an absolute score is meaningless.
How good, on a scale of 0 to 100, was that meal? That paragraph? That robot trajectory? People are terrible at absolute scores — everyone's scale drifts, a "7" today is an "8" tomorrow. But ask "did you prefer A or B?" and people are fast, consistent, and reliable. The lecture's example: a user clicks search result #2. One reading is absolute ("#2 is good"); the far more trustworthy reading is relative ("#2 is better than #1"). Preference-based feedback is easier to obtain and often more reliable than a number.
This reshapes the bandit. Instead of pulling one arm and reading its reward, each round you present a pair of arms and learn only which one won the comparison — the dueling bandit problem (Yue, Broder, Kleinberg & Joachims). The feedback is one bit: "A beat B." No payoff scale anywhere. As the dueling-bandits paper puts it, this fits applications where absolute rewards "have no natural scale or are difficult to measure (user-perceived quality, taste of food, product attractiveness), but where pairwise comparisons are easy to make."
How do scattered "A beat B" bits become a usable ranking — or, crucially, a reward number we can optimize? We posit that each item i has a hidden score si, and that the probability i beats j rises smoothly with the score gap. The standard choice is the Bradley-Terry model (a logistic in the score difference):
Read it: if two items have equal scores, the gap is 0 and each wins half the time (a coin flip, σ(0) = 0.5). The bigger i's score advantage, the closer the win probability to 1. Given a pile of observed comparisons, we fit the scores si by maximum likelihood — nudge each score up or down until the model's predicted win-rates best match the comparisons we actually saw (logistic regression on score differences). Out comes a single number per item, recovered from nothing but "this beat that."
Trace the data so you could build it. In: a set of comparisons, each a triple (winner i, loser j). Model: one learnable score si per item; predicted win-prob σ(si − sj). Loss: negative log-likelihood — for each comparison, −log σ(swinner − sloser) — summed over all comparisons. Fit: gradient descent on the scores. Out: a score vector that orders the items (and, scaled, serves as a reward). The scores are only identified up to an additive constant (shifting everyone by +5 changes no comparison), so we pin one down — exactly as RLHF reward models are defined only up to a baseline.
Now fit a Bradley-Terry model yourself: turn a table of pairwise wins into a score per item, and confirm the recovered scores order the items correctly.
You arrived knowing how to average. You leave able to balance exploration against exploitation optimally, prove an algorithm is "no-regret," and learn a reward from nothing but human preferences — the seed of RLHF. Here is the whole lecture on one page.
| Method | How it explores | Regret | Tuning knob |
|---|---|---|---|
| Greedy | not at all | linear (can lock in) | none |
| ε-greedy | random arm w.p. ε | linear (fixed ε) | ε (decay it) |
| UCB | optimism: Q + bonus | sublinear, ~√(T log T) | constant c |
| Thompson | sample the posterior | sublinear, great in practice | the prior |
| Contextual bandit | any of the above, on Q(s,a) | sublinear | — |
| Dueling / preference | compare pairs, fit scores | sublinear (log T) | — |
"You can do both exploitation and exploration — but not at the same time." — from the lecture. Every algorithm you just learned is a different, beautiful answer to how to split the difference.