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

Feb 18, 2026

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

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.

Emile Anand, Richard Hoffmann, Sarah Liaw +1

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

Ask PDF

Mar 7, 2026

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

Multi-agent reinforcement learning (MARL) is increasingly used to design learning-enabled agents that interact in shared environments. However, training MARL algorithms in general-sum games remains challenging: learning dynamics can become unstable, and convergence guarantees typically hold only in restricted settings such as two-player zero-sum or fully cooperative games. Moreover, when agents have heterogeneous and potentially conflicting preferences, it is unclear what system-level objective should guide learning. In this paper, we propose a new MARL pipeline called Near-Potential Policy Optimization (NePPO) for computing approximate Nash equilibria in mixed cooperative--competitive environments. The core idea is to learn a player-independent potential function such that the Nash equilibrium of a cooperative game with this potential as the common utility approximates a Nash equilibrium of the original game. To this end, we introduce a novel MARL objective such that minimizing this objective yields the best possible potential function candidate and consequently an approximate Nash equilibrium of the original game. We develop an algorithmic pipeline that minimizes this objective using zeroth-order gradient descent and returns an approximate Nash equilibrium policy. We empirically show the superior performance of this approach compared to popular baselines such as IPPO and MAPPO.

Addison Kalanther, Sanika Bharvirkar, Shankar Sastry +1

Electrical Engineering and Computer Sciences, UC Berkeley · Electrical and Computer Engineering, Data Science & Artificial Intelligence Institute, Johns Hopkins University

Multi-Agent Reinforcement Learning Game-Theoretic RL Nash Equilibrium Computation Potential Games

Ask PDF

Mar 6, 2026

Multi-Agent Reinforcement Learning with Submodular Reward

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(H^2KS\sqrt{AT})

over

T

episodes.

Wenjing Chen, Chengyuan Qian, Shuo Xing +2

Department of Computer Science and Engineering, Texas A&M University

Cooperative MARL Multi-Agent Reinforcement Learning Submodular Optimization

Ask PDF

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