Abstract
Cooperative multi-agent reinforcement learning (MARL) commonly adopts centralized training with decentralized execution (CTDE), where centralized critics leverage global information to guide decentralized actors. However, centralized-decentralized mismatch (CDM) arises when the suboptimal behavior of one agent degrades others' learning. Prior approaches mitigate CDM through value decomposition, but linear decompositions allow per-agent gradients at the cost of limited expressiveness, while nonlinear decompositions improve representation but require centralized gradients, reintroducing CDM. To overcome this trade-off, we propose the multi-agent cross-entropy method (MCEM), combined with monotonic nonlinear critic decomposition (NCD). MCEM updates policies by increasing the probability of high-value joint actions, thereby excluding suboptimal behaviors. For sample efficiency, we extend off-policy learning with a modified k-step return and Retrace. Analysis and experiments demonstrate that MCEM outperforms state-of-the-art methods across both continuous and discrete action benchmarks.
Introduction
In cooperative Multi-Agent Reinforcement Learning (MARL), the standard paradigm is Centralized Training with Decentralized Execution (CTDE). While agents act independently during execution, they are trained together using global state information. A significant challenge in this setup is Centralized-Decentralized Mismatch (CDM). In a typical centralized critic architecture, a single agent's suboptimal "blunder" can result in a low team reward, which then "pollutes" the gradients for all agents. This makes it difficult for high-performing agents to distinguish their positive contributions from the noise of their teammates' errors.
Existing solutions generally fall into two categories: linear value decomposition, which isolates gradients but lacks the expressiveness to model complex interactions, and nonlinear decomposition, which offers high representational power but relies on centralized gradients that reintroduce the CDM problem.
Methodology: MCEM-NCD
The proposed MCEM-NCD framework bridges this gap by combining a sampling-based optimization method with a powerful nonlinear critic.
Multi-agent Cross-Entropy Method (MCEM)
Instead of relying on standard policy gradients, MCEM utilizes a sampling-based approach. The algorithm samples a batch of potential joint actions and performs "Elite Selection," where only the top-performing actions (the top $1-\rho$ quantile) are used to update the policies. This mechanism naturally filters out suboptimal behaviors, ensuring that "blunders" do not degrade the learning signal for the rest of the team.
Monotonic Nonlinear Critic Decomposition (NCD)
To evaluate sampled actions, the framework employs a nonlinear mixing network. This network combines individual agent evaluations into a total team score. A monotonicity constraint is enforced: if an individual agent's performance improves, the total team score must also increase. This ensures that individual improvements are correctly reflected in the global objective.
Off-Policy Efficiency and Versatility
To improve sample efficiency, MCEM-NCD incorporates a modified $k$-step return combined with the Retrace algorithm. This allows for stable off-policy learning even with a complex nonlinear critic. Furthermore, unlike many value-based methods restricted to discrete actions, MCEM-NCD is versatile enough to support both discrete and continuous action spaces.
Experimental Results
The researchers evaluated MCEM-NCD on two major benchmarks: the StarCraft Multi-Agent Challenge (SMAC) for discrete actions and a Continuous Predator-Prey environment.
Performance on SMAC
In the SMAC benchmark, MCEM-NCD was tested against state-of-the-art methods including LICA, FACMAC, and DOP across 9 scenarios. The results demonstrate that MCEM-NCD consistently achieves higher win rates and faster convergence. Notably, in "Super Hard" maps like corridor and 6h_vs_8z, where baseline methods often struggle to achieve any wins, MCEM-NCD maintains robust performance.
Continuous Control and Robustness
In Predator-Prey environments, the method achieved higher mean episode returns than existing continuous MARL algorithms. Across all tests, MCEM-NCD exhibited lower variance across different random seeds, indicating superior training stability compared to traditional gradient-based approaches.
Conclusion
MCEM-NCD effectively addresses the Centralized-Decentralized Mismatch by replacing direct centralized gradients with a sampling-based "Elite Selection" process. By combining this with a monotonic nonlinear critic, the framework achieves high representational power without sacrificing learning stability. While the method introduces some sampling overhead, its performance on complex, "Super Hard" tasks suggests it is a powerful tool for coordinating large-scale multi-agent systems. Future research will focus on optimizing sampling efficiency and exploring adaptive selection thresholds.
Summary updated