Stochastic Games With Continuous Action Sets: Learning Pure Markov Nash Equilibrium via Gradient‐Play Algorithms

ABSTRACT

In this work, we study stochastic games with continuous action sets, finite state spaces, and deterministic strategies; a setting widely found in practice. These games pose two fundamental theoretical challenges. First, Nash equilibrium existence is not guaranteed in general. Second, even when equilibria exist, learning them is notoriously difficult, and existing works often impose structural assumptions on games that are hard to verify. To address the existence challenge, a sufficient condition for Nash equilibrium is derived, expressed explicitly in terms of the advantage functions and easily verifiable in some cases. For equilibrium learning, we develop a distributed algorithm that requires each player to know only their own actions and realized payoffs. Its feasibility relies on a new gradient‐estimation method specifically tailored for stochastic games. To guarantee the convergence, we further establish a decoupled sufficient condition that ensures the stochastic game is strongly monotone. This condition involves only the stage payoffs and the state visitation distribution, making it relatively easy to verify compared to direct verification. Under this condition, we provide a non‐asymptotic global convergence rate for the algorithm. Numerical experiments confirm the theoretical findings and suggest a discount factor threshold below which convergence is fast, indicating promising future directions.