PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain

Jianye Hao, Tianpei Yang, Hongyao Tang, Chenjia Bai, Jinyi Liu, Zhaopeng Meng, Peng Liu, Zhen Wang

arXiv:2109.06668v6cs.AIcs.LGcs.MA

TL;DR

DRL and deep MARL remain sample-inefficient because exploration must collect informative experience under sparse rewards, noise, long horizons, and non-stationary co-learners. This paper surveys exploration methods across single-agent and multiagent RL, organizes them taxonomically, and compares representative DRL methods empirically. The review finds distinct strengths and limitations across method categories and identifies unresolved challenges for future work.

  • Problem

    Exploration is a bottleneck for sample-efficient DRL and deep MARL, especially in environments with sparse or delayed rewards, noisy distractions, long horizons, and non-stationary co-learners.

  • Method

    The paper provides a comprehensive model-free survey with a unified taxonomy, algorithmic analysis, empirical comparison of representative DRL methods, and discussion of open problems.

  • Results

    Uncertainty-oriented methods generally improve exploration in most environments, whereas intrinsic motivation helps with sparse delayed rewards but can deteriorate performance in conventional environments; deep MARL exploration remains early-stage.

  • Takeaways & Limitations

    Exploration methods have different specialties and limitations, while deep MARL additionally faces exponentially larger joint state-action spaces, inconsistent individual exploration, and a lack of common benchmarks.

Abstract

from arXiv · show

Deep Reinforcement Learning (DRL) and Deep Multi-agent Reinforcement Learning (MARL) have achieved significant successes across a wide range of domains, including game AI, autonomous vehicles, robotics, and so on. However, DRL and deep MARL agents are widely known to be sample inefficient that millions of interactions are usually needed even for relatively simple problem settings, thus preventing the wide application and deployment in real-industry scenarios. One bottleneck challenge behind is the well-known exploration problem, i.e., how efficiently exploring the environment and collecting informative experiences that could benefit policy learning towards the optimal ones. This problem becomes more challenging in complex environments with sparse rewards, noisy distractions, long horizons, and non-stationary co-learners. In this paper, we conduct a comprehensive survey on existing exploration methods for both single-agent and multi-agent RL. We start the survey by identifying several key challenges to efficient exploration. Beyond the above two main branches, we also include other notable exploration methods with different ideas and techniques. In addition to algorithmic analysis, we provide a comprehensive and unified empirical comparison of different exploration methods for DRL on a set of commonly used benchmarks. According to our algorithmic and empirical investigation, we finally summarize the open problems of exploration in DRL and deep MARL and point out a few future directions.

I. INTRODUCTION

The paper surveys exploration in DRL and deep MARL, motivated by sample inefficiency and the difficulty of collecting informative experience in complex environments. It unifies algorithmic analysis, taxonomy, empirical comparison, and discussion of open problems.

  • DRL and deep MARL often require millions of interactions, while exploration becomes harder with sparse rewards, noise, long horizons, and non-stationary co-learners.The challenge is especially severe in multiagent settings because the state-action space grows exponentially with the number of agents.
  • The survey addresses a literature gap by systematically reviewing exploration methods for both DRL and deep MARL rather than treating exploration as a secondary topic.It presents a unified view spanning single-agent and multiagent exploration.
  • The authors introduce a taxonomy, analyze representative methods’ strengths and weaknesses, and assess their ability to address different exploration challenges.The taxonomy organizes the literature while the analysis evaluates methods against the identified challenges.
  • A unified empirical comparison evaluates representative DRL exploration methods on typical benchmarks using cumulative rewards and sample efficiency.The benchmarks expose both successes and failures of the compared algorithmic techniques.
  • The paper identifies open problems and future directions for exploration in DRL and deep MARL.Its investigation includes challenges specific to multiagent exploration as well as broader exploration issues.

A. Markov Decision Process and Markov Game

