mlsanityData to 14 Oct 2026

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

arXiv 2404.10851 ↗First posted 16 Apr 2024eess.SY cs.LG cs.SYcited by 8

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

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.

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.

Builds on

9 of 29 references.

References · 9

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  2. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  3. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 159
  4. 2020Naive Exploration is Optimal for Online LQRcited by 116
  5. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  6. 2018Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systemscited by 67
  7. 2019Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problemcited by 46
  8. 2022Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guaranteescited by 14
  9. 2022Logarithmic Regret in Adaptive Control of Noisy Linear Quadratic Regulator Systems Using Hintscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 3.

8 papers.

  1. 2025Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretrainingcited by 7
  2. 2025Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Datacited by 2
  3. 2025Harnessing Data from Clustered LQR Systems: Personalized and Collaborative Policy Optimizationcited by 1
  4. 2025Sample Complexity of Linear Quadratic Regulator Without Initial Stabilitycited by 0
  5. 2025Sample-Efficient Model-Free Policy Gradient Methods for Stochastic LQR via Robust Linear Regressioncited by 0
  6. 2026A Stochastic Gradient Descent Approach to Design Policy Gradient Methods for LQRcited by 0
  7. 2026Global Convergence of Policy Gradient Methods for ReLU Controllers in Linear Quadratic Regulationcited by 0
  8. 2026(Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulatorcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025On the Robustness of Derivative-free Methods for Linear Quadratic Regulator
  2. 2025Power-Constrained Policy Gradient Methods for LQR
  3. 2026Gradient Dominance in the Linear Quadratic Regulator: A Unified Analysis for Continuous-Time and Discrete-Time Systems
  4. 2025Second-Order Policy Gradient Methods for the Linear Quadratic Regulator
  5. 2025Bridging Continuous-time LQR and Reinforcement Learning via Gradient Flow of the Bellman Error
  6. 2025Model-free stochastic linear quadratic control for discrete-time systems with multiplicative and additive noises via semidefinite programming
  7. 2025On the Gradient Domination of the LQG Problem
  8. 2024Policy Gradient Methods for the Cost-Constrained LQR: Strong Duality and Global Convergence