Cooperative Exploration for Multi-Agent Deep Reinforcement Learning

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

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-based techniques. Very recently, exploration methods that consider cooperation among multiple agents have been developed. However, existing methods suffer from a common challenge: agents struggle to identify states that are worth exploring, and hardly coordinate exploration efforts toward those states. To address this shortcoming, in this paper, we propose cooperative multi-agent exploration (CMAE): agents share a common goal while exploring. The goal is selected from multiple projected state spaces via a normalized entropy-based technique. Then, agents are trained to reach this goal in a coordinated manner. We demonstrate that CMAE consistently outperforms baselines on various tasks, including a sparse-reward version of the multiple-particle environment (MPE) and the Starcraft multi-agent challenge (SMAC).

Introduction

Multi-agent reinforcement learning (MARL) faces a significant hurdle in sparse-reward environments. As the number of agents increases, the state-action space expands exponentially—a phenomenon known as the "curse of dimensionality." Traditional exploration strategies, such as $\epsilon$-greedy noise-based methods, often fail because they rely on independent random actions. In complex scenarios requiring coordinated efforts, such as multiple agents pushing a heavy object, the probability of discovering rewards through random noise is vanishingly small.

The core challenges are two-fold: agents lack a mechanism to identify which states are worth visiting (Identification) and struggle to coordinate their actions to reach those states during exploration (Coordination).

Cooperative Multi-Agent Exploration (CMAE)

To overcome these limitations, we introduce Cooperative Multi-Agent Exploration (CMAE). CMAE treats exploration as a coordinated sub-task using a "bottom-up" approach based on three pillars:

1. Restricted State Spaces

Instead of exploring the full high-dimensional state space, CMAE projects it into multiple low-dimensional "restricted spaces." By focusing on simpler projections (e.g., 1D or 2D coordinates), agents can more easily identify under-explored regions. A Space Tree structure manages these projections, expanding to higher dimensions only after simpler ones are sufficiently explored.

2. Normalized Entropy for Goal Selection

CMAE identifies "interesting" states by tracking visit frequencies in these restricted spaces. Using a normalized entropy metric, the algorithm selects a "shared goal" from the least-visited states in under-explored projections. This provides a clear, coordinated target for the agents.

3. Policy Decoupling

A key innovation in CMAE is the separation of Target Policies and Exploration Policies. Target policies focus on maximizing the environment's actual reward, while exploration policies are dedicated to reaching the shared goal. This decoupling allows agents to learn complex coordinated behaviors necessary for exploration without being hindered by the sparse external reward signal.

Experimental Results

We evaluated CMAE against state-of-the-art baselines like QMIX, EITI, and EDTI on modified versions of the Multi-Particle Environment (MPE) and the StarCraft Multi-Agent Challenge (SMAC).

Sparse Reward Performance

In sparse-reward MPE tasks such as Pass-sparse and Push-Box-sparse, CMAE achieved a 100% success rate, whereas all baselines failed to find any rewards (0% success). This demonstrates the power of coordinated exploration over noise-based methods.

CMAE achieves 100% success rate in sparse-reward tasks where baselines fail.

Dense Reward Robustness

CMAE is not only effective in sparse settings but also robust in dense-reward environments. In the Pass (Dense Reward) task, CMAE significantly outperformed baselines in both final reward and learning speed, proving it does not degrade performance when rewards are frequent.

CMAE outperforms baselines in dense-reward settings, demonstrating its general applicability.

Conclusion

CMAE addresses the fundamental coordination gap in multi-agent exploration. By leveraging low-dimensional projections and decoupled policies, it enables agents to systematically and cooperatively explore vast state spaces. While challenges remain for extremely high-dimensional tasks and specific complex strategies in SMAC, CMAE represents a significant step forward in making MARL practical for sparse-reward real-world applications.

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-based techniques. Very recently, exploration methods that consider cooperation among multiple agents have been developed. However, existing methods suffer from a common challenge: agents struggle to identify states that are worth exploring, and hardly coordinate exploration efforts toward those states. To address this shortcoming, in this paper, we propose cooperative multi-agent exploration (CMAE): agents share a common goal while exploring. The goal is selected from multiple projected state spaces via a normalized entropy-based technique. Then, agents are trained to reach this goal in a coordinated manner. We demonstrate that CMAE consistently outperforms baselines on various tasks, including a sparse-reward version of the multiple-particle environment (MPE) and the Starcraft multi-agent challenge (SMAC).
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