Exploration in Deep Reinforcement Learning: A Survey

1. Introduction

• Sparse-reward problems can require thousands of decisions before outcomes become visible, leaving agents without a clear link between actions and rewards to learn.The paper gives search-and-rescue and delivery as examples where rewards arrive only when an object is found or delivered.Source: §1 · pp. 1–2
• Random exploration can require impractically long learning, while poorly designed reward shaping can immobilize agents or make them repeat actions indefinitely, motivating more sophisticated methods.The commonly used ϵ-greedy method reduces random exploration over time with a decaying parameter ϵ.Source: §1 · p. 2
• The paper presents a systematic review of deep-RL exploration, categorizes approaches to support comparison, and discusses future challenges.It focuses on approaches that adapt exploration to learning, seek new outcomes, or continue exploring despite absent environmental rewards, with breadth and simplified explanations for beginners. Earlier reviews did not examine exploration in detail, and the previous exploration-focused review was outdated.Source: §1 · pp. 2–3

2.1.1. Markov Decision Process

• An MDP models an agent choosing actions in a stochastic, fully observable environment, with states, actions, transition probabilities, rewards, and a discount factor.Its transition probabilities satisfy the Markov property: the next state depends on the current state and action.Source: §2.1.1 · p. 3
• At each time step, a policy maps the observed state to an action, and the agent seeks to maximize expected discounted reward.Source: §2.1.1 · p. 3

2.1.2. Value-Based Methods

• Value-based methods estimate expected returns with state-value and action-value functions; Q-learning updates a target policy using samples from a stochastic behavior policy.Its behavior policy uses ϵ-greedy exploration, while selecting the next action with the largest Q-value under the target policy.Source: §2.1.2 · pp. 3–4

2.1.3. Policy-Based Methods

• Policy-based methods directly update a policy parameterized by θ to maximize expected return, and REINFORCE uses gradient ascent for this objective.Source: §2.1.3 · p. 4

2.2. Exploration

• Exploration searches for ways to improve reward and can involve random actions, following the best-known solution, or considering moves that may yield novel discoveries.Source: §2.2 · p. 4
• Exploration is especially useful when local optima or flat rewards obstruct the route to a solution, making the true rewards difficult to discover.The paper illustrates sparse-reward search-and-rescue and delivery tasks, where reward is received only after finding the victim or appropriate drop-off point.Source: §2.2 · pp. 4–5

2.3. Challenging Problems

• The challenging-problems section covers noisy-TV and sparse-reward settings, where exploration can fail to produce meaningful learning.Noisy-TV generates endless novelty without reward, while sparse rewards may leave the agent without useful learning signals.Source: §2.3.1 · p. 5, §2.3.2 · p. 5, §2.3 · p. 5

2.3.1. Noisy-TV

• In noisy-TV, random images create endless novelty without reward, keeping the agent exploring states that make no meaningful progress.The paper calls this behavior a “couch potato” problem.Source: §2.3.1 · p. 5

2.3.2. Sparse Reward Problems

• Sparse rewards leave long gaps without learning signals, so agents may converge to trivial solutions, especially in mazes too large for them to reach the goal.The maze example illustrates how increasing maze size makes the reward less likely to be seen.Source: §2.3.2 · p. 5

2.4. Benchmarks

• The section introduces four commonly used reinforcement-learning benchmarks: Atari Games, VizDoom, Minecraft via Malmo, and MuJoCo.They cover game environments, editable scenarios, flexible block-built worlds, and physics-based multi-joint simulations.Source: §2.4 · p. 5, §2.4.2 · p. 6, §2.4.3 · p. 6

2.4.1. Atari Games

• Atari’s ALE [25] combines 57 games, including 54 easy-exploration games and three difficult ones [26], with hard games featuring rare rewards and complex state-reward associations.States are typically images or RAM snapshots, and actions are five joystick controls.Source: §2.4.1 · p. 5

2.4.2. VizDoom

• VizDoom [27] uses first-person game images as states and typically offers eight directional controls plus two action buttons, with editable scenarios and low computational burden.Additional actions can be added as needed.Source: §2.4.2 · p. 6

