  We consider the task of learning to control a linear dynamical system under
fixed quadratic costs, known as the Linear Quadratic Regulator (LQR) problem.
While model-free approaches are often favorable in practice, thus far only
model-based methods, which rely on costly system identification, have been
shown to achieve regret that scales with the optimal dependence on the time
horizon T. We present the first model-free algorithm that achieves similar
regret guarantees. Our method relies on an efficient policy gradient scheme,
and a novel and tighter analysis of the cost of exploration in policy space in
this setting.
