Bandits: exploration vs. exploitation

You moved to a new neighborhood a month ago. There are five restaurants within walking distance. You have eaten at two of them; one was good. Tonight, do you go back to the good one, or try one of the three you have never been to?

If you always go back, you might eat at the second-best restaurant for the rest of your life and never know it. If you keep trying new places, you will eat a lot of mediocre dinners. Every learning agent faces this same tension between exploitation (doing what currently looks best) and exploration (doing something else to find out whether it is better). In Chapter 1 you met it as one of the core challenges of RL: because your actions choose your data, you only learn about the options you try.

This chapter studies that tension in its purest form, the multi-armed bandit. There are no states and no delayed consequences, just repeated choices and rewards. Everything difficult about bandits comes from exploration, so it is the cleanest place to understand it. You will meet five strategies (greedy, ε-greedy, optimistic initial values, UCB, Thompson sampling), learn how to score them (regret), and see why the problem matters for language models: RLHF on a single response is a bandit with a context.

The K-armed bandit

The name comes from slot machines, which are sometimes called “one-armed bandits”. Picture a row of $K$ slot machines. Each one pays out according to its own fixed probability distribution, which you don’t know. At each step $t = 1, 2, \dots, T$ you choose one machine (one arm) $a_t$, pull it, and receive a reward $r_t$. Your goal is to collect as much total reward as possible over the $T$ pulls.

The quantity that matters about each arm is its mean payout, the action value

If you knew $q_*$, the problem would be solved: pull $\arg\max_a q_*(a)$ every time. You don’t, so you keep an estimate $Q_t(a)$ built from the rewards you have seen, and you choose arms based on those estimates. The catch is that the estimates are only as good as your data, and your data depends on your choices.

A concrete example, which we’ll reuse. Four machines pay 1 (a win) or 0 (a loss), with hidden win probabilities

Arm 3 is best. Rewards that are 0 or 1 like this are called Bernoulli rewards; they are the natural model for clicks, conversions, and “was the answer correct?”.

In the language of Chapter 1, a bandit is an RL problem with a single state. The environment never changes in response to what you do; pulling arm 2 now does not change what arm 3 will pay later. That removes the credit-assignment problem (every reward is caused by the action just taken) and leaves only the exploration problem. Chapter 3 adds states back in.

Keeping score: regret

How should you judge a strategy? Total reward is natural but hard to compare across problems: 35 wins out of 50 is excellent on one set of machines and poor on another. Instead we compare against an oracle that knows the best arm. The regret after $T$ steps is

In words: the expected reward you gave up by not pulling the best arm every time. It uses the true means of the arms you chose, not the rewards you happened to get, so lucky wins on a bad arm don’t hide a bad choice.

Regret has a useful second form. Write $\Delta_a = \max_b q_*(b) - q_*(a)$ for the gap of arm $a$: how much worse it is than the best arm. Each pull of arm $a$ costs exactly $\Delta_a$, so

where $N_{T+1}(a)$ is the number of times arm $a$ was pulled in the whole game. Say you pulled our four arms 2, 3, 4 and 1 times in 10 steps. The gaps are $(0.40, 0.15, 0, 0.25)$, so

The first form gives the same answer: $10 \times 0.70 - (2 \times 0.30 + 3 \times 0.55 + 4 \times 0.70 + 1 \times 0.45) = 7 - 5.5 = 1.5$. The second form tells you what a good algorithm must do: pull bad arms rarely, and the worse the arm, the more rarely.

Before reading about any algorithm, play the game yourself.

You probably did something sensible: tried each machine a few times, then mostly pulled the one that looked best, with an occasional check on a runner-up. The rest of this chapter turns that instinct into algorithms and asks how good they can be.

Estimating an arm’s value

The obvious estimate of $q_*(a)$ is the sample average of the rewards arm $a$ has produced:

where $N_t(a)$ counts the pulls of $a$ before step $t$. By the law of large numbers, $Q_t(a) \to q_*(a)$ as $N_t(a) \to \infty$. The question is only how to compute it cheaply.