2.4.3. Malmo

• Malmo models first-person Minecraft worlds built from uniform blocks and supports flexible environment structure, domain size, custom scripts, and reward functions.Source: §2.4.3 · p. 6

2.4.4. Mujoco

• MuJoCo simulates multi-joint contact dynamics, commonly for controlling walking robots’ joint angles and forces to walk farther or reach a goal.Examples include cheetahs, ants, humanoids, and related derivatives.Source: §2.4.4 · p. 6

3. Exploration in Reinforcement Learning

• Exploration methods divide into efficiency, which seeks to explore in fewer steps, and safe exploration, which focuses on safety.The authors further divide efficiency methods into imitation-based and self-taught approaches.Source: §3 · p. 6
• Self-taught methods learn from scratch and include planning, intrinsic-reward, and random methods.Planning selects actions to better understand the environment; random methods explore without conscious plans and observe the consequences.Source: §3 · p. 6
• Intrinsic-reward methods reward either visits to novel states or discovery of novel behaviours, and are part of the broader notion of intrinsic motivation.The paper points to [16] and [30] for reviews of intrinsic motivation.Source: §3 · p. 6
• Planning methods include goal-based exploration, where the agent receives an exploratory goal, and probabilistic methods, which use probability models of the environment.The taxonomy review is represented in Fig. 1.Source: §3 · pp. 6, 8
• The taxonomy emphasizes an approach’s key contribution while recognizing that techniques can combine; Go-explore [31] uses novel-state rewards but is best classified as goal-based.Source: §3 · p. 8

3.1. Reward Novel States

• Novel-state approaches supplement environmental reward with intrinsic reward for discovery and are grouped here into prediction-error, count-based, and memory methods.The review describes the intrinsic reward as generated by an intrinsic-reward module alongside the agent.Source: Figure 2 · p. 8, §3.1 · p. 8

3.1.1. Prediction Error Methods

• Prediction-error methods reward inaccurate predictions of previously visited states; direct prediction error outperformed learning progress in Achiam et al. [33], and IDF performed best and scaled best to unseen environments [42].These methods use an environment model without buffers or complex approximations, but state representations can add design burden and prediction can struggle with many states; memory buffers can mitigate noisy-TV rewards.Source: §3.1.1 · pp. 8–12

3.1.2. Count-Based Methods

• Count-based methods give higher intrinsic rewards to less-visited states, but large or continuous state spaces make counting difficult and often require reduced state representations.Representations reduce count-storage demands but may still require substantial memory and careful design.Source: §3.1.2 · pp. 12–13

3.1.3. Memory Methods

• Memory methods reward states by comparing them with stored experiences; comparison models use little memory but need careful tuning, while limited replay buffers performed well in difficult exploratory Atari games.Replay approaches can combine episodic comparisons with RND for long-term novelty.Source: §3.1.3 · pp. 13–14

3.1.4. Summary

• Prediction-error methods are most common and generally perform very well: RND scores 6,500 in Montezuma’s Revenge, while memory methods reach 11,000 [71].Prediction-error methods may require hand-designed state representations, limiting applicability; memory methods require balancing stored data against comparison time.Source: Table 1 · p. 14, §3.1.4 · p. 14

3.2.1. Evolution Strategies

• Evolution strategies test and evolve populations of sample solutions, while policy-learning methods seek diversity among policies using distances such as KL divergence or mean squared error [72] [73].Evolutionary approaches are generally not considered part of reinforcement learning, though they can solve the same types of problems [72] [73].Source: §3.2.1 · p. 16, §3.2.2 · p. 17
• Combining novelty search with reward-based methods directs diverse behaviours toward higher rewards and appears more promising than stand-alone novelty search [77] [76].Novelty search uses a hand-designed diversity measure for each environment, limiting transferability; among three combinations compared, sequential optimization performed best in a simulated robot environment [77].Source: §3.2.1 · pp. 16–17

3.2.2. Policy Learning

