Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games

arXiv:2401.15240v2 Announce Type: replace
Abstract: 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) …

abstract algorithms arxiv computing convergence cs.gt cs.lg equilibria equilibrium games general markov math.oc near notion optimization paper policy rate results study sum type