Tabular studies are a common way to compare independent and centralized multi-agent learners, because they avoid function approximation. A natural expectation is that centralized learning, which learns joint actions, helps agents coordinate, especially when their bodies make solo success hard. Earlier work tests this only in parts: it measures coordination for one learning method, compares methods with the agents' bodies fixed, or varies speed but reports only how well the team did. We test it in a predator-prey environment, where teammates cooperatively hunt together while two teams compete. We compare independent Q-learning (IQL) with central Q-learning (CQL) in all four predator and prey pairings, under limits on speed and stamina, on a 5x5 and an 8x8 grid trained for 200,000 episodes each, and check that the agents learn on both. We measure coordination directly, with predictions for the main measurement fixed in advance. In this task, where one predator can capture prey alone, we find three things. First, CQL costs its agents in both roles on both grids, and its predators coordinate no more than IQL's. Second, its one benefit comes from acting on the best joint action: this cut capture time by 42% on the small grid with faster prey and unlimited stamina, but helped nowhere on the larger grid, where the best joint action had mostly never been tried. Third, on the larger grid a tie-breaking default decided which method won, even though the agents had passed a learning check. A tabular comparison can therefore be trusted only if it also checks how much of the state space the agents covered and implements the methods alike. We propose simple checks for both.
Figures & tables
Measure
What it measures
Splitting up
Share of steps in which the two predators’ nearest prey differ ( Gorelick et al., 2004 ; Liu et al., 2022 )
Catching together
Share of captures with both predators within one step of the captured prey ( Leibo et al., 2017 )
Flanking
Among steps with both predators one or two steps from the same prey: the share in which they are on opposite sides of it ( de Souza et al., 2021 )
Move dependence
How much one predator’s move tells about the other’s move in the same situation (mutual information in bits, minus a shuffled baseline) ( Jaques et al., 2019 ; Lowe et al., 2019 )
Partner swap
Extra capture time with a partner trained on another seed or with a random partner ( Barrett et al., 2011 ; Carroll et al., 2019 ; Strouse et al., 2021 )
Pair beats its parts
The pair’s captures per step above two random predators, minus the same gain for each member hunting with a random partner. Zero for two independent hunters ( Heuillet et al., 2022 )
Table 1. Coordination measures. We compare predator measures with random predators facing the same trained prey, and prey spacing with random prey facing the same trained predators.
5 × 5
8 × 8
Possible states visited
92–99%
40–58%
Visits per visited state
11–27
1.7–2.8
Actions tried per state, IQL
67–83%
34–43%
Joint actions tried per state, CQL
18–27%
7–9%
Untried greedy action, IQL
2–7%
51–82%
Untried greedy action, CQL
7–27%
87–94%
Table 2. How much of the state and action space the predators tried, ranges over the six settings (means over 10 seeds). Untried greedy action: share of the visits to a state in which the action the table rated best had never been taken.
Figure 1. CQL minus IQL in capture time, for each role and each opponent method, in the six settings, on both grids (means and 95% intervals over 10 seeds, paired by seed). On the left, positive values mean CQL predators are slower; on the right, negative values mean CQL prey are caught sooner.
We predicted that …
Verdict
Best moves
trained predators coordinate little, whatever their method
refuted (narrowly)
supported
predators coordinate more when slower than the prey
refuted
refuted
predators coordinate more with limited stamina
refuted
refuted
CQL predators coordinate more than IQL predators, yet capture more slowly
partly (performance only)
partly
CQL predators coordinate no more than IQL predators
not supported
not supported
joint-execution CQL predators score higher than CQL predators on the coordination measures when the prey are faster
supported
supported
Table 3. Predictions on the 5 × 5 grid, fixed before measurement, and their verdicts. Scored with 10% random moves, as in training, and checked with best moves only. A prediction is refuted when the opposite direction passes our rule.
Figure 2. 5 × 5 coordination measures, four pairings (predators against prey) in six settings, as differences from random predators facing the same trained prey; the pair measure is zero for independent hunters. Red: above; blue: below. Dots mark cells that pass our rule (Section 4 ) in either direction, with Holm correction over the 24 cells.
Contrast
Mean [95% CI]
Seeds
p
Catching together, largest cell
+0.42 [0.38, 0.45]
10/10
.047
Pair’s gain, faster predators a
+0.009 [0.005, 0.013]
10/10
.047
Pair’s gain, faster prey a
+0.023 [0.014, 0.032]
10/10
.047
Catching together, CQL − IQL
− 0.05 to − 0.21
≥ 9/10
.023
Joint execution − CQL, pair’s gain b
+0.035 [0.030, 0.040]
10/10
.004
Joint execution − CQL, catching b
+0.034 [ − 0.010, 0.079]
8/10
.21
Table 4. Coordination effect sizes (5 × 5 unless noted): mean paired difference over 10 seeds [95% CI], seeds in its direction, Holm-corrected Wilcoxon p . Shares are excess over random predators.
8 × 8
5 × 5
Setting
usual
matched
usual
matched
Equal speed
+5.5 ∗
− 5.6 ∗
+7.2 ∗
+7.6 ∗
Equal speed, limited stamina
+6.4 ∗
− 10.9 ∗
+1.6 ∗
+3.0 ∗
Faster predators
+8.4 ∗
+0.4
− 5.5
− 4.2
Faster predators, limited stamina
+6.2 ∗
− 5.8 ∗
− 9.1 ∗
− 8.3 ∗
Faster prey
+0.2
− 6.2 ∗
− 1.6
− 0.5
Table 5. Self-play capture time, CQL minus IQL, in steps (positive: CQL slower). IQL breaks ties by the first action (usual) or at random, as CQL does (matched). ∗ : significant after Holm correction over the six settings (10 seeds, paired by seed).
Centralized training with decentralized execution (CTDE) has become the dominant paradigm in multi-agent reinforcement learning (MARL), motivating extensive study of what privileged information should be made available to the critic during training. While prior work has examined the role of global state in fully cooperative settings, the design of centralized critics for N-agent ad hoc teamwork - in which dynamically varying set of learning agents must coordinate with an arbitrary set of uncontrolled teammates drawn from an unknown distribution - remains poorly understood. We study this question by comparing two natural classes of advantage estimators: controlled history estimators, which condition only on the observation and action histories of the learner's own agents, and joint history estimators, which additionally condition on the histories of the uncontrolled teammates. We prove that both estimators are unbiased and characterize the conditions under which the joint history estimate attains strictly lower variance than its controlled counterpart. Empirically, joint history critics match or outperform controlled history critics across a range of NAHT tasks, yielding improved sample efficiency and final returns. Together, these results provide both a theoretical justification and an empirical recommendation for incorporating uncontrolled agent histories into centralized critics for N-agent ad hoc teamwork.
Cooperative multi-agent reinforcement learning (MARL) benchmarks commonly emphasize aggregate outcomes such as return, success rate, or completion time. While essential, these metrics can obscure how agents coordinate and fail to distinguish policies that achieve similar outcomes through different interaction processes. We propose a process-aware evaluation framework that complements aggregate performance with diagnostics of interference, coordinated task completion, participation, and coordination efficiency. We evaluate the framework in STAT, a controlled spatial task-allocation testbed, and examine its broader applicability in two established cooperative MARL benchmarks. Across diverse value-based and actor-critic methods, we find policies with nearly identical return can exhibit substantial differences in coordination behavior. Controlled scaling in STAT reveals distinct process signatures for spatial, task, and agent scaling, while a reward-shaping ablation shows that explicitly penalizing assignment conflicts can alter coordination behavior with little change in task return. Results in the established benchmarks further show that the framework remains informative under different coordination mechanisms. These findings support process-aware evaluation as a complement to outcome-based benchmarking. The framework provides a common structure for selecting and interpreting environment-specific diagnostics that characterize not only what cooperative policies achieve, but how they coordinate to achieve it.
Constrained Multi-agent reinforcement learning (CMARL) faces two intertwined challenges: the joint action space grows exponentially with the number of agents, and additional requirements couple agents in ways that reward structure alone does not capture. We introduce Coordination Graphs for Constrained Multi-Agent Reinforcement Learning (CG-CMARL), a framework that addresses both challenges by combining coordination graphs with Lagrangian duality. The system decomposes the joint problem into pairwise regions, each served by a set of shared Q-functions, one for the primary objective and one for each of the constraints, so that the number of learned models is independent of the number of agents. At execution time, Max-Sum message passing coordinates actions across the factor graph, while a Lagrangian multiplier controls the objective--constraint tradeoff, allowing a single trained model to trace a Pareto front without retraining. We provide convergence guarantees under mild conditions, together with a compositional error bound that decomposes into separate interpretable sources, each traceable to a specific design choice and independently controllable. Experiments on cooperative navigation tasks (where teams of up to 10 agents must coordinate to reach target positions while satisfying pairwise constraints) show that our method produces Pareto fronts dominating established baselines trained at fixed reward-shaping ratios, while scaling to team sizes where centralized approaches become intractable.
Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders Jonsson
Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain