PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploration in Deep Reinforcement Learning: A Survey

Pawel Ladosz, Lilian Weng, Minwoo Kim, Hyondong Oh

arXiv:2205.00824v1cs.LG

TL;DR

Sparse rewards make learning useful behavior difficult because agents may receive little or no feedback. This survey organizes exploration methods, compares their reported performance, and identifies unresolved challenges including the noisy-TV problem.

  • Problem

    Sparse rewards leave reinforcement learning without timely feedback, making useful behavior difficult to learn.

  • Method

    The paper surveys exploration methods across intrinsic rewards, planning, imitation, safety, goal-based, uncertainty, and random approaches.

  • Results

    Imitation with exploration strategies outperforms imitation in experience replay alone, while prediction-error methods generally show very good performance but require hand-designed state representations.

  • Takeaways & Limitations

    The review provides a structured basis for comparing exploration approaches and identifying directions for future research.

  • Takeaways & Limitations

    The noisy-TV problem remains largely unsolved, and memory-based solutions may struggle with long noisy sequences and complex state spaces.

Abstract

from arXiv · show

This paper reviews exploration techniques in deep reinforcement learning. Exploration techniques are of primary importance when solving sparse reward problems. In sparse reward problems, the reward is rare, which means that the agent will not find the reward often by acting randomly. In such a scenario, it is challenging for reinforcement learning to learn rewards and actions association. Thus more sophisticated exploration methods need to be devised. This review provides a comprehensive overview of existing exploration approaches, which are categorized based on the key contributions as follows reward novel states, reward diverse behaviours, goal-based methods, probabilistic methods, imitation-based methods, safe exploration and random-based methods. Then, the unsolved challenges are discussed to provide valuable future research directions. Finally, the approaches of different categories are compared in terms of complexity, computational effort and overall performance.

1. Introduction

Sparse-reward problems delay observable outcomes across many decisions, making exploitation alone inadequate and motivating exploration in deep reinforcement learning. This review systematically surveys and categorizes exploration methods while identifying future challenges.

  • Motivation: Sparse-reward problems occur when outcomes become visible only after many events, often requiring thousands of decisions before rewards appear.Examples include search-and-rescue missions and delivery tasks, where rewards are given only when the objective is achieved.
  • Motivation: Because rewards are rare, agents may find nothing to exploit, making exploitation alone insufficient for solving sparse-reward problems.The agent must determine actions that maximize reward, but reward sparseness makes quickly finding exploitable rewards unlikely.
  • Existing approaches: Random exploration, particularly time-decaying ϵ-greedy exploration, can theoretically address sparse rewards given sufficient time but is often impractical in real-world applications.Random exploration selects actions regardless of progress, while ϵ decreases exploration over time.
  • Existing approaches: Reward shaping provides more frequent artificial rewards but depends heavily on designer experience and can cause inactivity or repetitive behavior when penalties or rewards are excessive.The passage illustrates these risks with search-and-rescue agents penalized for failing to find a victim.
  • Review scope and contributions: The review presents a systematic overview of exploration in deep reinforcement learning, proposes a categorization for comparing approaches, and discusses future challenges.Its stated focus is on exploratory approaches that adapt exploration to learning, seek new outcomes through actions, or persist despite absent environmental rewards.

2. Preliminaries · 2.1. Introduction to Reinforcement Learning · 2.2. Exploration

The paper introduces reinforcement learning through Markov decision processes, value-based and policy-based methods, then defines exploration as seeking rewards when solutions are difficult to discover. Exploration is especially important for complex reward functions and tasks where rewards are sparse or obstructed by local minima.

  • 2.1.1. Markov Decision Process: Reinforcement learning models an agent interacting with a stochastic, fully observable environment through a Markov decision process (S, A, P, R, γ).The agent selects actions sequentially to maximise cumulative rewards, with P satisfying the Markov property.
  • 2.1.1. Markov Decision Process: At each time step, policy π maps states to actions, rewards are received after actions, and the objective is to maximise discounted expected reward using γ ∈(0, 1].The return is represented as Gt.
  • 2.1.2. Value-Based Methods: The state-value function Vπ(st) estimates expected return from a state, while Qπ(st, at) estimates expected return from a state-action pair.These functions condition expected returns on the current state, with Qπ additionally conditioning on the selected action.
  • 2.1.2. Value-Based Methods: Q-learning is an off-policy method that updates a target policy from samples generated by a stochastic behaviour policy using Bellman and temporal-difference learning.Its behaviour policy uses ϵ-greedy exploration, while the action with the largest Q-value is selected for the target policy.
  • 2.1.3. Policy-Based Methods: Policy-based methods directly update a policy parameterized by θ to maximise the expected return objective J(θ) = Eπθ[Gt].REINFORCE performs gradient ascent in the direction of ∇θJ(θ).
  • 2.2. Exploration: Exploration is an agent’s search for rewards through actions intended to maximise a reward function, which is often complex and must support improvement over the agent’s lifetime.The paper notes that exploration can include randomly taking certain actions.
  • 2.2. Exploration: Exploration is most useful when local minima obstruct a route to the actual solution, making random or habitual behaviour unlikely to discover the reward.The section illustrates this with rescue tasks that reward finding a victim and delivery tasks that reward reaching an appropriate drop-off point.
  • 2.2. Exploration: The paper presents exploration as a ubiquitous problem relevant to many domains and an ongoing area of research.Examples include searching unknown areas for victims or delivering objects to unknown drop-off locations.

