# (Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator

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

## 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.

## 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, 18 of 18)

- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems](https://mlsanity.com/paper/1812.08305/) (2018)
- [Optimizing Static Linear Feedback: Gradient Method](https://mlsanity.com/paper/2004.09875/) (2020)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning](https://mlsanity.com/paper/2109.14756/) (2021)
- [Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator](https://mlsanity.com/paper/1905.12842/) (2019)
- [Data informativity: a new perspective on data-driven analysis and control](https://mlsanity.com/paper/1908.00468/) (2019)
- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees](https://mlsanity.com/paper/2202.00048/) (2022)
- [Policy Mirror Descent Inherently Explores Action Space](https://mlsanity.com/paper/2303.04386/) (2023)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [Sample Complexity of the Linear Quadratic Regulator: A Reinforcement Learning Lens](https://mlsanity.com/paper/2404.10851/) (2024)
- [Computation of Strong Solutions to Stochastic Variational Inequalities](https://mlsanity.com/paper/2609.04188/) (2026)

## 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.