Source-linked AI summary
Cooperative Exploration for Multi-Agent Deep Reinforcement Learning
Iou-Jen Liu, Unnat Jain, Raymond A. Yeh, Alexander G. Schwing
TL;DR
Multi-agent exploration methods often use noise and can struggle to identify worthwhile states or coordinate exploration toward them. CMAE selects shared goals from restricted state spaces and trains agents to reach them together. It consistently outperforms baselines in sparse-reward tasks, though a hard SMAC task remains unsolved by CMAE and the baselines.
Problem
Existing multi-agent methods commonly use noise-based exploration, and agents can struggle both to identify under-explored states and to coordinate exploration toward them.
Source: §1 · p. 1Method
CMAE selects shared goals from projected restricted spaces using normalized entropy and trains coordinated exploration policies to reach those goals.
Source: §1 · pp. 1–2Results
Takeaways & Limitations
CMAE increases exploration efficiency, particularly in sparse-reward environments, as an approach to coordinated exploration.
Source: §6 · p. 9On sparse-reward SMAC 3s vs 5z, CMAE and all baselines fail to solve the task without handcrafted intermediate rewards.
Source: §4 · p. 8
Abstract
from arXiv · showhide
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).
1. Introduction
Existing MARL methods commonly rely on noise-based exploration, while cooperative approaches still struggle to identify under-explored states and coordinate toward them. CMAE addresses these challenges with shared goals chosen from restricted state spaces, and outperforms baselines in sparse-reward tasks.
1. Introduction
- Prior methods such as QMIX, MADDPG, and COMA address MARL non-stationarity with centralized critics but retain noise-based exploration.Earlier work also explored shared latent variables and behavior-influence-based coordination.Source: §1 · p. 1
- Existing multi-agent methods use noise-based exploration, while cooperative exploration methods still struggle to find worthwhile states and coordinate efforts toward them.Identifying under-explored states becomes harder as the joint state and action spaces grow exponentially with the number of agents.Source: §1 · p. 1
- CMAE selects shared goals from projected, lower-dimensional spaces and trains agents to reach them in a coordinated manner.Its bottom-up scheme explores restricted spaces from low to high dimensions, with rewards reshaped to favor reaching the selected goal.Source: §1 · pp. 1–2
- CMAE consistently outperforms state-of-the-art baselines in sparse-reward tasks across the evaluated multi-agent settings.The evaluation includes a discrete multiple-particle environment and SMAC, with both dense- and sparse-reward settings considered.Source: §1 · p. 2
2. Preliminaries
The preliminaries define the cooperative multi-agent decision process and the off-policy MARL setting used by CMAE. Training follows centralized training with decentralized execution, while agents collect experience through exploration policies and target policies learn from replay memory.
2.1. Multi-Agent Markov Decision Process
- A cooperative n-agent MDP specifies state and per-agent action spaces, transitions, observations, collective rewards, and a shared-return objective.Agents act jointly, while each agent receives a local observation that may reveal only partial state information.Source: §2.1 · p. 2
2.2. Multi-Agent Reinforcement Learning
- Under centralized training and decentralized execution, training can access all agents’ observations, actions, and state, but each test-time agent sees only its local observation.CMAE is applicable to off-policy MARL methods.Source: §2.2 · p. 2
- Off-policy exploration policies collect transitions into replay memory, from which target policies are trained.Stored transitions include state, observations, joint action, next state and observations, and reward.Source: §2.2 · p. 2
3. Coordinated Multi-Agent Exploration (CMAE)
CMAE separates exploration from task policies and directs agents toward shared goals in progressively selected low-dimensional projections of the state space. It chooses goals and restricted spaces using visitation counts and normalized entropy, and its analysis describes settings where shared goals and restricted-space exploration reduce discovery effort.
3.1. Training of Exploration Policies
- Exploration policies are decoupled from target policies and trained with a modified reward that favors reaching a shared goal.Target policies maximize the usual external episode return, while exploration policies continuously learn to reach selected goals.Source: §3 · pp. 2–3, §3.1 · p. 3
3. Coordinated Multi-Agent Exploration (CMAE)
- CMAE projects the full state into low-dimensional restricted spaces, then expands exploration from lower- to higher-dimensional projections.Each restricted space retains selected state components, and the spaces form a tree for bottom-up selection.Source: §3 · p. 3
3.2. Shared Goal and Restricted Space Selection
- CMAE selects under-explored restricted spaces through bottom-up tree search, using lower normalized entropy as an indicator of under-exploration.Within a selected space, it chooses as the goal the least-count state among a sampled batch of replay-buffer states.Source: §3.2 · p. 4
3.3. Counting in Continuous State Spaces
- For continuous state spaces, CMAE uses hash-based counting to map projected states to integer-indexed counters.The paper reports that CMAE with hash counting performed well in continuous-state environments.Source: §3.3 · pp. 4–5
3.4. Analysis
- In a cooperative matrix game, shared-goal exploration sees distinct action configurations more efficiently by directing agents toward the least-visited configuration.Agents coordinate their actions to achieve the selected goal configuration.Source: §3.4 · p. 5
- When the payoff depends on both agents’ actions, the expected discovery effort after restricted-space exploration and full-space exploration is O(l + l^2) = O(l^2).When payoff depends on only one agent’s action, the analysis says restricted-space exploration can further reduce the expected steps to find maximal reward.Source: §3.4 · p. 5
4. Experimental Results
CMAE is evaluated across sparse- and dense-reward MPE and SMAC tasks, with strong sparse-reward results and performance comparable to baselines in dense-reward settings. The experiments also examine visitation behavior, design ablations, and a difficult SMAC task that remains unsolved.
Evaluation setup
- Evaluation covers discrete MPE and SMAC under sparse- and dense-reward settings; final metrics average the last 100 evaluation episodes across five random-seed runs.The authors report episode reward versus environment steps as a data-efficiency metric.Source: §4 · pp. 5, 7
MPE results
- 100% success on Pass, Secret-Room, and Push-Box within 3M environment steps; baselines solve none within that budget.This is the sparse-reward MPE comparison.Source: Table 1 · p. 6, §4 · p. 7
SMAC results
- 47.7% and 44.3% success rate on 3m-sparse and 2m vs 1z-sparse, respectively, versus 18% to 20% for QMIX and weighted QMIX with count-based exploration.CMAE achieves similar performance to state-of-the-art baselines on dense-reward SMAC tasks.Source: Table 2 · p. 7, §4 · p. 8
MPE results
- CMAE achieves similar or better performance than baselines on dense-reward MPE tasks.The final-episode-reward table covers sparse-reward results at top and dense-reward results at bottom.Source: Table 1 · p. 6, §4 · p. 7
Exploration behavior
- After 1.5M steps in Secret-Room, CMAE agents frequently visit the three right-side rooms, while ϵ-greedy agents mostly remain in the left room.The visitation map uses a log scale, with CMAE on top and ϵ-greedy below.Source: §4 · p. 7, Figure 2 · p. 7
SMAC results
- Although useful high-dimensional restricted spaces may be infeasible to discover in SMAC, low-dimensional restricted-space exploration was empirically beneficial on a subset of tasks.SMAC’s space tree grows combinatorially with dimensionality.Source: §4 · p. 7
Ablation study
- On 3m-sparse, removing policy decoupling lowers success rate from 47.7% to 25.4%, while full-state exploration lowers it to 9.4%.The study identifies both policy decoupling and restricted-space exploration as essential to CMAE’s success.Source: Figure 4 · p. 8, §4 · p. 8
Limitations
- CMAE and all baselines fail to solve sparse-reward 3s vs 5z, where the winning strategy requires forcing enemies to scatter and attending to them one by one.The authors report that without hand-crafted intermediate rewards, learning this strategy is extremely challenging for any approach.Source: §4 · p. 8
5. Related Work
Prior work spans single-agent exploration techniques, MARL systems, and newer coordinated-exploration methods. Concurrent reinforcement learning differs from CMAE’s multi-agent setting because agents act in separate environment instances.
Exploration for Deep Reinforcement Learning
- Single-agent methods include pseudo-count exploration bonuses, meta-policy gradients, model-based bonuses, state-marginal matching, curiosity, diversity, and other approaches.These methods are described as targeting single-agent deep reinforcement learning.Source: §5 · pp. 8–9
Multi-agent Deep Reinforcement Learning (MARL)
- MARL methods address non-stationarity, communication, and behavior modeling, while exploration approaches have relied on classical noise-based techniques.MADDPG uses a central critic; other examples include differentiable communication and self-other modeling.Source: §5 · p. 9
- MAVEN uses a hierarchical latent variable for committed exploration, while influence-based exploration encourages visits to interaction points that change other agents’ behavior.Source: §5 · p. 9
Concurrent Deep Reinforcement Learning
- Concurrent methods coordinate agents across separate environment instances, whereas multi-agent methods place agents in one shared instance where actions affect others’ observations and rewards.The concurrent setting is distinguished from the multi-agent setting on this basis.Source: §5 · p. 9
6. Conclusion
The conclusion presents CMAE as a shared-goal approach that learns coordinated exploration policies, with restricted-space selection helping efficient exploration, particularly in sparse-reward environments. The appendix outlines proofs, environment and implementation details, and additional results.
6. Conclusion
- CMAE defines shared goals and learns coordinated exploration policies, using restricted-space selection to find goals for efficient exploration, particularly in sparse-reward environments.Source: §6 · p. 9
- The authors report increased exploration efficiency and describe CMAE as a first step toward efficient coordinated exploration.Source: §6 · p. 9
A. Appendix
- The appendix covers proofs, MPE and SMAC environments, implementation details, an absolute metric, additional MPE and baseline results, and training curves.Source: A. Appendix · p. 12
B. Proof of Claim 1
Claim 1 contrasts shared-goal exploration with uncoordinated exploration when covering all m action configurations. Shared goals visit a new configuration each timestep, while uncoordinated exploration takes Θ(m ln m) expected time.
B. Proof of Claim 1
- Without shared goals, each step uniformly selects an action configuration; the proof sums the expected waits for each newly observed distinct configuration.The waiting time for the i-th distinct configuration follows a geometric distribution with success probability P(i).Source: B. Proof of Claim 1 · p. 12
- Uncoordinated exploration has expected coverage time Θ(m ln m), compared with m steps for shared-goal exploration.Source: B. Proof of Claim 1 · p. 12
- Shared-goal exploration visits a new action configuration at every timestep, requiring m timesteps to visit all m configurations.Source: B. Proof of Claim 1 · p. 12
C. Proof of Claim 2
Claim 2 considers a payoff matrix whose reward depends on only one agent’s action. Exploring the agents’ action spaces independently takes O(l) steps to find maximal reward, versus O(l²) for the full joint action space.
C. Proof of Claim 2
- When reward depends on one agent’s action, independent action-space exploration takes O(l) steps to discover maximal reward, while full joint-space exploration takes O(l²).Source: C. Proof of Claim 2 · p. 12
- Independent exploration checks at most 2l configurations, whereas joint exploration may encounter l² − l non-maximal configurations before finding maximal reward.Source: C. Proof of Claim 2 · pp. 12–13
D. Details Regarding MPE Environments
The MPE appendix specifies four sparse-reward cooperative tasks and describes denser variants that add checkpoint rewards to guide agents toward task landmarks.
D. Details Regarding MPE Environments
- In Pass-sparse, agents must occupy switches to open a door, then both reach the other room to solve the task.The agents receive collective positive reward, and the grid is 30 × 30.Source: D. Details Regarding MPE Environments · p. 13
- Secret-Room-sparse extends Pass with four rooms; both agents must reach one of three target rooms to receive positive reward.A switch in the large room controls all three doors, while each small-room switch controls its own door; the grid is 25 × 25.Source: D. Details Regarding MPE Environments · p. 13
- In Push-Box-sparse, both agents must push a heavy box in the same direction at the same time to move it to a wall.The task uses a 15 × 15 grid.Source: D. Details Regarding MPE Environments · p. 13
- In Island-sparse, two agents must jointly crush a wolf because one agent alone cannot overcome its energy limit.The agents receive a collective reward of 300 when the wolf is crushed; Island-dense adds +1 reward when the wolf’s energy decreases.Source: D. Details Regarding MPE Environments · p. 13
- Dense MPE variants add checkpoint rewards for moving toward task landmarks, with up to ten rewards in Pass and Secret-Room and six in Push-Box.Checkpoint regions are concentric circles around landmarks, and an agent receives +0.1 the first time it enters each region.Source: D. Details Regarding MPE Environments · p. 13
E. Details of SMAC environments
The SMAC appendix defines sparse and dense versions of three cooperative combat tasks, notes a game-version constraint, and explains how normalized entropy is estimated for restricted state spaces.
E. Details of SMAC environments
- The sparse SMAC tasks reward completion only: three Marines defeat three enemies, two Marines defeat one Zealot, and three Stalkers handle five Zealots.The 2m vs 1z task requires alternating fire, while 3s vs 5z requires scattering enemies and attending to them one by one.Source: E. Details of SMAC environments · p. 13
- Dense SMAC tasks provide intermediate combat rewards, while retaining a +200 collective reward when all enemies are defeated in 3m-dense.The 2m vs 1z-dense and 3s vs 5z-dense reward functions follow the 3m-dense task.Source: E. Details of SMAC environments · pp. 13–14
- SMAC results use StarCraft version SC2.4.6.2.69232, and results across versions are not directly comparable because the underlying dynamics differ.Source: E. Details of SMAC environments · p. 14
F.1. Normalized Entropy Estimation
- Normalized entropy is computed for a restricted space S_k, estimating its typically unavailable size with the number of distinct observed outcomes.The estimate |Ŝ_k| grows as exploration reveals new outcomes; a constant restricted space is assigned infinite normalized entropy.Source: §F.1 · p. 14
F.2. Architecture and Hyper-Parameters
CMAE is paired with tabular Q-learning or DQN on MPE and with QMIX on SMAC; this section also documents baseline rollout settings and distinguishes final from absolute metrics.
F.2. Architecture and Hyper-Parameters
- CMAE uses tabular Q-learning for Pass, Secret-Room, and Push-Box, and a three-layer DQN for Island.For MPE tasks, the goal bonus is 1 and the discount factor is 0.95.Source: §F.2 · p. 14
- EITI and EDTI use default settings with 512-step rollouts across 32 processes; shorter rollouts did not improve their Secret-Room results.After more than 500M steps, the shorter-rollout success rates were below the 80% achieved with the default setting.Source: §F.2 · p. 14
- On SMAC, CMAE is combined with QMIX using a recurrent DRQN agent, and the goal bonus is set to 0.1 across tasks.The DRQN uses a 64-dimensional GRU hidden state; the mix network has 32 units.Source: §F.2 · pp. 14–15
G. Absolute Metric and Final Metric
- The absolute metric is the best policy’s average episode reward over 100 evaluation episodes, reported alongside the final metric.The appendix summarizes both metrics for MPE and SMAC tasks.Source: G. Absolute Metric and Final Metric · p. 15
H. Additional Results on MPE Task: Island
Across the additional training curves, CMAE has higher success rates than baselines on challenging sparse-reward tasks and similar performance on dense-reward tasks; Island results and step comparisons add MPE evidence.
H. Additional Results on MPE Task: Island
- On Island-sparse, CMAE achieves higher than 50% success while baselines struggle to solve the task; on Island-dense, CMAE performs similarly to baselines.The curves are shown for sparse- and dense-reward Island tasks.Source: H. Additional Results on MPE Task:… · p. 15
I. Additional Results of Baselines
- On Pass-sparse, Secret-Room-sparse, and Push-Box-sparse, CMAE reaches 100% success within 3M steps, while EITI and EDTI require more than 300M steps to reach 80%.On Island-sparse, the baselines require more than 3M steps for 20% success, while CMAE requires fewer than 8M steps for the same rate.Source: §I · p. 16, Table 6 · p. 16
J. Additional Training Curves
- CMAE consistently achieves higher success rates than baselines on sparse-reward tasks and similar performance on dense-reward tasks across MPE and SMAC training curves.Source: J. Additional Training Curves · p. 16, Figure 5 · p. 17, Figure 6 · p. 17