Convergence and Sample Complexity of Gradient Methods for the Model-Free Linear-Quadratic Regulator Problem

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 nat...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2022-05, Vol.67 (5), p.2435-2450
Main Authors: Mohammadi, Hesameddin, Zare, Armin, Soltanolkotabi, Mahdi, Jovanovic, Mihailo R.
Format: Article
Language:English
Subjects:
Complexity
Complexity theory
Continuous time systems
Control theory
Convergence
Data-driven control
Differential equations
Dynamic stability
Flow stability
gradient descent
Gradient flow
gradient-flow dynamics
Heuristic algorithms
linear–quadratic regulator (LQR)
Mathematical model
Mathematical models
Model accuracy
model-free control
nonconvex optimization
Optimal control
Optimization
Ordinary differential equations
Parameters
Polyak–Łojasiewicz inequality
Random search method
Regulators
reinforcement learning (RL)
sample complexity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2021.3087455