Module 6 — Exploration: epsilon-greedy and alternatives

The Q-learning code of module 5 hid a critical detail behind one line: if np.random.rand() < epsilon. That line is what makes the whole algorithm work. Without it, the agent never tries a new action, Q never updates for unseen (s, a) pairs, and learning stops in the first local optimum. This module is about that line.

The exploration-exploitation dilemma

An agent that always exploits — always picks argmax Q(s, a) — will do well according to its current knowledge and terribly according to knowledge it never acquires. An agent that always explores — always picks a random action — will collect a lot of data but never leverage it. The dilemma has no closed-form solution in general MDPs; the algorithms that follow are compromises, each optimal under different assumptions.

The stakes are concrete on FrozenLake. Set epsilon = 0 from the start and the agent, initialized with Q = 0, breaks ties in a fixed direction and repeats one deterministic trajectory forever. If that trajectory happens to reach the goal once, it reinforces itself; if it does not, it dies quietly at zero reward. Under-exploration is the default failure mode, and it is easy to miss because the learning curve is a perfectly flat line at zero — no crash, no error, just silence.

Epsilon-greedy and its decay

The simplest exploration scheme is epsilon-greedy: with probability ε pick a uniformly random action, otherwise pick argmax Q.

A constant ε = 0.1 explores forever, which contradicts the goal of ever converging to a greedy policy. The fix is a decay schedule that starts high and shrinks over time. Three common shapes:

# 1. Linear decay: reaches epsilon_min after 'n_decay' steps.
epsilon = max(epsilon_min, 1.0 - step / n_decay)

# 2. Exponential decay: multiplicative each episode.
epsilon = max(epsilon_min, epsilon * 0.995)

# 3. Cosine decay: smooth, common with deep RL.
epsilon = epsilon_min + 0.5 * (1 - epsilon_min) * (1 + math.cos(math.pi * step / n_decay))

On FrozenLake, exponential decay from 1.0 to 0.05 over 20 000 episodes worked in module 5. Two failure modes to know: too fast and the agent commits to a suboptimal policy before exploring enough; too slow and the reported "final" performance is polluted by continuing random actions. Always report the reward of the greedy policy at the end of training, not the reward of the mixed exploration policy.

Softmax (Boltzmann) exploration

Epsilon-greedy has one flaw: it treats a slightly-worse action the same as a catastrophically-bad one. Both are picked with probability ε / |A|. Softmax exploration picks actions in proportion to their exponentiated Q-values:

$$\Pr(a | s) = \frac{\exp(Q(s, a) / \tau)}{\sum_{a'} \exp(Q(s, a') / \tau)}$$

The temperature τ plays the role of ε: high τ gives near-uniform sampling, low τ collapses to the greedy action. Softmax rewards good actions in proportion to how good they look, which helps in problems where the ranking among suboptimal actions matters.

Downside: softmax requires the Q-values to be on comparable scales. If one action's Q hovers around 100 and the others around 0, softmax essentially never explores those others regardless of τ. On sparse-reward environments where Q values differ by orders of magnitude, epsilon-greedy is often more robust.

UCB: exploration proportional to uncertainty

Upper confidence bound (UCB) is the theoretically principled approach for multi-armed bandits, and it extends to full RL with caveats. The idea: pick the action that maximizes an optimistic upper bound on its true value:

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

Where N(s_t, a) counts how many times a was chosen in s_t, and c controls the exploration bonus. An action that has rarely been tried gets a large bonus, and the algorithm is drawn toward it; an over-explored action loses its bonus and the algorithm reverts to exploitation.

UCB works beautifully on bandits and is central to AlphaGo's tree search. In full RL with large state spaces, per-state counts are impractical, and the bonus has to be approximated (pseudo-counts, hash-based counts). It is worth knowing exists; it is rarely the first tool you reach for.

Optimistic initialization: exploration for free

Initialize Q(s, a) = R_max / (1 - γ) — the highest possible return. Every unseen (s, a) looks like the best possible action, and greedy behavior will visit them all until their Q values drop to reality. On tasks where the reward is bounded and known, this replaces epsilon-greedy entirely, with zero hyperparameters. It fails when rewards are heavy-tailed or the horizon is too long for optimism to fade in reasonable time.

Demonstrating under-exploration

The most convincing evidence is empirical:

# Compare three schedules on the same seed.
def train_with_epsilon(epsilon_start, epsilon_min, decay, n_episodes=10_000):
    env = gym.make("FrozenLake-v1", is_slippery=True)
    Q = np.zeros((16, 4))
    epsilon = epsilon_start
    rewards = []
    for _ in range(n_episodes):
        state, _ = env.reset()
        done, total = False, 0.0
        while not done:
            action = np.random.randint(4) if np.random.rand() < epsilon else np.argmax(Q[state])
            next_state, r, term, trunc, _ = env.step(action)
            done = term or trunc
            Q[state, action] += 0.8 * (r + 0.99 * (0 if done else np.max(Q[next_state])) - Q[state, action])
            state = next_state
            total += r
        rewards.append(total)
        epsilon = max(epsilon_min, epsilon * decay)
    return rewards

Running this with (0.0, 0.0, 1.0) (pure exploitation), (1.0, 0.01, 0.9995) (decayed) and (1.0, 1.0, 1.0) (pure exploration) yields three very different curves. Pure exploitation stays at zero for the entire run — the flat-line signature. Pure exploration reaches the goal about 5 % of the time forever. The decayed schedule climbs to 70 %+ and stabilizes. Plotting the three side by side is the standard first exercise in any RL course, and it should be redone every time an exploration scheme changes.

Diagnosing an RL run that is not learning

When the reward curve is flat at zero, exploration is the first suspect, not the algorithm. Inspect the state visitation histogram: if 90 % of visits are to two states, you are stuck in a loop. Inspect epsilon at the current step: if it is already at its minimum after 100 episodes and the reward is still zero, the decay was too aggressive. These two checks solve the majority of "my Q-learning does not work" tickets.

Summary

• Under-exploration produces a silent zero-reward run; overriding it is what ε does in Q-learning.
• Epsilon-greedy with a decay schedule is the default; report greedy performance at the end of training, not the mixed exploration performance.
• Softmax samples in proportion to Q-values, UCB in proportion to uncertainty; both cost more but sometimes explore more intelligently.
• Optimistic initialization replaces the exploration hyperparameters with a single initial value when rewards are bounded and known.

Next module: leaving the tabular world for the deep one — Deep Q-Networks with a replay buffer and a target network, on CartPole.