  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.
