Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning

Shan Yang; Yang Liu

cs.MAFeb 23, 2026

Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning

Authors: Shan Yang, Yang Liu

Organizations: National University of Singapore

Abstract

Scaling cooperative multi-agent reinforcement learning (MARL) is fundamentally limited by cross-agent noise. When agents share a common reward, each agent's learning signal is computed from a shared return that depends on all agents, so the stochasticity of the other agents enters the signal as cross-agent noise that grows with $N$ . Many engineering systems, such as cloud computing and power systems, have differentiable analytical models that prescribe efficient system states, providing a new reference beyond noisy shared returns. In this work, we propose Descent-Guided Policy Gradient (DG-PG), a framework that augments policy-gradient updates with a low-noise descent signal toward this reference. We prove that DG-PG reduces policy-gradient estimator variance from $\mathcal{O}(N)$ to $\mathcal{O}(1)$ , preserves the stationary points of the cooperative objective, and achieves agent-independent sample complexity $\mathcal{O}(1/ε^3)$ . We evaluate DG-PG on cloud resource scheduling and power dispatch tasks, which involve discrete and continuous decisions, respectively. In both tasks, DG-PG converges within 10 episodes on average at every scale up to 1500 heterogeneous agents.

Figures & tables

Figure 1: (a) Gradient variance scaling. (b) Guidance weight sensitivity.

Figure 2: Training reward under the controlled comparison at

N\in\{2,5,10\}

Figure 3: Scalability and convergence.

Cloud scheduling	$N{=}10$	$N{=}20$	$N{=}50$	$N{=}100$	$N{=}200$	$N{=}500$	$N{=}1000$	$N{=}1500$
DG-PG (ours)	$-13.19{\pm}0.14$	$-12.49{\pm}0.10$	$-11.13{\pm}0.03$	$-10.84{\pm}0.02$	$\mathbf{-10.51{\pm}0.11}$	$\mathbf{-10.52{\pm}0.06}$	$\mathbf{-10.36{\pm}0.08}$	$\mathbf{-10.41{\pm}0.02}$
Best-Fit	$\mathbf{-12.15}$	$\mathbf{-11.58}$	$\mathbf{-10.88}$	$\mathbf{-10.77}$	$-10.58$	$-10.66$	$-10.55$	$-10.66$
Random Dispatch	$-50.82$	$-52.85$	$-37.98$	$-33.04$	$-32.40$	$-30.32$	$-29.49$	$-29.01$
Power dispatch	$N{=}10$	$N{=}20$	$N{=}50$	$N{=}100$	$N{=}200$	$N{=}500$	$N{=}1000$	$N{=}1500$
DG-PG (ours)	$\mathbf{-13.99{\pm}1.34}$	$\mathbf{-14.49{\pm}1.21}$	$\mathbf{-14.35{\pm}1.20}$	$\mathbf{-16.30{\pm}1.85}$	$\mathbf{-14.72{\pm}0.79}$	$\mathbf{-16.24{\pm}1.05}$	$\mathbf{-16.92{\pm}1.01}$	$\mathbf{-13.83{\pm}0.81}$
Centralized greedy	$-19.66$	$-19.97$	$-18.40$	$-18.02$	$-17.70$	$-18.10$	$-18.11$	$-18.15$

Table 1: Test reward across scales. DG-PG reports mean

\pm

std over training seeds.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Result	Bounded Increments (Asm. 4.1 )	Exogeneity (Asm. 4.2 )	Alignment (Asm. 4.3 )	Smoothness & GD (Asm. G.1 )	Role of Assumptions
Thm. 5.1 (Stationary Points)		✓	✓		Exogeneity ensures reference does not shift; Alignment ensures guidance gradient vanishes at stationary points.
Thm. 5.2 (Variance Bound)	✓	✓	✓		Bounded increments yield $\mathcal{O}(1)$ guidance variance; Exogeneity makes reference deterministic; Alignment ensures negative correlation $\rho<0$ .
Thm. 5.3 (Sample Complexity)	✓	✓	✓	✓	Smoothness enables the per-iteration bound; gradient domination yields the optimality-gap recursion; $\mathcal{O}(1)$ variance from Thm. 5.2 .
Prop. 1 in App. C.3 (Cloud Verification)					Standalone verification that Alignment holds for cloud scheduling via Cauchy-Schwarz on the load imbalance functional.

Appendix

Table 3: Dependency of theoretical results on assumptions. “✓” indicates that the result requires the corresponding assumption. All assumptions are stated in the main text (Section 4.1 ) and Appendix G .

Gen.	Instance Type	vCPUs	Memory (GB)	$\eta_{\text{CPU}}$	$\eta_{\text{Mem}}$	Weight
Gen-1	m4.8xlarge	32	128	0.70	0.68	10%
	t3.2xlarge	16	64	0.72	0.70	3%
	t3a.2xlarge	16	64	0.75	0.72	2%
Gen-2	m5.8xlarge	32	128	0.95	0.93	20%
	c5.18xlarge	64	128	0.98	0.93	10%
	c5.12xlarge	48	96	0.97	0.93	8%

Appendix

