Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games
Preprint
Abstract
We consider a general-sum N-player linear-quadratic game with stochastic dynamics over a finite horizon and prove the global convergence of the natural policy gradient method to the Nash equilibrium. In order to prove the convergence of the method, we require a certain amount of noise in the system. We give a condition, essentially a lower bound on the covariance of the noise in terms of the model parameters, in order to guarantee convergence. We illustrate our results with numerical experiments to show that even in situations where the policy gradient method may not converge in the deterministic setting, the addition of noise leads to convergence.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games2020
- On Gradient-Based Learning in Continuous GamesSIAM Journal on Mathematics of Data Science, 2020
- Convergence of Multi-Agent Learning with a Finite Step Size in General-Sum Games2019
- Natural Actor-CriticNeurocomputing, 2008
- Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principleCommunications in Information and Systems, 2006
- Multiagent learning using a variable learning rateArtificial Intelligence, 2002
- A matrix inequality associated with bounds on solutions of algebraic Riccati and Lyapunov equationsIEEE Transactions on Automatic Control, 1987
- Trace bounds on the solution of the algebraic matrix Riccati and Lyapunov equationIEEE Transactions on Automatic Control, 1986