  Learning in stochastic games is a notoriously difficult problem because, in
addition to each other's strategic decisions, the players must also contend
with the fact that the game itself evolves over time, possibly in a very
complicated manner. Because of this, the convergence properties of popular
learning algorithms - like policy gradient and its variants - are poorly
understood, except in specific classes of games (such as potential or
two-player, zero-sum games). In view of this, we examine the long-run behavior
of policy gradient methods with respect to Nash equilibrium policies that are
second-order stationary (SOS) in a sense similar to the type of sufficiency
conditions used in optimization. Our first result is that SOS policies are
locally attracting with high probability, and we show that policy gradient
trajectories with gradient estimates provided by the REINFORCE algorithm
achieve an $\mathcal{O}(1/\sqrt{n})$ distance-squared convergence rate if the
method's step-size is chosen appropriately. Subsequently, specializing to the
class of deterministic Nash policies, we show that this rate can be improved
dramatically and, in fact, policy gradient methods converge within a finite
number of iterations in that case.
