{"ID":23475017,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19712","arxiv_id":"2609.19712","title":"(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 $\\tilde{O}(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(\\mathtt{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 $\\tilde{O}(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.","short_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 $\\tilde{O}(1)$ interactions with the environment are needed, therefore allowing frequent policy improvement steps, and...","url_abs":"https://arxiv.org/abs/2609.19712","url_pdf":"https://arxiv.org/pdf/2609.19712v1","authors":"[\"Yan Li\",\"Chengze Xie\"]","published":"2026-09-17T05:06:19Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}