A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffs
On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization
Abstract (arXiv)
Despite the significant potential for various applications, stochastic games with long-run average payoffs have received limited scholarly attention, particularly concerning the development of learning algorithms for them due to the challenges of mathematical analysis. In this paper, we study the stochastic games with long-run average payoffs and present an equivalent formulation for individual payoff gradients by defining advantage functions which will be proved to be bounded. This discovery allows us to demonstrate that the individual payoff gradient function is Lipschitz continuous with respect to the policy profile and that the value function of the games exhibits the gradient dominance property. Leveraging these insights, we devise a payoff-based gradient estimation approach and integrate it with the Regularized Robbins-Monro method from stochastic approximation theory to construct a bandit learning algorithm suited for stochastic games with long-run average payoffs. Additionally, we prove that if all players adopt our algorithm, the policy profile employed will asymptotically converge to a Nash equilibrium with probability one, provided that all Nash equilibria are globally neutrally stable and a globally variationally stable Nash equilibrium exists. This condition represents a wide class of games, including monotone games.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 9 of its 31 references that are in the map. First posted on arXiv 16 May 2024.
Builds on
9 of 31 references.
References · 9
- 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
- 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
- 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
- 2018Bandit learning in concave N-person gamescited by 35
- 2021Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Gamescited by 25
- 2022A unified stochastic approximation framework for learning in gamescited by 23
- 2021On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Gamescited by 19
- 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 16
- 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 7
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024Provable Policy Gradient Methods for Average-Reward Markov Potential Games
- 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Games
- 2025NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria
- 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria
- 2026High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- 2026Convergence of Stochastic First-Order Algorithms in Bertrand Competition Under Incomplete Information ↗
- 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence
- 2026Equilibrium Selection in Multi-Agent Policy Gradients via Opponent-Aware Basin Entry