Robot Learning · Theory · M4

M4-T7 — Exploration Versus Exploitation

A robot learns only about what it tries, but every try costs something, and some tries cannot be undone.

Lesson 7 of 7
Module 4: Reinforcement Learning Foundations
Theory
About 14 minutes to read

Q-learning updates the entries of the table it visits. A route Scout never tries stays at its initial guess, however good it might be. That creates a dilemma: use what the table says now (exploit) or try something else to learn more (explore). A learning robot also pays for trying: a fall down the stairs is not a number in a log. This lesson covers the common ways to explore, how to measure the cost of exploring, and what to do when some tries are not allowed.

Learning objectives

After this lesson, you should be able to:

Write epsilon-greedy, with a decay schedule, and describe optimistic initial values, softmax and count-based bonuses.
Explain why sparse rewards defeat undirected exploration, and how each method helps.
Distinguish online return, greedy return and regret, and say which one a given deployment cares about.
Describe constraints, simulation and shielding as ways to keep exploration safe, and what each assumes.

The intuition

Compare two ways to find a good café in a new town. If you always return to the best one you have found, you may never learn that a better one is two streets away. If you try a new café every day, you eat mostly mediocre lunches. Exploration is the price paid for information, and the information is only worth what it will improve later.

Robots add two complications. Some tries are expensive or unsafe, and some rewards are so rare that random trying never finds them. The figure shows the first on the stairwell corridor of lesson M4-T6: the more often Scout takes a random step, the lower its online return, even though the table it ends up with is just as good.

Q-learning on the cliff, constant epsilon, 500 episodes, mean of 20 seeds. The online return (bars) falls steeply as epsilon grows; the greedy value of the learned table (printed below) barely moves.

The mathematics

Epsilon-greedy and its schedules

With probability ε choose an action uniformly at random, otherwise choose argmax_a Q(s, a), breaking ties consistently:

Epsilon-greedy with schedules

a=\text{random action}

with probability ε

a=\operatorname*{arg\,max}_{a}\,Q(s,\,a)

with probability 1 − ε

constant

\varepsilon _{t}=\varepsilon

exponential

\varepsilon _{t}=\max (\varepsilon _{\min},\,\varepsilon _{0}\cdot d^{t})

t=\text{episode},\,d\,\text{just below}\,1

\frac{1}{t}:

\varepsilon _{t}=\frac{1}{t}

satisfies the greedy-in-the-limit condition of lesson M4-T6

ε: exploration probability. Note that a random action may equal the greedy one, so the probability of an off-greedy action is 3ε/4 with four actions.
d: per-episode decay, for example 0.99. Starting from ε₀ = 1, d = 0.99 reaches 0.01 after 459 episodes (ln 0.01 / ln 0.99).
ε_min: a floor, so exploration never stops entirely when the world might change.

Epsilon-greedy is undirected: it explores uniformly, however much is already known. Its virtues are that it is one line and that it guarantees every pair is eventually visited, which is the condition the Q-learning convergence theorem needs.

Other ways to explore

Exploration methods
Method	Idea	Caution
Optimistic initial values	Start every Q(s, a) above any real return. Each try pulls its entry down toward the truth, so untried actions look best until tried.	Works in tabular settings only if the optimism is larger than reality and α is not too small; with a sampled, slippery world it fades after a few visits. Zero is already optimistic when every step costs.
Softmax (Boltzmann)	Choose a with probability proportional to exp( Q(s,a) / τ ). A near-greedy choice is likely, a terrible one rare.	The temperature τ is in units of reward, so it must be re-tuned when the reward scale changes. High τ approaches uniform, τ → 0 approaches greedy.
Count-based bonus	Add a bonus that shrinks with the visit count, for example choose argmax of Q(s,a) + β / sqrt( N(s,a) + 1 ). Rarely tried actions get a push. Its relatives are UCB for bandits and pseudo-counts for large state spaces.	Needs counts, which are only available in tables unless approximated; β is another number to tune.
Intrinsic reward	Reward the agent for reaching novel states (curiosity). A topic of lesson M6 and later.	The agent may chase novelty (noisy screens) rather than the task.

Sparse rewards

If the only non-zero reward is at the goal, and the goal is many steps from the start, a random walk reaches it with a tiny probability and all Q entries stay at 0. A greedy agent with ties broken the same way then repeats one action forever. ε-greedy eventually stumbles on the goal, after which the reward propagates backwards; its cost grows quickly with the distance. Optimistic values, softmax and count bonuses do the exploring systematically. Shaped rewards (lesson M5, reward design) change the problem instead, at the risk of rewarding the wrong thing.

Three ways to score exploration

