Decentralized Policy Gradient for Nash Equilibria Learning of General-sum Stochastic Games

2022-10-14 · Yan Chen, Tao Li

We study Nash equilibria learning of a general-sum stochastic game with an unknown transition probability density function. Agents take actions at the current environment state and their joint action influences the transition of the environment state and their immediate rewards. Each agent only observes the environment state and its own immediate reward and is unknown about the actions or immediate rewards of others. We introduce the concepts of weighted asymptotic Nash equilibrium with probability 1 and in probability. For the case with exact pseudo gradients, we design a two-loop algorithm by the equivalence of Nash equilibrium and variational inequality problems. In the outer loop, we sequentially update a constructed strongly monotone variational inequality by updating a proximal parameter while employing a single-call extra-gradient algorithm in the inner loop for solving the constructed variational inequality. We show that if the associated Minty variational inequality has a solution, then the designed algorithm converges to the k^{1/2}-weighted asymptotic Nash equilibrium. Further, for the case with unknown pseudo gradients, we propose a decentralized algorithm, where the G(PO)MDP gradient estimator of the pseudo gradient is provided by Monte-Carlo simulations. The convergence to the k^{1/4} -weighted asymptotic Nash equilibrium in probability is achieved.

📄 PDF Abstract BibTeX arXiv:2210.07651

Code (0)

등록된 구현이 없습니다.

Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games

2021-02-08 · Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng Luo

We study infinite-horizon discounted two-player zero-sum Markov games, and develop a decentralized algorithm that provably converges to the set of Nash equilibria under self-play. Our algorithm is based on running an Opt…

Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games

2019-07-08 · Eric Mazumdar, Lillian J. Ratliff, Michael. I. Jordan, S. Shankar Sastry

We show by counterexample that policy-gradient algorithms have no guarantees of even local convergence to Nash equilibria in continuous action and state space multi-agent settings. To do so, we analyze gradient-play in N…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria

2025-10-21 · Eason Yu, Tzu Hao Liu, Clément L. Canonne, Yunke Wang 외 arxiv

Finding Nash equilibria in two-player zero-sum imperfect-information games remains a central challenge in multi-agent reinforcement learning. Recent multi-round regularization methods offer a promising direction, yet exi…

Multi-agent Reinforcement Learning

Equilibria of Fully Decentralized Learning in Networked Systems

2023-05-15 · Yan Jiang, Wenqi Cui, Baosen Zhang, Jorge Cortés

Existing settings of decentralized learning either require players to have full information or the system to have certain special structure that may be hard to check and hinder their applicability to practical systems. T…

On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning

2021-10-12 · Weichao Mao, Lin F. Yang, Kaiqing Zhang, Tamer Başar

Multi-agent reinforcement learning (MARL) algorithms often suffer from an exponential sample complexity dependence on the number of agents, a phenomenon known as \emph{the curse of multiagents}. In this paper, we address…

Multi-agent Reinforcement Learning Q-Learning reinforcement-learning Reinforcement Learning (RL)+1