Sample Complexity of the Linear Quadratic Regulator: A Reinforcement
  Learning Lens
Amirreza Neshaei Moghaddam Alex Olshevsky Bahman Gharesifard
We provide the first known algorithm that provably achieves
$\varepsilon$-optimality within $\widetilde{\mathcal{O}}(1/\varepsilon)$
function evaluations for the discounted discrete-time LQR problem with unknown
parameters, without relying on two-point gradient estimates. These estimates
are known to be unrealistic in many settings, as they depend on using the exact
same initialization, which is to be selected randomly, for two different
policies. Our results substantially improve upon the existing literature
outside the realm of two-point gradient estimates, which either leads to
$\widetilde{\mathcal{O}}(1/\varepsilon^2)$ rates or heavily relies on stability
assumptions.