2.3. Challenging Problems · 2.4. Benchmarks

The paper identifies noisy-TV and sparse rewards as challenging exploration problems, then introduces Atari Games, VizDoom, Malmo, and MuJoCo as commonly used reinforcement-learning benchmarks.

  • 2.3. Challenging Problems: The challenging-problem discussion specifically covers noisy-TV and sparse reward problems before the benchmark overview.These problems frame why exploration is difficult in reinforcement learning.
  • 2.3.1. Noisy-TV: Noisy-TV traps the agent in infinitely many unrewarding states because each remote operation generates a novel random image.This continual novelty maintains the agent’s attention without producing reward.
  • 2.3.2. Sparse Reward Problems: Sparse rewards are rare and separated from actions by long gaps, preventing useful behavior learning and potentially causing convergence to a trivial solution.Maze tasks exemplify this difficulty because the agent must complete numerous steps before receiving reward.
  • 2.4. Benchmarks: The paper highlights four commonly used reinforcement-learning benchmarks: Atari Games, VizDoom, Minecraft through Malmo, and MuJoCo.These benchmarks are briefly introduced as representative environments for reinforcement-learning research.
  • 2.4.1. Atari Games: Atari Games combines 57 games in the Atari Learning Environment, using image or RAM states and five joystick actions.The benchmark distinguishes 54 easy-exploration games from 3 difficult-exploration games.
  • 2.4.2. VizDoom: VizDoom is a first-person Doom benchmark with image states, typically eight directional controls, and two action buttons.Its key advantages are easy-to-use scenario-editing tools and low computational burden.
  • 2.4.3. Malmo: Malmo uses Minecraft’s block-built, first-person environments with images as states and offers flexible environment structures, domain sizes, scripts, and reward functions.This flexibility is identified as Malmo’s key advantage.
  • 2.4.4. Mujoco: MuJoCo simulates multi-joint dynamics with contact and is commonly used for physics-based walking-robot simulations.Typical agents include cheetahs, ants, and humanoids, while tasks control joint angles and forces to walk far or reach a goal.

3. Exploration in Reinforcement Learning

The paper organizes reinforcement-learning exploration into efficiency and safe-exploration streams, further dividing efficiency methods into imitation-based and self-taught approaches. The categorization emphasizes each method’s key contribution while recognizing that approaches may combine multiple techniques.

  • 3. Exploration in Reinforcement Learning: Exploration methods are divided into efficiency, which seeks sample-efficient exploration, and safe exploration, which prioritizes safety during exploration.Efficiency aims to let agents explore in as few steps as possible.
  • 3. Exploration in Reinforcement Learning: Efficiency-based methods are further classified as imitation-based or self-taught methods.Imitation-based learning uses an expert policy, according to the passage.
  • 3. Exploration in Reinforcement Learning: The categorization highlights each approach’s key contribution, although a method can combine techniques from multiple categories.Go-explore uses reward-novel-states methods but is primarily described as goal-based.

3.1. Reward Novel States

