Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling

Emile Anand; Ishani Karmarkar

cs.MAMar 4, 2026

Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling

Authors: Emile Anand, Ishani Karmarkar

Organizations: Georgia Institute of Technology, Atlanta, GA · Stanford University, Palo Alto, CA

Abstract

Many large-scale platforms and networked control systems have a centralized decision maker interacting with a massive population of agents under strict observability constraints. Motivated by such applications, we study a cooperative Markov game with a global agent and $n$ homogeneous local agents in a communication-constrained regime, where the global agent only observes a subset of $k$ local agent states per time step. We propose an alternating learning framework $(\texttt{ALTERNATING-MARL})$ , where the global agent performs subsampled mean-field $Q$ -learning against a fixed local policy, and local agents update by optimizing in an induced MDP. We prove that these approximate best-response dynamics converge to an $\widetilde{O}(1/\sqrt{k})$ -approximate Nash Equilibrium, while separating the sample complexities between the joint state and action spaces. Finally, we validate our results in numerical simulations for multi-robot control.

Figures & tables

Panel of Figure 1 — Figure 1: (Left) Robot Coordination. This figure illustrates how our communication-constrained framework can be applied for decentralized coordination of large teams of robots. (Right) Subsampling with alternating best-response dynamics. AI was used to refine the aesthetics of the figures.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Notation	Meaning
$\\|\cdot\\|_{1}$	$\ell_{1}$ (Manhattan) norm;
$\\|\cdot\\|_{\infty}$	$\ell_{\infty}$ norm;
$\mathbb{Z}_{+}$	The set of strictly positive integers;
$\mathbb{R}^{d}$	The set of $d$ -dimensional reals;
$[m]$	The set $\{1,\dots,m\}$ , where $m\in\mathbb{Z}_{+}$ ;
${[m]\choose k}$	The set of $k$ -sized subsets of $\{1,\dots,m\}$ ;

Appendix

Table 1: Important notations in this paper.

Figure 2: The alternating best-response dynamics, which repeat until convergence. In it, the global agent does a best-response update, treating the policy representative $\pi_{\ell}$ fixed, and then the local agent representative does a best-response update, treating the global agent’s policy $\pi_{g}$ as fixed. We note that generative AI was used to refine the aesthetics of this figure.

|p-p^{\prime}|\leq\min\left(\sqrt{\frac{1}{2n}\ln(6/\delta_{1})},\sqrt{\frac{2p(1-p)}{n}\ln(6/\delta_{1})}+\frac{7}{3(n-1)}\ln\frac{6}{\delta_{1}}\right)\bigg\}

Appendix

Algorithm 5 UCFH : U pper- C onfidence F ixed- H orizon (UCFH) episodic RL algorithm from [ 33 ]

Figure 3: Construction of the $k$ -chained MDP from 21 . In this construction, along the chain of micro nodes, only one local replica is “active” at a time. At stage $j$ , the learner selects a single action $a_{\ell}\in\mathcal{A}_{l}$ , interpreted as the action for replica $j$ . The environment updates only that replica via $s_{j}^{\prime}\sim P_{l}(\cdot|s_{j},s_{g},a_{\ell})$ leaving the other $k-1$ local replica states unchanged. Next, the stage pointer increments $j\leftarrow j+1$ . At the end of the chain (stage $j=k$ ), we commit the cached global transition by setting $s_{g}\leftarrow\bar{s}_{g}$ and resetting $\bar{S}_{g}\leftarrow\perp$ , completing one macro step.

Figure 4: Construction of the $|\mathcal{S}_{l}|$ -chained MDP construction from 28 . In this parameterization, each macro step is unfolded into $|\mathcal{S}_{l}|+1$ micro steps. At micro step $j=0$ , we evaluate the global agent’s mean-field policy on the population and cache its resulting pending transition. Then, for the tagged local agent, we apply the action to the tagged agent $s_{\ell}$ and collect its reward. Next, for micro-steps $j=1,\dots,|\mathcal{S}_{l}|$ , we sweep through each local state-bin $u=j$ . If $h(u)$ agents occupy bin $u$ , we apply the shared local action for state $u$ and move the entire mass $h(u)$ to next states according to the multinomial induced by $P_{l}(\cdot|u,s_{g},a)$ , accumulating these counts in a new histogram $\bar{F}_{\Delta}$ . After processing all bins, we commit $(s_{g},s_{\ell},F_{\Delta})\leftarrow(\bar{s}_{g},\bar{s}_{\ell},\bar{F}_{\Delta})$ and repeat.

Panel of Figure 5 — Figure 5: Decision rule for consecutive best-response iterates using the progress statistic $\Delta_{k}=V^{\pi_{g}^{\prime},\pi_{\ell}^{\prime}}-V^{\pi_{g},\pi_{\ell}}$ . The middle region $|\Delta_{k}|\leq 2\eta$ triggers stopping and provides a $2\eta$ -approximate Nash certificate.

\hat{\pi}_{k,m}^{\mathrm{est}}(s_{g},s_{\Delta})=\mathop{\argmax}_{a_{g}\in\mathcal{A}_{g}}\hat{Q}_{k,m}^{T}(s_{g},s_{\Delta},a_{g}).

