Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator

By Maryam Fazel, Rong Ge, Sham M. Kakade, Mehran Mesbahi. International Conference on Machine Learning, 2018

718 citations recorded by the source corpus.

Direct policy gradient methods for reinforcement learning and continuous control problems are a popular approach for a variety of reasons: 1) they are easy to implement without explicit knowledge of the underlying model 2) they are an "end-to-end" approach, directly optimizing the performance metric of interest 3) they inherently allow for richly parameterized policies. A notable drawback is that even in the most basic continuous control problem (that of linear quadratic regulators), these methods must solve a non-convex optimization problem, where little is understood about their efficiency from both computational and statistical perspectives. In contrast, system identification and model based planning in optimal control theory have a much more solid theoretical footing, where much is known with regards to their computational and statistical properties. This work bridges this gap showing that (model free) policy gradient methods globally converge to the optimal solution and are efficient (polynomially so in relevant problem dependent quantities) with regards to their sample and computational complexities.

Subfields: Computational Theory and Mathematics, Control and Systems Engineering, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/9c0b482314dc8c10875b217b86cc5df5a4fe4bdf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Control and Systems Engineering

In Statistical and Nonlinear Physics

Citations in the corpus

Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator (2018, methodology): “[9] for policy gradient optimization on LQR can be applied to prove convergence of PGD on the OFU subroutine, which would provide an optimal polynomial-time algorithm.”
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes (2019, background): “A variant of this result also appears in Theorem 2 of Scherrer and Geist [2014], which itself can be viewed as a generalization of the approach in Kakade and Langford [2002]. In contrast to CPI [Kakade and Langford, 2002] and the more general boosting-based approach in Scherrer and Geist [2014], we ”
CAQL: Continuous Action Q-Learning (2019, background): “Moreover, at least with linear function approximation (Melo & Ribeiro, 2007), under reasonable assumptions, Q-learning converges to optimality, while such optimality guarantees for non-convex policy-based methods are generally limited (Fazel et al., 2018).”
Provably Efficient Maximum Entropy Exploration (2018, background): “the Linear Quadratic Regulators (Bertsekas, 2005), (Fazel et al., 2018)), one may only appeal to the recent empirical successes of sample-based planning algorithms that rely on the power of non-linear function approximation.”
Provably Efficient Exploration in Policy Optimization (2019, methodology): “Our work is based on the aforementioned line of recent work (Fazel et al., 2018; Yang et al., 2019a; Abbasi-Yadkori et al., 2019a,b; Bhandari and Russo, 2019; Liu et al., 2019; Agarwal et al., 2019; Wang et al., 2019) on the computational eﬃciency of policy optimization, which covers PG, NPG, TRPO,…”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, methodology): “…square, generative adversarial imitation learning for linear quadratic regulator (LQR) dynamics [Cai et al., 2019], and potentially many others in adversarial learning [Du et al., 2019], robust phase retrieval [Sun et al., 2018, Zhou et al., 2016], robust control [Fazel et al., 2018], and etc.”
Reward Learning for Efficient Reinforcement Learning in Extractive Document Summarisation (2019, background): “Many RL algorithms have been proven to be δ -convergent, including value-based RL [Sutton et al. , 2009], actor-critic [Sutton et al. , 1999] and policy gradient [Fazel et al. , 2018].”
On the Sample Complexity of the Linear Quadratic Regulator (2017, methodology): “egret setting in terms of prediction error. As mentioned previously, converting prediction error bounds into concrete bounds on sub-optimality of control performance is an open question. Fazel et al. [21] show that randomized search algorithms similar to policy gradient can learn the optimal control”
Recent advances in reinforcement learning in finance (2021, methodology): “For a theoretical analysis of RL algorithms within the LQ framework, see for example [75] and [111] for the global linear convergence of policy gradient methods in LQR problems with infinite and finite horizon, respectively.”
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift (2019, background): “More broadly, it is worth noting the global convergence of policy gradients for Linear Quadratic Regulators [Fazel et al., 2018] also goes through a similar proof approach of gradient domination.”
Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms (2021, background): “For instance, many require that the MDP admits a linear approximation [6–8], or that the model is precisely Linear Quadratic Regulator (LQR) [9–11].”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, background): “For example, it has been proven to be true for objectives of over-parameterized deep networks [16], learning LQR models [19], phase retrieval [54], and many other simple problems discussed in [30].”
Observational Overfitting in Reinforcement Learning (2019, methodology): “Furthermore, in terms of gradient dynamics and optimization, LQR readily possesses nontrivial qualities compared to linear regression, as the LQR cost is a non-convex function but all of its minima are global minima (Fazel et al., 2018).”