Focus on one arm and drop the $a$. Let $r_1, \dots, r_n$ be its first $n$ rewards and $Q_{n+1} = \frac{1}{n}\sum_{i=1}^{n} r_i$ the average after them. You don’t need to store all the rewards. Each new reward moves the average a fraction $\frac{1}{n}$ of the way toward itself:

You’ll derive this in Exercise 2.1 (it takes three lines). A worked example: arm 3 pays $1, 0, 0, 1, 1$ on its first five pulls.

The final value is $3/5$, the plain average. Notice that the first step has step size 1, so whatever $Q_1$ you started from is overwritten immediately.

Greedy, and how it gets stuck

The simplest strategy uses the estimates directly: always pull the arm that currently looks best,

breaking ties at random. This is the greedy policy. It never explores on purpose, and that is fatal.

Take two arms with $q_*(1) = 0.9$ and $q_*(2) = 0.5$, both estimates starting at 0. At the start the estimates tie, so greedy picks at random. Suppose it picks arm 2 and arm 2 pays 1. Now $Q(2) = 1$ and $Q(1) = 0$, so greedy pulls arm 2 next time. Can $Q(2)$ ever fall back to 0? No: arm 2’s average includes that first win, so $Q(2) \geq 1/n > 0$ forever. And $Q(1)$ stays at exactly 0, because greedy never pulls arm 1 again to learn otherwise. Greedy is now locked onto the worse arm for the rest of time, losing $\Delta = 0.4$ per step. Its regret grows linearly in $T$. Exercise 2.2 asks you to compute the probability of this lock-in (it’s about 36%).

The deeper problem: greedy treats its estimates as facts. An arm with one unlucky pull looks bad, so it is never pulled again, so its estimate never gets corrected. Mistakes that make an arm look too good get fixed (you keep pulling it and the average comes down). Mistakes that make an arm look too bad are permanent. Exploration exists to fix the second kind.

Switch the slot-machine demo above to Greedy and press Play a few times (Restart between games). Some games it finds the best machine; in others it settles on a mediocre machine after one or two lucky pulls and never looks back.

ε-greedy: explore on purpose

The simplest fix is to explore at random some fixed fraction of the time. The ε-greedy policy is:

at each step t:
    with probability ε:   pick an arm uniformly at random      (explore)
    otherwise:            pick argmax_a Q(a), ties at random   (exploit)
    pull it, observe r
    N(a) ← N(a) + 1
    Q(a) ← Q(a) + (1 / N(a)) · (r − Q(a))

Because every arm keeps being pulled (each with probability at least $\epsilon / K$ per step), every estimate eventually converges to the truth, and the exploit steps end up on the best arm. With $\epsilon = 0.1$ and $K = 10$, the agent eventually pulls the best arm $0.9 + 0.01 = 91\%$ of the time.

That remaining 9% is the price. ε-greedy explores forever at the same rate, even after it has seen thousands of pulls and is sure which arm is best. Each exploration step pulls a random arm and costs, on average, $\frac{1}{K}\sum_a \Delta_a$. So the regret of ε-greedy also grows linearly, at a rate of at least $\frac{\epsilon}{K}\sum_a \Delta_a$ per step (Exercise 2.5). It is a much smaller line than greedy’s, but it is still a line. Lowering ε makes the slope smaller but slows down learning at the start; a schedule that decays ε over time can fix this, but only if it is tuned to the problem.

Exploration in ε-greedy is also undirected: when it explores, it is as likely to re-check an arm it has pulled 500 times as one it has pulled twice, and as likely to try an arm that is clearly terrible as one that is nearly tied with the leader. The methods below explore where it is useful.

Optimistic initial values

Here is a trick that makes even greedy explore. Start every estimate high, above any reward you expect: for 0/1 rewards, $Q_1(a) = 1$. Now every arm looks wonderful until it has been tried. Greedy pulls one, gets a reward below the optimistic guess, and that arm’s estimate drops below the untried ones, so greedy moves on to another. Every arm gets tried, and arms keep being retried until their estimates have been pulled down to their real level. The best arm is the one that disappoints least.

