Exploration vs Exploitation

Most of the models in these Knowledge pages learn from a dataset that someone else collected. A bandit algorithm collects its own. Each round it picks one option, sees how that one option paid off, and then picks again. That small change creates a choice supervised learning never faces. The learner can go with the option that looks best so far, or it can spend a round on an option it knows less about. This note is about that choice.

The idea

Picture a new suburb with four cafés, each of which you have tried once. The one on the corner was good, so you could go back every morning. You would then never learn whether the café by the station is better, because one bad coffee on a busy day put you off it. Going back to the corner is exploitation, using what you already know to get a good result today. Trying the station again is exploration, giving up a probably good morning to learn something that could pay off for months.

The trade-off appears whenever a learner's own choices decide what it gets to see. The cleanest version is the multi-armed bandit. There are several arms, each with an unknown average reward. Every round you pull one arm and see only that arm's reward. Nothing you do changes the arms, so there is no state to plan around, only the question of where to spend each pull. A bandit is a Markov decision process with a single state, the simplest case in the Reinforcement Learning topic. Most of what makes exploration hard in full RL already shows up here, in a form small enough to simulate in a browser.

Exploring has a price, and the price is reward. Every pull spent on a worse arm is reward you did not collect. The usual way to count it is regret, the reward you gave up compared with someone who knew the best arm from the start.

The maths

Let arm $a$ have mean reward $\mu_a$ , and call the largest mean $\mu^{*}$ . After arm $a$ has been pulled $N_a$ times, its estimate $Q_a$ is the average of the rewards it returned. You do not need to keep every reward to update it, because the running mean takes one line.

Q_a \leftarrow Q_a + \frac{1}{N_a}\bigl(R - Q_a\bigr)

The estimate moves a fraction 1/Nₐ of the way towards the latest reward R. Early rewards move it a lot and later ones barely move it.

Greedy pulls the arm with the highest $Q_a$ every round. ε-greedy does the same most of the time, but with probability $\varepsilon$ it pulls an arm chosen at random.

A_t = \begin{cases} \arg\max_a Q_a & \text{with probability } 1-\varepsilon \\ \text{an arm chosen uniformly at random} & \text{with probability } \varepsilon \end{cases}

ε-greedy explores blindly. It is as likely to retry an arm that has failed 200 times as one it has barely touched. UCB1 (upper confidence bound) aims its exploration. It adds a bonus to each estimate that is large while the arm has few pulls and shrinks as $N_a$ grows, then pulls the arm with the highest total.

A_t = \arg\max_a \left[\, Q_a + c\sqrt{\frac{\ln t}{N_a}} \,\right]

Every arm is pulled once first, so Nₐ is never zero. Auer, Cesa-Bianchi and Fischer's UCB1 uses c = √2 for rewards between 0 and 1.

The $\ln t$ in the bonus grows slowly, so an arm that has been ignored for a long time slowly earns another look. An arm with a low estimate and many pulls has a small bonus and stays ignored. This is optimism in the face of uncertainty. Each arm is treated as if it could be as good as the data still allows, and the pulls are left to prove it wrong.

\operatorname{Regret}(T) = T\mu^{*} - \mathbb{E}\Bigl[\sum_{t=1}^{T} R_t\Bigr] = \sum_{a} \Delta_a\, \mathbb{E}\bigl[N_a(T)\bigr], \qquad \Delta_a = \mu^{*} - \mu_a

Each pull of a worse arm costs its gap Δₐ, so regret counts how often each worse arm was pulled and how much worse it was.

How regret grows with $T$ is the score that matters. Greedy can lock onto a worse arm and stay there, so its regret grows in a straight line. ε-greedy with a fixed $\varepsilon$ keeps exploring at the same rate forever, so its regret also grows in a straight line, with a slope set by $\varepsilon$ and the gaps. UCB1's regret grows like $\ln T$ , because a worse arm is only pulled about as often as it takes to rule it out. Lai and Robbins showed in 1985 that any rule that does well on every bandit problem has regret growing at least like $\ln T$ , so UCB1 already has the best possible shape.

Try it

The simulator below runs all three rules on the same four-armed bandit. Each arm pays 1 with its hidden probability and 0 otherwise. Every line is the mean of 20 seeded runs, and the three rules see the same random draws, so any gap between the lines comes from the rules themselves.

ε, how often ε-greedy explores0.10

c, the weight on UCB1's bonus0.5

Rounds

Seed 7

