Linear Quadratic Regulator (LQR)

Contents

• Notation
• Discrete-time Time-Varying Finite-Horizon Linear System
• LQR
• Deriving the Optimal LQR Controller
  • Inductive Step
  • Standard LQR
  • Non-Symmetric Cost Matrices
• Summary
• Discussion
  • Linear Dynamics with Constant
  • Closed-Loop vs. Open-Loop
  • Constrained LQR
  • Other Related Topics
• References

Notation

Let \(\Sym^n\) denote the set of symmetric matrices in \(\R^{n \times n}\). Also, superscripts are interpreted after subscripts: \(M_x^\top\) denotes \((M_x)^\top\), and \(M_x^{-1}\) denotes \((M_x)^{-1}\).

Discrete-time Time-Varying Finite-Horizon Linear System

Consider a discrete-time time-varying finite-horizon linear system:

• finite-horizon: \(t = 1, \dotsc, T\)
• states: \(s_t \in \R^n\)
• actions: \(a_t \in \R^m\)
• random noise: \(w_t \in \R^n\), \(\E[w_t] = 0\), each \(w_t\) is independent
  • The only assumption on the random vector \(w_t\) is that it has zero mean. No other assumptions are made about its distribution.
  • \(w_t\) and \(w_k\) need not be drawn from the same distribution, for \(t \neq k\).
• dynamics: \(s_{t+1} = A_t s_t + B_t a_t + w_t\) for some given matrices \(A_t \in \R^{n \times n}\) and \(B_t \in \R^{n \times m}\)
  • An equivalent formulation is \(s_{t+1} = F_t x_t + w_t\) where \(F_t = \begin{bmatrix} A_t & B_t \end{bmatrix}\) and \(x_t = \sa[t]\).
• instantaneous cost function \(c_t(s,a): \R^n \times \R^m \to \R\)
  • The cost functions \(c_t\) for \(t = 1, \dotsc, T-1\) are known as the stage cost.
  • The cost \(c_T\) at the final time step is called the terminal cost.

The overall goal, given a starting state \(s_0\), is to find a sequence of actions \(a_t\) to minimize the total expected cost

For each time step \(t\), the \(q\)-function and value function are defined as

The value function is also known as the optimal cost-to-go, sometimes denoted as \(J_t^*(s)\).

Thus, the minimum expected cost is

LQR

LQR, short for “linear quadratic regulator,” refers to the optimal controller for a linear system with quadratic costs. This post analyzes the discrete-time finite-horizon case, although similar results hold for continuous-time systems and infinite time horizons as well.

The standard (canonical) LQR cost function is \(c_t(s,a) = s^\top Q_t s + a^\top R_t a\) for some given matrices \(Q_t \in \Sym^n\) and \(R_t \in \Sym^m\) with \(Q_t \succeq 0\) and \(R_t \succ 0\).

In standard LQR, the minimum instantaneous cost is achieved by \(s, a = 0\). Furthermore, this is a fixed point in the linear system dynamics. Therefore, the optimization objective is essentially to find a series of actions that moves the state closer and closer to the origin.

A more general case is

given \(\delta_t \in \R\), \(D_t = \begin{bmatrix} Q_t & S_t^\top \\ S_t & R_t \end{bmatrix} \in \Sym^{n+m}\) where \(D_t, Q_t \succeq 0\) and \(R_t \succ 0\), and \(d_t = \begin{bmatrix} d_{t,s} \\ d_{t,a} \end{bmatrix} \in \R^{n+m}\).

Setting \(S_t = 0\) and \(d_t = 0\) yields the standard LQR cost function.

Here, \(A_t\), \(B_t\), \(D_t\), and \(d_t\) are assumed to be known for all \(t = 0, \dotsc, T\). When these quantities are not known in real-world settings, they can usually be estimated by first collecting some state transitions from an arbitrary policy.

Deriving the Optimal LQR Controller

The derivation of the optimal LQR controller is inductive. It relies on the following lemma, which shows that in a linear system with a quadratic cost function, the optimal action \(a^*\) is a linear function of the state \(s\), and the optimal cost function \(c^*\) is a quadratic function of \(s\).

Lemma 1: Consider the function \(c: \R^n \times \R^m \to \R\) given by