Table 4: Server instance types used in the simulation, based on AWS instance configurations.

Figure 4: Environment characteristics. (a) Bimodal workloads with heavy-tailed demands. (b) Server heterogeneity across hardware generations. (c) Non-stationary arrivals with tidal fluctuation.

Servers ( $N$ )	Clusters ( $K$ )	Servers/Cluster ( $S$ )	Episode Length	Target Util. ( $\rho$ )
2	2	1	3000	$[0.80,0.85]$
5	5	1	3000	$[0.80,0.85]$
10	10	1	3000	$[0.80,0.85]$
20	20	1	3000	$[0.80,0.85]$
50	25	2	3000	$[0.80,0.85]$
100	25	4	3000	$[0.80,0.85]$

Appendix

Table 5: Scale configurations used in the experimental evaluation.

Parameter	Value
Model class	Linear (single layer, no hidden units)
Learning rate	$1\times 10^{-3}$ (linear decay to $1\%$ )
PPO clipping $\epsilon$	$0.2$
Critic epochs / Actor epochs	20 / 3 (split-epoch)
Mini-batch size	10,000
Gradient clipping	max norm $10.0$

Appendix

Table 6: Hyperparameters for controlled comparison (Section 6.3 ).

Servers ( $N$ )	Hidden Dimension	Mini-batch	Rollouts	Parallel Environments	PPO Clip ( $\epsilon$ )	Active Samples
10	128	512	12	4	0.2	$\sim 120{,}000$
20	128	512	12	4	0.2	$\sim 240{,}000$
50	256	1024	8	4	0.4	$\sim 400{,}000$
100	512	1024	6	2	0.4	$440{,}000$ (cap)
200	1024	1024	2	1	0.4	$440{,}000$ (cap)
500	1024	1024	1	1	0.4	$440{,}000$ (cap)

Appendix

Table 7: Scale-specific hyperparameters.

Run	Key Change	Mini-batch	PPO Epochs	$c_{\text{ent}}$	Observed Failure
0	DG-PG defaults	256	4	0.02 (decay)	Entropy collapse ( $1.59\to 0.26$ )
1	+ValueNorm	256	10	0.01	Entropy collapse ( $1.60\to 0.88$ )
2	$K$ : $10\to 4$	256	4	0.01	Slow entropy collapse ( $1.54\to 1.36$ )
3	$c_{\text{ent}}$ : $0.01\to 0.03$	256	4	0.03	Entropy bonus drowns advantage
4	Align with MAPPO defaults	50,000	10	0.01	Critic too slow (explained variance $\leq 0.30$ )
5	Batch: $50\text{K}\to 20\text{K}$	20,000	15	0.01	Critic still insufficient

Appendix

Table 8: Representative MAPPO runs with neural-network actor and critic models at

N{=}5

	Cloud scheduling			Power dispatch
$N$	Episode	Time	Per-Episode	Episode	Time	Per-Episode
10	5.4	0.9 min	10.5 s	6.2	2.8 min	26.8 s
20	5.8	1.8 min	18.9 s	8.2	4.4 min	31.9 s
50	5.0	3.4 min	40.9 s	8.2	6.9 min	50.2 s
100	4.0	9.6 min	2.4 min	9.0	12.7 min	1.4 min
200	4.3	18.2 min	4.2 min	2.7	6.6 min	2.5 min

Appendix

Table 9: DG-PG convergence episode, convergence time, and per-episode training time (CPU-only).

Cooperative MARL

Cooperative multi-agent reinforcement learning (MARL) trains agents to coordinate toward shared goals under partial information and decentralized control.

See all 234 papers

Decentralized Diffusion Policy Learning for Enhanced Exploration in Cooperative Multi-agent Reinforcement Learning
May 8, 2026Yuyang Zhang, Haldun Balim, Na LiDiffusion Policy Decentralized MARL
SEAS, Harvard University
ACPO: Agent-Chained Policy Optimization for Multi-Agent Reinforcement Learning
Jun 29, 2026Daiki E. Matsunaga, Junho Na, Tri Wahyu Guntara +4Multi-Agent System Optimization Multi-Agent Coordination
1KAIST · 2KRAFTON · University of Toronto +2
Multi-Agent Reinforcement Learning with Submodular Reward
Mar 6, 2026Wenjing Chen, Chengyuan Qian, Shuo Xing +2Cooperative MARL Multi-Agent Reinforcement Learning
Department of Computer Science and Engineering, Texas A&M University

May 8, 2026J/K move · Enter open · S save

Decentralized Diffusion Policy Learning for Enhanced Exploration in Cooperative Multi-agent Reinforcement Learning

Yuyang Zhang, Haldun Balim, Na Li

SEAS, Harvard University

Diffusion Policy Decentralized MARL Cooperative MARL Multi-Agent Reinforcement Learning

Open paper AskPDF arXiv

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.

Abstract

Cooperative MARL

Explore similar work

Decentralized Diffusion Policy Learning for Enhanced Exploration in Cooperative Multi-agent Reinforcement Learning

ACPO: Agent-Chained Policy Optimization for Multi-Agent Reinforcement Learning

Multi-Agent Reinforcement Learning with Submodular Reward