(Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator
On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization
Abstract (arXiv)
We study the convergence of the vanilla stochastic policy gradient method applied to the linear quadratic regulator (LQR) problem. The method is cheap in the following sense: (1) at each iteration only tildeO(1) interactions with the environment are needed, therefore allowing frequent policy improvement steps, and (2) to ensure stability throughout and convergence to an ε-optimal policy with probability 1-δ, only O(mathttPolylog(1/δ)/ε) interactions are needed. To the best of our knowledge, this appears to be the first time that a stochastic model-free policy optimization method for LQR converges with high probability with tildeO(1) per-iteration computation and polylogarithmic dependence on the confidence level. The convergence analysis presented here is agnostic to LQR specifics and hence could be potentially generalized to a broader class of problems.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 18 of its 42 references that are in the map. First posted on arXiv 17 Sep 2026.
Builds on
18 of 42 references.
Closest ancestors · 1
Same direction, newest first
Other references · 17
- 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
- 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
- 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 159
- 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
- 2022On the Convergence Rates of Policy Gradient Methodscited by 119
- 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
- 2018Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systemscited by 67
- 2020Optimizing Static Linear Feedback: Gradient Methodcited by 27
- 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 24
- 2019Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulatorcited by 23
- 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 23
- 2019Data informativity: a new perspective on data-driven analysis and controlcited by 19
5 more
- 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 17
- 2022Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guaranteescited by 14
- 2023Policy Mirror Descent Inherently Explores Action Spacecited by 13
- 2023Accelerated stochastic approximation with state-dependent noisecited by 11
- 2026Computation of Strong Solutions to Stochastic Variational Inequalitiescited by 4
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2025Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Data
- 2025Sample-Efficient Model-Free Policy Gradient Methods for Stochastic LQR via Robust Linear Regression
- 2026A Stochastic Gradient Descent Approach to Design Policy Gradient Methods for LQR
- 2025Policy Gradient for LQR with Domain Randomization
- 2025On the Gradient Domination of the LQG Problem
- 2025Second-Order Policy Gradient Methods for the Linear Quadratic Regulator
- 2026On Globally Optimal Stochastic Policy Gradient Methods for Domain Randomized LQR Synthesis
- 2024Convergence of Policy Gradient for Stochastic Linear-Quadratic Control Problem in Infinite Horizon