• Policy-learning diversity methods include skill-entropy objectives and skew-fit, which oversamples rarely visited goals to seek reward-useful goals [82].A diversity criterion is reported to beat standard reinforcement learning by significant margins.Source: §3.2.2 · pp. 17–18
• In sparse-reward MuJoCo, storing successful policies and maximizing between-policy parameter entropy outperforms evolution strategies and PPO.The method stores successful policies in experience replay and minimizes the difference between the current policy and those stored policies.Source: §3.2.2 · p. 17

3.2.3. Summary

• Evolution strategies search diverse populations and neural-network structures but are sample-inefficient, while policy learning works in discrete and continuous state spaces but remains within pre-specified structures.Evolution strategies may find solutions not envisioned by designers; policy learning can nevertheless produce remarkable results.Source: §3.2.3 · p. 18

3.3. Goal-Based Methods

• Goal-based methods focus exploration on largely unknown areas and require a goal generator, a policy to reach goals, and an exploration strategy.The exploration strategy operates after a goal is reached or while the agent is trying to reach it.Source: §3.3 · p. 19, Figure 8 · p. 19

3.3.1. Goals to Explore from Methods

• Goals-to-explore-from methods memorize visited states or trajectories to select goals, or assume a known reward state and learn how to reach it [91] [92].For the latter, a model can predict backward steps so the agent can imagine states before the goal [91]; another approach starts at the reward position [92].Source: §3.3.1 · pp. 19–20

3.3.2. Exploratory Goal Methods

• Exploratory-goal methods include meta-controllers that set goals for workers and sub-goals based on bottlenecks, progress toward the main goal, or uncertainty.Meta-controllers avoid excessive self-rewarding but are challenging to train; sub-goal methods place the burden on designers to define suitable goals.Source: §3.3.2 · pp. 20–21

3.3.3. Summary

• Goals-to-explore-from methods have recently shown very good performance in difficult exploratory games such as Montezuma’s Revenge [84].The discussion also reports remarkable results on Montezuma’s Revenge and Pitfall when memorizing visited states and trajectories, and says using a reward state as a goal can mitigate exploration.Source: §3.3.1 · p. 20, §3.3.3 · p. 21
• Challenges include storing trajectories and navigating to goals; uses position but is problem-specific, while sparse rewards complicate exploratory goals, partly mitigated by [94] [104] when tasks are parameterizable.The summary also notes that methods using state and trajectory storage face both storage and navigation challenges.Source: §3.3.3 · p. 22

3.4. Probabilistic Methods

• Optimistic methods use reward estimates’ upper bounds, while uncertainty-based methods choose actions to reduce uncertainty about the environment [108].Uncertainty-based methods may use optimistic estimates but use them differently; Figure 9 illustrates the two approaches.Source: §3.4 · p. 23, Figure 9 · p. 24

3.4.1. Optimistic Methods

• Optimistic exploration models rewards directly or through value functions, whose partial rewards can aid learning as reward sparsity increases.Examples include Gaussian-process reward models [109], bootstrapped DQNs, and selecting the most optimistic value function for an episode [112] [113].Source: §3.4.1 · p. 24

3.4.2. Uncertainty Methods

• Information-theoretic methods choose actions for information gain, while network ensembles approximate distributions through sampled models or policies that maximize model disagreement [122],, [126].Information-directed sampling expresses information gain as a ratio of regret to how informative an action is [122].Source: §3.4.2 · p. 25
• Uncertainty methods sample policy parameters or actions and Q-values; action/Q-value sampling enables faster dynamic updates but requires simplifying intractable probability estimates [114],.Bayesian sampling can hold a hypothesis for several steps to save computation, and tree-based state representations were added for efficiency [120].Source: §3.4.2 · pp. 24–26

3.4.3. Summary

• Optimistic methods’ independent confidence sets can trigger unnecessary exploration of states that do not lead to reward, whereas uncertainty methods build interdependent confidence bounds [108].Making optimistic confidence sets dependent on one another is described as computationally intractable.Source: §3.4.3 · p. 26

3.5.1. Imitations in Experience Replay Methods

