# Sample Complexity of Linear Quadratic Regulator Without Initial Stability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 20 Feb 2025.

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

- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems](https://mlsanity.com/paper/1812.08305/) (2018)
- [Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon](https://mlsanity.com/paper/2011.10300/) (2020)
- [Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem](https://mlsanity.com/paper/1912.11899/) (2019)
- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [A Historical Perspective of Adaptive Control and Learning](https://mlsanity.com/paper/2108.11336/) (2021)
- [Revisiting LQR Control from the Perspective of Receding-Horizon Policy Gradient](https://mlsanity.com/paper/2302.13144/) (2023)
- [Model-free optimal control of discrete-time systems with additive and multiplicative noises](https://mlsanity.com/paper/2008.08734/) (2020)
- [Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens](https://mlsanity.com/paper/2404.10851/) (2024)
- [Data-driven distributionally robust LQR with multiplicative noise](https://mlsanity.com/paper/1912.09990/) (2019)

## Abstract (arXiv)

Inspired by REINFORCE, we introduce a novel receding-horizon algorithm for the Linear Quadratic Regulator (LQR) problem with unknown dynamics. Unlike prior methods, our algorithm avoids reliance on two-point gradient estimates while maintaining the same order of sample complexity. Furthermore, it eliminates the restrictive requirement of starting with a stable initial policy, broadening its applicability. Beyond these improvements, we introduce a refined analysis of error propagation through the contraction of the Riccati operator under the Riemannian distance. This refinement leads to a better sample complexity and ensures improved convergence guarantees.