$O(T^{-1})$ Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games
This provides a faster convergence guarantee for solving Markov games, which is important for applications in multi-agent reinforcement learning, though it is an incremental improvement over prior work.
The paper tackles the problem of finding Nash equilibria in two-player zero-sum Markov games, achieving an O(T^{-1}) convergence rate for optimistic-follow-the-regularized-leader with smooth value updates, which improves upon the previous rate of O(T^{-5/6}).
We prove that optimistic-follow-the-regularized-leader (OFTRL), together with smooth value updates, finds an $O(T^{-1})$-approximate Nash equilibrium in $T$ iterations for two-player zero-sum Markov games with full information. This improves the $\tilde{O}(T^{-5/6})$ convergence rate recently shown in the paper Zhang et al (2022). The refined analysis hinges on two essential ingredients. First, the sum of the regrets of the two players, though not necessarily non-negative as in normal-form games, is approximately non-negative in Markov games. This property allows us to bound the second-order path lengths of the learning dynamics. Second, we prove a tighter algebraic inequality regarding the weights deployed by OFTRL that shaves an extra $\log T$ factor. This crucial improvement enables the inductive analysis that leads to the final $O(T^{-1})$ rate.