Can We Find Nash Equilibria at a Linear Rate in Markov Games?

Zhuoqing Song, Jason D. Lee, Zhuoran Yang

We study decentralized learning in two-player zero-sum discounted Markov games where the goal is to design a policy optimization algorithm for either agent satisfying two propertie…