On the convergence of policy gradient methods to Nash equilibria in general stochastic games

Angeliki Giannou, Kyriakos Lotidis, Panayotis Mertikopoulos, Emmanouil V. Vlatakis-Gkaragkounis

Abstract

This paper establishes the first rigorous convergence guarantees for policy gradient (PG) methods in general multi-agent stochastic games, bypassing the restrictive assumptions of "zero-sum" or "potential" game structures. The authors demonstrate that policy gradient trajectories locally converge to stable Nash equilibria at an $O(1/\sqrt{n})$ rate. Furthermore, they introduce a "lazy projection" variant that enables agents to reach deterministic Nash equilibria in a finite number of iterations, even in the presence of stochastic noise.

Introduction

Learning in stochastic games presents a dual challenge: agents must navigate both strategic interactions—where the optimal move depends on the actions of others—and a dynamic environment, where actions alter the state and subsequent reward structures. While convergence guarantees have been established for specific classes, such as two-player zero-sum or common-interest potential games, the general-sum case has historically been viewed as a "wild west" of instability.

Most existing literature focuses on the convergence of the "best-iterate" or time-averaged policies. This research addresses a more fundamental question: Can the actual trajectory of play for an ensemble of agents, learning independently via policy gradients, stabilize at a Nash equilibrium in a general stochastic game?

Methodology

The study analyzes a general Policy Gradient (PG) template where agents update policies episode-by-episode. The analysis covers three distinct feedback models:

  1. Full Gradient: Agents possess perfect information regarding their value function gradients.
  2. Stochastic Gradients: Agents utilize unbiased but noisy estimates.
  3. Value-Based (REINFORCE): Agents observe only rewards and reconstruct gradients using the "log-trick."

To address the inherent instability of multi-agent learning, the authors focus on Second-Order Stationary (SOS) policies. These are Nash equilibria that satisfy sufficiency conditions analogous to those used in non-convex optimization to identify stable local minima.

A significant algorithmic contribution is the Lazy Policy Gradient (LPG) scheme. Unlike standard PG, which projects the policy back into the valid simplex after every infinitesimal step, LPG maintains an auxiliary variable that aggregates gradients over time. Projection occurs only when determining the actual play. This "laziness" allows the gradient drift to push the policy decisively toward the boundaries of the strategy space, effectively mitigating the impact of noise near deterministic strategies.

Key Theoretical Insights

Gradient Dominance

The authors leverage the fact that stochastic games satisfy a "gradient dominance" property. This implies that a small gradient directly correlates to a player being near their optimal response, bridging the gap between standard optimization metrics and game-theoretic equilibrium concepts.

Local Attraction vs. Global Convergence

Given that general-sum games often exhibit limit cycles and multiple equilibria, global convergence is frequently impossible. By reframing the problem as a study of local attraction, the authors prove that if agents begin within a reasonable proximity of a stable equilibrium, they will converge to it with high probability.

The Mechanism of Laziness

The LPG algorithm's most striking feature is its ability to reach deterministic Nash equilibria in finite time. In standard PG, stochastic noise can perpetually displace a player from a deterministic strategy. LPG’s aggregation mechanism ensures that once the directional drift toward an equilibrium becomes sufficiently strong, the cumulative gradient outweighs the noise, allowing the player to "lock in" the strategy exactly.

Results and Convergence Rates

The research provides several landmark results for the tabular setting:

  • Local Stability: Stable Nash equilibria are shown to be locally attracting with arbitrarily high probability, even under the high-variance noise of the REINFORCE algorithm.
  • Convergence Rates: For SOS policies, the squared distance to the equilibrium vanishes at a rate of $O(1/\sqrt{n})$ when using REINFORCE. In the presence of perfect gradients, this improves to a geometric (exponential) rate.
  • Finite-Time Convergence: For deterministic Nash policies, the LPG algorithm converges to the exact equilibrium in a finite number of episodes, representing a significant improvement over asymptotic convergence results.

Discussion and Limitations

While this work provides a foundational theoretical framework, it focuses on the tabular setting, where states and actions are finite and discrete. Extending these proofs to accommodate function approximation (e.g., Deep Reinforcement Learning) remains a critical open challenge. Additionally, the guarantees are local; identifying conditions for global convergence in general-sum games remains a primary objective for future research. Finally, while this study utilizes Euclidean projections, the authors suggest that exploring softmax or mirror descent techniques may yield further refinements in convergence behavior.

Summary updated

BibTeX
@inproceedings{giannou2022convergence,
  author = {Angeliki Giannou and Kyriakos Lotidis and Panayotis Mertikopoulos and Emmanouil V. Vlatakis-Gkaragkounis},
  title = {{On the convergence of policy gradient methods to Nash equilibria in general stochastic games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=QedyATtQ1H},
}
Figure