Reward-novel-state methods add intrinsic rewards for discovering new states, supplementing environmental rewards to incorporate exploration into agent behaviour. They include prediction-error, count-based, and memory-based approaches, with distinct mechanisms, advantages, and limitations.

  • Reward Novel States: Intrinsic rewards rint supplement environmental rewards rext when agents discover novel states, incorporating exploration into their behaviours.The intrinsic reward is generated by an intrinsic reward module.
  • Reward Novel States: Intrinsic rewards are classified into prediction error, count-based, and memory methods.Prediction-error methods use model inaccuracies, count-based methods use visitation counts, and memory methods compare current states with stored states.
  • Prediction Error Methods: Prediction-error methods reward states whose model predictions are inaccurate, and inverse dynamic features achieved the best performance and scaled best to unseen environments.The prediction error indicates that a state has not been seen often; IDF was compared with state prediction and random representation methods.
  • A Priori Knowledge Methods: A depth point cloud prediction-error approach performed well across starting positions in the same environment but did not scale to a new scenario.A priori knowledge methods depend on designer-selected state-space components such as depth point clouds, position, and sound.
  • Prediction Error Methods: Prediction-error methods require only an environment model, avoiding buffers or complex approximation methods.Their reliance on a model is identified as a key advantage in the discussion.
  • Count-Based Methods: Count-based methods reduce computational effort by counting visits to state representations, but these representations can require substantial memory and careful design.The methods approximate intrinsic reward from visitation counts rather than directly counting states.

3.2. Reward Diverse Behaviours

Reward diverse behaviour methods make exploration itself the objective by seeking varied experiences, using either evolutionary strategies or policy learning. Combined novelty methods and carefully designed policy diversity show promising advantages, while evolution strategies remain limited by low sample efficiency.

  • 3.2. Reward Diverse Behaviours: Reward diverse behaviour methods seek as many different experiences as possible, reframing exploration as an objective rather than reward finding.These approaches are divided into evolution strategies and policy learning.
  • Evolution Strategies: Evolutionary approaches test and evolve a population of sample solutions, although they are generally not considered part of reinforcement learning.They can nevertheless solve the same type of problems as reinforcement learning.
  • Evolution Strategies: Novelty search encourages numerous different behaviours through a diversity measure, but hand-designed measures limit transferability across domains.Recent work combines novelty search with reward maximization or reward novel state methods.
  • Evolution Strategies: Combining novelty search with other techniques is more beneficial in terms of reward because diverse behaviours become more directed toward highly scoring ones.The survey contrasts this with novelty search used initially as a stand-alone technique.
  • Policy Learning: Policy-based diversity methods measure differences between policies and can outperform evolution strategies and PPO in sparse reward Mujoco problems.Successful policies may be stored and compared with the current policy while maximizing parameter entropy for exploration.
  • Comparison: Evolution strategies can discover solutions beyond designers’ expectations but suffer from low sample efficiency, making training computationally expensive or slow.Policy learning instead seeks a diverse policy, while evolution strategies use a diverse population.

3.3. Goal-Based Methods

Goal-based methods guide exploration toward specific states or generated goals, using goal generators, goal-achieving policies, and exploration strategies to focus on largely unknown areas. They include goals-to-explore-from and exploratory-goal methods, with strong results in difficult games but persistent challenges in storage, navigation, goal design, and controller training.

  • 3.3. Goal-Based Methods: Goal-based methods guide agents directly toward specific goals or states to focus exploration on largely unknown areas.They require a goal generator, a policy for achieving goals, and an exploration strategy.
  • 3.3. Goal-Based Methods: They divide into goals to explore from, which use visited states or trajectories, and exploratory goal methods, which generate goals for the agent to reach.The former can select buffered states probabilistically or use visitation counts, while the latter includes meta-controllers and sub-goal methods.
  • 3.3. Goal-Based Methods: Exploratory goal methods use meta-controllers or sub-goals, but controller training remains challenging and designer-defined sub-goals burden researchers with specifying meaningful goals.Meta-controllers let agents set goals without excessively rewarding themselves, whereas sub-goal methods can target bottlenecks, progress toward the main goal, or uncertain states.
  • 3.3. Goal-Based Methods: Goals-to-explore-from methods have shown very good performance in difficult exploratory games such as Montezuma’s Revenge.Memorizing visited states and trajectories has also produced remarkable results on Montezuma’s Revenge and Pitfall.
  • 3.3. Goal-Based Methods: Key limitations include storing states and trajectories, navigating to goals, and devising exploratory goals as reward sparsity increases.Some approaches mitigate these issues, but may depend on problem-specific state representations or the ability to parameterize the task.

3.4. Probabilistic Methods