• Experience-replay methods mix demonstrations with agent experience, with variants using prioritized sampling [127], demonstration-only pretraining and controlled sample ratios [128], R2D2, or two replays [130].Using one or two replays seems to have negligible performance impact; one replay is simpler and allows imitation data to be dropped when no longer needed.Source: §3.5.1 · pp. 27–28

3.5.2. Imitation with Exploration Strategy Methods

• Demonstrations used to start exploration have performed well in difficult exploratory games, including Montezuma’s Revenge [26] and [131].The approach in [26] achieved high scores with a single demonstration, making it sample efficient, and can combine multiple data sources; instead requests human guidance in unknown environments.Source: §3.5.2 · pp. 28–29

3.5.3. Summary

• Imitation with exploration strategies can overcome initial exploration difficulty and outperform imitation in experience replay alone.The comparison also notes their potential to discover novel strategies around existing ones.Source: Table 5 · p. 29, §3.5.3 · p. 29

3.6.1. Human Designer Knowledge Methods

• Baseline methods use human-defined safety constraints, including risk functions and fallback behaviors, action-modifying modules [135], baseline performance guarantees [136], and object-avoidance knowledge that can generalize to new scenarios [137].Some methods classify dangerous objects and how to avoid them before agent training; others constrain the agent to perform no worse than a known baseline.Source: §3.6.1 · p. 30
• Human intervention stops disasters early before a supervised network replaces humans [138], while prediction models use environmental models or heuristics to avoid unsafe actions and may adapt better to unseen environments.Examples include Gaussian-process terrain-height estimates [139] and heuristic action pruning [140]; unlike baseline and intervention methods, prediction methods require an environment model.Source: §3.6.1 · pp. 30–31

3.6.2. Auxiliary Reward Methods

• Auxiliary rewards penalize dangerous states with less human intervention but produce weaker safety behavior; approaches include distance-to-death penalties [141], a stochastic variant, and learned undesirable-state penalties [143].The automatic approach in [143] assumes that perishing corresponds to a low score, which may not always hold; [141] is reported to prevent half of deaths.Source: §3.6.2 · p. 31

3.6.3. Summary

• The summary contrasts human designer knowledge, which guarantees safe behavior in certain states but struggles to learn new safe behaviors, with auxiliary rewards, which can adapt to new scenarios but require training time and negative-reward design.Prediction models are the third general approach.Source: §3.6.3 · pp. 31–32

3.7.1. Exploration Parameters Methods

• Exploration parameters can adapt with learning progress, using reward, value-estimate error, model entropy [146], learning-rate adjustment [147], or short- and long-term reward averages.Using reward alone can be problematic with sparse rewards; increasing exploration is suggested when short-term reward falls below the long-term average.Source: §3.7.1 · p. 33
• State reduction methods use ART in and its extension [152] to favor positive or unexplored action chunks, with selection probabilities for remaining actions based on how well they are known [152].Reducing states can improve sample efficiency, but may fail to account for unseen states encountered after states have been eliminated.Source: §3.7.1 · p. 34

3.7.2. Random Noise

• Random noise may be fixed, induced by chaotic networks, adjusted through gradient learning [155], or triggered when noisy and noiseless policies differ sufficiently [156].A state-dependent random-action function gives the same action for the same state, addressing difficult credit assignment when states recur.Source: §3.7.2 · p. 34
• Policy-parameter noise achieved a 50% improvement averaged over 52 Atari games [155].The review says parameter noise was first developed for evolutionary methods and has more recently been used in policy-based methods.Source: §3.7.2 · p. 34

3.7.3. Summary

• Reduced-state exploration can be effective but requires memory of visited states; parameter methods manage the exploration–exploitation trade-off but may explore unnecessary states, while noise methods are simple and promising but need careful tuning.Changing learning rate based on exploration can avoid learning uncertain information, but slows training.Source: §3.7.3 · pp. 34–35, §3.7.1 · p. 34

Evaluation

• Evaluation remains difficult because exploration lacks common benchmarks, evaluation strategies, and suitable metrics, while reporting practices also impede comparisons.Benchmarks differ in state-space complexity, reward sparsity, and action space, and proposed common benchmarks are not widely adopted. Results vary with the number of steps tested and may report average or maximum rewards, sometimes without clear definitions; reward also misses learning speed and exploratory-behaviour quality.Source: §4 · p. 36