The section formalizes single-agent and multi-agent reinforcement learning settings, then outlines common learning paradigms and why exploration remains difficult in large environments.

  • A. Markov Decision Process and Markov Game: An MDP models states, actions, stochastic transitions, rewards, an initial-state distribution, and discounting for sequential decision-making.Its objective is to maximize expected cumulative discounted reward.
  • A. Markov Decision Process and Markov Game: A Markov Game extends an MDP with multiple agents, individual action sets, joint transitions, and agent-specific reward functions.In partially observable settings, agents act from local observations using decentralized policies.
  • A. Markov Decision Process and Markov Game: Value-based methods learn value functions from which policies are derived, whereas policy-based methods optimize explicit policies directly.Value-based methods are generally suited to off-policy learning and discrete action spaces.
  • A. Markov Decision Process and Markov Game: DQN learns a parameterized Q-function by minimizing temporal-difference loss using replay data and a target network.Its variants address approximation error, distributional value modeling, and architectural or training improvements.
  • A. Markov Decision Process and Markov Game: Policy-gradient methods update explicit policy parameters by gradient ascent, while actor-critic methods estimate action values with bootstrapping.REINFORCE uses complete returns, whereas deterministic policy gradients optimize an approximated Q-function.
  • A. Markov Decision Process and Markov Game: Independent learning treats other agents as part of the environment, joint learning trains a shared policy, and CTDE addresses their respective drawbacks.Independent learning suffers from non-stationarity, while joint learning has poor scalability; MADDPG is a representative CTDE method.
  • A. Markov Decision Process and Markov Game: Exploration balances exploiting high-reward actions against acquiring information about novel states and actions, and is indispensable in immense state-action spaces.This dilemma remains non-trivial in practical reinforcement-learning problems.

C. Basic Exploration Techniques

Basic exploration techniques inject randomness or optimism into action selection, but their suitability depends on the action space and optimization objective.

  • C. Basic Exploration Techniques: ϵ-greedy selects the greedy action with probability 1−ϵ and a random action otherwise, but is inefficient in complex large state-action spaces.The method directly trades exploitation for random exploration.
  • C. Basic Exploration Techniques: Boltzmann exploration samples actions according to a distribution over Q-values, with temperature τ controlling randomness.Higher τ produces more random action selection, but the method cannot be directly applied in continuous state-action spaces.
  • C. Basic Exploration Techniques: UCB methods select actions using an upper confidence bound on expected reward rather than naive random exploration.The bound incorporates reward estimates and action-selection counts.
  • C. Basic Exploration Techniques: Entropy regularization encourages stochastic policies to take diverse actions by adding policy entropy to the objective.This regularizer may deviate from the original optimization objective.
  • C. Basic Exploration Techniques: Noise perturbation induces exploration for deterministic policies by adding stochastic-process noise to the policy output.Ornstein-Uhlenbeck noise is preferred for physical control problems, while Gaussian noise is a general alternative.

D. Exploration based on Bayesian Optimization

Bayesian optimization treats black-box objectives probabilistically and uses acquisition functions to choose promising, previously untried samples under uncertainty.

  • D. Exploration based on Bayesian Optimization: Bayesian optimization seeks the maximizer of a black-box objective over a candidate set.A Bayesian statistical model represents the unknown objective function.
  • D. Exploration based on Bayesian Optimization: The Bayesian model supports a tractable acquisition function that scores candidate samples for more efficient exploration.The acquisition function seeks selections that are probably better and have not yet been attempted.
  • D. Exploration based on Bayesian Optimization: GP-UCB uses a Gaussian-process posterior mean and standard deviation to make optimistic upper-confidence-bound decisions.Its uncertainty bonus guides exploration.
  • D. Exploration based on Bayesian Optimization: Thompson Sampling draws a function from its posterior and acts greedily with respect to that sampled belief.Posterior uncertainty enables deep exploration.
  • D. Exploration based on Bayesian Optimization: Bayesian-optimization methods provide primitive ideas for uncertainty-oriented exploration methods in deep reinforcement learning.The survey discusses these DRL methods separately as Bayesian statistical approaches to the optimization objective.

III. WHAT MAKES EXPLORATION HARD IN RL

Efficient exploration is difficult because RL agents must discover informative experiences in large, sparse, delayed, noisy, and multi-agent environments. Multi-agent settings add exponential joint spaces, coordination difficulties, and tension between local and global exploration.

  • Large State-action Space: Large state-action spaces make exploration difficult, especially for high-dimensional observations, many degrees of freedom, and complex action structures.Learned compact representations can improve exploration in high-dimensional state spaces, but efficient exploration in large action spaces remains an open question.
  • Sparse, Delayed Rewards: Sparse and delayed rewards make basic strategies unlikely to discover meaningful states or informative feedback.Effective approaches may use reward-agnostic dense signals and temporally extended exploration, but long-horizon environments remain difficult.
  • White-noise Problem: Unpredictable observation noise can attract agents toward noisy states and prevent them from reaching other parts of the environment.The Noisy-TV example adds Gaussian observation noise that keeps the agent in its current room; robust exploration in stochastic environments remains an important research problem.
  • Multi-agent Exploration: Multi-agent exploration faces an exponentially growing joint state-action space, partial observability, non-stationarity, and the need for coordinated behavior.Individual local exploration reduces joint-space costs but can fail when tasks require cooperation because local measurements do not reflect global information.
  • Multi-agent Exploration: Agents must balance local and global exploration because relying too heavily on local information causes redundant exploration, while global information does not reveal each agent’s contribution.This trade-off can produce inadequate or redundant exploration in cooperative navigation tasks.