There is a subtlety. With the sample average (step $1/n$) the initial value is forgotten after one pull, because the first step size is 1 (look back at the table above). So optimism only guarantees that each arm is tried once. To make it last, Sutton and Barto pair it with a constant step size, $Q \leftarrow Q + \alpha(r - Q)$ with $\alpha = 0.1$, under which the initial value fades geometrically (we study constant step sizes properly below). The race demo later in the chapter uses that version: initial value 1 for 0/1 rewards, 5 for Gaussian ones, $\alpha = 0.1$.

Optimistic initialization is cheap and often works well on small stationary problems. But all its exploration happens at the beginning, driven by an arbitrary number you chose; if the world changes later, nothing makes it explore again. The next idea keeps the optimism and makes it principled.

UCB: optimism in the face of uncertainty

Look at what optimistic initialization got right: it treated an arm we know little about as if it might be great. Upper confidence bound (UCB) methods make this precise. For each arm, ask: given the data so far, how good could this arm plausibly be? Then pull the arm with the highest plausible value.

An estimate built from $N$ samples has a statistical error of order $1/\sqrt{N}$. So add to each estimate a bonus that is large when $N_t(a)$ is small:

where $t$ is the number of pulls so far and untried arms count as having an infinite score, so they are tried first. (Sources differ by one in how they count $t$; it changes nothing important.) The constant $c$ sets how wide the “plausible” range is. The version called UCB1 (Auer, Cesa-Bianchi and Fischer, 2002) uses $c = \sqrt{2}$ for rewards in $[0, 1]$; the derivation below shows where the $\sqrt{2}$ comes from.

Read the bonus term by term:

• $1/\sqrt{N_t(a)}$: every pull of arm $a$ shrinks its own bonus. An arm you have measured carefully gets little benefit of the doubt.
• $\sqrt{\ln t}$: while an arm is not being pulled, $t$ keeps growing, so its bonus slowly rises. No arm is abandoned forever; a neglected arm is eventually re-checked. Because $\ln t$ grows very slowly, the re-checks become rare.
• $Q_t(a)$: arms that look good are favored, as in greedy.

An arm gets pulled either because its estimate is high (exploitation) or because its uncertainty is high (exploration). The formula trades the two automatically.

A worked example

Three Bernoulli arms after $t = 20$ pulls, with $c = \sqrt{2}$ and $\ln 20 = 3.00$:

UCB pulls arm 3, which has never paid out, because two pulls are too few to rule out that it is the best arm. (Scores above 1 are fine: they are optimistic scores, not probabilities.) Suppose arm 3 loses again. Now $t = 21$, $\ln 21 = 3.04$, arm 3 has $N = 3$, and the scores become $1.30$, $1.51$, $1.42$. Arm 2 is next. Arm 1 has the highest estimate but the lowest score, because it is already well measured and an extra pull would teach little.

Switch the slot-machine demo to UCB and step through a game. The blue bars run from each estimate (dot) up to its score; when scores exceed 1, the vertical axis stretches to fit them. Watch the tallest bar get pulled, then shrink.

The $\sqrt{2}$ comes from demanding that the bound fail with probability only $t^{-4}$, for any rewards in $[0, 1]$, so it is conservative. In practice $c$ is a tuning knob, and it should scale with how noisy the rewards are. For 0/1 rewards (standard deviation at most 0.5), $c \approx 0.5$ usually works much better than $\sqrt{2}$, and both demos in this chapter start there. For Gaussian rewards with standard deviation 1, the race demo switches to $c = 1$.

Thompson sampling: act on a plausible world

UCB asks “how good could each arm be?” and acts as if the most optimistic answer were true. Thompson sampling asks a different question: “what do I currently believe about each arm?”, keeps that belief as a full probability distribution, and acts on a random draw from it. It is the oldest idea in this chapter (Thompson, 1933) and often the best performer in practice.

Beliefs about a coin

