Exploration vs Exploitation (Bandits and Epsilon Schedules)

Reinforcement learning has one difficulty that supervised learning does not: the data depends on what you do. A classifier is handed a labelled set; an agent only learns about an action by taking it, and every action taken is one not taken elsewhere.

A k-armed bandit is that dilemma with everything else removed. There are ten levers, each paying out from a fixed but unknown Gaussian, and the only question is which lever to pull next. No states, no transitions, no credit assignment across time — just the trade-off.

Because the arms are fixed and known to the experimenter, regret is exact: the reward given up by not pulling the best arm. Zero is unreachable — you cannot know which arm is best without trying the others — and that is precisely what makes it a good measurement.

Strategy	Total regret	sd	Best seed	Worst seed	Optimal action share
Greedy (ε = 0)	520.92	564.19	0.00	2394.40	0.3200
ε-greedy 0.1	224.74	122.62	69.91	789.46	0.8012
Decaying ε	373.31	117.72	130.24	788.61	0.8124
Optimistic start (+5)	137.07	243.88	6.36	1278.93	0.6600
UCB (c = 2)	152.03	31.49	75.43	244.06	0.8481

Look at the greedy row before anything else. Its best seed scored a perfect zero — it happened to try the best arm first and never left. Its worst scored 2394.40. Reporting either number alone would be a completely different conclusion about the same algorithm.

What you’ll learn

• Why a purely greedy agent can be both the best and the worst strategy, measured.
• What ε actually buys, and why ε = 0.3 (regret 480.01) is worse than ε = 0.1 (224.74).
• Two alternatives that explore without randomness: optimistic initialisation and UCB.
• Why regret falls as a problem gets harder, and what to report instead.

The setup

Ten arms, fixed means, Gaussian noise

class Bandit:
    def __init__(self, arms=10, seed=0, spread=1.0, noise=1.0):
        rng = np.random.default_rng(seed)
        self.means = rng.normal(0.0, spread, arms)   # unknown to the agent
        self.best = int(np.argmax(self.means))
 
    def pull(self, arm):
        return float(self._rng.normal(self.means[arm], self.noise))
 
    def regret(self, arm):
        return self.means[self.best] - self.means[arm]

With seed 0 the arm means are +0.126, −0.132, +0.640, +0.105, −0.536, +0.362, +1.304, +0.947, −0.704, −1.265. Arm 6 is best at +1.3040, and arm 7 at +0.947 is close enough to be genuinely confusable given noise with standard deviation 1.0 — a single pull tells you almost nothing.

The agent keeps a running mean per arm, which is the whole of its learning:

$$Q_{n+1}(a) = Q_n(a) + \frac{1}{N(a)}\left[r - Q_n(a)\right]$$

Epsilon, swept

figure 10 arms, 1000 pulls, averaged over 200 different bandits matplotlib

Both extremes lose. Epsilon 0 plateaus at 0.32 optimal actions because it stops looking as soon as an arm seems good — it is stuck on whatever it got lucky with early. Epsilon 0.3 keeps 30% of its pulls random forever, so even after it knows the answer it throws away reward on purpose, and its regret line stays straight rather than flattening.

Setting	Total regret	sd	Optimal action share (last 200 pulls)
ε = 0.0	520.92	564.19	0.3200
ε = 0.01	373.27	412.00	0.5100
ε = 0.1	224.74	122.62	0.8012
ε = 0.3	480.01	150.66	0.6684
ε = 1/(1 + t/100)	373.31	117.72	0.8124

The shape of a regret curve says more than its endpoint. A curve that keeps climbing at a constant slope has an agent still paying for exploration it no longer needs — that is ε = 0.3. A curve that flattens has an agent that has settled. Greedy’s curve is neither: it is erratic across seeds, because its outcome is decided by the first few pulls.

The decaying schedule is the interesting row. Its total regret (373.31) is worse than fixed ε = 0.1, but its final optimal-action share (0.8124) is the best of the four ε settings — it spent more early and is still improving at the end. Which of those matters depends on whether the run is about to stop or about to continue.

Exploring without randomness

Two strategies get exploration without a coin flip.

Optimistic initialisation starts every arm’s estimate at +5, far above any real payout. The first pull of any arm returns something lower, so the estimate drops and another untried arm becomes the most attractive. It explores thoroughly at the start and then stops, without ever choosing randomly.

