Local Optimization Achieves Global Optimality in Multi-Agent
  Reinforcement Learning
Yulai Zhao Zhuoran Yang Zhaoran Wang Jason D. Lee
Policy optimization methods with function approximation are widely used in
multi-agent reinforcement learning. However, it remains elusive how to design
such algorithms with statistical guarantees. Leveraging a multi-agent
performance difference lemma that characterizes the landscape of multi-agent
policy optimization, we find that the localized action value function serves as
an ideal descent direction for each local policy. Motivated by the observation,
we present a multi-agent PPO algorithm in which the local policy of each agent
is updated similarly to vanilla PPO. We prove that with standard regularity
conditions on the Markov game and problem-dependent quantities, our algorithm
converges to the globally optimal policy at a sublinear rate. We extend our
algorithm to the off-policy setting and introduce pessimism to policy
evaluation, which aligns with experiments. To our knowledge, this is the first
provably convergent multi-agent PPO algorithm in cooperative Markov games.