Appendix

Algorithm 10 ALTERNATING-MARL : Learning with Stochastic Rewards

Hyperparameter	Value
Population size ( $n$ )	1000
Discount Factor ( $\gamma$ )	0.95
Global agent state space size ( $\|\mathcal{S}_{g}\|$ )	5
Local agent state space size ( $\|\mathcal{S}_{l}\|$ )	5
Global agent action space size ( $\|\mathcal{A}_{g}\|$ )	5
Local agent action space size ( $\|\mathcal{A}_{l}\|$ )	3

Appendix

Table 3: ALTERNATING-MARL Training and Evaluation Configuration

Panel of Figure 6 — Figure 6: a) Discounted cumulative rewards for $k<n=1000$ . As $k$ increases, the rewards generally increase and converge, b) As $k$ increases, the runtime required to converge to a $\tilde{O}(1/\sqrt{k})$ -approximate Nash Equilibrium blows up. For some values of $k$ , the runtime is significantly shorter since ALTERNATING-MARL learns a policy before $N_{\text{steps}}$ iterations, and terminates early.

Figure 7: Simulation of the multi-agent warehouse system for subsampling budgets $k=1,10,20,35$ . The heatmap shows the fraction of $n=1000$ robots occupying each of the $5$ zones at each timestep, where darker shades imply a higher concentration. The solid blue line indicates the zone chosen by the dispatcher (global agent), while the dashed black line shows the true population mode (the zone with the most robots). At $k=1$ , the dispatcher’s choices differ significantly from the true mode, while at $k=35$ , the dispatcher tracks the mode substantially better, steering resources to the correct zone more than twice as often. The initial agent positions are drawn from $\mathsf{Dirichlet}(0.3)$ , creating a concentrated starting configuration, and all panels share the same random seed for comparability.

Figure 8: Discounted Cumulative Rewards for $k<n=500$ for continuous state spaces. We include a baseline of uniformly random actions.

\mathcal{L}_{g}=-\frac{1}{M}\sum_{i=1}^{M}\log\pi_{g}(m_{i}^{*}|h_{i}),

Appendix

Algorithm 11 ALTERNATING-MARL Heuristic with Function Approximation

Hyperparameter	Value
Population size ( $n$ )	500
Discount Factor ( $\gamma$ )	0.95
Global agent action space size ( $\|\mathcal{A}_{g}\|$ )	5
Local agent action space size ( $\|\mathcal{A}_{l}\|$ )	3
Steering gain ( $\alpha$ )	$0.6$
State clipping range	$[-2,2]$

Appendix

Table 4: ALTERNATING-MARL Heuristic Training and Evaluation Configuration

Figure 9: Dispatcher accuracy in the continuous state space setting

Figure 10: Simulation of the multi-agent warehouse for subsampling budgets $k=1,10,35,75$ , where the heatmap shows the fraction of $N=500$ robots occupying the various zones at each timestep where darker colors imply a higher concentration.

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,661 papers

Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning
Feb 18, 2026Emile Anand, Richard Hoffmann, Sarah Liaw +1Reinforcement Learning Cooperative MARL
School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA · Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA · Kempner Institute, Harvard University, Cambridge, MA, USA
NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning
Mar 7, 2026Addison Kalanther, Sanika Bharvirkar, Shankar Sastry +1Multi-Agent Reinforcement Learning Game-Theoretic RL
Electrical Engineering and Computer Sciences, UC Berkeley · Electrical and Computer Engineering, Data Science & Artificial Intelligence Institute, Johns Hopkins University
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

Feb 18, 2026J/K move · Enter open · S save

Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning

Emile Anand, Richard Hoffmann, Sarah Liaw, Adam Wierman

School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA · Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA · Kempner Institute, Harvard University, Cambridge, MA, USA

Reinforcement Learning Cooperative MARL Heterogeneous MARL Multi-Agent Coordination

Open paper AskPDF arXiv

Coordinating large populations of interacting agents is a central challenge in multi-agent reinforcement learning (MARL), where the size of the joint state-action space scales exponentially with the number of agents. Mean-field methods alleviate this burden by aggregating agent interactions, but these approaches assume homogeneous interactions. Recent graphon-based frameworks capture heterogeneity, but are computationally expensive as the number of agents grows. Therefore, we introduce

\texttt{GMFS}

, a

\textbf{G}

raphon

\textbf{M}

ean-

\textbf{F}

ield

\textbf{S}

ubsampling framework for scalable cooperative MARL with heterogeneous agent interactions. By subsampling

κ

agents according to interaction strength, we approximate the graphon-weighted mean-field and learn a policy with sample complexity

\mathrm{poly}(κ)

and optimality gap

O(1/\sqrtκ)

. We verify our theory with numerical simulations in robotic coordination, showing that

\texttt{GMFS}

achieves near-optimal performance.

Abstract

Reinforcement Learning

Explore similar work

Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning

NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning

Multi-Agent Reinforcement Learning with Submodular Reward