Policy Optimization for Markov Games: Unified Framework and Faster Convergence

We begin by proposing an algorithm framework for two-player zero-sum Markov Games in the full-information setting, where each iteration consists of a policy update step at each state using a certain matrix game algorithm, and a value update step with a certain learning rate. We show that the \emph{state-wise average policy} of this algorithm converges to an approximate Nash equilibrium (NE) of the game, as long as the matrix game algorithms achieve low weighted regret at each state, with respect to weights determined by the speed of the value updates. Next, we show that this framework instantiated with the Optimistic Follow-The-Regularized-Leader (OFTRL) algorithm at each state (and smooth value updates) can find an \mathcal{\widetilde{O}}(T {-5/6}) approximate NE in T iterations, and a similar algorithm with slightly modified value update rule achieves a faster \mathcal{\widetilde{O}}(T {-1}) convergence rate. These improve over the current best \mathcal{\widetilde{O}}(T {-1/2}) rate of symmetric policy optimization type algorithms. We also extend this algorithm to multi-player general-sum Markov Games and show an \mathcal{\widetilde{O}}(T {-3/4}) convergence rate to Coarse Correlated Equilibria (CCE).