# Naive Exploration is Optimal for Online LQR

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

## Key facts

- Cited by 116 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2020.

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

- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [Optimistic Active Exploration of Dynamical Systems](https://mlsanity.com/paper/2306.12371/) (2023)
- [Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2206.09421/) (2022)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [Stabilizing Dynamical Systems via Policy Gradient Methods](https://mlsanity.com/paper/2110.06418/) (2021)
- [A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning](https://mlsanity.com/paper/2111.11485/) (2021)
- [Meta-Adaptive Nonlinear Control: Theory and Algorithms](https://mlsanity.com/paper/2106.06098/) (2021)
- [Efficient Exploration in Continuous-time Model-based Reinforcement Learning](https://mlsanity.com/paper/2310.19848/) (2023)
- [Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex models](https://mlsanity.com/paper/2112.10264/) (2021)
- [Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Sets](https://mlsanity.com/paper/2205.10671/) (2022)
- [Optimal Exploration for Model-Based RL in Nonlinear Systems](https://mlsanity.com/paper/2306.09210/) (2023)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity](https://mlsanity.com/paper/2101.01041/) (2021)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Exploration](https://mlsanity.com/paper/2107.07410/) (2021)
- [Learning over All Stabilizing Nonlinear Controllers for a Partially-Observed Linear System](https://mlsanity.com/paper/2112.04219/) (2021)
- [Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression](https://mlsanity.com/paper/2310.11428/) (2023)
- [Online Control of Unknown Time-Varying Dynamical Systems](https://mlsanity.com/paper/2202.07890/) (2022)
- [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)
- [Sublinear Regret for a Class of Continuous-Time Linear-Quadratic Reinforcement Learning Problems](https://mlsanity.com/paper/2407.17226/) (2024)
- [Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees](https://mlsanity.com/paper/2111.00411/) (2021)
- [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022)
- [Learning to Control Linear Systems can be Hard](https://mlsanity.com/paper/2205.14035/) (2022)
- [Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling](https://mlsanity.com/paper/2203.08248/) (2022)
- [How are policy gradient methods affected by the limits of control?](https://mlsanity.com/paper/2206.06863/) (2022)
- [Sparsity in Partially Controllable Linear Systems](https://mlsanity.com/paper/2110.06150/) (2021)

## Abstract (arXiv)

We consider the problem of online adaptive control of the linear quadratic regulator, where the true system parameters are unknown. We prove new upper and lower bounds demonstrating that the optimal regret scales as widetildeTheta(√du2 dx T), where T is the number of time steps, du is the dimension of the input space, and dx is the dimension of the system state. Notably, our lower bounds rule out the possibility of a poly(logT)-regret algorithm, which had been conjectured due to the apparent strong convexity of the problem. Our upper bound is attained by a simple variant of textitcertainty equivalent control, where the learner selects control inputs according to the optimal controller for their estimate of the system while injecting exploratory random noise. While this approach was shown to achieve √T-regret by (Mania et al. 2019), we show that if the learner continually refines their estimates of the system matrices, the method attains optimal dimension dependence as well. Central to our upper and lower bounds is a new approach for controlling perturbations of Riccati equations called the textitself-bounding ODE method, which we use to derive suboptimality bounds for the certainty equivalent controller synthesized from estimated system dynamics. This in turn enables regret upper bounds which hold for textitany stabilizable instance and scale with natural control-theoretic quantities.