IV. EXPLORATION IN SINGLE-AGENT DRL

Single-agent exploration methods are organized around uncertainty estimation and intrinsic motivation. Uncertainty can guide either optimistic action selection or episode-level posterior sampling.

  • Single-agent DRL exploration is classified into uncertainty-oriented and intrinsic motivation-oriented methods.
  • Uncertainty-oriented methods estimate value-function uncertainty, distinguishing epistemic uncertainty from aleatoric uncertainty.Epistemic uncertainty reflects insufficient environmental knowledge, whereas aleatoric uncertainty reflects intrinsic environmental randomness.
  • Table I compares uncertainty-oriented algorithms by posterior type and by how extensively they address identified exploration challenges.
  • Optimistic action selection chooses actions maximizing Q+ at each time step, where Q+ adds an uncertainty bonus to the ordinary Q-value.
  • Thompson sampling samples a Q-function from its posterior and uses it for action selection throughout an episode.Using one sampled Q-function across the episode enables temporally extended exploration and benefits long-horizon tasks.

1) Exploration via Epistemic Uncertainty:

Epistemic-uncertainty exploration estimates uncertainty through parametric or non-parametric value-function posteriors. These approaches support optimistic or posterior-sampling exploration but face action-space and estimation limitations.

  • Epistemic uncertainty is estimated by maintaining either a parametric or non-parametric posterior of the value function.
  • Parametric posterior methods use Bayesian regression or related approximations, with RLSVI achieving a near-optimal worst-case regret bound in linear settings.
  • Bootstrapped DQN maintains independent Q-estimators and samples among them, enabling temporally extended exploration with one exploratory policy per episode.
  • Parametric posterior methods generally handle discrete control, whereas non-parametric posterior methods can also select actions in continuous control.
  • Combining epistemic and aleatoric uncertainty helps avoid exploring highly random regions that cannot become less uncertain through training.
  • Information-directed methods combine distributional estimates of aleatoric uncertainty with bootstrapped Q-values for epistemic uncertainty, balancing regret and information gain.
  • Posterior-based exploration can remain sensitive to white noise when Q-functions are estimated inaccurately by parametric or non-parametric methods.

B. Intrinsic Motivation-oriented Exploration

Intrinsic-motivation exploration creates intrinsic rewards that encourage agents to seek accomplishment through interaction. Prediction-error methods reward discrepancies between predicted and actual next states, while representation learning determines their robustness.

  • Intrinsic-motivation methods design intrinsic rewards to encourage exploratory behavior and are organized into three technical categories.
  • Prediction Error: Prediction-error methods reward states whose predicted and actual next states differ, using distance in a learned latent space.
  • Prediction Error: Dynamic-AE computes prediction distance in an autoencoder latent space but cannot handle white-noise distractions or long-horizon effects.
  • Prediction Error: ICM improves robustness to white noise by learning representations through a self-supervised inverse model, but considers only one-step action influence.
  • Prediction Error: AR4E expands low-dimensional actions into higher-dimensional representations, increasing dynamics-model representation power and improving results over ICM.

2) Novelty:

