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

Abstract

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 Optimistic Gradient Descent Ascent algorithm on each state to learn the policies, with a critic that slowly learns the value of each state. To the best of our knowledge, this is the first algorithm in this setting that is simultaneously rational (converging to the opponent's best response when it uses a stationary policy), convergent (converging to the set of Nash equilibria under self-play), agnostic (no need to know the actions played by the opponent), symmetric (players taking symmetric roles in the algorithm), and enjoying a finite-time last-iterate convergence guarantee, all of which are desirable properties of decentralized algorithms.

References in corpus (6)

• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Fast Convergence of Regularized Learning in Games
• Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
• Independent Policy Gradient Methods for Competitive Reinforcement Learning

Cited by in corpus (6)

• Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Decentralized Q-Learning in Zero-sum Markov Games
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces