Skip to yearly menu bar Skip to main content


Poster

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

Yang Cai · Haipeng Luo · Chen-Yu Wei · Weiqiang Zheng

MR1 & MR2 - Number 44
[ ]
Fri 3 May 8 a.m. PDT — 8:30 a.m. PDT
 
Oral presentation: Oral: RL & Optimization
Thu 2 May 1:30 a.m. PDT — 2:30 a.m. PDT

Abstract: We study policy optimization algorithms for computing correlated equilibria in multi-player general-sum Markov Games. Previous results achieve $\Tilde{O}(T^{-1/2})$ convergence rate to a correlated equilibrium and an accelerated $\Tilde{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 \emph{optimistic-follow-the-regularized-leader} algorithm with the log barrier regularizer.

Live content is unavailable. Log in and register to view live content