Technical Summary: Coordination Matters: Evaluation of Cooperative Multi-Agent Reinforcement Learning

Problem Statement

Cooperative Multi-Agent Reinforcement Learning (MARL) benchmarks traditionally rely on aggregate outcome metrics—such as return, success rate, or completion time—to evaluate performance. While essential, the authors argue these metrics are insufficient for diagnosing how agents coordinate, particularly in settings where agents, tasks, and joint assignment choices scale combinatorially. Two policies may achieve similar returns while relying on fundamentally different interaction patterns, or a decline in return may conflate poor coordination with other factors like inefficient labor division or domain-specific bottlenecks. This limitation is critical for benchmarks intended to evaluate scaling behavior, where increasing the number of agents or tasks can alter not only task difficulty but also the structural nature of coordination itself. The paper posits that current evaluations fail to reveal process-level failures, such as redundant assignments or poor workload distribution, which are often masked by aggregate scores.

Methodology

The STAT Testbed

To address this gap, the authors introduce STAT (Spatial Task Allocation Testbed), a controlled, commitment-constrained spatial task-allocation environment. STAT is designed to isolate high-level task-assignment coordination by abstracting away low-level collision avoidance and path planning.

• Environment: Agents start at a fixed origin and must distribute themselves across spatially distributed tasks on a 2D grid. The environment is fully observable.
• Commitment Structure: Agents operate under a finite-state commitment structure. Once an agent selects a task, it becomes committed to that assignment, moves toward it, executes it, and only then returns to a selection state. This creates sparse, high-impact decision points.
• Conflict Resolution: If multiple agents select the same task simultaneously, a retrospective conflict resolution mechanism assigns the task to the closest agent; others are forced to idle. This makes redundant allocation an observable process-level failure rather than just a latent cause of lower reward.
• Scaling: STAT allows for systematic scaling along three axes: number of agents, number of tasks, and environment size, while holding task rules and observation access fixed.

Process-Level Diagnostics

The paper proposes a "coordination-aware evaluation" perspective that supplements return with specific process-level diagnostics tailored to the assignment structure:

1. Total Task Assignment Conflicts: The count of distinct tasks selected by more than one agent before resolution (measuring redundant assignment breadth).
2. Conflict Rate: Timestep-normalized conflicts to distinguish between methods that accumulate conflicts due to longer episodes versus those that generate them frequently.
3. Conflicts per Task: Normalized conflict density relative to the task set size.
4. Assignment Diversity: The number of distinct new task assignments retained by the team after conflict resolution, measuring the breadth of the division of labor.
5. Task Completion Throughput: The number of completed tasks per timestep, distinguishing coordination failures from spatial inefficiencies (e.g., travel time).

Experimental Setup

The authors evaluate six representative value-based MARL methods across varying levels of centralization:

• CTCE (Centralized Training, Centralized Execution): DQN, FDQN.
• CTDE (Centralized Training, Decentralized Execution): VDN, QMIX, QTRAN.
• DTDE (Decentralized Training, Decentralized Execution): IQL.
  Experiments span "Baseline" (smaller scales) and "Extreme" (larger scales) configurations, varying agents, tasks, and grid size independently.

Key Results

1. Return Alone is Insufficient

The study demonstrates that similar return trends can reflect distinct coordination mechanisms. For instance, in task-scaling experiments, increasing the number of tasks often led to higher returns (due to more reward opportunities) but simultaneously increased total conflicts and redundant assignments. A policy might appear successful based on return while actually suffering from significant coordination inefficiencies that process-level diagnostics reveal.

2. Scaling Dynamics

• Environment Size: Increasing grid size primarily reduced throughput and assignment opportunities (as agents spent more time moving) rather than increasing conflict rates. This highlights that performance drops in spatial scaling are often due to reduced decision frequency rather than coordination failure.
• Number of Tasks: Increasing tasks expanded the assignment space, leading to higher absolute conflicts. While returns initially improved, the coordination burden eventually offset gains. Normalized metrics (conflicts per task) showed that contention did not always grow linearly with task count, but total redundant assignments did.
• Number of Agents: Adding agents did not uniformly improve performance. In smaller settings, extra agents often degraded performance by amplifying redundant assignments without sufficient tasks to justify the parallelism. In larger settings, returns improved, but only for methods capable of converting team capacity into coordinated work. Independent learners (IQL) were particularly vulnerable to increased conflict rates under agent scaling.

3. Method-Specific Behaviors

• Centralized Methods (DQN/FDQN): FDQN, which uses a factorized centralized representation, remained tractable and effective at reducing redundant assignments across scales, often outperforming others in coordination metrics. Standard DQN was limited to small scales due to exponential joint action space growth.
• CTDE Methods (VDN/QMIX/QTRAN): These methods remained scalable and competitive in return but often exhibited higher conflict rates or lower assignment diversity compared to the strongest centralized approaches, suggesting that comparable returns can mask differences in coordination quality.
• Independent Learning (IQL): IQL showed the highest vulnerability to redundant assignment in highly interdependent settings, confirming that independent learners struggle when assignment decisions are strongly coupled.

Significance and Claims

The paper claims that coordination-aware evaluation is a necessary complement to return-based benchmarking for cooperative MARL. The authors argue that:

1. Diagnosis of Failure Modes: Process-level diagnostics allow researchers to distinguish whether a method fails due to poor coordination (redundant assignments), inefficient division of labor, or environmental constraints (spatial scale), which aggregate return cannot do.
2. Scaling Insights: Performance under scale is shaped not only by the nominal action-space size but also by "assignment pressure," sparse decision opportunities, and inter-agent dependencies.
3. Benchmark Design: Future benchmarks should report process-level diagnostics to characterize how agents coordinate, not just what return they achieve. The authors position STAT as a controlled testbed to isolate these coordination dynamics, distinct from complex environments like StarCraft or Overcooked where multiple failure modes (navigation, partial observability) are entangled.

The paper concludes that while existing benchmarks have driven progress, they often obscure the specific coordination mechanisms that enable or hinder performance in combinatorial scaling regimes. By making assignment conflicts and diversity directly observable, this work provides a more interpretable view of MARL failure modes.