TL;DR
The authors introduce MCEM-NCD, a cooperative multi-agent reinforcement learning (MARL) framework that resolves the dilemma between critic expressiveness and credit assignment. By replacing centralized policy gradients with a multi-agent Cross-Entropy Method (MCEM) over a monotonic nonlinear critic (NCD), it prevents one agent's blunders from poisoning others' policy updates while retaining high representational power across both discrete and continuous action domains.
What Problem Does This Paper Address?
In cooperative MARL under the Centralized Training with Decentralized Execution (CTDE) paradigm, agents use centralized critic networks during training to evaluate joint behavior, but must act independently during execution. A persistent challenge is Centralized-Decentralized Mismatch (CDM): when a single agent makes a suboptimal blunder, the entire team's joint action-value ($Q_{tot}$) plummets. In standard actor-critic methods, backpropagating this centralized gradient unfairly penalizes all agents—even those executing optimal actions.
Prior attempts to mitigate CDM created an undesirable trade-off:
- Linear value decomposition (e.g., DOP) decomposes $Q_{tot}$ into individual utility sums, isolating per-agent gradients and avoiding CDM, but linear critics lack representational capacity for complex coordination.
- Nonlinear value decomposition (e.g., FACMAC, VDAC-mix, LICA) enhances expressive capacity, but actor optimization requires backpropagating through a centralized gradient, reintroducing CDM.
MCEM-NCD resolves this trade-off by combining expressive, monotonic nonlinear critic decomposition with derivative-free, sample-based actor updates.
Methods
MCEM-NCD consists of three main components:
- Multi-Agent Cross-Entropy Method (MCEM): Rather than updating policies via centralized policy gradients, agents use a derivative-free stochastic optimization procedure. At each time step:
- Sampling: Candidate joint actions are sampled using auxiliary, entropy-regularized proposal policies $\hat{\pi}^a$.
- Evaluation: Candidate joint actions are scored using the monotonic nonlinear critic $Q_{tot}$.
- Elite Selection: The top $(1 - \rho)$ quantile of actions (the "elites") is selected.
- Policy Update: Main decentralized policies $\pi^a$ (and proposal policies $\hat{\pi}^a$) are updated via cross-entropy/maximum likelihood to increase the probability of producing actions from the elite set, effectively filtering out joint actions poisoned by one agent's misbehavior.
- Monotonic Nonlinear Critic Decomposition (NCD): Individual agent action-values $Q^a$ are mixed via a monotonic neural network (constrained such that $\frac{\partial Q_{tot}}{\partial Q^a} \ge 0$, adhering to the Individual-Global-Max principle).
- Off-Policy Critic Updates with Sarsa & Retrace: To avoid the intractable combinatorial expectation over joint actions required by Expected Sarsa/Tree-Backup in nonlinear settings, the authors employ an $n$-step return in Sarsa form combined with Retrace($\lambda$) importance weight truncation. This enables sample-efficient off-policy training and natively supports continuous action spaces (parameterized via Gaussian policies).
[ Decentralized Actors ] ──(Sample Proposals)──> [ Candidate Actions E(τ) ]
│
[ Monotonic Mixing (NCD) ] ──(Score & Quantile Filter)───┘
│
▼
[ Elite Actions I(τ) ] ──(Cross-Entropy Update)──> [ Policy Improvements ]
Datasets
The authors evaluated the method across two standard cooperative MARL benchmark environments (no new datasets or environments were introduced):
- StarCraft Multi-Agent Challenge (SMAC): 9 discrete-action micromanagement scenarios, featuring 4 Hard maps (
2c_vs_64zg,8m_vs_9m,3s_vs_5z,5m_vs_6m) and 5 Super Hard maps (3s5z_vs_3s6z,corridor,6h_vs_8z,MMM2,27m_vs_30m). - Continuous Predator-Prey: 3 continuous control scenarios requiring coordinate hunting among agents (
3_agents_and_1_prey,6_agents_and_2_preys, and9_agents_and_3_preys).
Key Insights and Ideas
- Eliminating Gradient-Based Sabotage: In policy gradient setups, a joint score is directly differentiated, propagating credit misallocation. By selecting elite joint actions based purely on rank, MCEM ignores suboptimal joint actions completely, insulating well-behaved agents from another agent's bad decisions.
- Guaranteed Policy Improvement (Theorem 5.1): The authors theoretically establish that the percentile-greedy policy $\pi_\rho$ is guaranteed to perform at least as well as centralized gradient policies $\pi_g$ under any history $\tau$.
- Sarsa-Retrace Bridges Continuous Non-Linear MARL: Using Retrace with Sarsa targets enables off-policy learning over nonlinear multi-agent critics without combinatorial explosions, overcoming limitations of prior linear methods that relied on Expected Sarsa.
Key Results
- SMAC (Discrete): MCEM-NCD outperformed six strong baselines (DOP, VDAC-mix, FACMAC, LICA, FOP, RIIT). On challenging asymmetric and Super Hard benchmarks (
3s5z_vs_3s6z,corridor,6h_vs_8z, andMMM2), baselines achieved low win rates, while MCEM-NCD maintained high median win rates and faster convergence. - Predator-Prey (Continuous): MCEM-NCD outperformed MADDPG and FACMAC across all settings. Performance advantages widened on larger multi-agent teams (
9_agents_and_3_preys), demonstrating robust scaling as coordination complexity intensified. - Ablations: Removing the nonlinear critic (
MCEM-NCD_linear), reverting to on-policy updates (MCEM-NCD_on-policy), or substituting Retrace with Tree-Backup (MCEM-NCD_tree-backup) each caused substantial performance drops on complex tasks.
Limitations and Future Work
- Sensitivity to Quantile Selection ($\rho$): Performance depends heavily on the percentile threshold $\rho$. Too large a $\rho$ starves the actor updates of diverse training samples, while too small a $\rho$ risks including suboptimal actions.
- Sampling Overhead: Generating, scoring, and sorting candidate joint actions at each optimization step adds computational and memory overhead relative to standard single-pass policy gradient methods.
- Empirical Scale: Experiments were conducted over three random seeds per scenario, which is standard for compute-heavy MARL benchmarks but on the lower side for statistical variance evaluation.
Summary updated