Task-Optimal Exploration in Linear Dynamical Systems
Task-Optimal Exploration in Linear Dynamical Systems
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Andrew J. Wagenmaker;Max Simchowitz;Kevin G. Jamieson
中科院分区：
文献类型：
--
作者：
Andrew J. Wagenmaker;Max Simchowitz;Kevin G. Jamieson
未知环境中的探索是强化学习和控制中的一个基本问题。在这项工作中，我们研究了任务引导的探索，并确定代理必须了解他们的环境，以完成特定的任务。形式上，我们研究了广泛的一类决策问题的线性动态系统的设置，一类，包括线性二次调节器问题。我们提供了实例和任务相关的下限，明确量化完成感兴趣的任务的难度。我们的下限的动机，我们提出了一个计算效率的实验设计为基础的探索算法。我们表明，它最佳地探索环境，精确地收集完成任务所需的信息，并提供有限的时间范围，保证它实现了实例和任务的最佳样本复杂性，常数因子。通过LQR问题的几个例子，我们表明，执行任务引导的探索可证明提高探索计划，不考虑感兴趣的任务。沿着的方式，我们建立确定性等价决策是实例和任务最优的，并获得线性二次调节器问题的第一个算法，这是实例最优的。最后，我们用几个实验来说明我们的方法在实践中的有效性。
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.