# Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2020.

## Built on by (most cited first, 30 of 35)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds](https://mlsanity.com/paper/2111.07018/) (2021)
- [Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2102.12608/) (2021)
- [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022)
- [Sparsity in Partially Controllable Linear Systems](https://mlsanity.com/paper/2110.06150/) (2021)
- [Thompson Sampling Achieves tilde O(√T) Regret in Linear Quadratic Control](https://mlsanity.com/paper/2206.08520/) (2022)
- [Learning Dynamical Systems by Leveraging Data from Similar Systems](https://mlsanity.com/paper/2302.04344/) (2023)
- [On the Sample Complexity of Decentralized Linear Quadratic Regulator with Partially Nested Information Structure](https://mlsanity.com/paper/2110.07112/) (2021)
- [Optimal Rates for Bandit Nonstochastic Control](https://mlsanity.com/paper/2305.15352/) (2023)
- [Regret Analysis of Distributed Online LQR Control for Unknown LTI Systems](https://mlsanity.com/paper/2105.07310/) (2021)
- [Nonasymptotic Regret Analysis of Adaptive Linear Quadratic Control with Model Misspecification](https://mlsanity.com/paper/2401.00073/) (2023)
- [Rate-Optimal Online Convex Optimization in Adaptive Linear Control](https://mlsanity.com/paper/2206.01426/) (2022)
- [Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems](https://mlsanity.com/paper/2111.03772/) (2021)
- [Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics](https://mlsanity.com/paper/2203.01170/) (2022)
- [Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge](https://mlsanity.com/paper/2312.12558/) (2023)
- [Regret Analysis of Multi-task Representation Learning for Linear-Quadratic Adaptive Control](https://mlsanity.com/paper/2407.05781/) (2024)
- [Model-Free Learning for the Linear Quadratic Regulator over Rate-Limited Channels](https://mlsanity.com/paper/2401.01258/) (2024)
- [Convergence Guarantees of Model-free Policy Gradient Methods for LQR with Stochastic Data](https://mlsanity.com/paper/2502.19977/) (2025)
- [Learning Decentralized Linear Quadratic Regulators with √T Regret](https://mlsanity.com/paper/2210.08886/) (2022)
- [Regret Analysis of Distributed Online Control for LTI Systems with Adversarial Disturbances](https://mlsanity.com/paper/2310.03206/) (2023)
- [On the Hardness of Learning to Stabilize Linear Systems](https://mlsanity.com/paper/2311.11151/) (2023)
- [Online Change Points Detection for Linear Dynamical Systems with Finite Sample Guarantees](https://mlsanity.com/paper/2311.18769/) (2023)
- [Stability-Certified On-Policy Data-Driven LQR via Recursive Learning and Policy Gradient](https://mlsanity.com/paper/2403.05367/) (2024)
- [Adversarially Robust Multitask Adaptive Control](https://mlsanity.com/paper/2511.05444/) (2025)
- [Improper Reinforcement Learning with Gradient-based Policy Optimization](https://mlsanity.com/paper/2102.08201/) (2021)
- [Safe Linear-Quadratic Dual Control with Almost Sure Performance Guarantee](https://mlsanity.com/paper/2103.13278/) (2021)
- [Reinforcement Learning Policies in Continuous-Time Linear Systems](https://mlsanity.com/paper/2109.07630/) (2021)
- [Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics](https://mlsanity.com/paper/2202.05799/) (2022)
- [Learning to Control under Time-Varying Environment](https://mlsanity.com/paper/2206.02507/) (2022)
- [Regret Analysis of Certainty Equivalence Policies in Continuous-Time Linear-Quadratic Systems](https://mlsanity.com/paper/2206.04434/) (2022)

## Abstract (arXiv)

We consider the problem of learning in Linear Quadratic Control systems whose transition parameters are initially unknown. Recent results in this setting have demonstrated efficient learning algorithms with regret growing with the square root of the number of decision steps. We present new efficient algorithms that achieve, perhaps surprisingly, regret that scales only (poly)logarithmically with the number of steps in two scenarios: when only the state transition matrix A is unknown, and when only the state-action transition matrix B is unknown and the optimal policy satisfies a certain non-degeneracy condition. On the other hand, we give a lower bound that shows that when the latter condition is violated, square root regret is unavoidable.