(Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator
Abstract
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 Õ(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(Polylog(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 Õ(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.
Related
- Finite-time boundary collision in planar linear quadratic regulator gradient flows
- Characterizing Identifiability and Generalization for Inverse Receding-Horizon Linear-Quadratic Regulator Problems
- Continuous-Time Constrained Linear Quadratic Regulator for Switched Linear Systems
- Endpoint gradient bounds for centered convex maximal operators and probability kernels
- Uncertainty Quantification in Full Waveform Inversion with Gradient Flows in Probability Space
BibTeX
@misc{li2026cheap,
title = {{(Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator}},
author = {Yan Li and Chengze Xie},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19712},
eprint = {2609.19712},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19712},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - (Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator
AU - Yan Li
AU - Chengze Xie
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.19712
UR - https://arxiv.org/abs/2609.19712
AB - 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 Õ(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(Polylog(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 Õ(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.
ER -