  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. In particular,
$\texttt{Homotopy-PO}$ interweaves two base algorithms $\texttt{Local-Fast}$
and $\texttt{Global-Slow}$ via homotopy continuation. $\texttt{Local-Fast}$ is
an algorithm that enjoys local linear convergence while $\texttt{Global-Slow}$
is an algorithm that converges globally but at a slower sublinear rate. By
switching between these two base algorithms, $\texttt{Global-Slow}$ essentially
serves as a ``guide'' which identifies a benign neighborhood where
$\texttt{Local-Fast}$ enjoys fast convergence. However, since the exact size of
such a neighborhood is unknown, we apply a doubling trick to switch between
these two base algorithms. The switching scheme is delicately designed so that
the aggregated performance of the algorithm is driven by $\texttt{Local-Fast}$.
Furthermore, we prove that $\texttt{Local-Fast}$ and $\texttt{Global-Slow}$ can
both be instantiated by variants of optimistic gradient descent/ascent (OGDA)
method, which is of independent interest.
