  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.
