Task-Optimal Exploration in Linear Dynamical Systems
arXiv:2102.05214
Abstract
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.
References in corpus (20)
- On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
- Gradient Descent Learns Linear Dynamical Systems
- On the Sample Complexity of the Linear Quadratic Regulator
- Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning
- Near optimal finite time identification of arbitrary linear dynamical systems
- Improper Learning for Non-Stochastic Control
- Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification
- Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
- Exploration in Structured Reinforcement Learning
- Fast active learning for pure exploration in reinforcement learning
- Naive Exploration is Optimal for Online LQR
- Learning Linear Dynamical Systems with Semi-Parametric Least Squares
- Active Learning for Nonlinear System Identification with Guarantees
- Information Theoretic Regret Bounds for Online Nonlinear Control
- Learning Linear-Quadratic Regulators Efficiently with only Regret
- Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation
- Adaptive Sampling for Best Policy Identification in Markov Decision Processes
- Navigating to the Best Policy in Markov Decision Processes
- Convergence Rates of Active Learning for Maximum Likelihood Estimation
- On Uninformative Optimal Policies in Adaptive LQR with Unknown B-Matrix