# Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems

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

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2018.

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

- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [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)
- [Oracle-free Reinforcement Learning in Mean-Field Games along a Single Sample Path](https://mlsanity.com/paper/2208.11639/) (2022)
- [Stochastic Control for Fine-tuning Diffusion Models: Optimality, Regularity, and Convergence](https://mlsanity.com/paper/2412.18164/) (2024)
- [Meta-Learning Linear Quadratic Regulators: A Policy Gradient MAML Approach for Model-free LQR](https://mlsanity.com/paper/2401.14534/) (2024)
- [Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity](https://mlsanity.com/paper/2101.01041/) (2021)
- [Derivative-Free Reinforcement Learning: A Review](https://mlsanity.com/paper/2102.05710/) (2021)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Fast Policy Learning for Linear Quadratic Control with Entropy Regularization](https://mlsanity.com/paper/2311.14168/) (2023)
- [Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2102.12608/) (2021)
- [Sublinear Regret for a Class of Continuous-Time Linear-Quadratic Reinforcement Learning Problems](https://mlsanity.com/paper/2407.17226/) (2024)
- [Revisiting LQR Control from the Perspective of Receding-Horizon Policy Gradient](https://mlsanity.com/paper/2302.13144/) (2023)
- [Learning the Kalman Filter with Fine-Grained Sample Complexity](https://mlsanity.com/paper/2301.12624/) (2023)
- [Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator](https://mlsanity.com/paper/2208.08744/) (2022)
- [Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens](https://mlsanity.com/paper/2404.10851/) (2024)
- [On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structure](https://mlsanity.com/paper/2110.07112/) (2021)
- [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)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearity](https://mlsanity.com/paper/2106.07814/) (2021)
- [Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions](https://mlsanity.com/paper/2202.13046/) (2022)
- [Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/2209.07883/) (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)
- [Coreset-Based Task Selection for Sample-Efficient Meta-Reinforcement Learning](https://mlsanity.com/paper/2502.02332/) (2025)
- [Model-Free μ Synthesis via Adversarial Reinforcement Learning](https://mlsanity.com/paper/2111.15537/) (2021)
- [Rate-Optimal Online Convex Optimization in Adaptive Linear Control](https://mlsanity.com/paper/2206.01426/) (2022)
- [Policy Gradient Converges to the Globally Optimal Policy for Nearly Linear-Quadratic Regulators](https://mlsanity.com/paper/2303.08431/) (2023)
- [Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent](https://mlsanity.com/paper/2107.12416/) (2021)
- [Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence](https://mlsanity.com/paper/2309.04272/) (2023)

## Abstract (arXiv)

We study derivative-free methods for policy optimization over the class of linear policies. We focus on characterizing the convergence rate of these methods when applied to linear-quadratic systems, and study various settings of driving noise and reward feedback. We show that these methods provably converge to within any pre-specified tolerance of the optimal policy with a number of zero-order evaluations that is an explicit polynomial of the error tolerance, dimension, and curvature properties of the problem. Our analysis reveals some interesting differences between the settings of additive driving noise and random initialization, as well as the settings of one-point and two-point reward feedback. Our theory is corroborated by extensive simulations of derivative-free methods on these systems. Along the way, we derive convergence rates for stochastic zero-order optimization algorithms when applied to a certain class of non-convex problems.