# Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Dec 2019.

## Built on by (most cited first, 30 of 46)

- [On the Role of Attention in Prompt-tuning](https://mlsanity.com/paper/2306.03435/) (2023)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [Efficient Exploration in Continuous-time Model-based Reinforcement Learning](https://mlsanity.com/paper/2310.19848/) (2023)
- [Neural Operators of Backstepping Controller and Observer Gain Functions for Reaction-Diffusion PDEs](https://mlsanity.com/paper/2303.10506/) (2023)
- [Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity](https://mlsanity.com/paper/2101.01041/) (2021)
- [Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees](https://mlsanity.com/paper/2202.00048/) (2022)
- [Neural Operators for PDE Backstepping Control of First-Order Hyperbolic PIDE with Recycle and Delay](https://mlsanity.com/paper/2307.11436/) (2023)
- [Learning the Kalman Filter with Fine-Grained Sample Complexity](https://mlsanity.com/paper/2301.12624/) (2023)
- [Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens](https://mlsanity.com/paper/2404.10851/) (2024)
- [Global Convergence of Direct Policy Search for State-Feedback H_∞ Robust Control: A Revisit of Nonsmooth Synthesis with Goldstein Subdifferential](https://mlsanity.com/paper/2210.11577/) (2022)
- [Towards a Theoretical Foundation of Policy Optimization for Learning Control Policies](https://mlsanity.com/paper/2210.04810/) (2022)
- [Controlgym: Large-Scale Control Environments for Benchmarking Reinforcement Learning Algorithms](https://mlsanity.com/paper/2311.18736/) (2023)
- [Model-Free μ Synthesis via Adversarial Reinforcement Learning](https://mlsanity.com/paper/2111.15537/) (2021)
- [Policy Gradient Adaptive Control for the LQR: Indirect and Direct Approaches](https://mlsanity.com/paper/2505.03706/) (2025)
- [Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence](https://mlsanity.com/paper/2309.04272/) (2023)
- [Global Convergence of Receding-Horizon Policy Search in Learning Estimator Designs](https://mlsanity.com/paper/2309.04831/) (2023)
- [Asynchronous Heterogeneous Linear Quadratic Regulator Design](https://mlsanity.com/paper/2404.09061/) (2024)
- [Non-Uniform Noise-to-Signal Ratio in the REINFORCE Policy-Gradient Estimator](https://mlsanity.com/paper/2602.01460/) (2026)
- [Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems](https://mlsanity.com/paper/2303.12981/) (2023)
- [Learning Stabilizing Policies via an Unstable Subspace Representation](https://mlsanity.com/paper/2505.01348/) (2025)
- [Oracle Complexity Reduction for Model-free LQR: A Stochastic Variance-Reduced Policy Gradient Approach](https://mlsanity.com/paper/2309.10679/) (2023)
- [System stabilization with policy optimization on unstable latent manifolds](https://mlsanity.com/paper/2407.06418/) (2024)
- [Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Data](https://mlsanity.com/paper/2502.19977/) (2025)
- [Learning Decentralized Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2210.08886/) (2022)
- [Suboptimality analysis of receding horizon quadratic control with unknown linear systems and its applications in learning-based control](https://mlsanity.com/paper/2301.07876/) (2023)
- [On the Hardness of Learning to Stabilize Linear Systems](https://mlsanity.com/paper/2311.11151/) (2023)
- [Stability-Certified On-Policy Data-Driven LQR via Recursive Learning and Policy Gradient](https://mlsanity.com/paper/2403.05367/) (2024)
- [Asynchronous Parallel Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/2407.03233/) (2024)

## Abstract (arXiv)

Model-free reinforcement learning attempts to find an optimal control action for an unknown dynamical system by directly searching over the parameter space of controllers. The convergence behavior and statistical properties of these approaches are often poorly understood because of the nonconvex nature of the underlying optimization problems and the lack of exact gradient computation. In this paper, we take a step towards demystifying the performance and efficiency of such methods by focusing on the standard infinite-horizon linear quadratic regulator problem for continuous-time systems with unknown state-space parameters. We establish exponential stability for the ordinary differential equation (ODE) that governs the gradient-flow dynamics over the set of stabilizing feedback gains and show that a similar result holds for the gradient descent method that arises from the forward Euler discretization of the corresponding ODE. We also provide theoretical bounds on the convergence rate and sample complexity of the random search method with two-point gradient estimates. We prove that the required simulation time for achieving ε-accuracy in the model-free setup and the total number of function evaluations both scale as log , (1/ε).