Preprint
Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
arXiv (Cornell University)
07/07/2021
DOI: 10.48550/arxiv.2102.04540
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.
Details
- Title: Subtitle
- Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
- Creators
- Chen-Yu Wei - University of Southern CaliforniaChung-Wei LeeMengxiao Zhang - Southern California University for Professional StudiesHaipeng Luo - Southern California University for Professional Studies
- Resource Type
- Preprint
- Publication Details
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2102.04540
- eISSN
- 2331-8422
- Language
- English
- Date posted
- 07/07/2021
- Academic Unit
- Business Analytics
- Record Identifier
- 9984701827502771
Metrics
1 Record Views