Online return, greedy return and regret
Measure	Question	Matters when
Online return	How much reward did the agent earn while learning, exploration included?	The robot works while it learns; mistakes cost.
Greedy (final) return	How good is the policy that comes out, run without exploration?	You train first (often in simulation), then deploy the table.
Regret	The sum over episodes of (optimal return − return achieved). Online return accumulated, against a perfect agent.	You want one number for the cost of learning; it penalises early exploration.

These can rank settings in opposite orders. A policy that explores heavily early and then stops can have the best greedy return and the worst regret.

Safe exploration

No amount of clever statistics makes a fall down the stairwell reversible. Approaches, all at the level of a principle here:

Explore in simulation. Reset is free there, a simulated fall costs nothing, and millions of tries are cheap. The price is the sim-to-real gap: a policy that is safe in the simulator is only as safe as the simulator is faithful.
Constrain. State a cost for unsafe events separately from the reward and require its expected total to stay below a budget (a constrained MDP, Altman, 1999). Methods such as constrained policy optimisation (Achiam et al., 2017) then trade reward against the budget. The constraint holds on average; it does not forbid a single fall.
Shield. Put a monitor between the learner and the actuators that vetoes any action that could lead to an unsafe state (Alshiekh et al., 2018). The learner explores freely inside what the shield allows. A shield needs a model of what is unsafe and a way to compute one step ahead, and it cannot be better than that model.
Start from a safe policy and stay near it. Begin with a demonstration or a conservative controller (Module 3) and explore only in a neighbourhood of it.

A worked example

Every number comes from running RLCore’s tabular worlds. “Cliff”: the 4 × 8 stairwell corridor (step −1, goal +10, stairwell −100 and back to the start, γ = 0.99, α = 0.5, 500 episodes, optimal greedy value 0.579, optimal undiscounted return +1). “Ward”: the 7 × 9 ward with slip 0.2 (step −0.1, goal +10, stairwell −10 and the episode ends, γ = 0.95, 1,000 episodes, optimal value 3.314). Seeds 1 to 20. “Online” is the mean undiscounted return of the last 100 episodes; “greedy” is the exact discounted value of the table’s greedy policy at the start (so the two columns are not on the same scale).

1. Constant epsilon on the cliff.

Constant epsilon on the cliff
ε	Online, last 100	Mean over all 500	Greedy value (mean)	Seeds with optimal greedy
0	1.00	−1.64	0.579	20 of 20
0.01	−0.62	−3.49	0.479	19 of 20
0.05	−9.20	−11.18	0.279	17 of 20
0.1	−20.76	−23.89	0.479	19 of 20
0.2	−56.15	−58.27	0.579	20 of 20
0.5	−247.49	−284.50	0.579	20 of 20

Online return drops with ε, as the figure shows: with ε = 0.5 Scout falls almost every episode. The greedy value is not monotone: it is 0.579, the optimum, for most seeds at every ε. Greedy ε = 0 is best here, which looks like a contradiction of this whole lesson. It is not: every step costs −1, so a table filled with 0 is optimistic about every untried action, and in a deterministic world the greedy agent is pushed into trying each in turn. The ward shows the same setting without that help.

2. Decay schedules on the cliff.

Decaying epsilon on the cliff
Schedule	Online, last 100	Mean over all 500	Greedy value	Optimal seeds
1 → 0.01, d = 0.99	−1.90	−143.44	0.579	20 of 20
0.5 → 0.01, d = 0.99	−1.13	−34.41	0.579	20 of 20
0.3 → 0.01, d = 0.98	−0.54	−11.46	0.479	19 of 20
1 → 0.01, d = 0.9	−1.14	−18.98	0.379	18 of 20

Decaying ε fixes the final online return (about −1 against −20.8 at constant 0.1) but not the cost along the way. Regret, the sum over the 500 episodes of (1 − return): about 1,320 at ε = 0, 2,246 at ε = 0.01, 12,447 at ε = 0.1, 6,232 for 0.3 → 0.01 with d = 0.98, and 72,219 for 1 → 0.01 with d = 0.99. The schedule that ends with the best behaviour has the worst regret because of the hundred episodes it spends falling early. Whether that is acceptable is a deployment question, not a mathematical one.

3. The ward, with slip. Slip makes Q noisy, so the free optimism of the cliff does not carry. Optimal greedy value 3.314.

Epsilon settings on the ward
Setting	Online, last 100	Greedy value (mean)	Seeds with optimal greedy
ε = 0	7.13	1.882	0 of 20
ε = 0.01	6.89	2.106	1 of 20
ε = 0.05	5.19	1.772	7 of 20
ε = 0.1	3.78	0.971	7 of 20
ε = 0.2	2.60	0.833	5 of 20
ε = 0.5	−0.62	0.564	4 of 20
0.3 → 0.01, d = 0.98	6.87	2.446	5 of 20

