Oracle Complexity Reduction for Model-free LQR: A Stochastic
  Variance-Reduced Policy Gradient Approach
Leonardo F. Toso Han Wang James Anderson
We investigate the problem of learning an $\epsilon$-approximate solution for
the discrete-time Linear Quadratic Regulator (LQR) problem via a Stochastic
Variance-Reduced Policy Gradient (SVRPG) approach. Whilst policy gradient
methods have proven to converge linearly to the optimal solution of the
model-free LQR problem, the substantial requirement for two-point cost queries
in gradient estimations may be intractable, particularly in applications where
obtaining cost function evaluations at two distinct control input
configurations is exceptionally costly. To this end, we propose an
oracle-efficient approach. Our method combines both one-point and two-point
estimations in a dual-loop variance-reduced algorithm. It achieves an
approximate optimal solution with only
$O\left(\log\left(1/\epsilon\right)^{\beta}\right)$ two-point cost information
for $\beta \in (0,1)$.