# Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2020.

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

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Task-Optimal Exploration in Linear Dynamical Systems](https://mlsanity.com/paper/2102.05214/) (2021)
- [Identification and Adaptive Control of Markov Jump Systems: Sample Complexity and Regret Bounds](https://mlsanity.com/paper/2111.07018/) (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)
- [Thompson Sampling Achieves tilde O(√T) Regret in Linear Quadratic Control](https://mlsanity.com/paper/2206.08520/) (2022)
- [SOMBRL: Scalable and Optimistic Model-Based RL](https://mlsanity.com/paper/2511.20066/) (2025)
- [The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective](https://mlsanity.com/paper/2501.15910/) (2025)
- [NeoRL: Efficient Exploration for Nonepisodic RL](https://mlsanity.com/paper/2406.01175/) (2024)
- [Certainty Equivalent Quadratic Control for Markov Jump Systems](https://mlsanity.com/paper/2105.12358/) (2021)
- [Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2505.14821/) (2025)
- [Sample-efficient and Scalable Exploration in Continuous-Time RL](https://mlsanity.com/paper/2510.24482/) (2025)
- [Scalable regret for learning to control network-coupled subsystems with unknown dynamics](https://mlsanity.com/paper/2108.07970/) (2021)
- [Near-continuous time Reinforcement Learning for continuous state-action spaces](https://mlsanity.com/paper/2309.02815/) (2023)
- [A relaxed technical assumption for posterior sampling-based reinforcement learning for control of unknown linear systems](https://mlsanity.com/paper/2108.08502/) (2021)
- [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)
- [Learning to Control under Time-Varying Environment](https://mlsanity.com/paper/2206.02507/) (2022)

## Abstract (arXiv)

We study the exploration-exploitation dilemma in the linear quadratic regulator (LQR) setting. Inspired by the extended value iteration algorithm used in optimistic algorithms for finite MDPs, we propose to relax the optimistic optimization of ofulq and cast it into a constrained textitextended LQR problem, where an additional control variable implicitly selects the system dynamics within a confidence interval. We then move to the corresponding Lagrangian formulation for which we prove strong duality. As a result, we show that an ε-optimistic controller can be computed efficiently by solving at most Obig(log(1/ε)big) Riccati equations. Finally, we prove that relaxing the original ofu problem does not impact the learning performance, thus recovering the tildeO(√T) regret of ofulq. To the best of our knowledge, this is the first computationally efficient confidence-based algorithm for LQR with worst-case optimal regret guarantees.