Too little exploration (0 or 0.01) gives the best online return and the worst greedy tables; too much gives low online return and still not a good table. No setting in this list is reliably optimal in 1,000 episodes: with α = 0.5 under slip the table keeps being shaken. With α = 0.1 and 3,000 episodes, constant ε = 0.1 reached the optimum in 9 of 20 seeds (greedy mean 2.564) and a decay 1 → 0.01 with d = 0.995 in 8 of 20 (2.755). The honest summary is that this small ward needs more episodes or a smaller step size than the labs allow, and that the best ε is a compromise, not a number.

4. Sparse reward. Change the ward so that stepping costs nothing: the goal (+10) and the stairwell (−10) are the only rewards (optimal value 4.256, α = 0.2, 500 episodes, 20 seeds). Greedy ε = 0 and 0.05: 0 of 20 seeds ever reach the goal, and the greedy value is 0. ε = 0.1: 1 of 20, first at episode 290. ε = 0.3: 20 of 20, median first success at episode 65.5, greedy value 3.25. ε = 1: 20 of 20, median episode 4. Optimistic initial values of 10 with ε = 0: 20 of 20, median 3. Softmax with τ = 0.5: 20 of 20, median 6. A count bonus (β = 1) with ε = 0: 20 of 20, median 4.5. Optimism and bonuses find the goal in a handful of episodes with no random actions; small ε does not find it in 500.

5. Other methods on the original ward (α = 0.1, 1,000 episodes, 20 seeds, step cost −0.1): ε = 0.1: greedy mean 2.211, optimal in 8 of 20, online 5.15. Softmax τ = 0.5: 3.267, optimal in 19 of 20, online 6.39. Softmax τ = 2: 2.988, 13 of 20, online −3.54. Count bonus 1: 2.558, 6 of 20, online 7.26. Initial values of 10 and ε = 0: 2.470, 2 of 20. Initial values of −20 and ε = 0 (pessimistic): every seed stuck at −2.0, a policy that never leaves the corridor. One setting of each was tried and the settings were not tuned, so these show how different the methods behave, not a ranking; the temperature τ = 0.5 against 2 already changes the picture.

6. A shield on the cliff. Mask every action whose next cell is the stairwell, in exploring and greedy choices alike. With ε = 0.1: online return −0.38 (instead of −20.76), 0 falls per run (instead of 108.7 on average), greedy value 0.579. With ε = 0.3: −4.33 online instead of −105.41, 0 falls instead of 489. The cliff is deterministic, so a one-step check is a perfect shield. With slip, an action that looks safe can still end on the edge, and a shield needs a model that includes the slip.

What the simulation simplifies. These worlds have 25 and 32 cells, fixed rewards and a tabular Q; the numbers show the mechanism, not the size of the effects in a real task. The “falls” are counted events, not damage.

Engineering implications and limitations

Pick the quantity you actually care about

If Scout trains in a simulator and is deployed afterwards, the objective is the greedy return of the final policy, and aggressive exploration is cheap. If it learns on the ward floor, online return and safety events count from the first episode and you cannot choose ε only by looking at the final table. Write down which one it is before tuning (lab M4-L3 has you sweep ε, its decay and α and read both).

Schedules

Start at a high ε, decay to a small floor (0.01 to 0.1), and spread the decay across a fixed fraction of the training budget. Decay per episode, not per step, in episodic tasks. Always evaluate the greedy policy separately, because the online return is a measurement of the exploring policy, not the one you will ship.

Check the learner can reach the reward at all

Before tuning anything, count how many episodes reach the goal. A flat return with zero goal reaches is an exploration failure, not a bug in the update, and the cure is a different method, a nearer goal, a curriculum, a shaped reward (lesson M5) or demonstrations to start from (Module 3). If goal reaches grow but the return does not, look at the update (lab M4-L4).

Safe exploration in practice

List the irreversible events (falls, collisions, pinches) and give each a separate counter, not just a penalty in the reward.
Explore in simulation first; deploy with the learned policy and a small, decayed ε only when the robot may recover from a mistake.
Add a shield or a speed and region limit below the learner for events that must never happen.
Treat a reward penalty as a price, not a prohibition: a −100 is accepted if the gain is large enough.

Where this leads

With neural networks the table disappears and so do exact counts; lesson M6 returns to ε-greedy in deep Q-networks, entropy bonuses and pseudo-counts. Reward design (lesson M5) decides how sparse the reward is in the first place.

Common misconceptions

“Exploration is a nuisance that should be turned off as soon as possible.”

With sparse rewards a policy that never explores never finds the goal (0 of 20 seeds at ε ≤ 0.05 above). Turn it down on a schedule, not off at the start.

“The best ε is the one with the best online return.”

That favours ε = 0 on the ward (online 7.13) and gives the worst greedy table. Choose by what you will deploy and what mistakes cost.

“ε = 0 never works.”