Show the true means

UCB1
ε-greedy
Greedy

Read the chart at round500

Share of pulls going to each arm (A to D) and regret by round 500, mean of 20 seeded runs.
Rule	Aμ ?	Bμ ?	Cμ ?	Dμ ?	Regret
UCB1	4%	1%	77%	17%	15.5
ε-greedy	6%	3%	60%	31%	27.9
Greedy	16%	5%	34%	45%	48.6

By round 500, mean regret is 15.5 for UCB1, 27.9 for ε-greedy and 48.6 for greedy. UCB1 gave the best arm 77% of its pulls, ε-greedy 60% and greedy 34%.

Simulation with synthetic data, seeded so a run repeats. Hover over the chart, or use the round slider, to read the numbers at any round.

Set ε to 0. The ε-greedy line lands exactly on greedy, because without random pulls the two rules are the same.
Set c to 0. UCB1 collapses onto greedy as well.
Raise c to 1.4, close to the √2 in the original paper. At 500 rounds UCB1 now trails ε-greedy. The √2 comes from a bound that has to hold for any rewards between 0 and 1, and on this problem that much caution costs more than it saves.
Switch to 2,000 rounds and look at the shapes. Greedy and ε-greedy keep climbing in straight lines while UCB1 flattens out.
Press New arms a few times. On some problems greedy gets lucky and looks fine. Averaged over many problems it does not.

Where I used it

COMP90051 · Bandit Lab

My COMP90051 project in 2023 was a bandit problem. I built successive-elimination bandits that cope with late or lost feedback, Thompson sampling and Doubly-Adaptive Thompson Sampling, and evaluated them by replaying 300,000 recorded news clicks. In 2026 I rebuilt it as Bandit Lab, where up to seven algorithms race on a seeded synthetic log whose delays you can reshape. ε-greedy and UCB1 are its baselines, so this note is the warm-up and the lab is the full version. This race of ε-greedy, UCB1 and Thompson sampling opens on the view that steps through what each algorithm believes, round by round.

The same trade-off sits under A/B testing. A fixed 50/50 test explores for its whole run and only exploits once you call a winner. A bandit moves traffic towards the better variant while the test is still running. It loses less along the way, but the final estimate is harder to read, because the algorithm chose which data it collected. When the goal is a clean estimate of the difference, a plain randomised test is still the better tool (see Causal Inference).

Easy to get wrong

Five traps, one of them from my own notes

Counting the cost of exploring as compute. My 2023 wiki page said exploration was expensive to compute. A pull costs the same whichever arm you choose. What exploring costs is reward, and regret is how you measure it.
Keeping ε fixed forever. A constant ε never stops paying for exploration, so regret keeps growing in a straight line. Letting ε decay over time fixes the shape, but the schedule needs tuning for each problem, which UCB1 avoids.
Treating c = √2 as a law. It comes from a worst-case bound for rewards between 0 and 1. If your rewards sit on another scale, rescale them or retune c. Otherwise the bonus is either too small to matter or large enough to drown out the estimates.
Judging a rule on one run. A single bandit run is noisy, and greedy wins some of them. Compare over many seeded runs that share their random draws, which is what the simulator above and Bandit Lab both do.
Assuming the arms stand still. The running mean gives a reward from round 1 the same weight as one from round 1,000. If the arms drift, as click rates do, use a constant step size or a sliding window so old rewards fade.

Sources

Reinforcement Learning: An IntroductionSutton and Barto, 2nd edition, MIT Press, 2018. Chapter 2.The friendliest place to start. Chapter 2 builds ε-greedy, optimistic starting values and UCB on a ten-armed test problem, and the whole book is free to read online.
Bandit AlgorithmsLattimore and Szepesvári, Cambridge University Press, 2020.The reference when you want the proofs, including UCB's regret bound and the lower bound below. The authors host a free PDF.
Finite-time analysis of the multiarmed bandit problemAuer, Cesa-Bianchi and Fischer, Machine Learning 47, 2002, pp. 235–256.The paper behind UCB1. It proves a logarithmic regret bound for any finite number of rounds, where earlier results only held as the number of rounds grew without limit.
Asymptotically efficient adaptive allocation rulesLai and Robbins, Advances in Applied Mathematics 6(1), 1985, pp. 4–22.The lower bound. A rule that does well on every bandit problem cannot keep its regret below a multiple of ln T.

First drafted in my UOM-DS wiki (2023), rewritten from scratch in 2026.