# Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approach

arXiv: https://arxiv.org/abs/2309.10679 · HTML: https://mlsanity.com/paper/2309.10679/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 29 references that are in the map.
- First posted on arXiv 19 Sep 2023.

## Builds on (most cited first, 15 of 15)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems](https://mlsanity.com/paper/1812.08305/) (2018)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem](https://mlsanity.com/paper/1912.11899/) (2019)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [Model-free Learning with Heterogeneous Dynamical Systems: A Federated LQR Approach](https://mlsanity.com/paper/2308.11743/) (2023)
- [How are policy gradient methods affected by the limits of control?](https://mlsanity.com/paper/2206.06863/) (2022)
- [Zeroth-Order Feedback Optimization for Cooperative Multi-Agent Systems](https://mlsanity.com/paper/2011.09728/) (2020)

## Built on by (most cited first, 2 of 2)

- [Meta-Learning Linear Quadratic Regulators: A Policy Gradient MAML Approach for Model-free LQR](https://mlsanity.com/paper/2401.14534/) (2024)
- [Asynchronous Heterogeneous Linear Quadratic Regulator Design](https://mlsanity.com/paper/2404.09061/) (2024)

## Abstract (arXiv)

We investigate the problem of learning an ε-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 Oleft(logleft(1/εright)βright) two-point cost information for β ∈ (0,1).