Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence

Dongsheng Ding, Chen-Yu Wei, Kaiqing Zhang, Mihailo R. Jovanovic

Introduction

Multi-agent reinforcement learning (MARL) presents a fundamental challenge: as multiple agents learn simultaneously, the environment becomes non-stationary from the perspective of any individual agent. While "independent learning"—where agents optimize their own policies without explicit coordination—is the most scalable approach for real-world applications, its theoretical guarantees have historically been limited to "tabular" settings with small, discrete state and action spaces.

This paper addresses the "curse of dimensionality" in Markov Potential Games (MPGs), a class of games where a global potential function captures the collective progress of all agents. The authors provide the first global convergence guarantees for independent policy gradient (IPG) methods in large-scale MPGs, offering sharper rates and extending the theory to function approximation for infinite state spaces.

Methodology: Scaling Independent Learning

The authors propose three distinct algorithms to bridge the gap between MARL theory and large-scale practice, focusing on state-space independence and game-agnosticism.

1. State-Space Independent IPG

Standard policy gradient methods are typically weighted by the state visitation distribution. This weighting often leads to slow learning in states that are rarely visited during early training phases, making convergence rates dependent on the size of the state space $|S|$. The proposed Independent Policy Gradient Ascent (Algorithm 1) removes this weighting. By decoupling the update from the initial state distribution, the algorithm achieves an iteration complexity of $O(1/\epsilon^2)$, which is invariant to the state space size.

2. Function Approximation and Sample Complexity

In real-world scenarios, agents lack access to exact gradients and must estimate them from sampled trajectories. Algorithm 2 introduces a sample-based IPG that utilizes linear function approximation (Linear $Q$-learning) and $\epsilon$-greedy exploration. The authors demonstrate that the statistical error from sampling and the optimization error from gradient steps can be controlled separately, resulting in a sample complexity bound of $O(1/\epsilon^5)$ even in potentially infinite state spaces.

3. Game-Agnostic Convergence

A significant hurdle in MARL is the "moving target" problem, where agents struggle to adapt to the changing strategies of others. Algorithm 3 (Independent Optimistic Policy Gradient) employs "optimistic" updates and a smoothed critic. This approach allows agents to anticipate the learning steps of their peers. Remarkably, this structure is game-agnostic: it converges to a Nash Equilibrium in both zero-sum competitive settings and cooperative potential games without the agents needing to know the game type in advance.

Experimental Evaluation: Congestion Games

To validate their theoretical findings, the authors conducted experiments using a synthetic Congestion Game MDP. This environment simulates resource contention among eight players across two states ("safe" and "distancing"). Rewards are determined by the number of players choosing the same action; excessive congestion triggers a transition to a lower-reward "distancing" state.

The results demonstrate a significant empirical advantage for the proposed IPG method. While standard baseline methods (such as projected stochastic gradient ascent) failed to converge with learning rates above $\eta = 0.0001$, the proposed IPG method converged reliably with a stepsize of $\eta = 0.002$. This 20x improvement in the usable learning rate underscores the practical efficiency of the new approach.

Key Contributions and Insights

  • Sharper Convergence Rates: The $O(1/\epsilon^2)$ iteration complexity significantly improves upon previous MPG results, which typically scaled at $O(1/\epsilon^3)$ or $O(1/\epsilon^6)$.
  • First Function Approximation Bounds for MPGs: The paper provides the first sample complexity analysis for MPGs using function approximation, proving that independent learning is viable even when visiting every state is impossible.
  • Unified Learning: The optimistic update mechanism provides a path toward universal MARL agents that can perform effectively across different game structures (cooperative vs. zero-sum) without prior knowledge of the environment's competitive nature.

Limitations and Future Directions

While the paper marks a major advancement, several areas remain for future exploration. The function approximation results are currently limited to linear models; extending these guarantees to non-linear architectures like deep neural networks is a critical next step. Additionally, the proof for game-agnostic last-iterate convergence is currently restricted to two-player games. Finally, integrating more sophisticated exploration strategies could further enhance the sample efficiency of the proposed algorithms beyond the current $\epsilon$-greedy approach.

Summary updated

Abstract

We examine global non-asymptotic convergence properties of policy gradient methods for multi-agent reinforcement learning (RL) problems in Markov potential games (MPG). To learn a Nash equilibrium of an MPG in which the size of state space and/or the number of players can be very large, we propose new independent policy gradient algorithms that are run by all players in tandem. When there is no uncertainty in the gradient evaluation, we show that our algorithm finds an $\epsilon$-Nash equilibrium with $O(1/\epsilon^2)$ iteration complexity which does not explicitly depend on the state space size. When the exact gradient is not available, we establish $O(1/\epsilon^5)$ sample complexity bound in a potentially infinitely large state space for a sample-based algorithm that utilizes function approximation. Moreover, we identify a class of independent policy gradient algorithms that enjoys convergence for both zero-sum Markov games and Markov cooperative games with the players that are oblivious to the types of games being played. Finally, we provide computational experiments to corroborate the merits and the effectiveness of our theoretical developments.
BibTeX
@inproceedings{ding2022independent,
  author = {Dongsheng Ding and Chen-Yu Wei and Kaiqing Zhang and Mihailo R. Jovanovic},
  title = {{Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=ggH2lwqgYX},
}
Figure