  Multi-Agent Reinforcement Learning (MARL) -- where multiple agents learn to
interact in a shared dynamic environment -- permeates across a wide range of
critical applications. While there has been substantial progress on
understanding the global convergence of policy optimization methods in
single-agent RL, designing and analysis of efficient policy optimization
algorithms in the MARL setting present significant challenges, which
unfortunately, remain highly inadequately addressed by existing theory. In this
paper, we focus on the most basic setting of competitive multi-agent RL, namely
two-player zero-sum Markov games, and study equilibrium finding algorithms in
both the infinite-horizon discounted setting and the finite-horizon episodic
setting. We propose a single-loop policy optimization method with symmetric
updates from both agents, where the policy is updated via the
entropy-regularized optimistic multiplicative weights update (OMWU) method and
the value is updated on a slower timescale. We show that, in the
full-information tabular setting, the proposed method achieves a finite-time
last-iterate linear convergence to the quantal response equilibrium of the
regularized problem, which translates to a sublinear last-iterate convergence
to the Nash equilibrium by controlling the amount of regularization. Our
convergence results improve upon the best known iteration complexities, and
lead to a better understanding of policy optimization in competitive Markov
games.
