Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 37 ยท Q-learning and SARSA

Exploration Strategies

Compare the main exploration strategies in reinforcement learning: epsilon-greedy and decay, softmax, UCB, optimistic initialization and count bonuses, with runnable experiments.

Every reinforcement learning agent faces the same dilemma. Exploitation means choosing the action that currently looks best. Exploration means trying something else to learn whether it is better. An agent that never explores can get stuck with a mediocre habit forever; an agent that always explores never cashes in on what it knows.

Q-learning and SARSA do not solve this dilemma by themselves: they only tell you how to update values from the data you collect. Which data you collect is decided by your exploration strategy. In this lesson you will compare the main strategies on two small problems, a bandit and a chain where good rewards are hard to find.

Epsilon-greedy and its schedule

With probability epsilon choose a random action; otherwise choose the greedy one. It is simple, works with any value-based method and is the default in most code.

A constant epsilon (say 0.1) keeps exploring forever, which wastes a little reward after learning is done. A common refinement is a decay schedule: start high (explore a lot) and shrink toward a floor.

TEXT
epsilon_t = max(eps_min, eps_start * decay ** t)          # exponential
epsilon_t = max(eps_min, eps_start - t * (eps_start - eps_min) / T)   # linear

The right schedule depends on how long the problem takes to "discover". A rule of thumb: finish decaying after roughly 10 to 50 percent of the training budget, then keep a small floor such as 0.01 to 0.05.

Softmax (Boltzmann) exploration

Epsilon-greedy treats every non-greedy action as equally likely, even one that looks terrible. Softmax exploration chooses actions with probability proportional to exp(Q / tau):

TEXT
P(a | s) = exp(Q(s, a) / tau) / sum_b exp(Q(s, b) / tau)

A high temperature tau makes the choice nearly uniform; a low one makes it nearly greedy. Actions that look worse are tried less often, which is more sensible than a flat random choice.

Optimistic initialization

Start every Q value higher than any reward you could really get. The first action you try disappoints you (its value drops toward reality) while untried actions still look wonderful, so a purely greedy agent is pulled toward them. Exploration emerges without any randomness. It is a clever trick for tabular problems, but it only encourages exploration at the beginning, and it needs you to know a reasonable upper bound on returns.

Upper confidence bound (UCB)

UCB adds a bonus that is large for actions tried only a few times:

TEXT
a = argmax_a [ Q(a) + c * sqrt( ln(t) / N(a) ) ]

N(a) counts how often the action was tried. As an action is sampled, its bonus shrinks. UCB explores systematically instead of randomly, and has strong theory for bandits.

Let us compare these on a 10-armed bandit. Each arm pays a noisy reward around a hidden mean. Higher average reward is better.

Python Exploration strategies on a 10-armed bandit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see the plain greedy agent end below the others: it locks on to whichever arm looked good first. Optimistic initialization starts slowly (it deliberately tries everything) and catches up; softmax and UCB do well.

Hard exploration: the chain

Bandits have no states. Real tasks often hide a big reward behind a long sequence of moves where random behavior almost never succeeds. Here is a chain: action right advances, action left resets you to the start and pays a tiny, tempting reward of 0.1. The big reward of 10 sits at the far end.

flowchart LR
    S0["0 start"] -->|right| S1["1"] -->|right| S2["2"] -->|right| S3["3"] -->|right| S4["4"] -->|right| S5["5"] -->|right| G["6 goal: +10"]
    S3 -.->|"left: +0.1, back to 0"| S0

A greedy agent learns to grab the 0.1 forever.

Python Which strategies solve the chain?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Constant epsilon = 0.1 almost never strings six lucky right moves together, so it never sees the +10. Decay starts with pure randomness and has a chance, optimism pulls the agent toward untried actions, and a count bonus does the same in a principled way. Compare the scores: which strategy would you trust on an unknown problem?

Beyond the tabular case

  • Gaussian action noise is the standard exploration for continuous actions (see Policy gradients).
  • Entropy bonuses keep stochastic policies from collapsing too early.
  • Intrinsic motivation rewards novelty or surprise (count-based bonuses, curiosity, random network distillation) when extrinsic rewards are rare.
  • Thompson sampling samples a plausible world from a posterior and acts as if it were true.

Common mistakes

  • Evaluating the agent with exploration still switched on, then concluding learning failed.
  • Decaying epsilon per step when you meant per episode (or the reverse).
  • Setting the optimistic value so high that it never fades, or so low that it does not help.
  • Tuning exploration on one random seed. Always average several runs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the main weakness of epsilon-greedy compared with softmax exploration?

    Epsilon-greedy picks uniformly among all actions when exploring; softmax favors actions that look better.
  2. 2. Why does optimistic initialization encourage exploration?

    Every tried action's value falls toward reality, so the greedy choice keeps moving to actions that are still overvalued.
  3. 3. In UCB, what happens to the bonus of an action as it is selected more often?

    The bonus is proportional to sqrt(ln t / N(a)); a large N(a) means less uncertainty and a smaller bonus.
  4. 4. A trained agent scores badly when evaluated with epsilon = 0.3. What is the most likely mistake?

    Exploration noise during evaluation hides what the learned policy can really do.

Summary

  • Exploration decides what data an agent learns from; the update rule alone does not fix it.
  • Epsilon-greedy with decay is the simplest option; softmax picks better random actions.
  • UCB and count bonuses explore systematically; optimism explores through inflated values.
  • Hard-exploration tasks (sparse rewards) need more than constant epsilon.
  • Always evaluate with exploration off, over several seeds.

Next: Expected SARSA and Double Q-learning