Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games

2021/02/17 by Zhao, Yulai, Tian, Yuandong, Lee, Jason D. +1
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2102.08903

Abstract

Policy-based methods with function approximation are widely used for solving two-player zero-sum games with large state and/or action spaces. However, it remains elusive how to obtain optimization and statistical guarantees for such algorithms. We present a new policy optimization algorithm with function approximation and prove that under standard regularity conditions on the Markov game and the function approximation class, our algorithm finds a near-optimal policy within a polynomial number of samples and iterations. To our knowledge, this is the first provably efficient policy optimization algorithm with function approximation that solves two-player zero-sum Markov games.

Related

• Towards General Function Approximation in Zero-Sum Markov Games
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence
• Value Function Approximation in Zero-Sum Markov Games
• A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium