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

Understand

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 properties.

• First, the player does not need to know the policy of the opponent to update its policy.
• Second, when both players adopt the algorithm, their joint policy converges to a Nash equilibrium of the game.
• To this end, we construct a meta algorithm, dubbed as $\texttt{Homotopy-PO}$, which provably finds a Nash equilibrium at a global linear rate.