Exploration in Reinforcement Learning: From Epsilon-Greedy to Random Network Distillation

TL;DR

An agent that only ever exploits what it currently believes is best will never discover a better strategy it hasn’t tried — but an agent that explores too much never capitalizes on what it’s learned. Epsilon-greedy is the simplest possible answer (act randomly some fraction of the time); UCB and Thompson Sampling replace blind randomness with principled uncertainty estimates; count-based exploration rewards visiting rarely-seen states directly; and curiosity-driven methods (ICM, Random Network Distillation) generate an intrinsic reward from how surprising an observation is, which is what finally cracked notoriously sparse-reward benchmarks like Montezuma’s Revenge. Used in sparse-reward games, robotics exploration, and recommendation cold-start problems.

Problem Statement

Every RL algorithm needs a way to occasionally try actions it doesn’t currently believe are best, or it will converge to whatever looks good early and never discover anything better — this is the explore/exploit trade-off, and it’s orthogonal to which learning algorithm (Q-learning, actor-critic, etc.) sits underneath it. This article covers the exploration strategies layered on top of those algorithms, independent of which one you’re using.

Epsilon-Greedy: The Default Baseline

With probability ε, take a uniformly random action; otherwise, take the current best action. ε is usually annealed down over training as the agent’s estimates become more trustworthy.

def epsilon_greedy_action(q_values, epsilon):
    if random.random() < epsilon:
        return random.randint(0, len(q_values) - 1)
    return np.argmax(q_values)

It’s simple and works well enough for many benchmarks, but it’s exploration with no memory — it’s exactly as likely to re-explore an action already known to be bad as one that’s genuinely uncertain.

UCB: Optimism in the Face of Uncertainty

Upper Confidence Bound exploration doesn’t pick actions randomly — it picks the action with the highest upper bound on its plausible value, where the bound shrinks as an action is tried more often:

def ucb_action(q_values, action_counts, total_steps, c=2.0):
    bonus = c * np.sqrt(np.log(total_steps + 1) / (action_counts + 1e-6))
    return np.argmax(q_values + bonus)

An action tried only a few times gets a large exploration bonus regardless of its current estimate; an action tried many times gets almost none, because its estimate is already trustworthy. This gives exploration that’s targeted at genuine uncertainty rather than uniformly random.

Thompson Sampling: Bayesian Exploration

Thompson Sampling maintains a full posterior distribution over each action’s value (rather than a point estimate plus a bonus), and on each step samples one value from each action’s posterior and greedily picks the max of the samples:

def thompson_sampling_action(posteriors: list[BetaDistribution]):
    sampled_values = [p.sample() for p in posteriors]
    return np.argmax(sampled_values)

Actions with wide, uncertain posteriors occasionally sample a high value purely by chance and get tried — exploration falls naturally out of posterior uncertainty rather than needing a hand-tuned bonus term like UCB’s c.

Count-Based Exploration: Pseudo-Counts for Large State Spaces

UCB and Thompson Sampling both need a notion of “how many times has this state/action been visited,” which is trivial in a small tabular setting but undefined in a high-dimensional state space like raw pixels, where almost no two states are ever exactly identical. Count-based exploration solves this with a density model over states that produces a pseudo-count — an estimate of how novel a state is, even if it’s technically never been seen before:

def pseudo_count_bonus(density_model, state, beta=0.1):
    prob_before = density_model.prob(state)
    density_model.update(state)
    prob_after = density_model.prob(state)

    pseudo_count = prob_before * (1 - prob_after) / (prob_after - prob_before + 1e-8)
    return beta / np.sqrt(pseudo_count + 1)

Curiosity-Driven Exploration: ICM

Intrinsic Curiosity Module (Pathak et al., 2017) generates an exploration bonus from prediction error: it trains a forward model to predict the next state’s features given the current state and action, and rewards the agent for visiting states where that prediction was wrong — i.e., states that were genuinely surprising, not just visually different.

def curiosity_reward(forward_model, feature_encoder, state, action, next_state):
    predicted_features = forward_model(feature_encoder(state), action)
    actual_features = feature_encoder(next_state)
    intrinsic_reward = F.mse_loss(predicted_features, actual_features, reduction="none").sum(-1)
    return intrinsic_reward.detach()

Predicting in a learned feature space rather than raw pixels matters: predicting raw pixels rewards the agent for finding visual noise (like a TV playing static) that’s fundamentally unpredictable but meaningless — the “noisy TV problem” — whereas predicting compact learned features focuses the curiosity bonus on things that matter for control.

Random Network Distillation

RND (Burda et al., 2018) sidesteps the noisy-TV problem entirely with a much simpler idea: take a fixed, randomly initialized neural network as a target, train a second network to predict its output on visited states, and use the prediction error as the exploration bonus.

def rnd_bonus(target_network_frozen, predictor_network, state):
    with torch.no_grad():
        target_features = target_network_frozen(state)
    predicted_features = predictor_network(state)
    return F.mse_loss(predicted_features, target_features, reduction="none").sum(-1)

Since the target network is fixed and arbitrary (not trying to predict anything meaningful about the environment’s dynamics), prediction error is high purely because the predictor hasn’t seen states like this one before — and it naturally decays for states visited often, exactly the novelty signal exploration needs, without ever having to model environment dynamics or worry about stochastic, unpredictable noise sources.

Comparison Table

Applications

• Sparse-reward games — RND was the technique that first got competitive scores on Montezuma’s Revenge, a benchmark that had stumped most prior exploration methods.
• Robotics exploration — curiosity-driven bonuses help agents discover useful behaviors in environments with little to no natural reward signal during early training.
• Recommendation cold-start — Thompson Sampling and UCB (as contextual bandits) are standard tools for balancing showing users known-good content against exploring new content.
• Scientific and simulation environments — count-based and curiosity bonuses help agents cover a simulation’s state space thoroughly rather than fixating early on one region.

Key Learnings

1. Untargeted exploration (epsilon-greedy) is a baseline, not an endpoint — every subsequent technique targets exploration toward genuine uncertainty or novelty rather than spending exploration budget uniformly at random.
2. The “noisy TV problem” is the central failure mode of prediction-error-based curiosity, and it’s precisely what motivated RND’s shift to predicting a fixed random target instead of environment dynamics.
3. Exploration strategy is a layer, not an algorithm. Any of these can sit on top of Q-learning, actor-critic, or model-based methods covered elsewhere on this site — the choice of exploration bonus is largely independent of the choice of underlying RL algorithm.