Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
Preprint
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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms2021
- Grandmaster level in StarCraft II using multi-agent reinforcement learningNature, 2019
- Mastering the game of Go without human knowledgeNature, 2017
- AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponentsMachine Learning, 2006
- A Unified Analysis of Value-Function-Based Reinforcement-Learning AlgorithmsNeural Computation, 1999
- On the Algorithm of Pollatschek and Avi-ltzhak1991