# Thompson Sampling Achieves tilde O(√T) Regret in Linear Quadratic Control

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 17 Jun 2022.

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

- [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)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Online Linear Quadratic Control](https://mlsanity.com/paper/1806.07104/) (2018)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [Black-Box Control for Linear Dynamical Systems](https://mlsanity.com/paper/2007.06650/) (2020)
- [Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently](https://mlsanity.com/paper/2002.08095/) (2020)
- [On Adaptive Linear-Quadratic Regulators](https://mlsanity.com/paper/1806.10749/) (2018)
- [Reinforcement Learning with Fast Stabilization in Linear Dynamical Systems](https://mlsanity.com/paper/2007.12291/) (2020)
- [Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation](https://mlsanity.com/paper/2007.06482/) (2020)
- [Thompson Sampling for Linear-Quadratic Control Problems](https://mlsanity.com/paper/1703.08972/) (2017)
- [Optimism-Based Adaptive Regulation of Linear-Quadratic Systems](https://mlsanity.com/paper/1711.07230/) (2017)
- [Certainty Equivalence is Efficient for Linear Quadratic Control](https://mlsanity.com/paper/1902.07826/) (2019)
- [Learning-based Control of Unknown Linear Systems with Thompson Sampling](https://mlsanity.com/paper/1709.04047/) (2017)
- [Finite-time System Identification and Adaptive Control in Autoregressive Exogenous Systems](https://mlsanity.com/paper/2108.11959/) (2021)

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

- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [Learning the Uncertainty Sets for Control Dynamics via Set Membership: A Non-Asymptotic Analysis](https://mlsanity.com/paper/2309.14648/) (2023)
- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)
- [Learning-Based Adaptive Control for Stochastic Linear Systems with Input Constraints](https://mlsanity.com/paper/2209.07040/) (2022)
- [Stability Bounds for Learning-Based Adaptive Control of Discrete-Time Multi-Dimensional Stochastic Linear Systems with Input Constraints](https://mlsanity.com/paper/2304.00569/) (2023)
- [The Confusing Instance Principle for Online Linear Quadratic Control](https://mlsanity.com/paper/2510.19531/) (2025)
- [Optimistic Online LQR via Intrinsic Rewards](https://mlsanity.com/paper/2603.28938/) (2026)
- [Thompson Sampling-Based Learning and Control for Unknown Dynamic Systems](https://mlsanity.com/paper/2506.22186/) (2025)

## Abstract (arXiv)

Thompson Sampling (TS) is an efficient method for decision-making under uncertainty, where an action is sampled from a carefully prescribed distribution which is updated based on the observed data. In this work, we study the problem of adaptive control of stabilizable linear-quadratic regulators (LQRs) using TS, where the system dynamics are unknown. Previous works have established that tilde O(√T) frequentist regret is optimal for the adaptive control of LQRs. However, the existing methods either work only in restrictive settings, require a priori known stabilizing controllers, or utilize computationally intractable approaches. We propose an efficient TS algorithm for the adaptive control of LQRs, TS-based Adaptive Control, TSAC, that attains tilde O(√T) regret, even for multidimensional systems, thereby solving the open problem posed in Abeille and Lazaric (2018). TSAC does not require a priori known stabilizing controller and achieves fast stabilization of the underlying system by effectively exploring the environment in the early stages. Our result hinges on developing a novel lower bound on the probability that the TS provides an optimistic sample. By carefully prescribing an early exploration strategy and a policy update rule, we show that TS achieves order-optimal regret in adaptive control of multidimensional stabilizable LQRs. We empirically demonstrate the performance and the efficiency of TSAC in several adaptive control tasks.