# Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 16 Apr 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [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)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems](https://mlsanity.com/paper/1812.08305/) (2018)
- [Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem](https://mlsanity.com/paper/1912.11899/) (2019)
- [Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees](https://mlsanity.com/paper/2202.00048/) (2022)
- [Logarithmic Regret in Adaptive Control of Noisy Linear Quadratic Regulator Systems Using Hints](https://mlsanity.com/paper/2210.16303/) (2022)

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

- [Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretraining](https://mlsanity.com/paper/2502.05790/) (2025)
- [Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Data](https://mlsanity.com/paper/2502.19977/) (2025)
- [Harnessing Data from Clustered LQR Systems: Personalized and Collaborative Policy Optimization](https://mlsanity.com/paper/2511.17489/) (2025)
- [Sample Complexity of Linear Quadratic Regulator Without Initial Stability](https://mlsanity.com/paper/2502.14210/) (2025)
- [Sample-Efficient Model-Free Policy Gradient Methods for Stochastic LQR via Robust Linear Regression](https://mlsanity.com/paper/2512.03764/) (2025)
- [A Stochastic Gradient Descent Approach to Design Policy Gradient Methods for LQR](https://mlsanity.com/paper/2602.18933/) (2026)
- [Global Convergence of Policy Gradient Methods for ReLU Controllers in Linear Quadratic Regulation](https://mlsanity.com/paper/2604.22138/) (2026)
- [(Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator](https://mlsanity.com/paper/2609.19712/) (2026)

## Abstract (arXiv)

We provide the first known algorithm that provably achieves varepsilon-optimality within widetildeO(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 widetildeO(1/varepsilon2) rates or heavily relies on stability assumptions.