mlsanityData to 7 Oct 2026

Task-Optimal Exploration in Linear Dynamical Systems

arXiv 2102.05214 ↗First posted 10 Feb 2021cs.LG math.OC stat.MLcited by 15

Not on the map. Why?

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.

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

Builds on

30 of 70 references.

References · 30

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  3. 2018Learning Without Mixing: Towards A Sharp Analysis of Linear System Identificationcited by 158
  4. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 151
  5. 2020Naive Exploration is Optimal for Online LQRcited by 111
  6. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  7. 2019Online Control with Adversarial Disturbancescited by 92
  8. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  9. 2018Near optimal finite time identification of arbitrary linear dynamical systemscited by 89
  10. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 87
  11. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  12. 2020Improper Learning for Non-Stochastic Controlcited by 83
18 more
  1. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  2. 2016Gradient Descent Learns Linear Dynamical Systemscited by 78
  3. 2020Active Learning for Nonlinear System Identification with Guaranteescited by 78
  4. 2018Non-asymptotic Identification of LTI Systems from a Single Trajectorycited by 77
  5. 2019Finite Sample Analysis of Stochastic System Identificationcited by 67
  6. 2017Finite Time Identification in Unstable Linear Systemscited by 66
  7. 2019Learning Linear Dynamical Systems with Semi-Parametric Least Squarescited by 58
  8. 2018Spectral Filtering for General Linear Dynamical Systemscited by 37
  9. 2018Exploration in Structured Reinforcement Learningcited by 34
  10. 2020Active Learning for Identification of Linear Dynamical Systemscited by 33
  11. 2017The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regimecited by 31
  12. 2018Safely Learning to Control the Constrained Linear Quadratic Regulatorcited by 31
  13. 2015Convergence Rates of Active Learning for Maximum Likelihood Estimationcited by 25
  14. 2019Sample Complexity Lower Bounds for Linear System Identificationcited by 20
  15. 2020Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxationcited by 18
  16. 2017Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identificationcited by 16
  17. 2019Certainty Equivalence is Efficient for Linear Quadratic Controlcited by 13
  18. 2020On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrixcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 3; 2024: 3; 2025: 2; 2026: 1.

15 papers.

Sort:

By area:

  1. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 52
  2. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  3. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  4. 2024ASID: Active Exploration for System Identification in Robotic Manipulationcited by 27
  5. 2023Optimal Exploration for Model-Based RL in Nonlinear Systemscited by 17
  6. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  7. 2022Regret Lower Bounds for Learning Linear Quadratic Gaussian Systemscited by 11
  8. 2024Active Learning for Control-Oriented Identification of Nonlinear Systemscited by 7
  9. 2023FLEX: an Adaptive Exploration Algorithm for Nonlinear Systemscited by 2
  10. 2022Online greedy identification of linear dynamical systemscited by 1
  11. 2025High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systemscited by 1
  12. 2023Spectral learning of Bernoulli linear dynamical systems modelscited by 0
3 more
  1. 2024Active learning of neural population dynamics using two-photon holographic optogeneticscited by 0
  2. 2025Digital Twin Calibration with Model-Based Reinforcement Learningcited by 0
  3. 2026Optimal Centered Active Excitation in Linear System Identificationcited by 0