It can: on the cliff, zero-initialised Q is optimistic because every step costs, and 20 of 20 seeds found the optimum. It fails with sparse, non-negative rewards and with slip.

“A penalty of −100 makes falling off the stairs impossible.”

It makes it expensive. The agent still falls during exploration (about 109 times per run at ε = 0.1) until a shield or constraint forbids it.

Engineering takeaways

Epsilon-greedy explores uniformly; schedules lower ε over time, and the floor keeps some exploration alive.
Optimistic values, softmax and count bonuses explore in a directed way, and find a sparse reward in a few episodes where ε ≤ 0.1 failed in 500.
Online return, greedy return and regret answer different questions; a decay schedule can have the best final return and the worst regret (72,219 against 12,447).
On the cliff, ε = 0.1 gave online −20.8 and ε = 0.01 gave −0.6, with greedy values about the same.
Falls cannot be undone: explore in simulation, constrain the cost, or shield the actions (online −0.38 with 0 falls versus −20.8 with 109).

References and further reading

The textbook chapters on bandits and temporal-difference control, and primary sources for the safe-exploration and bonus methods named above.

R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd edition, MIT Press, 2018 (section 2.6 optimistic initial values, 2.8 gradient bandits and softmax, chapter 6 for epsilon-greedy control, Example 6.6).
P. Auer, N. Cesa-Bianchi and P. Fischer, “Finite-time Analysis of the Multiarmed Bandit Problem”, Machine Learning 47(2–3), 235–256, 2002 (the UCB rule behind count-based bonuses).
M. G. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton and R. Munos, “Unifying Count-Based Exploration and Intrinsic Motivation”, NeurIPS, 2016.
J. García and F. Fernández, “A Comprehensive Survey on Safe Reinforcement Learning”, Journal of Machine Learning Research 16, 1437–1480, 2015.
M. Alshiekh, R. Bloem, R. Ehlers, B. Könighofer, S. Niekum and U. Topcu, “Safe Reinforcement Learning via Shielding”, AAAI, 2018.
J. Achiam, D. Held, A. Tamar and P. Abbeel, “Constrained Policy Optimization”, ICML, 2017.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

Starting at ε = 1 and multiplying by 0.99 each episode, with a floor of 0.01, after how many episodes does the floor take over?

Explanation

Solve 0.99^t = 0.01: t = ln 0.01 / ln 0.99 = 458.2, so the floor applies from episode 459 on.

Question 2

Why can a schedule that ends with the best online return still have the highest regret?

Explanation

Regret sums the shortfall over every episode. The schedule that starts at ε = 1 spends its early episodes exploring and falling (mean return −143 over the whole run on the cliff, regret 72,219), even though its last 100 episodes are near the optimum.

Question 3

Scout can only afford 20 trials on the real ward floor, and one fall damages the robot. Name two ways to explore that are safer than epsilon-greedy on the floor, and what each one assumes.

Explanation

Learn in a simulator first, which assumes the simulator is faithful; or put a shield that vetoes any action that could reach the stairwell, which assumes a correct one-step model of what is unsafe. A constrained objective or starting near a safe controller also qualify.

What’s next

Next: lab M4-L2 has you implement epsilon-greedy and the Q-learning update, lab M4-L3 sweeps exploration settings on the cliff and the ward, and lab M4-L4 asks you to find the bug in an agent that does not learn. Module 5 then asks what reward to write in the first place.

Practice this lesson

Tune Exploration

Vary epsilon, its decay and the learning rate and watch which runs find the pharmacy and which never do.

Next lesson

M5-T1 — What a Reward Really Says

Explain that the agent optimizes the reward written and not the intention, and give examples of the gap.

Nothing below is required to finish this lesson.

Before
M4-T6: Q-Learning and SARSA
Write the Q-learning and SARSA updates, and say why one is off-policy and the other on-policy.
Lab
M4-L3: Tune Exploration
Vary epsilon, its decay and the learning rate and watch which runs find the pharmacy and which never do.
Lab
M4-L4: Debug a Q-Learning Agent
The agent's return stays flat for 5,000 episodes: find the terminal-state, discount and update bugs.

Learning objectives

The intuition

The mathematics

Epsilon-greedy and its schedules

Other ways to explore

Sparse rewards

Three ways to score exploration

Safe exploration

A worked example

Engineering implications and limitations

Pick the quantity you actually care about

Schedules

Check the learner can reach the reward at all

Safe exploration in practice

Where this leads

Common misconceptions

“Exploration is a nuisance that should be turned off as soon as possible.”

“The best ε is the one with the best online return.”

“ε = 0 never works.”

“A penalty of −100 makes falling off the stairs impossible.”

Engineering takeaways

References and further reading

Knowledge check

Question 1

Question 2

Question 3

What’s next

Tune Exploration

M5-T1 — What a Reward Really Says

Related content

Get notified when the next lesson and new labs are released.