Take one Bernoulli arm with unknown win probability $\theta = q_*(a)$. Before any pulls, a reasonable belief is “any $\theta$ in $[0, 1]$ is equally likely”: the uniform distribution, which is the Beta distribution $\text{Beta}(1, 1)$. In general $\text{Beta}(\alpha, \beta)$ has density

(Here $\alpha$ and $\beta$ are just the two shape parameters of the Beta distribution. They are unrelated to the step size $\alpha$ later in this chapter and to the KL coefficient $\beta$ of Part III; the letters are traditional in all three places.)

Now pull the arm and see a win. Bayes’ rule multiplies the prior by the likelihood of a win, which is $\theta$: the posterior is $\propto \theta^{\alpha}(1-\theta)^{\beta - 1}$, that is, $\text{Beta}(\alpha + 1, \beta)$. A loss multiplies by $1 - \theta$ and gives $\text{Beta}(\alpha, \beta + 1)$. So the whole belief is two counters:

(A prior that stays in the same family after an update is called conjugate; Beta is conjugate to Bernoulli.) The prior acts like one imaginary win and one imaginary loss. An arm with 3 wins and 1 loss has posterior $\text{Beta}(4, 2)$, mean $4/6 = 0.67$, a little below the raw average $0.75$. As data accumulates the posterior narrows around the true $\theta$; its standard deviation shrinks like $1/\sqrt{N}$, the same rate as UCB’s bonus.

The algorithm

keep α(a) = β(a) = 1 for every arm
at each step t:
    for each arm a: draw θ(a) ~ Beta(α(a), β(a))     (one plausible world)
    pull a_t = argmax_a θ(a)                        (the best arm in that world)
    observe r ∈ {0, 1}
    α(a_t) ← α(a_t) + r ;  β(a_t) ← β(a_t) + (1 − r)

That’s all. There is no exploration parameter to tune. Each step imagines one world consistent with the evidence and plays optimally in that world.

Why does this explore well? Each arm is pulled with exactly the posterior probability that it is the best arm. This property is called probability matching. An arm with a wide posterior sometimes produces a high draw, so it gets tried. An arm whose posterior is narrow and clearly below the leader almost never wins the draw, so it is (correctly) ignored. As evidence accumulates, the posteriors sharpen and exploration fades on its own.

A worked example with three arms:

(The last column was computed by sampling.) B and C have the same mean, 0.5, but B is pulled more than twice as often, because B’s uniform posterior gives real probability to $\theta_B > 0.67$ while C’s twelve pulls have pinned it near 0.5. Exercise 2.4 has you compute a case like this exactly.

Switch the slot-machine demo to Thompson. Each machine shows its Beta posterior as a green violin shape and the value it drew this step as a diamond. Early on the violins are wide and the diamonds jump around; after a few dozen pulls the best machine’s violin is narrow and high, and it wins almost every draw.

How good can a strategy be?

You now have five strategies. Before racing them, what is the best regret any strategy could possibly get?

Not zero. Any strategy has to pull each bad arm a few times to find out it is bad. In 1985, Lai and Robbins made this precise. Informally: for any strategy that does reasonably well on every bandit problem (its regret grows more slowly than any power of $T$), each suboptimal arm must be pulled at least

times as $T \to \infty$, where $\mathrm{KL}$ is the Kullback–Leibler divergence between the arm’s reward distribution and the best arm’s (for Bernoulli arms, $\mathrm{KL}(p \Vert q) = p \ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q}$). Multiplying by $\Delta_a$ and summing gives the Lai–Robbins lower bound: regret must grow at least like $\ln T$, with a constant set by how hard the arms are to tell apart.

So the target is logarithmic regret. Here is the scorecard:

Two honest caveats. First, these are statements about large $T$, and constants matter. Over 1,000 pulls, ε-greedy with ε = 0.1 beats UCB1 with its textbook $c = \sqrt{2}$; set $c$ to 1.41 in the race below to see it. Second, $\ln T / \Delta$ blows up when gaps are tiny; for the worst-case problem at a given $T$, no algorithm can guarantee regret smaller than order $\sqrt{KT}$ (UCB1 achieves that up to a log factor). Lattimore and Szepesvári’s book covers both kinds of bound carefully.