Novelty methods reward visiting less-frequent or unseen states, using counts, density models, representations, or episodic memory. Information-gain methods instead reward reductions in dynamics uncertainty, while stochasticity and computation remain important constraints.

  • Novelty: Count-based novelty assigns intrinsic reward inversely proportional to state visit counts, but large or continuous spaces require hashing or density-based pseudo-counts.
  • Novelty: Count-based and related novelty methods can work well with sparse, delayed rewards, although density estimation adds computational complexity.
  • Novelty: Novelty estimation includes inter-episode and intra-episode forms, with the latter resetting novelty at each episode to encourage within-episode state diversity.
  • Novelty: NGU combines inter-episode RND novelty with intra-episode episodic similarity, supporting generalization across complex tasks and temporally extended exploration.
  • Novelty: NovelD rewards first visits to states at boundaries between explored and unexplored regions, and its results outperform SOTA in Mini-Grid.
  • Information Gain: Information-gain rewards measure decreases in uncertainty about environment dynamics, but stochastic environments make accurate prediction difficult.
  • Information Gain: VIME uses a Bayesian neural network to reward uncertainty reduction about dynamics weights, but its computation costs hinder complex-scenario applications.
  • Information Gain: Ensemble-based exploration uses output variance as intrinsic reward, with noise eventually ignored as dynamics models converge.

C. Other Advanced Methods for Exploration

Beyond the main exploration streams, the survey reviews distributed, parametric-noise, safe, and other specialized approaches. These methods offer diverse exploration mechanisms but often involve setting-specific trade-offs or limited generality.

  • Distributed Exploration: Distributed exploration combines heterogeneous actors, independent environments, and prioritized replay to improve exploration and learning efficiency.Ape-X uses workers with different ϵ values, while R2D2 adds recurrent state information.
  • Distributed Exploration: NGU and Agent57 augment distributed architectures with episodic and lifelong novelty, achieving strong Atari performance on hard-exploration tasks.Agent57 additionally uses separate Q-function parametrization and a meta-controller for value approximation and policy selection.
  • Exploration with Parametric Noise: Parametric-noise methods perturb network parameters to encourage diverse and consistent exploration, but they struggle to realize targeted behaviors in sparse, delayed-reward settings.NoisyNet learns the noise variance through the RL loss, unlike heuristic adaptive mechanisms.
  • Safe Exploration: Safe exploration seeks efficient discovery while avoiding unsafe states or dangerous behavior, using modified optimization criteria or altered exploration processes.CMDP and CPO exemplify criterion-based approaches, whereas other methods use prior knowledge, demonstrations, teacher advice, or risk-directed exploration.
  • Comparison: Table III summarizes how reviewed advanced algorithms address exploration challenges, excluding specialized safe-exploration methods.Its symbols indicate whether each method addresses a problem not at all, partially, highly, or fully.
  • Other Advanced Methods: Go-Explore uses a return-then-explore recipe and robustification to solve extremely difficult Atari tasks, but its sophisticated designs may not generalize broadly.DTSIL relaxes this limitation to some extent through a similar idea.

V. EXPLORATION IN MULTI-AGENT DRL

Deep MARL exploration remains preliminary, with most methods extending single-agent ideas to joint-agent settings. Large joint state-action spaces, partial observation, and non-stationarity make uncertainty and intrinsic-reward estimation difficult, while coordinated exploration remains an open challenge.

  • Overview: Deep MARL exploration is at a preliminary stage, and most methods extend single-agent techniques while incorporating multi-agent characteristics.The joint state-action space increases exploration difficulty as the number of agents grows.
  • Comparison: Table IV reports how reviewed multi-agent exploration algorithms address the surveyed challenges, excluding multi-agent MAB works from the “Others” category.The table uses blank, partial, high, and check-mark categories to indicate coverage.
  • Uncertainty-oriented Exploration: In multi-agent settings, partial observation makes uncertainty estimates local and potentially biased, while non-stationarity further complicates global uncertainty measurement.Each agent observes only part of the joint state space, limiting the reliability of local uncertainty.
  • Uncertainty-oriented Exploration: Epistemic-uncertainty methods extend the OFU principle to MARL, including Gaussian-process Q-function posteriors whose variance represents epistemic uncertainty.Multi Safe Q-Agent explores using an upper Q-function bound and a Boltzmann policy.
  • Uncertainty-oriented Exploration: Other MARL methods combine epistemic and aleatoric uncertainty or use categorical and quantile value distributions for uncertainty-aware value estimation.Some distributional methods use aleatoric uncertainty only for improved value estimation rather than exploration.
  • Intrinsic motivation-oriented Exploration: Intrinsic motivation encourages exploration of unseen regions, but its measurement and reward assignment become harder with more agents, partial observation, and non-stationarity.Multi-agent interactions also provide reward-agnostic information that can support intrinsic-reward design.
  • Intrinsic motivation-oriented Exploration: Multi-agent intrinsic-reward methods include centralized novelty bonuses, decentralized curiosity combined by a meta-policy, and learned individual rewards aligned with team reward.The decentralized curiosity reward types described are domain-specific, while LIIR learns individual intrinsic rewards for policy updates.
  • Intrinsic motivation-oriented Exploration: Coordinated exploration can target joint-action effects that cannot be reproduced by sequential individual actions, but some methods require unrealistic environment modifications.The survey identifies robust intrinsic-motivation estimation balancing local and global information as an open direction.

