Near-Optimal Last-iterate Convergence of Policy Optimization in Zero-sum Polymatrix Markov games

Zailin Ma, Jiansheng Yang, Zhihua Zhang

Computing approximate Nash equilibria in multi-player general-sum Markov games is a computationally intractable task. However, multi-player Markov games with certain cooperative or…