Probabilistic methods represent uncertainty over states, actions, values, rewards, or combinations thereof, then choose actions either optimistically or to reduce uncertainty. The section reviews these approaches, including reward modeling, parameter and action/value sampling, network ensembles, and information-directed exploration.

  • 3.4. Probabilistic Methods: Probabilistic methods maintain probability distributions over states, actions, values, rewards, or combinations and divide into optimistic and uncertainty-based approaches.The distinction concerns how probability is modeled and used for action selection.
  • Optimistic approaches: Optimistic methods follow upper confidence bounds of reward estimates, using models such as Gaussian processes, linear Gaussian algorithms, bootstrapped DQNs, or sampled value functions.Value-function approximation can provide partial reward information when reward sparsity increases.
  • Uncertainty-based methods: Uncertainty-based methods choose actions that minimize uncertainty about the environment, including parameter uncertainty, policy and Q-value uncertainty, network ensembles, and information-theoretic methods.Information-directed sampling selects actions for maximal information gain, expressed as a ratio between regret and action informativeness.
  • Sampling methods: Parameter sampling updates sampled policy parameters over time, whereas policy and Q-value sampling adjusts action or Q-value distributions dynamically for faster updates.The latter makes exact probability estimation intractable, requiring simplifications.
  • Limitations: Optimistic exploration can cause unnecessary visits to high-confidence states that do not lead to reward because confidence sets are built independently.The paper notes that remedying this issue would be computationally intractable.

3.5. Imitation-Based Methods

Imitation-based methods use demonstrations to kick-start exploration, either by incorporating them into experience replay or by combining them directly with exploration strategies. Direct combination can overcome initial exploration difficulty and achieve strong performance in difficult exploratory games, while replay organization has negligible performance impact.

  • Imitation-Based Methods: Imitation learning uses demonstrations as a starting point that supplements standard reinforcement learning, without requiring demonstrations to be perfect.Demonstrations from different sources, usually humans, guide initial behavior and need only provide a good starting point.
  • Imitation in Experience Replay: Experience-replay methods combine demonstration samples with agent-collected samples so demonstrations remain available throughout learning.Demonstrations may be stored alongside agent experience in one prioritized replay or in separate buffers sampled together.
  • Imitation in Experience Replay: Using one or two experience replays has negligible impact on performance, while a single replay is simpler and can discontinue imitation experiences when unnecessary.A single replay is described as easier conceptually and in implementation.
  • Imitations with Exploration Strategies: Directly combining imitations with exploration strategies uses demonstrations as a kick-start and has shown impressive performance in difficult exploratory games.Reported approaches scored highly in Montezuma’s Revenge, overcoming the initial exploration burden through demonstrations.
  • Comparison of Imitation Methods: Imitations combined with exploration strategies can find novel strategies around existing ones and achieve better performance than using imitations alone.The comparison describes these methods as capable of overcoming initial exploration difficulty.

3.6. Safe Exploration

Safe exploration prevents unsafe behaviours through three approaches: human designer knowledge, prediction models, and auxiliary rewards. These approaches trade off guarantees and adaptability against human intervention, environment modeling, or training requirements.

  • 3.6. Safe Exploration: Safe exploration is categorized into human designer knowledge, prediction models, and auxiliary rewards.Human-designed boundaries constrain behaviour, prediction models identify and avoid unsafe actions, and auxiliary rewards punish dangerous states.
  • Human designer knowledge: Human designer knowledge uses safety boundaries, baseline behaviours, direct intervention, or pre-trained modules to prevent unsafe actions.Human intervention can stop disasters during early exploration before a supervised network trained on human-collected data replaces the humans.
  • Prediction models: Prediction models assess whether actions lead to unsafe positions using mathematical environment models or heuristic rules.A Gaussian process can estimate terrain height against a safe limit, while action pruning uses prior knowledge to block unsafe actions.
  • Discussion: Human designer methods guarantee safe behaviour in certain states but struggle with new safe behaviours, whereas auxiliary rewards adapt to new scenarios but require training time and negative-reward design.Baseline and intervention methods work only in pre-defined situations, while prediction models have a higher chance of working in previously unseen environments but require an environment model.
  • Auxiliary rewards: Auxiliary rewards punish dangerous situations and require the least human intervention, but they generate the weakest safety behaviours.They can prevent deaths or automatically identify undesirable states, although automatic avoidance assumes that perishing produces a low score.

3.7. Random-Based Methods