where \(\delta \in \R\), \(D = \begin{bmatrix} Q & S^\top \\ S & R \end{bmatrix} \in \Sym^{n+m}\) with \(D, Q \succeq 0\) and \(R \succ 0\), and \(d = \begin{bmatrix} d_s \\ d_a \end{bmatrix} \in \R^{n+m}\). Then \(c(s,a)\) is minimized by setting

where \(K = -R^{-1} S\) and \(k = -\frac{1}{2} R^{-1} d_a\). Plugging \(a^*\) into the cost function yields the optimal cost function

where \(Z = Q + S^\top K\) is positive semidefinite, and \(z = 2 S^\top k + d_s\). The term \(\text{const} = \delta - \frac{1}{4} d_a^\top R^{-1} d_a\) is constant with respect to the state \(s\) and action \(a\).

Inductive Step

The inductive derivation of the LQR works backwards from the final time step \(t=T\) down to \(t=0\). Consider the inductive hypothesis that \(q_t\) has the form

for some vector \(p_t\) and symmetric matrix \(P_t = \begin{bmatrix} P_{t,s} & P_{t,as}^\top \\ P_{t,as} & P_{t,a} \end{bmatrix}\) with \(P_t, P_{t,s} \succeq 0\) and \(P_{t,a} \succ 0\). The scalar \(\lambda_t\) is constant with respect to the state \(s\) and action \(a\).

Notation: For the rest of this section, the subscript \(t\) is dropped from variables to reduce notational clutter. Every variable that is not written with a subscript is understood to have a subscript \(t\). Variables with subscripts other than \(t\) are written with the appropriate subscript.

The base case \(q_T(s,a) = c_T(s,a) = x^\top D_T x + d_T^\top x + \delta_T\) clearly satisfies the inductive hypothesis with \(P_T = D_T\), \(p_T = d_T\), and \(\lambda_T = \delta_T\).

For the inductive step, suppose that the hypothesis holds for some time step \(t+1\). By Lemma 1, the optimal value function at time \(t+1\) is

where \(Z_{t+1} \succeq 0\) and \(z_{t+1}\) are functions of \(P_{t+1}\) and \(p_{t+1}\). The constant term is \(\text{const} = \lambda_{t+1} - \frac{1}{4} d_{t+1,a}^\top (P_{t+1,a})^{-1} d_{t+1,a}\).

If \(s_{t+1} = A s + B a + w = F x + w\), then

