Derivative-Free Methods for Policy Optimization: Guarantees for Linear
  Quadratic Systems
  We study derivative-free methods for policy optimization over the class of
linear policies. We focus on characterizing the convergence rate of these
methods when applied to linear-quadratic systems, and study various settings of
driving noise and reward feedback. We show that these methods provably converge
to within any pre-specified tolerance of the optimal policy with a number of
zero-order evaluations that is an explicit polynomial of the error tolerance,
dimension, and curvature properties of the problem. Our analysis reveals some
interesting differences between the settings of additive driving noise and
random initialization, as well as the settings of one-point and two-point
reward feedback. Our theory is corroborated by extensive simulations of
derivative-free methods on these systems. Along the way, we derive convergence
rates for stochastic zero-order optimization algorithms when applied to a
certain class of non-convex problems.
