On the Linear Convergence of Random Search for Discrete-Time LQR

Model-free reinforcement learning techniques directly search over the parameter space of controllers. Although this often amounts to solving a nonconvex optimization problem, for benchmark control problems simple local search methods exhibit competitive performance. To understand this phenomenon, we study the discretetime Linear Quadratic Regulator (LQR) problem with unknown state-space parameters. In spite of the lack of convexity, we establish that the random search method with two-point gradient estimates and a fixed number of roll-outs achieves E-accuracy in O(log (1/ϵ)) iterations. This significantly improves existing results on the model-free LQR problem which require O(1/ϵ) total roll-outs.