where \(P = D + F^\top Z_{t+1} F\) and \(p = d + F^\top z_{t+1}\). The first equation for \(\E_w[v_{t+1}(s')]\) uses the assumption that \(\E[w] = 0\); the second equality absorbs \(\E_w[w^\top Z_{t+1} w]\) into \(\text{const}_w\) because it is constant with respect to states and actions. The constant term is therefore

Since \(D, Z_{t+1} \succeq 0\), it follows that \(P \succeq 0\). The block matrix form of \(P\) is

which implies \(P_a = R + B^\top Z_{t+1} B \succ 0\) because \(R \succ 0\) and \(Z_{t+1} \succeq 0\).

This shows that \(q_t(s,a)\) satisfies the inductive hypothesis, which gives a backwards recursion:

• For the final time step \(t = T\):

  \[\begin{aligned} P_T &= D_T & p_T &= d_T \\ K_T &= -R_T^{-1} S_T, & k_T &= -\frac{1}{2} R_T^{-1} d_{T,a} \\ Z_T &= Q_T + S_T^\top K_T, & z_T &= 2 S_T^\top k_T + d_{T,s} \end{aligned}\]

• For \(t = T-1, \dotsc, 0\):

  \[\begin{aligned} P &= D + F^\top Z_{t+1} F, & p &= d + F^\top z_{t+1} \\ K &= -P_a^{-1} P_{as}, & k &= -\frac{1}{2} P_a^{-1} p_a \\ Z &= P_s + P_{as}^\top K, & z &= 2 P_{as}^\top k + p_s \end{aligned}\]

This can be simplified further by defining \(Z_{T+1} = \zero_{n \times n}\) and \(z_{T+1} = \zero_n\). Then the equations above hold for all \(t = T, \dotsc, 0\).

Additionally, it is common to expand out the recursion equations (which removes the need for explicitly constructing \(P\) and \(p\)). In particular, the expression for \(Z\) is known as the discrete-time Ricatti equation.

Finally, to solve for actions \(a_t\), apply forward recursion. For \(t = 0, \dotsc, T\):

The optimal controller defined by the matrices \(K_t\) and vectors \(k_t\) is known as the linear quadratic regulator (LQR). Note that the optimal controller \((K_t, k_t)\) does not depend on the actual observed state \(s_t\). As long as the future noise variables \(w_t\) are independently distributed with mean 0, then the sequence of controllers \(\{(K_t, k_t)\}_{t=0}^T\) is always optimal.

Standard LQR

Consider the standard LQR setting where \(S = 0\), \(d = 0\), and \(\delta = 0\), so the cost function at each step is simply

(As in the previous section, the subscript \(t\) is dropped to reduce notational clutter. All variables that are written without a subscript are understood to implicitly have a subscript \(t\).)

For the inductive hypothesis, suppose that \(z_{t+1} = 0\). The base case is satisfied with \(z_{T+1} = 0\). Then the recursion vectors all become 0:

The recursion matrices simplify to

and the optimal action from any state \(s_t\) at time \(t\) is \(a_t = K_t s_t\). In this case, the linear quadratic regulator is the set of matrices \(\{K_t\}_{t=0}^T\).

Furthermore, if we assume \(\E[w w^\top] = \Sigma\) (for example, \(w \sim \mathcal{N}(0, \Sigma)\)), then

so \(\lambda = \tr(\Sigma Z_{t+1}) + \lambda_{t+1}\). Applying Lemma 1 to \(q_t(s,a)\), the value function at each time step is precisely

with base case \(\lambda_T = 0\) and \(v_T(s) = c_T^*(s) = s^\top Q_T s\).

If there is no randomness in the state transitions (i.e., \(w_t = 0\) always), then \(\E_w\left[ w^\top Z_{t+1} w \right] = 0\) so \(v_t(s) = s^\top Z s\).

Non-Symmetric Cost Matrices

In the setup above, it was assumed that \(D_t, Q_t \succeq 0\) and \(R_t \succ 0\). However, this requirement can in fact be generalized a bit. By Lemma 2 below, it suffices that

satisfy \(D_t + D_t^\top \succeq 0\), \(Q_t + Q_t^\top \succeq 0\), and \(R_t + R_t^\top \succ 0\).

Lemma 2: For any square matrix \(M \in \R^{n \times n}\) and vector \(x \in \R^n\),

In other words, \(x^\top M x\) can always be replaced with an equivalent expression \(x^\top \hat{M} x\) where \(\hat{M} = \frac{1}{2} (M + M^\top)\) is symmetric.

Summary

Consider a discrete-time finite-horizon linear dynamical system

where the goal is to choose actions \(a_t\) (\(t=0, \dotsc, T\)) that minimize quadratic costs

Define the \(q\)-functions and value functions

In the inductive step, I showed that if

for some matrix \(P_t\), vector \(p_t\), and scalar \(\lambda_t\), then

In addition, \(q_{t-1}\) and \(v_{t-1}\) have the same form as \(q_t\) and \(v_t\), and I derived recursive formulas for \(P_t, p_t, Z_t, z_t\) in terms of the given cost matrices for all \(t = T, \dotsc, 0\). In particular, the equation for \(Z_t\) is known as the Ricatti equation.

Finally, given \(P_t, p_t\), I showed how to compute \(K_t, k_t\) such that the optimal action from any state \(s_t\) is

The set of controllers \(\{(K_t, k_t)\}_{t=0}^T\) form the linear quadratic regulator (LQR). Importantly, the LQR is optimal from any state \(s\) and does not depend on the noise distribution for the \(w_t\). The optimal policy is always the same, as long as \(w_t\) has zero mean!

Discussion

Linear Dynamics with Constant

In some settings, the system dynamics are expressed as

with an additional constant vector \(C \in \R^n\). This can actually be re-written as a standard linear dynamical system as

This reformulation is commonly used when linearizing nonlinear dynamical systems.

Closed-Loop vs. Open-Loop

This post presented the discrete-time finite-horizon unconstrained LQR problem and provided a recursive (a.k.a. dynamic programming) approach to finding the optimal controller. Because the recursive controller

depends on the actual state \(s_t\) to decide the next action \(a_t\), this controller is a “closed-loop” controller; the state influences the next action, creating a feedback loop.

However, it is also possible to formulate this unconstrained LQR problem as one-shot quadratic optimization problem, sometimes known as the “batch” or “least-squares” approach. This results in an “open-loop” controller, because the control actions \(a_t\) for all time steps are treated as optimization variables and solved for simultaneously.

Sources

• For the “batch” / “least-squares” formulation of the unconstrained LQR problem, see slides from either Stanford EE363 (2008-09), Lecture 1 or Caltech CS159 (2020-21), Lecture 2.

Constrained LQR

The setting presented above assumes that all states \(s_t \in \R^n\) and \(a_t \in \R^m\) are allowed. However, many real-world control problems have constraints on the states and/or actions:

With state and input constraints, Lemma 1 no longer applies, so the recursion equations no longer hold.

If the state and input constraints are polytopes, then the constrained LQR problem can still be formulated as a quadratic optimization problem. However, the dynamic programming approach is more involved.

Sources

• See the Caltech CS159 (2020-21), Lecture 2 slides for more information on the quadratic problem formulation.
• See Borelli et al. (2016) textbook (Chapters 11.3.3 and 17.6) for more details on the dynamic programming approach.

Other Related Topics

Linearization and Differential Dynamic Programming (DDP)

Let \(s_{t+1} = f_t(s,a)\) express the system dynamics. LQR works when \(f\) is a linear function. If \(f\) is a differentiable and continuous nonlinear function, it can be approximated by a Taylor series expansion. Linearization requires choosing a point \((s,a)\) around which to linearize \(f_t\).

In some problems, if the initial state and a desired ending state are close, then choosing either of those points (or something in between) may suffice. For example, in the standard LQR setting, the desired end state is typically the origin, and often the objective is to simply keep the system centered around the origin.

In general, though, it may be unclear what point to choose for linearization. One strategy is simply to choose random points \((s_t^{(0)}, a_t^{(0)})\) around which to linearize each \(f_t\). After solving the LQR problem, then the optimal points \((s_t^{(1)}, a_t^{(1)})\) from the LQR solution can be used as the new points for linearization. This process can be repeated until some stopping criterion (e.g., a maximum number of iterations, or convergence).

However, linearization generally does not result in cost nor stability guarantees.

Linear Quadratic Gaussian (LQG)

LQR can be further generalized to the partially observable Markov decision process (POMDP) setting. Instead of observing the states \(s_t\), suppose that we only observe a random vector \(y_t\) whose conditional distribution depends on \(s_t\). Specifically, the problem of minimizing a quadratic cost function

with the system described by

is called the linear-quadratic-Gaussian (LQG) control problem. In this problem, only the \(y_t\) variables are observed, even though the underlying system dynamics and cost function are in terms of the unobserved state vectors \(s_t\).

As with vanilla LQR, there exists a recursive derivation of the optimal LQG controller, not too different from the standard LQR controller.

Continuous and infinite-horizon

Even though I only provided derivation for the finite-horizon discrete-time setting, the results are similar for continuous-time and infinite-horizon settings. Essentially, the sum in the cost function is replaced by an integral, and the discrete-time algebraic Ricatti equation is replaced by a continuous-time Ricatti differential equation.

References

• UC Berkeley CS285 (2020), Lecture 10
  • the original slides (sadly riddled with many typos) which inspired this blog post
  • presents the general LQR setting without noise
• Stanford CS229 (2018) Lecture Notes
  • covers standard LQR with Gaussian noise, linearization of dynamics, DDP, and a simplified version of the linear quadratic Gaussian problem
• Stanford EE363 (2008-09) Lecture Notes
  • Lecture 1 presents dynamic programming and least-squares solutions to the standard LQR problem without noise
  • Lecture 5 presents the standard LQR problem with Gaussian noise
• Caltech CS159 (2020-21), Lecture 2
  • presents the standard LQR setting without noise
  • includes batch approach to solving constrained LQR and discussion on linearization of nonlinear systems
• Predictive Control for Linear and Hybrid Systems by Borelli et al. (2016). Available here.
  • all-around good reference
  • covers the standard LQR setting with and without noise and goes in-depth into both batch and recursive controllers for constrained and nonlinear problems