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

Abstract

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.

Method

NePPO computes approximate Nash equilibria of a general-sum Markov game by learning a single, player-independent potential function $\Phi$ and solving the cooperative game in which every player maximizes $\Phi$. If $\Phi$ reproduces the change in each player's own utility under a unilateral deviation from that cooperative equilibrium, then the cooperative solution is an approximate equilibrium of the original game.

Objective

Let $\pi^{\Phi}$ be a Nash equilibrium of the cooperative game with common utility $\Phi$, and let $\pi_i^{J}$ be player $i$'s best response to $\pi_{-i}^{\Phi}$ under its own utility $J_i$. For each player, $$F_i(\Phi) \;=\; \big[\,\Phi(\pi^{\Phi}) - \Phi(\pi_i^{J}, \pi_{-i}^{\Phi})\,\big] \;-\; \big[\,J_i(\pi^{\Phi}) - J_i(\pi_i^{J}, \pi_{-i}^{\Phi})\,\big]$$ measures the mismatch between the change in potential and the change in the player's own value along its best-response deviation. Each $F_i$ is non-negative, and if $\max_i F_i(\Phi) \le \alpha$ then $\pi^{\Phi}$ is an $\alpha$-approximate Nash equilibrium of the original game (Theorem 3.1). NePPO therefore minimizes $\max_i F_i(\Phi)$ over $\Phi$. Unlike the defining condition of a Markov near-potential function, this only asks $\Phi$ to be accurate around $\pi^{\Phi}$ rather than uniformly over policy space — which is why NePPO can recover equilibria even in zero-sum games, where no global potential function exists.

Algorithm

$\Phi_w$ is restricted to a parameterized family and the max over players is smoothed with a log-sum-exp, $\tilde F_\beta(\Phi) = \tfrac{1}{\beta} \log \sum_i \exp\big(\beta F_i(\Phi)\big)$. Because $F_i$ depends on $w$ only through the solutions of two nested RL problems, its gradient is estimated with a two-point zeroth-order estimator. Each iteration:

1. Sample a direction $u$ uniformly on the unit sphere and set $\hat w = w + \delta u$, $\check w = w - \delta u$.
2. CoopGameSolver (HAPPO): warm-starting from the current $\pi^{\Phi}$, solve the cooperative game under $\Phi_{\hat w}$ and $\Phi_{\check w}$ for $K_1$ updates.
3. RLSolver (PPO): for each player, compute a best response to the other players' cooperative policies for $K_2$ updates.
4. Estimate $\tilde F_\beta(\Phi_{\hat w})$ and $\tilde F_\beta(\Phi_{\check w})$ from Monte-Carlo rollouts and take the step $$w \;\leftarrow\; w - \eta\,\frac{\dim(w)}{2\delta}\,\big[\tilde F_\beta(\Phi_{\hat w}) - \tilde F_\beta(\Phi_{\check w})\big]\,u.$$

The algorithm returns $\pi^{\Phi}$. Both solvers are modular: any cooperative MARL method can serve as the CoopGameSolver and any single-agent RL method as the RLSolver. The parameterization of $\Phi$ is a design handle — restricting it to a structured class biases which equilibrium is selected without modifying any player's reward.

Results

Mechanism on a 2×2 game

On the general-sum game of eq. (8), the candidate potential is the convex combination $\Phi_w = w J_1 + (1 - w) J_2$. The objective can be evaluated in closed form and is minimized (at zero) for every $w \in [0.6, 1]$, even though the game is not a potential game.

Matrix games

Eq. (7) defines a family of two-player, two-action games indexed by $\alpha \in [0, 1]$: $\alpha = 0$ is the general-sum game above, $\alpha = 1$ is zero-sum, and for $0.2 < \alpha < 1$ the unique equilibrium is fully mixed. Here the potential is the quadratic $\Phi_w(x, y) = -(x - p)^2 - (y - q)^2$ over the players' mixed strategies, with $w = (p, q)$. NePPO attains the lowest max regret at every $\alpha$ and recovers exact equilibria at $\alpha \in \{0, 0.2, 1\}$, including the zero-sum case. IPPO cycles at the mixed equilibria (top figure), and MAPPO converges to non-equilibrium profiles because it maximizes the summed reward.

Simple World Comm

A partially observable, general-sum Markov game from the Multi-Particle Environment suite with six agents: two heroes that collect food while avoiding capture, and four adversaries that pursue them, one of which sees the heroes and can broadcast to the rest. The potential is the discounted sum of a state-dependent softmax mixture of the agents' rewards, $\phi_w(s, a) = \sum_i \sigma_i(W s + b)\, r_i(s, a)$, so the learned potential can weight players differently in different states. Regret is measured per agent by training a PPO best response against the others' frozen policies.

Citation

@inproceedings{kalanther2026neppo,
  author       = {Kalanther, Addison and Bharvirkar, Sanika and Sastry, Shankar and Maheshwari, Chinmay},
  title        = {NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning},
  booktitle    = {Proceedings of the 2026 65th IEEE Conference on Decision and Control (CDC)},
  year         = {2026},
  month        = {Dec},
  organization = {IEEE},
  note         = {To appear}
}