Things to notice in the race (default settings, Bernoulli rewards; exact numbers vary with “New bandits”):

• Greedy reaches about 20% best-arm pulls and stays there forever. Its regret is a steep straight line, about 250 after 1,000 steps.
• ε-greedy learns quickly, then its regret keeps growing in a straight line (about 65–70 after 1,000 steps), with a slope set by ε. In “Where the pulls went” it gives 1% of its pulls to every arm, even the worst, by construction.
• Optimistic greedy does surprisingly well on this problem (about 45).
• UCB with $c = 0.5$ and Thompson sampling are best (about 35 and 30), and their regret curves keep flattening. By the end, Thompson puts nearly 90% of its pulls on the best arm.
• With Gaussian rewards the order changes a little: UCB with $c = 1$ edges ahead of Thompson, and optimistic greedy ends near ε-greedy’s total. Its initial value of 5 is far above every arm, so it spends its first few hundred pulls wearing that optimism down on every arm; after that its curve is much flatter than ε-greedy’s. “Usually the strongest” is a tendency, not a law.

When the world changes: constant step sizes

Everything so far assumed stationary arms: each $q_*(a)$ is fixed forever. Real problems drift. A restaurant changes chefs; users’ tastes shift; in RL proper, the “arm values” an agent estimates change as its own policy improves (that is how Chapter 5 will use these updates).

The sample average is the wrong tool for a moving target. After 1,000 pulls its step size is $1/1000$, so it would take hundreds of new rewards to move it. The fix is to stop shrinking the step: use a constant $\alpha \in (0, 1]$,

Unrolling this recursion (Exercise 2.6) shows what it computes:

This is an exponential recency-weighted average: the newest reward gets weight $\alpha$, the one before it $\alpha(1-\alpha)$, then $\alpha(1-\alpha)^2$, and so on; the weights (including the one on $Q_1$) sum to 1. With $\alpha = 0.1$ a reward’s weight halves about every 7 steps, so the estimate “remembers” roughly the last $1/\alpha = 10$ rewards. Physicists will recognize a discrete low-pass filter, the response of an RC circuit with time constant $1/\alpha$ steps.

The price of tracking is noise. The sample average converges to $q_*(a)$; the constant-α average never settles but keeps jittering, with variance $\frac{\alpha}{2 - \alpha}\sigma^2$ for rewards of variance $\sigma^2$ (Exercise 2.6). Small α means less jitter but slower tracking. The classical conditions for a step-size sequence $\alpha_n$ to converge to the true mean (the Robbins–Monro conditions) are

$\alpha_n = 1/n$ satisfies both. A constant α fails the second on purpose: in a nonstationary world you want to keep moving.

In the race demo, tick Shuffle the arms halfway: at the midpoint, the arms’ true means are randomly reassigned, so the best arm is suddenly some other arm. Everyone’s ”% best arm” crashes. The sample-average ε-greedy agent barely recovers, because hundreds of old rewards outvote each new one. Now tick ε-greedy forgets (constant α = 0.1): it recovers far faster. (One detail: the demo’s forgetting agent uses the plain average for an arm’s first 10 pulls and α = 0.1 after that. Starting with a constant α from $Q_1 = 0$ would leave weight $(1-\alpha)^n$ on that 0, dragging down the estimates of arms that have been explored only a few times.) Optimistic greedy, which also uses α = 0.1, recovers fastest of all, and UCB recovers well too. Thompson sampling, whose model says the arms never change, is the slowest of the three principled methods to recover (though still faster than sample-average ε-greedy). Exercise 2.8 asks you to explain each curve.

Contextual bandits

In many problems you see some information before choosing. A news site sees who is visiting before picking which article to show; a doctor sees the patient before picking a treatment. A contextual bandit adds this: at each step

1. the environment shows you a context $x_t$ (drawn from some distribution, not caused by you),
2. you choose an action $a_t$ using a policy $\pi(a \mid x_t)$,
3. you receive a reward $r_t$ with mean $q_*(x_t, a_t)$, and the round ends.

