  Policy gradient methods are widely used in solving two-player zero-sum games
to achieve superhuman performance in practice. However, it remains elusive when
they can provably find a near-optimal solution and how many samples and
iterations are needed. The current paper studies natural extensions of Natural
Policy Gradient algorithm for solving two-player zero-sum games where function
approximation is used for generalization across states. We thoroughly
characterize the algorithms' performance in terms of the number of samples,
number of iterations, concentrability coefficients, and approximation error. To
our knowledge, this is the first quantitative analysis of policy gradient
methods with function approximation for two-player zero-sum Markov games.
