Global Convergence of Policy Gradient Methods to (Almost) Locally
  Optimal Policies
  Policy gradient (PG) methods are a widely used reinforcement learning
methodology in many applications such as video games, autonomous driving, and
robotics. In spite of its empirical success, a rigorous understanding of the
global convergence of PG methods is lacking in the literature. In this work, we
close the gap by viewing PG methods from a nonconvex optimization perspective.
In particular, we propose a new variant of PG methods for infinite-horizon
problems that uses a random rollout horizon for the Monte-Carlo estimation of
the policy gradient. This method then yields an unbiased estimate of the policy
gradient with bounded variance, which enables the tools from nonconvex
optimization to be applied to establish global convergence. Employing this
perspective, we first recover the convergence results with rates to the
stationary-point policies in the literature. More interestingly, motivated by
advances in nonconvex optimization, we modify the proposed PG method by
introducing periodically enlarged stepsizes. The modified algorithm is shown to
escape saddle points under mild assumptions on the reward and the policy
parameterization. Under a further strict saddle points assumption, this result
establishes convergence to essentially locally-optimal policies of the
underlying problem, and thus bridges the gap in existing literature on the
convergence of PG methods. Results from experiments on the inverted pendulum
are then provided to corroborate our theory, namely, by slightly reshaping the
reward function to satisfy our assumption, unfavorable saddle points can be
avoided and better limit points can be attained. Intriguingly, this empirical
finding justifies the benefit of reward-reshaping from a nonconvex optimization
perspective.