Random-based methods improve inefficient random exploration by reducing explored states or actions, adapting exploration parameters, or injecting noise into network parameters. These approaches offer different trade-offs involving efficiency, exploration–exploitation balance, implementation simplicity, memory, and parameter tuning.

  • 3.7. Random-Based Methods: Random-based methods address inefficient exploration by reducing revisited states, modifying exploration parameters, or adding noise to policy parameters.The three categories are reduced states/actions, exploration-parameter methods, and network-parameter-noise methods.
  • Exploration Parameters: Exploration parameters can be adjusted according to learning progress, using rewards, value-estimate errors, environmental-model entropy, or other learning signals.Using pure rewards can be problematic in sparse-reward settings, motivating alternatives such as value-function estimation errors.
  • Reduced States/Actions: Reduced-state methods select actions from a smaller exploration space, including ART-based positive and unclassified action chunks.ART divides action knowledge into positive, negative, and empty chunks, then randomly chooses from positive and unclassified chunks.
  • Network Parameter Noise: Network-parameter noise methods perturb policy parameters, with adaptable noise strength and state-dependent random actions addressing exploration and credit-assignment problems.A policy-based approach achieved 50% improvement averaged over 52 Atari games.
  • Comparison: Reduced-state methods can be effective but require memory, parameter methods balance exploration and exploitation yet may explore unnecessary states, and noise methods are simple but require careful tuning.The comparison identifies distinct practical limitations for each random-based approach.

4. Future Challenges

The paper identifies unresolved challenges in evaluating, scaling, and designing exploration methods for reinforcement learning. Key issues include balancing exploration and exploitation, intrinsic-reward design, noisy-TV environments, safety, and transferability.

  • Evaluation: Exploration algorithms are difficult to evaluate and compare because benchmarks, evaluation strategies, and metrics are not standardized.Common benchmarks differ substantially in state-space complexity, reward sparseness, and action space, while reward-based reporting varies with testing duration and may not reflect learning speed or exploratory behavior.
  • Scalability: Exploration does not scale well to real-world problems because training requires millions of samples and large domains make state representation and memorization difficult.Go-Explore, for example, does not scale well when the environment is large; the paper contrasts this with the brain’s faster novelty detection and greater memory capacity.
  • Exploration-exploitation dilemma and intrinsic reward: The exploration–exploitation balance remains unresolved, especially in goal-based methods and approaches whose behavior depends on designer-provided thresholds.Intrinsic-reward methods also need more self-directed reward design and better long-term versus short-term novelty balancing; meta-learning addresses the balance at increased training complexity.
  • Noisy-TV problem: The noisy-TV problem remains largely unsolved because memory-based solutions require substantial memory, while clustering requires correctly designed clusters.Very long noisy sequences and complex state spaces can therefore overwhelm memory approaches.
  • Safe exploration: Safe exploration is crucial for real-world applications, yet few methods address it and current approaches often rely on hand-designed rules that may not prevent catastrophes.The paper calls for agents to recognize unsafe situations and act accordingly, noting that carefully engineered rewards have still failed to prevent catastrophes.
  • Transferability: Exploration strategies often fail to transfer beyond their training domain, including to environments with larger state spaces or different reward functions.Improved transferability could support teaching behaviors in smaller scenarios before deployment in larger ones, reducing computational demands.

5. Conclusions

The paper reviews exploration methods in reinforcement learning, organizing them into seven categories and discussing their implementation ease, computational cost, and overall performance. It concludes that reward-novel-state, reward-diverse-behaviour, and random-based approaches are among the easiest to implement.

  • Exploration-method categories: The review categorizes exploration methods as reward novel states, reward diverse behaviours, goal-based, probabilistic, imitation-based, safe exploration, and random methods.These categories span novelty, behavioural diversity, goals, uncertainty, demonstrations, safety, and random-exploration improvements.
  • Exploration-method categories: Reward novel state methods reward discovering novel or surprising states using prediction error, visitation counts, or memory-based differences.Prediction-error rewards depend on environmental-model accuracy, count-based rewards on visit frequency, and memory-based rewards on differences from buffered states.
  • Exploration-method categories: Reward diverse behaviour methods seek diverse action sequences or policies through evolutionary strategies that diversify populations or policy learning that diversifies parameters.Goal-based methods either explore from a selected goal or explore while travelling toward an exploration-suitable goal.
  • Exploration-method categories: Probabilistic methods use environmental uncertainty to sample optimistic rewards or move toward least-known areas, while imitation-based methods combine demonstrations with replay or exploration strategies.Safe exploration uses designer-defined boundaries, predictive stopping models, or negative rewards for dangerous states.
  • Implementation and comparison: Random-based approaches improve random exploration by modifying states, automatically choosing exploration parameters, or adding noise to network parameters.The review highlights reward novel states, reward diverse behaviours, and random-based approaches as easiest to implement, with basic versions adaptable to many reinforcement-learning algorithms.
Loading 2205.00824v1…