Cooperative Exploration for Multi-Agent Deep Reinforcement Learning

Iou-Jen Liu, Unnat Jain, Raymond A. Yeh, Alexander G. Schwing

TL;DR

Cooperative Multi-Agent Exploration (CMAE) addresses the "curse of dimensionality" in multi-agent reinforcement learning by having agents pursue shared, under-explored goals. By projecting high-dimensional state spaces into simpler "restricted spaces" and decoupling exploration policies from target policies, CMAE enables agents to coordinate their search and solve complex sparse-reward tasks where traditional noise-based methods fail.

The Challenge of Multi-Agent Exploration

In Multi-Agent Reinforcement Learning (MARL), exploration is notoriously difficult. Most existing algorithms rely on noise-based exploration (like $\epsilon$-greedy), where agents essentially move randomly to find rewards. This fails in two major ways:

  1. The State Space Explosion: As the number of agents increases, the possible combinations of states and actions grow exponentially. Finding a "needle in a haystack" reward becomes mathematically improbable.
  2. Lack of Coordination: Many tasks require agents to work together to trigger a reward (e.g., two agents pushing a heavy box). Random individual noise is unlikely to result in the precise simultaneous actions needed for such coordination.

The authors identify that while the joint state space is huge, the reward function often depends on a small subset of that space (e.g., the location of the box, not every agent's exact orientation).

The CMAE Approach

CMAE introduces a "bottom-up" approach to exploration through three key mechanisms:

  • Restricted Space Projections: Instead of looking at the full, high-dimensional state space $S$, CMAE projects it into lower-dimensional "restricted spaces" ($S_k$). It starts with 1D projections and builds a Space Tree. If a low-dimensional space is well-explored, the algorithm "expands" the tree to explore higher-dimensional combinations.
  • Shared Goal Selection: The algorithm identifies "under-explored" states within these restricted spaces using a normalized entropy-based utility. It selects a specific state as a "shared goal" ($g$) that the agents haven't visited much.
  • Policy Decoupling: CMAE maintains two sets of policies. The target policies ($\pi$) are trained to maximize the actual environment reward. The exploration policies ($\mu$) are trained specifically to reach the shared goal $g$. By giving agents a bonus reward for reaching $g$, they learn to coordinate their movements toward that specific state.

The training follows the Centralized Training and Decentralized Execution (CTDE) paradigm, meaning agents can share information during training but must act based on local observations during testing.

Experimental Setup

The authors evaluated CMAE on two primary benchmarks, focusing heavily on sparse-reward variants where agents only receive a reward upon full task completion:

  1. Multi-Particle Environment (MPE):
    • Pass-sparse: Two agents must navigate rooms and occupy switches.
  2. Secret-Room-sparse: Agents must find a specific target room behind doors.
  3. Push-Box-sparse: Two agents must coordinate to push a heavy box to a wall.
  4. StarCraft Multi-Agent Challenge (SMAC):
    • Tested on scenarios like 3m (3 Marines), 2m_vs_1z (2 Marines vs 1 Zealot), and 3s_vs_5z (3 Stalkers vs 5 Zealots).
  5. The authors created sparse versions of these tasks to test exploration limits.

Key Results and Insights

CMAE demonstrated a massive leap in performance over state-of-the-art baselines like QMIX, EITI, and EDTI.

Performance comparison on MPE tasks
  • MPE Sparse Tasks: As shown in the figure above, CMAE achieved a 100% success rate on Pass, Secret-Room, and Push-Box tasks. All other baselines (including those with curiosity bonuses) stayed at 0% success.
  • SMAC Sparse Tasks: In the 3m-sparse scenario, CMAE reached a 47.7% success rate, while the best baseline (Weighted QMIX + Bonus) only reached 11.5%.
  • Efficiency: CMAE often identifies the winning strategy within the first few million environment steps, whereas noise-based methods fail to find any reward even after 100 million steps.

Why does it work so well? * Inductive Bias via Projection: Agents don't need to explore the entire joint state space simultaneously. By starting with low-dimensional projections, the agents can find "interesting" areas much faster. * Coordination through Common Goals: By training exploration policies to reach a specific state, coordination emerges naturally. Agents aren't just "wandering"; they are "commuting" to a specific destination together. * Decoupling is Essential: Ablation studies showed that trying to make the main target policy do the exploration (without decoupling) significantly hurts performance. Exploration requires a different "mindset" (and reward structure) than exploitation.

Limitations and Future Work

  • Complex Strategic Requirements: CMAE struggled with the "hard" SMAC task (3s_vs_5z-sparse). The authors note that the winning strategy here requires a very specific "scatter and kite" maneuver that is difficult to capture even with coordinated exploration.
  • State Tree Scaling: While the bottom-up approach helps, the number of possible restricted spaces still grows combinatorially. For extremely high-dimensional environments, more sophisticated ways to prune or grow the Space Tree might be needed.
  • Continuous Spaces: While the paper mentions hash-based counting for continuous spaces, the primary evaluation was on discretized or grid-like environments. Extending this to fully continuous, high-fidelity robotics simulations remains a promising direction.

Summary updated

Abstract

Exploration is critical for good results in deep reinforcement learning and has attracted much attention. However, existing multi-agent deep reinforcement learning algorithms still use mostly noise...
BibTeX
@inproceedings{liu2021cooperative,
  author = {Iou-Jen Liu and Unnat Jain and Raymond A. Yeh and Alexander G. Schwing},
  title = {{Cooperative Exploration for Multi-Agent Deep Reinforcement Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=VoFrm6JhZkW},
}
Figure