Your action affects only the current reward, never the next context. That is the line between contextual bandits and full RL: in an MDP (Chapter 3) your action also changes the next state.

With many contexts you can’t keep a separate table of estimates for each one, so you learn a model $Q(x, a)$ that generalizes across contexts, and explore with the same principles as before. LinUCB (Li, Chu, Langford and Schapire, 2010), for example, uses a linear model per article and a UCB-style bonus based on the model’s uncertainty; the paper tests it on news recommendation with real traffic from Yahoo!‘s front page.

Bandits also return in Chapter 7, which learns a softmax policy over a bandit’s arms directly by gradient ascent (the “gradient bandit”), and in Chapter 10, where the UCB formula reappears inside Monte Carlo tree search as UCT, the rule for choosing which moves to explore, and AlphaGo-style search uses a variant of it.

Summary

• A K-armed bandit is RL with one state: choose an arm, get a reward, repeat. Only exploration vs. exploitation remains.
• Estimate each arm’s value $q_*(a)$ by its sample average, computed incrementally as $Q \leftarrow Q + \frac{1}{n}(r - Q)$. The pattern “estimate ← estimate + step × (target − estimate)” runs through all of RL.
• Regret $= \sum_a \Delta_a N_{T+1}(a)$ measures what exploration costs. Greedy and fixed-ε ε-greedy have linear regret; the best possible is logarithmic (Lai–Robbins), with a constant set by how hard arms are to tell apart.
• Greedy can lock onto a bad arm forever: estimates that are too low never get corrected. Optimistic initial values force early exploration but stop exploring later.
• UCB pulls the arm with the highest plausible value, $Q + c\sqrt{\ln t / N}$: optimism in the face of uncertainty. UCB1’s regret is $O(\ln T)$, proved with Hoeffding’s inequality.
• Thompson sampling keeps a posterior (Beta for 0/1 rewards), samples one plausible world, and acts optimally in it. Each arm is pulled with the probability that it is best. It is simple, has no exploration parameter to tune, and is usually the strongest of the five.
• For nonstationary problems, use a constant step size α: an exponential recency-weighted average with memory about $1/\alpha$.
• A contextual bandit adds a context before each choice. An LLM responding to a prompt and getting a reward is one, which is the view Chapters 11–16 build on.

Exercises

cd 02-bandits
python -m pytest -q          # your code: tests fail until you fill in the TODOs
RL_SOLUTIONS=1 python -m pytest -q   # reference solutions: all pass

Further reading

• Sutton & Barto (2018), Reinforcement Learning: An Introduction, ch. 2. The classic treatment and the source of the 10-armed testbed, optimistic initial values and the gradient bandit. Sections 2.1–2.7 match this chapter.
• Lattimore & Szepesvári (2020), Bandit Algorithms. The reference for the theory, free online: UCB and its analysis, lower bounds (Lai–Robbins and minimax), Thompson sampling, contextual and linear bandits. Read the chapters on UCB and on lower bounds first.
• Russo, Van Roy, Kazerouni, Osband & Wen (2018), A Tutorial on Thompson Sampling. A readable tutorial with many examples, including Thompson sampling beyond Beta–Bernoulli.
• Auer, Cesa-Bianchi & Fischer (2002), Finite-time Analysis of the Multiarmed Bandit Problem. The UCB1 paper; the proof of Theorem 1 is the one sketched in this chapter’s derivation, and it also analyzes the decaying-ε schedule.
• Slivkins (2019), Introduction to Multi-Armed Bandits. A shorter, more lecture-like book than Lattimore & Szepesvári.
• Li, Chu, Langford & Schapire (2010), A Contextual-Bandit Approach to Personalized News Article Recommendation. LinUCB, and a well-known example of contextual bandits running on a real website.
• Kaufmann, Korda & Munos (2012), Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis. Shows Thompson sampling matches the Lai–Robbins lower bound for Bernoulli arms.

Next, the world starts to respond to you: Chapter 3 adds states that change with your actions, and with them the idea of planning ahead.