# Task-Optimal Exploration in Linear Dynamical Systems

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 70 references that are in the map.
- First posted on arXiv 10 Feb 2021.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Finite Sample Analysis of Stochastic System Identification](https://mlsanity.com/paper/1903.09122/) (2019)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [Spectral Filtering for General Linear Dynamical Systems](https://mlsanity.com/paper/1802.03981/) (2018)
- [Exploration in Structured Reinforcement Learning](https://mlsanity.com/paper/1806.00775/) (2018)
- [Safely Learning to Control the Constrained Linear Quadratic Regulator](https://mlsanity.com/paper/1809.10121/) (2018)
- [Active Learning for Identification of Linear Dynamical Systems](https://mlsanity.com/paper/2002.00495/) (2020)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Convergence Rates of Active Learning for Maximum Likelihood Estimation](https://mlsanity.com/paper/1506.02348/) (2015)
- [Sample Complexity Lower Bounds for Linear System Identification](https://mlsanity.com/paper/1903.10343/) (2019)
- [Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation](https://mlsanity.com/paper/2007.06482/) (2020)
- [Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification](https://mlsanity.com/paper/1707.04791/) (2017)
- [Certainty Equivalence is Efficient for Linear Quadratic Control](https://mlsanity.com/paper/1902.07826/) (2019)
- [On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix](https://mlsanity.com/paper/2011.09288/) (2020)

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

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [ASID: Active Exploration for System Identification in Robotic Manipulation](https://mlsanity.com/paper/2404.12308/) (2024)
- [Optimal Exploration for Model-Based RL in Nonlinear Systems](https://mlsanity.com/paper/2306.09210/) (2023)
- [On Gap-dependent Bounds for Offline Reinforcement Learning](https://mlsanity.com/paper/2206.00177/) (2022)
- [Regret Lower Bounds for Learning Linear Quadratic Gaussian Systems](https://mlsanity.com/paper/2201.01680/) (2022)
- [Active Learning for Control-Oriented Identification of Nonlinear Systems](https://mlsanity.com/paper/2404.09030/) (2024)
- [FLEX: an Adaptive Exploration Algorithm for Nonlinear Systems](https://mlsanity.com/paper/2304.13426/) (2023)
- [Online greedy identification of linear dynamical systems](https://mlsanity.com/paper/2204.06375/) (2022)
- [Active learning of neural population dynamics using two-photon holographic optogenetics](https://mlsanity.com/paper/2412.02529/) (2024)
- [High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systems](https://mlsanity.com/paper/2509.11907/) (2025)
- [Spectral learning of Bernoulli linear dynamical systems models](https://mlsanity.com/paper/2303.02060/) (2023)
- [Digital Twin Calibration with Model-Based Reinforcement Learning](https://mlsanity.com/paper/2501.02205/) (2025)
- [Optimal Centered Active Excitation in Linear System Identification](https://mlsanity.com/paper/2604.05518/) (2026)

## Abstract (arXiv)

Exploration in unknown environments is a fundamental problem in reinforcement learning and control. In this work, we study task-guided exploration and determine what precisely an agent must learn about their environment in order to complete a particular task. Formally, we study a broad class of decision-making problems in the setting of linear dynamical systems, a class that includes the linear quadratic regulator problem. We provide instance- and task-dependent lower bounds which explicitly quantify the difficulty of completing a task of interest. Motivated by our lower bound, we propose a computationally efficient experiment-design based exploration algorithm. We show that it optimally explores the environment, collecting precisely the information needed to complete the task, and provide finite-time bounds guaranteeing that it achieves the instance- and task-optimal sample complexity, up to constant factors. Through several examples of the LQR problem, we show that performing task-guided exploration provably improves on exploration schemes which do not take into account the task of interest. Along the way, we establish that certainty equivalence decision making is instance- and task-optimal, and obtain the first algorithm for the linear quadratic regulator problem which is instance-optimal. We conclude with several experiments illustrating the effectiveness of our approach in practice.