Scalability

• Real-world scalability is constrained by sample demands and inefficient state representations, leaving exploration less sample-efficient than deployment requires.Even the fastest training in complex environments requires millions of samples, which is unrealistic for physical devices; reducing the sim-to-real gap or improving sample efficiency may help. Go-Explore [31] does not scale well in large environments, and efficient novelty recognition without storing full states remains unmatched; the brain comparison is discussed in [159].Source: §4 · p. 37

Exploration-exploitation dilemma

• Exploration–exploitation balance often depends on designer-set thresholds or hand-designed goal-based methods; learning reusable skills [160] is proposed as a possible alternative.The proposed approach trains skills during exploration and combines them into larger goal-oriented policies for later exploitation.Source: §4 · p. 37

Intrinsic reward

• Intrinsic-reward methods need agents to learn how to reward themselves and better balance short- and long-term novelty.Expert-designed rewards are time-consuming and may miss useful formulations; novelty balance is also hand-tuned, while meta-learning [15] has been proposed at added training-computation cost.Source: §4 · pp. 37–38

Noisy-TV problem

• The noisy-TV problem remains largely unsolved: memory methods face capacity limits, while clustering [107] depends on designing suitable clusters.Very long noisy sequences and complex state spaces may also challenge memory-based approaches.Source: §4 · p. 38

Optimal exploration

• Optimal exploration remains rarely studied; a proposed demand-matrix method estimates state-action exploration costs online, but needs further development.The matrix tracks exploration counts across states and actions and need not be known in advance.Source: §4 · p. 38

Safe exploration

• Safe exploration has few approaches, relies heavily on hand-designed rules, and lacks a rigorous definition of unsafe situations.Reinforcement learning still struggles to prevent catastrophes even with engineered rewards [141], and unclear safety definitions hinder scalability and transferability.Source: §4 · p. 38

Transferability

• Exploration strategies often fail in new environments [49] [43], limiting reuse from smaller scenarios to larger ones and across tasks with changing state spaces.Transfer could reduce computational demands and help domains where suitable state spaces are difficult to define or vary substantially.Source: §4 · p. 38

• Reward novel state methods reward discovering novel or surprising states using prediction error, visit counts, or differences from states stored in memory.Prediction-error rewards reflect the accuracy of an internal environmental model; count-based rewards depend on visit frequency, while memory-based rewards compare a state with states in a buffer.Source: §5 · p. 39
• Reward diverse behaviour methods encourage discovery of varied action sequences or policies through population diversity in evolutionary strategies or policy-parameter diversity in policy learning.Source: §5 · p. 39
• Goal-based methods either set a goal for the agent to explore from, emphasizing unknown areas, or provide an exploratory goal to pursue while travelling.The latter approach depends on choosing goals suitable for exploration.Source: §5 · p. 39
• Probabilistic methods use an environmental uncertainty model to guide movement, either sampling optimistic reward estimates or sampling internal uncertainty to reach less-known areas.Source: §5 · p. 39
• Imitation-based methods use demonstrations either in a shared replay buffer with agent-collected experience or as a starting point for another exploration strategy.Source: §5 · p. 39
• Safe exploration methods constrain behaviour using designer-defined boundaries, models that predict and stop disastrous actions, or negative rewards for dangerous states.Source: §5 · p. 39
• Random-based methods improve standard random exploration by modifying explored states or actions, adapting exploration parameters to learning progress, or adding noise to network parameters before weight convergence.Source: §5 · p. 40
• Reward novel states, reward diverse behaviours, and random-based methods are easiest to implement; random-based, reward novel states, and reward diverse behaviours are generally least resource-intensive.Goal-based and reward novel states methods are currently the best-performing; goal-based methods have achieved high scores on difficult exploratory problems such as Montezuma’s revenge but are the most complex to implement. Reward novel states methods offer a good compromise between implementation ease and performance.Source: §5 · p. 40