# Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2019.

## Built on by (most cited first, 23 of 23)

- [Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data](https://mlsanity.com/paper/2308.04428/) (2023)
- [Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2102.12608/) (2021)
- [Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator](https://mlsanity.com/paper/2208.08744/) (2022)
- [Towards a Theoretical Foundation of Policy Optimization for Learning Control Policies](https://mlsanity.com/paper/2210.04810/) (2022)
- [Model-Free μ Synthesis via Adversarial Reinforcement Learning](https://mlsanity.com/paper/2111.15537/) (2021)
- [Scalable Reinforcement Learning for Linear-Quadratic Control of Networks](https://mlsanity.com/paper/2401.16183/) (2024)
- [Learning to Stabilize Unknown LTI Systems on a Single Trajectory under Stochastic Noise](https://mlsanity.com/paper/2406.00234/) (2024)
- [Global Optimality of Single-Timescale Actor-Critic under Continuous State-Action Space: A Study on Linear Quadratic Regulator](https://mlsanity.com/paper/2505.01041/) (2025)
- [Managing Temporal Resolution in Continuous Value Estimation: A Fundamental Trade-off](https://mlsanity.com/paper/2212.08949/) (2022)
- [Stability-Certified On-Policy Data-Driven LQR via Recursive Learning and Policy Gradient](https://mlsanity.com/paper/2403.05367/) (2024)
- [Interacting Particle Systems for Fast Linear Quadratic RL](https://mlsanity.com/paper/2406.11057/) (2024)
- [Exploiting inter-agent coupling information for efficient reinforcement learning of cooperative LQR](https://mlsanity.com/paper/2504.20927/) (2025)
- [Regret Analysis of Online LQR Control via Trajectory Prediction and Tracking: Extended Version](https://mlsanity.com/paper/2302.10411/) (2023)
- [Reinforcement Learning with Partial Parametric Model Knowledge](https://mlsanity.com/paper/2304.13223/) (2023)
- [MR-ARL: Model Reference Adaptive Reinforcement Learning for Robustly Stable On-Policy Data-Driven LQR](https://mlsanity.com/paper/2402.14483/) (2024)
- [Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problem](https://mlsanity.com/paper/2411.15972/) (2024)
- [A Fully Data-Driven Value Iteration for Stochastic LQR: Convergence, Robustness and Stability](https://mlsanity.com/paper/2505.02970/) (2025)
- [An adaptive data sampling strategy for stabilizing dynamical systems via controller inference](https://mlsanity.com/paper/2506.01816/) (2025)
- [Learning-based primal-dual optimal control of discrete-time stochastic systems with multiplicative noise](https://mlsanity.com/paper/2506.02613/) (2025)
- [Policy Transfer for Continuous-Time Reinforcement Learning: A (Rough) Differential Equation Approach](https://mlsanity.com/paper/2510.15165/) (2025)
- [Comparative Study of Q-Learning for State-Feedback LQG Control with an Unknown Model](https://mlsanity.com/paper/2511.07870/) (2025)
- [Distributional Active Inference](https://mlsanity.com/paper/2601.20985/) (2026)
- [(Cheap) Stochastic Policy Gradient Converges with High Probability for Linear Quadratic Regulator](https://mlsanity.com/paper/2609.19712/) (2026)

## Abstract (arXiv)

We study the sample complexity of approximate policy iteration (PI) for the Linear Quadratic Regulator (LQR), building on a recent line of work using LQR as a testbed to understand the limits of reinforcement learning (RL) algorithms on continuous control tasks. Our analysis quantifies the tension between policy improvement and policy evaluation, and suggests that policy evaluation is the dominant factor in terms of sample complexity. Specifically, we show that to obtain a controller that is within varepsilon of the optimal LQR controller, each step of policy evaluation requires at most (n+d)3/varepsilon2 samples, where n is the dimension of the state vector and d is the dimension of the input vector. On the other hand, only log(1/varepsilon) policy improvement steps suffice, resulting in an overall sample complexity of (n+d)3 varepsilon-2 log(1/varepsilon). We furthermore build on our analysis and construct a simple adaptive procedure based on varepsilon-greedy exploration which relies on approximate PI as a sub-routine and obtains T2/3 regret, improving upon a recent result of Abbasi-Yadkori et al.