LQR through the Lens of First Order Methods: Discrete-time Case

Abstract

We consider the Linear-Quadratic-Regulator (LQR) problem in terms of optimizing a real-valued matrix function over the set of feedback gains. Such a setup facilitates examining the implications of a natural initial-state independent formulation of LQR in designing first order algorithms. It is shown that this cost function is smooth and coercive, and provide an alternate means of noting its gradient dominated property. In the process, we provide a number of analytic observations on the LQR cost when directly analyzed in terms of the feedback gain. We then examine three types of well-posed flows for LQR: gradient flow, natural gradient flow and the quasi-Newton flow. The coercive property suggests that these flows admit unique solutions while gradient dominated property indicates that the corresponding Lyapunov functionals decay at an exponential rate; we also prove that these flows are exponentially stable in the sense of Lyapunov. We then discuss the forward Euler discretization of these flows, realized as gradient descent, natural gradient descent and the quasi-Newton iteration. We present stepsize criteria for gradient descent and natural gradient descent, guaranteeing that both algorithms converge linearly to the global optima. An optimal stepsize for the quasi-Newton iteration is also proposed, guaranteeing a $Q$-quadratic convergence rate--and in the meantime--recovering the Hewer algorithm.

Cited by in corpus (20)

• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• On the Optimization Landscape of Dynamic Output Feedback Linear Quadratic Control
• First Order Methods For Globally Optimal Distributed Controllers Beyond Quadratic Invariance
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Policy Gradient-based Algorithms for Continuous-time Linear Quadratic Control
• Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon
• Combining Model-Based and Model-Free Methods for Nonlinear Control: A Provably Convergent Policy Gradient Approach
• Optimization Landscape of Policy Gradient Methods for Discrete-time Static Output Feedback
• Optimization Landscape of Gradient Descent for Discrete-time Static Output Feedback
• Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent
• Global Convergence of Policy Gradient Primal-dual Methods for Risk-constrained LQRs
• Derivative-Free Policy Optimization for Linear Risk-Sensitive and Robust Control Design: Implicit Regularization and Sample Complexity
• Policy Optimization for Markovian Jump Linear Quadratic Control: Gradient-Based Methods and Global Convergence
• Primal-dual Learning for the Model-free Risk-constrained Linear Quadratic Regulator
• Robust Reinforcement Learning: A Case Study in Linear Quadratic Regulation
• Lossless Convexification and Duality
• On the Optimization Landscape of Dynamic Output Feedback: A Case Study for Linear Quadratic Regulator
• Model-Free $\mu$ Synthesis via Adversarial Reinforcement Learning