Near-Optimal Policy Optimization for Correlated Equilibrium in
  General-Sum Markov Games
Yang Cai Haipeng Luo Chen-Yu Wei Weiqiang Zheng
We study policy optimization algorithms for computing correlated equilibria
in multi-player general-sum Markov Games. Previous results achieve
$O(T^{-1/2})$ convergence rate to a correlated equilibrium and an accelerated
$O(T^{-3/4})$ convergence rate to the weaker notion of coarse correlated
equilibrium. In this paper, we improve both results significantly by providing
an uncoupled policy optimization algorithm that attains a near-optimal
$\tilde{O}(T^{-1})$ convergence rate for computing a correlated equilibrium.
Our algorithm is constructed by combining two main elements (i) smooth value
updates and (ii) the optimistic-follow-the-regularized-leader algorithm with
the log barrier regularizer.