C. Others Methods for Multi-agent Exploration

The survey reviews multi-agent exploration methods beyond uncertainty and intrinsic motivation, alongside benchmark design and empirical comparisons across DRL and MARL settings.

  • Multi-agent exploration research includes methods outside uncertainty estimation and intrinsic motivation, presented chronologically.
  • Efficient coordinated exploration in large multi-agent environments requires adaptivity, commitment, and diversity.
  • A CTDE framework trains a centralized maximum-entropy policy, then distills cooperative behavior into decentralized policies.
  • The empirical comparison covers Montezuma’s Revenge, the overall Atari suite, Vizdoom, and SMAC, each targeting different exploration challenges.
  • Uncertainty-oriented methods generally improve exploration in Atari, whereas intrinsic motivation is especially effective on sparse-reward tasks but can hurt conventional tasks.
  • Distributed training, parametric noise, and potential-based exploration are additional approaches, while MARL methods show advances on difficult and sparse-reward SMAC tasks.

B. Open Problems

The survey identifies unresolved exploration challenges involving scale, noise, long horizons, reward transformation, multi-agent coordination, and safety.

  • Large and complex action spaces remain a major limitation because most methods assume small discrete or low-dimensional continuous actions.
  • Representation learning is proposed as a surrogate space for more efficient state and action exploration, with action semantics supporting generalization.
  • Extremely sparse, delayed rewards over long horizons remain unsolved and require long-term context memorization and control of complex environmental semantics.
  • Noise can distract exploration, motivating compact task-relevant representations and robustness-oriented regularization.
  • Uncertainty-based methods depend on uncertainty estimates converging toward zero, while reliable estimation remains difficult in general environments.
  • Intrinsic reward transformations are often heuristic and may alter the original objective, hinder performance, or produce suboptimal solutions.
  • Deep MARL exploration remains early-stage, with unresolved partial observability, non-stationarity, scale, coordination, and benchmark-standardization challenges.
  • Safe exploration requires safety during training interactions, not only during final evaluation or deployment, and prior knowledge is highlighted as a promising tool.

VII. CONCLUSION

The paper surveys exploration in DRL and deep MARL through a challenge-based taxonomy, algorithmic analysis, and unified empirical evaluation. It concludes that large-scale, long-horizon, semantically complex exploration remains difficult, especially in deep MARL.

  • The survey organizes exploration methods into uncertainty-oriented and intrinsic motivation-oriented categories, while also covering distinct advanced methods.
  • The paper identifies major exploration challenges for both single-agent and multi-agent reinforcement learning.
  • Exploration remains highly challenging in large state-action spaces, long-horizon environments, and settings with complex semantics.
  • Deep MARL exploration is substantially less studied than exploration in the single-agent setting.
  • The survey calls for multidimensional evaluation criteria and standard experimental benchmarks beyond cumulative rewards and sample efficiency.

APPENDIX A MODEL-BASED EXPLORATION

The appendix broadens the survey to model-based, goal-conditional, skill-discovery, and self-imitation approaches. These methods use models, hindsight goals, mutual information, or successful past experiences to support exploration and learning.

  • Model-based RL uses an environment model for simulated experience or planning, including uncertainty estimation and intrinsic motivation.
  • Model-assisted RL uses ensemble dynamics uncertainty and artificial data selectively in high-uncertainty regions.
  • Intrinsic motivation in model-based RL can use dynamics information gain to encourage exploration of uncertain areas.
  • Hindsight experience replay substitutes achieved goals from failed trajectories and recomputes rewards, helping agents learn in goal-conditional tasks.
  • Unsupervised skill discovery learns skill-conditional policies without extrinsic rewards by maximizing mutual information between states and latent skills.
  • Skill-discovery methods commonly optimize variational lower bounds for reverse or forward mutual-information objectives.
  • Self-Imitation Learning reuses superior experiences from the agent’s history and differs from uncertainty- and intrinsic-motivation-based exploration.
Loading 2109.06668v6…