Multi-agent reinforcement learning (MARL) methods have achieved state-of-the-art results on a range of multi-agent tasks. Yet, MARL algorithms typically require significantly more environment interactions than their single-agent counterparts to converge, a problem exacerbated by the difficulty in exploring over a large joint action space and the high variance intrinsic to MARL environments. To tackle these issues, we propose a novel algorithm that combines a decomposed centralized critic with decentralized ensemble learning, incorporating several key contributions. The main component in our scheme is a selective exploration method that leverages ensemble kurtosis. We extend the global decomposed critic with a diversity-regularized ensemble of individual critics and utilize its excess kurtosis to guide exploration toward high-uncertainty states and actions. To improve sample efficiency, we train the centralized critic with a novel truncated variation of the TD(λ) algorithm, enabling efficient off-policy learning with reduced variance. On the actor side, our suggested algorithm adapts the mixed samples approach to MARL, mixing on-policy and off-policy loss functions for training the actors. This approach balances between stability and efficiency and outperforms purely off-policy learning. The evaluation shows our method outperforms state-of-the-art baselines on standard MARL benchmarks, including a variety of SMAC II maps.
Figures & tables
Figure 1: Ensemble MIX architecture: (1) Each agent’s critic is an ensemble of N sub-critics. (2) The ensemble kurtosis utilized for selective exploration during action selection. (3) The backbone follows DOP with retrace instead of TB.
Method
Backbone
Exploration signal
MAVEN
VD
mutual information
PAC
MAPG
entropy
FOX
VD
mutual information
CMAE
VD
goal / entropy
EMC
VD
curiosity
SUNRISE
SAC
variance & Q-learning
Table 1: Positioning of Ensemble MIX versus existing baselines for exploration in single-agent and MARL.
Figure 3
Figure 3: Analysis of aleatoric noise and ensembles on the multi-taxi environment. (a) 8×8 multi-taxi environment illustration. (b-c) Common ensemble measurements on a heatmap that represent values on the grid. (d) The reward thorough training with different exploration methods (e) Increasing the number of agents with effect on ensemble disagreement.
Ensemble MIX, smaller ensemble ( N=5 )
Ensemble MIX, without retrace
No exploration ( β=0 )
Ensemble MIX with variance exploration
Original, all components (with exploration)
1c3s5z
0.63±0.06
0.79±0.04
0.88±0.02
0.82±0.01
0.96±0.00
MMM2
0.67±0.08
0.77±0.06
0.83±0.05
0.8±0.04
0.94±0.04
MMM3
0.68±0.04
0.69±0.03
0.75±0.05
0.69±0.03
0.82±0.03
MACF
0.64±0.04
0.66±0.03
0.72±0.05
0.71±0.03
0.82±0.03
Table 3: Ablation and analysis. The leftmost and second columns show the performances with a smaller ensemble. In the third column, we add the ensemble with no exploration. The fourth is an ensemble mix with variance-based exploration.
Figure 4: (a): Win rates on six (regular-reward) SMAC maps. (b): Win rates on six sparse reward maps. Sparse reward structure is similar to previous works and is given in the Appendix C.
Figure 5: Returns and win rates on predator-prey, MACF, and the two-corridors (SMAC) map.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Algorithm Parameters
HyperParameters
Value
T (train interval)
20K
U (num test episodes)
24
C1
0.01
C2
0.001
β
0.001
Appendix
Table 4: Hyperparameter Table - SMAC
Figure 6: Parameter analysis on MMM2 and MMM3 maps for c,β,C1 , and ensemble sizes. Ablations on the Bhattacharyya distance and our version of TD( λ ) versus retrace( λ ) are presented in the bottom graphs.
Cooperative multi-agent reinforcement learning (MARL) involves complex agent interactions and requires effective exploration strategies. A prominent class of MARL algorithms, decentralized softmax policy gradient (DecSPG), addresses this through energy-based policy updates. In practice, however, such energy-based policies are intractable to maintain and are commonly projected onto the Gaussian policy class. In this work, we show that the limited expressiveness of Gaussian policies severely hinders exploration in DecSPG, and this limitation worsens as the number of agents grows. To address this issue, we propose decentralized diffusion policy learning (DDPL), which parameterizes each agent's policy with a denoising diffusion probabilistic model, an expressive generative model that captures multi-modal action distributions for enhanced exploration. DDPL enables efficient online training of diffusion policies via importance sampling score matching (ISSM), a novel training method with theoretical guarantee. We evaluate DDPL on representative continuous-action MARL benchmarks, including multi-agent particle environment, multi-agent MuJoCo, IsaacLab, and JAX-reimplemented StarCraft multi-agent challenge, and observe consistently improved performance.
Multi-agent reinforcement learning (MARL) holds great potential but faces robustness challenges due to environmental uncertainty. To address this, distributionally robust Markov games (RMGs) optimize worst-case performance when the environment deviates from the nominal model within a uncertainty set. Beyond robustness, an equally urgent goal for MARL is data efficiency -- sampling from vast state and action spaces that grow exponentially with the number of agents potentially leads to the curse of multiagency. However, current provably data-efficient algorithms for RMGs are limited to tabular settings with finite state and action spaces, which are only computationally manageable for small-scale problems, leaving RMGs with large-scale (or infinite) state spaces largely unexplored. The only existing work beyond tabular settings focuses on linear function approximation (LFA) for a restrictive class of RMGs using vanish minimal value assumption and still suffers from sample complexity with the curse of multiagency. In this work, we focuses on general RMGs with LFA. For uncertainty sets defined by total variation distance, we develop provably data-efficient algorithms that break the curse of multiagency in both the generative model setting and a newly proposed online interactive setting. To our knowledge, our results are the first to break the curse of multiagency of sample complexity for RMGs with large (possibly infinite) state spaces, regardless of the uncertainty set construction.
Jingchu Gai, Laixi Shi
Machine Learning Department, Carnegie Mellon University. · Department of Electrical and Computer Engineering, Johns Hopkins University, MD 21286, USA.
In this paper, we study cooperative multi-agent reinforcement learning (MARL) where the joint reward exhibits submodularity, which is a natural property capturing diminishing marginal returns when adding agents to a team. Unlike standard MARL with additive rewards, submodular rewards model realistic scenarios where agent contributions overlap (e.g., multi-drone surveillance, collaborative exploration). We provide the first formal framework for this setting and develop algorithms with provable guarantees on sample efficiency and regret bound. For known dynamics, our greedy policy optimization achieves a 1/2-approximation with polynomial complexity in the number of agents K, overcoming the exponential curse of dimensionality inherent in joint policy optimization. For unknown dynamics, we propose a UCB-based learning algorithm achieving a 1/2-regret of O(H2KSAT) over T episodes.
Wenjing Chen, Chengyuan Qian, Shuo Xing +2
Department of Computer Science and Engineering, Texas A&M University