Convergence and Sample Complexity of Gradient Methods for the Model-Free Linear–Quadratic Regulator Problem
Convergence and Sample Complexity of Gradient Methods for the Model-Free Linear–Quadratic Regulator Problem
复制标题
DOI：
10.1109/tac.2021.3087455
复制
发表时间：
2019-12
影响因子：
6.8
通讯作者：
Hesameddin Mohammadi;A. Zare;M. Soltanolkotabi;M. Jovanovi'c
中科院分区：
文献类型：
--
作者：
Hesameddin Mohammadi;A. Zare;M. Soltanolkotabi;M. Jovanovi'c
无模型强化学习试图通过直接搜索控制器的参数空间来为未知的动态系统找到最优控制动作。这些方法的收敛行为和统计特性往往知之甚少，因为基本的优化问题的非凸性和缺乏精确的梯度计算。在这篇文章中，我们采取了一个步骤，以揭开神秘的性能和效率的方法，专注于标准的无限时域线性二次调节器问题的连续时间系统未知的状态空间参数。我们建立指数稳定的常微分方程（ODE），管理的梯度流动力学的一组稳定的反馈增益，并表明类似的结果适用于梯度下降法，所产生的相应的ODE的前向欧拉离散化。我们还提供了两点梯度估计的随机搜索方法的收敛速度和样本复杂度的理论界。我们证明，所需的模拟时间实现$\log\，（1/\log）$的无模型设置和函数评估的总数量都规模为$\log \，$\n $的准确性。
Model-free reinforcement learning attempts to find an optimal control action for an unknown dynamical system by directly searching over the parameter space of controllers. The convergence behavior and statistical properties of these approaches are often poorly understood because of the nonconvex nature of the underlying optimization problems and the lack of exact gradient computation. In this article, we take a step toward demystifying the performance and efficiency of such methods by focusing on the standard infinite-horizon linear–quadratic regulator problem for continuous-time systems with unknown state-space parameters. We establish exponential stability for the ordinary differential equation (ODE) that governs the gradient-flow dynamics over the set of stabilizing feedback gains and show that a similar result holds for the gradient descent method that arises from the forward Euler discretization of the corresponding ODE. We also provide theoretical bounds on the convergence rate and sample complexity of the random search method with two-point gradient estimates. We prove that the required simulation time for achieving $\epsilon$-accuracy in the model-free setup and the total number of function evaluations both scale as $\log \, (1/\epsilon)$.