Policy Optimization for Markov Games: Unified Framework and Faster Convergence

Understand

This paper studies policy optimization algorithms for multi-agent reinforcement learning.

• 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.
• This framework unifies many existing and new policy optimization algorithms.
• We show that the 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.