UCB picks the arm with the best optimistic bound, adding a bonus that grows with how long an arm has been neglected:

$$a_t = \arg\max_a \left[ Q(a) + c\sqrt{\frac{\ln t}{N(a)}} \right]$$

figure 200 bandits per strategy, 1000 pulls each matplotlib

Optimistic initialisation has the lowest mean regret at 137.07 and UCB is second at 152.03 — but the error bars reverse the ranking's reliability. UCB's spread across seeds is 31.49 with a worst case of 244.06, while optimistic initialisation varies by 243.88 and can reach 1278.93. If you must be right on one attempt rather than on average, those are different recommendations.

This is the part usually skipped. Optimistic initialisation wins on the mean and UCB wins on the worst case, and the gap between them is smaller than either one’s variation across seeds. On this evidence the honest statement is that both beat ε-greedy, and that choosing between them by a single run would be guesswork.

Why UCB is so consistent: its exploration is directed. It never pulls an arm at random, only one whose bound is genuinely uncertain, so it cannot waste a pull on an arm it has already ruled out. ε-greedy’s random 10% keeps re-testing arms it has known were bad for hundreds of pulls.

diagram Diagram mermaid

  flowchart TD
  Q["estimates so far"] --> D{"how to choose?"}
  D -->|"greedy"| G["best estimate
regret 520.92, sd 564.19"]
  D -->|"epsilon-greedy"| E["best, or random with prob e
regret 224.74 at e=0.1"]
  D -->|"optimistic"| O["best, starting from +5
regret 137.07, sd 243.88"]
  D -->|"UCB"| U["best upper bound
regret 152.03, sd 31.49"]
  G -.->|"never revisits"| S["0.32 optimal actions"]
  U -.->|"directed exploration"| T["0.85 optimal actions"]

Regret can fall while the agent gets worse

The last figure sweeps how far apart the arms are. It contains a trap worth walking into deliberately.

figure 80 bandits per cell, 1000 pulls matplotlib

The left panel looks like epsilon-greedy performing best on the hardest problems — 99.87 regret at spread 0.2 against 414.38 at spread 2.0. It is not. When the arms are nearly identical, picking the wrong one barely costs anything, so regret is small however badly the agent chooses. The right panel is the honest view: at spread 0.2 it is picking the best arm far less often than at spread 2.0.

Arm spread	ε-greedy 0.1	UCB (c = 2)	Greedy
0.2	99.87	171.99	125.09
0.5	149.66	186.37	290.70
1.0	217.90	156.02	593.29
2.0	414.38	112.43	1342.53

Two real findings here:

1. Low regret can mean an easy problem, not a good agent. Always report an accuracy-style measure — here the optimal-action share — beside any regret number.
2. UCB is the only strategy whose regret falls as the arms separate (171.99 → 112.43), while ε-greedy’s rises 4× and greedy’s rises 10×. When arms are far apart, UCB’s bounds resolve quickly and it stops exploring; ε-greedy keeps spending a fixed 10% of pulls on arms it has long since ruled out, and each of those mistakes now costs more.

sketch Ten arms, one thousand pulls p5.js Pause Restart

Pick a strategy and step the simulation. Bar height is the running estimate, the number beneath is how many times each arm has been pulled, and the true best arm is marked.

sketch The measured table, ranked p5.js Pause Restart

Click a column to rank every row by it. The bars are that column's values and the highest and lowest are computed from the numbers, not written in.

Pitfalls

• Ranking strategies from one run. Greedy scored 0.00 on its best seed and 2394.40 on its worst. Every number on this page is a mean over 200 bandits.
• Reading regret without a difficulty reference. ε-greedy’s regret was lowest on the hardest problem (99.87 at spread 0.2) because mistakes there are cheap.
• Assuming more exploration is safer. ε = 0.3 scored 480.01, more than double ε = 0.1’s 224.74, because it never stops paying.
• Setting ε = 0 because the estimates “look converged”. They looked converged to the greedy agent too, which ended on 0.32 optimal actions.
• Comparing total regret between runs of different lengths. Regret accumulates; a 1000-pull run cannot be compared with a 200-pull one.
• Forgetting that optimistic initialisation depends on the reward scale. +5 works because payouts are around ±1.3; on a problem with rewards in the thousands it is just a zero start.

Recap

• A bandit isolates exploration from everything else, and its regret is exact because the best arm is known to the experimenter.
• Greedy has the widest spread of any strategy — 0.00 to 2394.40 — and the lowest optimal-action share, 0.3200.
• ε = 0.1 beat both ε = 0.01 and ε = 0.3; the trade is not monotonic in either direction.
• Optimistic initialisation had the best mean regret (137.07) and UCB the best worst case (244.06, sd 31.49).
• UCB was the only strategy whose regret improved as the arms separated, because its exploration is directed rather than random.
• Always report an optimal-action share next to regret: low regret can mean an easy problem.

Next

Bandits have no states. Add them — where an action changes the situation you face next — and you need a value function and a discount factor: Introduction to Reinforcement Learning.

pch.quizTag pch.quizDefaultTitle

1. The greedy strategy scored 0.00 regret on its best seed and 2394.40 on its worst. What does that mean in practice?

   A Greedy is the best strategy when it works B A single run cannot rank strategies — greedy's outcome is decided by which arm it happens to try first, so only the distribution over many bandits is informative C The bandit implementation is broken D Greedy should be used with more pulls
   pch.quizShowAnswer

   B — A single run cannot rank strategies — greedy's outcome is decided by which arm it happens to try first, so only the distribution over many bandits is informative — Its mean regret of 520.92 with a standard deviation of 564.19 is the honest summary, and its 0.3200 optimal-action share explains why.

2. Why did epsilon = 0.3 (regret 480.01) do worse than epsilon = 0.1 (224.74)?

   A It converged to the wrong arm B It keeps making 30% of its pulls at random forever, so it continues to pay for exploration long after it has identified the best arm C Higher epsilon values are numerically unstable D It did not run for enough pulls
   pch.quizShowAnswer

   B — It keeps making 30% of its pulls at random forever, so it continues to pay for exploration long after it has identified the best arm — The shape of its regret curve shows it: a constant slope means the cost per pull never falls, unlike a curve that flattens once the agent settles.

3. Optimistic initialisation had the lowest mean regret (137.07) and UCB the second lowest (152.03), but UCB's spread was 31.49 against 243.88. Which should you pick?

   A Optimistic, since the mean is what matters B It depends on whether you get many attempts or one — UCB's worst case was 244.06 against optimistic's 1278.93, so UCB is the safer single-shot choice C Neither; epsilon-greedy is more reliable D They are statistically identical
   pch.quizShowAnswer

   B — It depends on whether you get many attempts or one — UCB's worst case was 244.06 against optimistic's 1278.93, so UCB is the safer single-shot choice — The difference in means is smaller than either strategy's variation across seeds, so the mean alone does not separate them.

4. Epsilon-greedy's regret was 99.87 when the arms were close together and 414.38 when they were far apart. Was it doing better on the hard problem?

   A Yes — lower regret is better B No — when the arms are nearly identical each wrong choice costs almost nothing, so regret is small regardless of how often it chooses wrongly; the optimal-action share shows it choosing worse there C Yes, because close arms are easier to distinguish D The comparison is invalid
   pch.quizShowAnswer

   B — No — when the arms are nearly identical each wrong choice costs almost nothing, so regret is small regardless of how often it chooses wrongly; the optimal-action share shows it choosing worse there — This is why regret should never be reported without an accuracy-style measure beside it.

5. Why is UCB the only strategy whose regret fell as the arms became easier to tell apart?

   A It uses a larger exploration constant B Its exploration is directed — it only pulls arms whose upper bound is genuinely uncertain, so once the bounds separate it stops exploring, while epsilon-greedy keeps spending a fixed fraction of pulls on arms it has already ruled out C It has a decaying epsilon built in D It ignores the noise in the rewards
   pch.quizShowAnswer

   B — Its exploration is directed — it only pulls arms whose upper bound is genuinely uncertain, so once the bounds separate it stops exploring, while epsilon-greedy keeps spending a fixed fraction of pulls on arms it has already ruled out — Random exploration costs more precisely when the arms are far apart, which is why epsilon-greedy's regret rose 4x over the same range.

🧪 Try It Yourself

pch.exerciseTag pch.exerciseTitle

pch.exerciseTag pch.exerciseTitle

pch.exerciseTag pch.exerciseTitle

pch.exerciseTag pch.exerciseTitle

pch.exerciseTag pch.exerciseTitle

pch.exerciseTag pch.exerciseTitle