# Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 53 references that are in the map.
- First posted on arXiv 11 Feb 2022.

## Builds on (most cited first, 29 of 29)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [A Tour of Reinforcement Learning: The View from Continuous Control](https://mlsanity.com/paper/1806.09460/) (2018)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits](https://mlsanity.com/paper/1904.00242/) (2019)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Logarithmic Regret for Adversarial Online Control](https://mlsanity.com/paper/2003.00189/) (2020)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently](https://mlsanity.com/paper/2002.08095/) (2020)
- [Exploration in Structured Reinforcement Learning](https://mlsanity.com/paper/1806.00775/) (2018)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints](https://mlsanity.com/paper/1805.05071/) (2018)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems](https://mlsanity.com/paper/1303.5984/) (2013)
- [Minimal Expected Regret in Linear Quadratic Control](https://mlsanity.com/paper/2109.14429/) (2021)
- [Safe Adaptive Learning-based Control for Constrained Linear Quadratic Regulators with Regret Guarantees](https://mlsanity.com/paper/2111.00411/) (2021)
- [Learning-based Control of Unknown Linear Systems with Thompson Sampling](https://mlsanity.com/paper/1709.04047/) (2017)
- [Exact Asymptotics for Linear Quadratic Adaptive Control](https://mlsanity.com/paper/2011.01364/) (2020)
- [Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems](https://mlsanity.com/paper/2111.03772/) (2021)

## Abstract (arXiv)

The theory of reinforcement learning currently suffers from a mismatch between its empirical performance and the theoretical characterization of its performance, with consequences for, e.g., the understanding of sample efficiency, safety, and robustness. The linear quadratic regulator with unknown dynamics is a fundamental reinforcement learning setting with significant structure in its dynamics and cost function, yet even in this setting there is a gap between the best known regret lower-bound of Omegap(√T) and the best known upper-bound of Op(√T,polylog(T)). The contribution of this paper is to close that gap by establishing a novel regret upper-bound of Op(√T). Our proof is constructive in that it analyzes the regret of a concrete algorithm, and simultaneously establishes an estimation error bound on the dynamics of Op(T-1/4) which is also the first to match the rate of a known lower-bound. The two keys to our improved proof technique are (1) a more precise upper- and lower-bound on the system Gram matrix and (2) a self-bounding argument for the expected estimation error of the optimal controller.