Exploration Strategies in Deep Reinforcement Learning

In reinforcement learning, the exploration-exploitation dilemma is a core challenge. If an agent only exploits known actions that yield moderate rewards, it may never discover high-reward states hidden behind a sequence of complex, non-rewarding actions.

In environments with dense rewards (like continuous control or cart-pole balance), simple heuristics like $\epsilon$-greedy or Gaussian action noise are often sufficient. However, in sparse reward environments (such as Montezuma’s Revenge, maze navigation, or long-horizon robotic assembly), random exploration has virtually zero probability of stumbling upon a reward signal.

To solve this, modern deep RL incorporates principled intrinsic motivation and curiosity-driven exploration.

Why Random Exploration Fails in Sparse Reward Tasks

Sparse Reward Maze:
Start [S] ──► [Empty Room] ──► [Empty Room] ──► ... ──► [Key] ──► ... ──► [Goal +100]
Under ε-greedy / Gaussian Noise:
Probability of reaching the Goal decays exponentially with horizon length: P ~ (1 / |A|)^T ≈ 0.

Random actions cause the agent to wander aimlessly near the starting state, experiencing diffusion-like brownian motion rather than targeted, systematic exploration.

Evolution of Modern Exploration Techniques

1. Count-Based Exploration (Pseudo-Counts)
   Bonus reward r_i ~ 1 / sqrt(N(s)) using generative density estimators.
                         │
                         ▼
2. Intrinsic Curiosity Modules (ICM)
   Bonus reward based on prediction error of next-state features in an inverse dynamics space.
                         │
                         ▼
3. Random Network Distillation (RND)
   Bonus reward based on prediction error between a trained predictor and a frozen random target network.
                         │
                         ▼
4. Go-Explore
   Separates exploration into state archiving, deliberate return (Go), and non-random exploration (Explore).

1. Count-Based Exploration & Pseudo-Counts

In tabular RL, the Upper Confidence Bound (UCB) formula grants an exploration bonus inversely proportional to state visitation count:

$$r_t^{\text{intrinsic}} = \frac{\beta}{\sqrt{N(s_t)}}$$

In high-dimensional continuous state spaces (e.g., raw pixel inputs), an agent rarely encounters the exact same state twice ($N(s) \in {0, 1}$).

Pseudo-Counts (Bellemare et al., 2016) overcome this by fitting a generative density model $\rho(s)$ over observations. When a new state $x$ is seen, the pseudo-count $\hat{N}(x)$ is derived from the increase in probability density assigned to $x$ after an online update:

$$\hat{N}(x) = \frac{\rho(x)(1 - \rho’(x))}{\rho’(x) - \rho(x)}$$

The agent optimizes total reward: $r_t = r_t^{\text{extrinsic}} + \frac{\beta}{\sqrt{\hat{N}(x_t)}}$.

2. Intrinsic Curiosity Module (ICM) & The “Noisy TV” Problem

Pathak et al. (2017) proposed using prediction error as curiosity: an agent receives intrinsic reward whenever the environment transitions into a state that its predictive model failed to anticipate.

The Noisy TV Problem

If intrinsic reward is simply raw next-state prediction error $|f(s_t, a_t) - s_{t+1}|^2$, the agent will become hopelessly addicted to irreducible environmental entropy—such as a television displaying random static noise or leaves rustling in the wind. The agent cannot predict random noise, so it receives infinite curiosity reward while doing nothing useful.

The ICM Solution

ICM filters out uncontrollable entropy by learning a self-supervised feature space $\phi(s)$ using an Inverse Dynamics Model:

State s_t     ──► [ Encoder φ ] ──► φ(s_t)   ──┐
                                               ├──► [ Inverse Model g ] ──► Predicted Action â_t
State s_{t+1} ──► [ Encoder φ ] ──► φ(s_{t+1}) ─┘   (Trained to predict actual action a_t)

φ(s_t) + Action a_t ──► [ Forward Model f ] ──► Predicted Feature φ̂(s_{t+1})
                                                    │
                                                    ▼
                       Intrinsic Reward r_t^i = ||φ̂(s_{t+1}) - φ(s_{t+1})||^2

Because $\phi(s)$ is trained only to predict features that the agent’s actions directly influence, random background static is completely stripped out of the representation, curing the Noisy TV problem.

3. Random Network Distillation (RND)

Introduced by Burda et al. (2018) at OpenAI, Random Network Distillation (RND) offers a mathematically clean and computationally efficient approach that is completely immune to the Noisy TV dilemma:

Observation x ──► [ Target Network f(x) (Weights Frozen at Random Init) ] ──► Target Vector y*
              ──► [ Predictor Network f̂(x; θ) (Trained via Gradient Descent) ] ──► Vector y
                                                   │
                                                   ▼
                          Intrinsic Reward: r_i = ||f̂(x; θ) - f(x)||^2

1. Target Network $f$: A neural network initialized with random weights and frozen permanently.
2. Predictor Network $\hat{f}$: A neural network trained via gradient descent to match the output of the target network on observed states:

$$\mathcal{L}_{\text{RND}}(\theta) = |\hat{f}(x; \theta) - f(x)|^2$$

3. Intrinsic Reward: $r_i(x) = |\hat{f}(x; \theta) - f(x)|^2$.
   • For frequently visited states, the predictor network has trained on them repeatedly, driving prediction error near zero.
   • For novel or rarely visited states, the predictor has not seen the state, producing high prediction error and granting a substantial exploration bonus.
   • For noisy static / stochastic states, the target network is deterministic, so the predictor easily learns to output the mean target vector, avoiding attraction to random noise.

RND was the first algorithm to conquer Montezuma’s Revenge without demonstrations or human guidance.

4. Go-Explore: Solving Detachment and Derailment

In 2021, Ecoffet et al. identified two major systemic pathologies that plague curiosity-based RL:

• Detachment: An agent discovers an interesting boundary, explores one path, runs out of novelty, and forgets how to return to the unexplored frontier.
• Derailment: Standard exploration noise perturbs the agent before it can reach deep, hard-to-access states found earlier in training.

Go-Explore solves this by decoupling exploration into explicit phases:

┌────────────────────────────────────────────────────────────────────────┐
│ 1. Remember: Archive all discovered states/cells in a structured memory │
└───────────────────────────────────┬────────────────────────────────────┘
                                    │
                                    ▼
┌────────────────────────────────────────────────────────────────────────┐
│ 2. Return (Go): Deterministically travel back to a promising frontier   │
│                 cell without random exploratory noise                  │
└───────────────────────────────────┬────────────────────────────────────┘
                                    │
                                    ▼
┌────────────────────────────────────────────────────────────────────────┐
│ 3. Explore: Perform targeted exploration from that deep frontier cell  │
└────────────────────────────────────────────────────────────────────────┘

Once exploration maps out viable high-reward trajectories, the discovered demonstrations are distilled into a robust policy network using standard imitation learning or PPO fine-tuning.

Comparison Summary