Technical Summary: CTC: The Composite Task Challenge for Cooperative Multi-Agent Reinforcement Learning

Problem Statement

While Division of Labor (DOL) is a fundamental principle for enhancing efficiency in biological and human systems, its integration into Cooperative Multi-Agent Reinforcement Learning (MARL) faces a critical bottleneck: the lack of benchmark tasks specifically designed to evaluate and necessitate DOL. Existing MARL testbeds (e.g., MPE, LBF, RWARE, SMAC, GRF) often allow agents to succeed through homogeneous behaviors or partial task completion. In these environments, DOL is beneficial but not strictly necessary, and the failure of a single subtask does not necessarily lead to overall task failure. Consequently, current cooperative MARL methods, which incorporate DOL mechanisms via policy diversity, agent grouping, or hierarchical architectures, lack rigorous environments to validate their ability to form effective, necessary cooperation. This gap limits the effective development and deployment of DOL mechanisms in practical applications.

Methodology

1. The Composite Tasks Challenge (CTC)

To address this gap, the authors propose the Composite Tasks Challenge (CTC), a suite of benchmark tasks constructed on two core design principles:

1. Necessity of DOL: DOL is a mandatory condition for task success.
2. Strict Cooperation: The failure of any atomic subtask results in the failure of the overall task.

Task Construction:

• Environment: Implemented within the StarCraft Multi-Agent Challenge (SMAC) framework to leverage existing infrastructure while introducing specific constraints.
• Atomic Subtasks: The CTC tasks are composed of two fundamental subtask types:
  • Defense Subtask: Agents must eliminate enemy units attempting to occupy a base building. Failure occurs if any enemy reaches the base.
  • Pursuit Subtask: Agents must eliminate enemy units attempting to retreat to their own base. Failure occurs if any enemy reaches the retreat base.
• Task Variants: Four specific tasks are designed to introduce asymmetry and heterogeneity, reflecting real-world complexity:
  • Defense 3/4 Subtask: Multiple defense subtasks with varying configurations and increasing numbers of subtasks (3 and 4, respectively).
  • Mixed 2/3 Subtask: Combinations of defense and pursuit subtasks with different ratios (1:1 and 2:1), introducing task heterogeneity.
• Heterogeneity: Agents and enemies utilize three distinct unit types (Marine, Marauder, Medivac) with unique capabilities, requiring agents to consider both task assignment and unit-specific strengths.
• Constraints: All subtasks are initiated simultaneously and are spatially separated, preventing a single agent from completing multiple subtasks concurrently.

2. Experimental Evaluation

The authors evaluated nine representative cooperative MARL methods on the CTC tasks:

• Baselines: QMIX (classic), EOI, DCC, CDS (Policy Diversity); RODE, ROMA, GoMARL (Agent Grouping); LDSA, HSD (Hierarchical MARL).
• Metrics: Test winning rate (mean and standard deviation over 5 seeds) and episode length.

3. Guiding Solution

To demonstrate the solvability of CTC tasks and provide a baseline for future research, the authors introduced a guiding solution consisting of:

• Rule-based External Reward (RER): A manually designed reward signal incorporating:
  • Damage Reward: Prioritizes eliminating high-value targets (Medivacs) which are critical for task success.
  • Action Reward: Encourages continuous offensive actions to prevent the "wandering issue" (agents idling after completing their primary subtask).
• Extended QMIX (e-QMIX): An architecture modification of QMIX to enhance policy diversity:
  • Feature Diversity: Utilizes a Sparse Mixture of Experts (MoE) framework to generate differentiated feature representations for agents sharing the same network.
  • Output Diversity: Employs a mixture of experts for action-value estimation, with weights dynamically generated based on local observations and multi-head attention mechanisms.

Key Results

Baseline Performance

• Zero Success Rate: All nine baseline methods achieved a 0% test winning rate across all four CTC tasks.
• Analysis of Failure:
  • Most methods failed to learn effective DOL policies, often resulting in agents failing to coordinate on specific subtasks.
  • Wandering Issue: A recurring failure mode where agents, upon completing their assigned subtask, remained idle or wandered locally instead of assisting teammates in other subtasks.
  • Subtask Sensitivity: Episode length analysis revealed that methods often failed to handle the time-critical nature of pursuit subtasks or the combat requirements of defense subtasks simultaneously.

Guiding Solution Performance

• Solvability Demonstrated: The e-QMIX architecture, supported by the RER, achieved non-zero test winning rates across all CTC tasks, proving that the tasks are solvable.
• Performance Variance:
  • e-QMIX achieved stable, non-zero winning rates (e.g., >10% in Defense 3, ~10% in Mixed 3).
  • RER significantly improved the performance of GoMARL and QMIX in specific tasks (e.g., GoMARL reached >80% in Defense 3), but failed to improve others (e.g., ROMA showed no improvement).
  • The solution highlighted that while RER helps mitigate specific issues like wandering and target prioritization, it is not a universal fix for all MARL architectures.

Significance and Claims

The paper claims the following significance for the cooperative MARL community:

1. Bridging the Gap: CTC serves as a novel testbed that explicitly bridges the gap between theoretical DOL mechanisms in MARL and the rigorous requirements of real-world cooperative applications.
2. Revealing Limitations: The consistent failure of state-of-the-art methods on CTC tasks highlights a substantial gap between the theoretical capabilities of current cooperative MARL methods and their practical ability to form necessary, robust cooperation.
3. Benchmarking Value: By enforcing strict conditions where DOL is necessary and subtask failure is fatal, CTC provides a discriminative benchmark for evaluating the true efficacy of DOL and cooperation mechanisms.
4. Research Direction: The introduction of the guiding solution (RER + e-QMIX) demonstrates that the tasks are solvable but remain highly challenging. It underscores the need for more generalizable, environment-agnostic solutions for learning effective DOL policies, as the current rule-based approach is specific to the SMAC implementation.

In summary, the authors posit that CTC is a challenging yet solvable testbed that exposes the limitations of current cooperative MARL methods and provides a necessary platform for advancing research into effective division of labor and cooperation.