19  Finite-Horizon MDPs and the Linear Quadratic Regulator

Lecture 19

Keywords

finite-horizon MDPs, linear quadratic regulator, LQR, Riccati equation, linearization

Based on the lecture by Andrew Ng — CS229, Stanford University, Autumn 2018.

Fitted value iteration (Section 18.4) handles continuous states by approximating the value function. This lecture finds the one important case where no approximation is needed: if the dynamics are linear and the reward quadratic, the value function is exactly quadratic, the optimal policy is exactly linear, and both come out of a short matrix recursion however many state variables there are. Getting there takes two small generalizations of the MDP first, rewards that depend on the action and a finite horizon, because the algorithm, the linear quadratic regulator (LQR), is most naturally a backward pass over a fixed number of time steps. Ng’s summary is that LQR applies to a narrow set of problems, but when it applies it is the algorithm to use.

19.1 Rewards that depend on the action

4:16 So far the reward has been a function of the state alone. Letting it depend on the action too, R:S×A→RR : S \times A \to \mathbb{R}, makes the payoff

R(s0,a0)+γR(s1,a1)+γ2R(s2,a2)+⋯ , R(s_0, a_0) + \gamma R(s_1, a_1) + \gamma^2 R(s_2, a_2) + \cdots,

and it lets a problem say that actions have costs. A robot in a maze can be charged for moving and nothing for standing still. A helicopter can be charged for yanking the sticks hard, which makes it jerk around. A route planner can charge each road segment its own cost, and a factory can price sending a maintenance crew differently from doing nothing. 5:55 Bellman’s equation changes in one visible way:

V∗(s)=max⁡a[R(s,a)+γ∑s′Psa(s′)V∗(s′)],(19.1) V^*(s) = \max_a \Bigl[ R(s, a) + \gamma \sum_{s'} P_{sa}(s') V^*(s') \Bigr], \tag{19.1}

with the max now outside the immediate reward, since that reward depends on the action being chosen. A student checks that the max covers the whole bracket, and it does. Value iteration uses Equation 19.1 as its update unchanged, and the optimal policy is the argmax of the same bracket. The reward depends on the current state and action, not on the next state. Ng notes that other formulations exist and this is one convenient one.

19.2 Finite horizons and policies that watch the clock

11:00 The second generalization replaces the discount factor with a horizon TT. The MDP runs for TT steps and then stops, and the payoff is the finite sum

R(s0,a0)+R(s1,a1)+⋯+R(sT,aT), R(s_0, a_0) + R(s_1, a_1) + \cdots + R(s_T, a_T),

usually without discounting, though discounting is still allowed. Ng’s example is a model helicopter with thirty minutes of fuel: the aim is to collect as much reward as possible before the clock runs out.

13:11 A finite horizon has a consequence that is easy to miss. The best action can depend on the time. Put a robot between a small +1+1 nearby and a large +10+10 farther off. With plenty of time it should go for the +10+10. With two or three steps left it should grab the +1+1, because the +10+10 is out of reach. So the optimal policy is written πt∗(s)\pi^*_t(s), and is called non-stationary. 15:46 Ng points out what was implicit until now: in the infinite-horizon discounted setting of lectures 16 and 17 the optimal policy is stationary, the same at every step, because the future always looks the same.

16:31 Once the policy may change over time, so may the world. A non-stationary MDP has Psa(t)P^{(t)}_{sa} and R(t)(s,a)R^{(t)}(s, a) indexed by time. Ng gives three examples. A long-haul airliner can burn a third of its take-off weight in fuel, so it handles differently on landing. A drive to San Francisco at 5 pm runs into rush hour, and into mud if the forecast says rain. And in a factory running round the clock, labour costs and availability change with the shift.

19.3 Solving it backwards

21:11 Define Vt∗(s)V^*_t(s) as the best expected payoff from state ss at time tt to the end. With nothing left after the last step, the base case is just the best immediate reward,

VT∗(s)=max⁡aR(s,a), V^*_T(s) = \max_a R(s, a),

23:27 and each earlier step looks one step ahead to the next:

Vt∗(s)=max⁡a[R(s,a)+∑s′Psa(s′)Vt+1∗(s′)],πt∗(s)=arg⁡max⁡a[⋯ ].(19.2) V^*_t(s) = \max_a \Bigl[ R(s, a) + \sum_{s'} P_{sa}(s') V^*_{t+1}(s') \Bigr], \qquad \pi^*_t(s) = \arg\max_a \Bigl[ \cdots \Bigr]. \tag{19.2}

This is no longer value iteration in the sense of repeating an update until it converges. It is dynamic programming: compute VT∗V^*_T, then VT−1∗V^*_{T-1} from it, then VT−2∗V^*_{T-2}, down to V0∗V^*_0, once each, and read πt∗\pi^*_t off at every step. Time-varying P(t)P^{(t)} and R(t)R^{(t)} slot into Equation 19.2 at no extra cost.

28:31 A student asks whether letting T→∞T \to \infty recovers ordinary value iteration. The two are closely related, but undiscounted sums can grow without bound as TT grows. That is one reason discounting exists. If ∣R∣≤Rmax⁡|R| \le R_{\max}, a discounted value is at most Rmax⁡/(1−γ)R_{\max}/(1-\gamma) in size, and a finite-horizon one at most (T+1)Rmax⁡(T+1) R_{\max}.

30:30 Ng sketches the +1+1/+10+10 corridor with deterministic moves. With two steps left, the values read like “10, 10, 10, 1, 1, 1, 0, 0, 0”: cells within reach of the +10+10, cells only within reach of the +1+1, and cells that can reach neither. He suggests building the little simulator to watch the policy change as the clock runs down. Figure 19.1 does that for an eleven-cell corridor of our own, with the +10+10 in cell 0, the +1+1 in cell 8, and a state-action reward of −0.1-0.1 for each move, so that it uses both of this lecture’s generalizations. The generator checks the dynamic programme against brute force over every action sequence up to seven steps. Cell 5 shows the non-stationarity in full. With one or two steps left it stays put, since nothing is reachable and moving costs. With three or four it heads right for the +1+1. With five or more it heads left for the +10+10.

Figure 19.1: The optimal action in each cell of a corridor, for each number of steps left, from one at the bottom to twelve at the top, with the optimal value in each square. Cell 0 holds +10+10, cell 8 holds +1+1, and each move costs 0.1. Where moving now and moving later tie, as they often do when waiting is free and nothing is discounted, the figure shows the move.

The figure’s caption hides one more lesson. Without discounting and with waiting free, many cells have several optimal actions. Leaving for the +10+10 now or one step later gives the same total if there is time either way. Discounting is what makes sooner strictly better.

19.4 The LQR model

32:04 LQR is a finite-horizon MDP with continuous states S=RnS = \mathbb{R}^n, continuous actions A=RdA = \mathbb{R}^d, and two specific assumptions. The first is that the dynamics are linear with Gaussian noise:

st+1=Ast+Bat+wt,wt∼N(0,Σw),(19.3) s_{t+1} = A s_t + B a_t + w_t, \qquad w_t \sim \mathcal{N}(0, \Sigma_w), \tag{19.3}

with A∈Rn×nA \in \mathbb{R}^{n \times n} and B∈Rn×dB \in \mathbb{R}^{n \times d}. 34:27 Ng apologises for the notation. AA is now both the set of actions and a matrix, because LQR comes from control theory in electrical and mechanical engineering and reinforcement learning from computer science, and when the two literatures met, their letters clashed. The same thing happens to VV below. 36:30 The second assumption is a quadratic reward,

R(s,a)=−(s⊤Us+a⊤Va),U⪰0,  V⪰0,(19.4) R(s, a) = -\bigl(s^\top U s + a^\top V a\bigr), \qquad U \succeq 0,\; V \succeq 0, \tag{19.4}

with U∈Rn×nU \in \mathbb{R}^{n \times n} and V∈Rd×dV \in \mathbb{R}^{d \times d} positive semi-definite, so both terms are costs. For a helicopter that should hover at the origin, U=IU = I and V=IV = I give R=−∥s∥2−∥a∥2R = -\lVert s \rVert^2 - \lVert a \rVert^2. That penalises drifting from the hover point and penalises large control inputs. Time-varying AtA_t, BtB_t, UtU_t, VtV_t are allowed but not needed for the derivation.

40:43 Where do AA and BB come from? The first way was lecture 18’s (Equation 18.1): fly the helicopter, log mm trajectories, and fit AA and BB by least squares. Ng says again that this gives a good model for slow flight.

19.5 Linearizing a nonlinear model

43:02 The second way starts from a nonlinear simulator st+1=f(st,at)s_{t+1} = f(s_t, a_t), from a physics engine or “a friend with a physics degree”. Ng tried the inverted pendulum’s equations himself and found them complicated. To make it linear, he draws the one-dimensional case. 45:31 Plot st+1=f(st)s_{t+1} = f(s_t) against sts_t, pick a point sˉt\bar s_t, and replace ff with its tangent line there:

st+1≈f(sˉt)+f′(sˉt) (st−sˉt). s_{t+1} \approx f(\bar s_t) + f'(\bar s_t)\,(s_t - \bar s_t).

49:05 The tangent is good near sˉt\bar s_t and poor far away, so sˉt\bar s_t should be where the system spends its time: the hover point for a helicopter, the upright pole at rest for the pendulum. 50:37 With an action as well, linearize around a typical pair (sˉt,aˉt)(\bar s_t, \bar a_t) using the Jacobians:

st+1≈f(sˉt,aˉt)+∇sf(sˉt,aˉt) (st−sˉt)+∇af(sˉt,aˉt) (at−aˉt).(19.5) s_{t+1} \approx f(\bar s_t, \bar a_t) + \nabla_s f(\bar s_t, \bar a_t)\,(s_t - \bar s_t) + \nabla_a f(\bar s_t, \bar a_t)\,(a_t - \bar a_t). \tag{19.5}

53:20 This is affine rather than linear, because of the constant terms. Ng’s fix is to add an intercept to the state, a component fixed at 1. Then Equation 19.5 takes the form st+1=Ast+Bats_{t+1} = A s_t + B a_t after “some algebraic munging”. When the linearization point is the origin and the system rests there, f(0,0)=0f(0, 0) = 0, as for the upright pendulum, the constants vanish and no intercept is needed.

Figure 19.2 does this for a pendulum on a motorised pivot, with the angle θ\theta measured from upright and a torque as the action. The only nonlinear term is gravity, (g/l)sin⁡θ(g/l)\sin\theta, and linearizing at θˉ=0\bar\theta = 0 replaces it with (g/l)θ(g/l)\theta. The generator checks the hand-derived AA and BB against finite differences. The line is 1% too strong at 0.25 rad, 4% at 0.5 rad, 19% at 1 rad and 50% at 1.5 rad. The right panel runs the LQR controller designed on the linear model on the true pendulum. From 0.3 rad the real and predicted trajectories coincide. From 1.4 rad they come apart by up to 0.11 rad, but the controller still brings the pole up. Feedback forgives a model that is wrong in the right direction. Because the measured state is fed back every step, the controller corrects its own model errors as they appear. In this toy, with unlimited torque, it recovers even from 3 rad. A real motor’s torque limit would end that long before.

Figure 19.2: Left: the pendulum’s gravity term (g/l)sin⁡θ(g/l)\sin\theta and its tangent at the upright position. Right: the pole angle under the LQR controller designed on the linear model, on the true pendulum (solid) and as the linear model predicts it (dashed), from three starting angles.

19.6 The value function is exactly quadratic

56:05 Now run the backward recursion Equation 19.2 on the LQR model. With continuous states, the sum over s′s' becomes an expectation over st+1∼N(Ast+Bat,Σw)s_{t+1} \sim \mathcal{N}(A s_t + B a_t, \Sigma_w). 57:07 The base case is immediate:

VT∗(sT)=max⁡aT[−sT⊤UsT−aT⊤VaT]=−sT⊤UsT, V^*_T(s_T) = \max_{a_T} \bigl[-s_T^\top U s_T - a_T^\top V a_T\bigr] = -s_T^\top U s_T,

because a⊤Va≥0a^\top V a \ge 0, so the best last action is aT=0a_T = 0. A student notices that s⊤Uss^\top U s is also non-negative. It is, but it cannot be chosen: only aTa_T is maximised over.

59:09 The inductive step carries the whole method. Suppose

Vt+1∗(s)=s⊤Φt+1s+Ψt+1 V^*_{t+1}(s) = s^\top \Phi_{t+1} s + \Psi_{t+1}

for some matrix Φt+1∈Rn×n\Phi_{t+1} \in \mathbb{R}^{n \times n} and scalar Ψt+1\Psi_{t+1}. This holds at t+1=Tt+1 = T with ΦT=−U\Phi_T = -U and ΨT=0\Psi_T = 0. 1:04:23 Then

Vt∗(st)=max⁡at[−st⊤Ust−at⊤Vat+Est+1∼N(Ast+Bat, Σw)[st+1⊤Φt+1st+1]+Ψt+1]. V^*_t(s_t) = \max_{a_t} \Bigl[ -s_t^\top U s_t - a_t^\top V a_t + \mathbb{E}_{s_{t+1} \sim \mathcal{N}(A s_t + B a_t,\, \Sigma_w)}\bigl[ s_{t+1}^\top \Phi_{t+1} s_{t+1} \bigr] + \Psi_{t+1} \Bigr].

The expectation of a quadratic under a Gaussian is a quadratic of the mean plus a constant, E[s⊤Φs]=μ⊤Φμ+tr⁡(ΣwΦ)\mathbb{E}[s^\top \Phi s] = \mu^\top \Phi \mu + \operatorname{tr}(\Sigma_w \Phi). So the bracket is a quadratic function of ata_t, and since Φt+1⪯0\Phi_{t+1} \preceq 0 and V⪰0V \succeq 0 it is concave. 1:06:57 Setting its derivative to zero gives

at∗=−(B⊤Φt+1B−V)−1B⊤Φt+1A  st=Lt st.(19.6) a^*_t = -\bigl(B^\top \Phi_{t+1} B - V\bigr)^{-1} B^\top \Phi_{t+1} A \; s_t = L_t\, s_t . \tag{19.6}

1:08:03 Ng stops on this. The optimal action is a linear function of the state. He stresses that this is not a function-approximation claim. Nobody fitted a line to the optimal action. Of all functions of the state, linear or not, the best one turns out to be linear. Substituting at∗a^*_t back into the bracket gives another quadratic in sts_t, which completes the induction. 1:09:45 The coefficients obey the discrete Riccati equations:

Φt=A⊤(Φt+1−Φt+1B(B⊤Φt+1B−V)−1B⊤Φt+1)A−U,Ψt=Ψt+1+tr⁡(ΣwΦt+1).(19.7) \begin{aligned} \Phi_t &= A^\top \Bigl( \Phi_{t+1} - \Phi_{t+1} B \bigl(B^\top \Phi_{t+1} B - V\bigr)^{-1} B^\top \Phi_{t+1} \Bigr) A - U, \\ \Psi_t &= \Psi_{t+1} + \operatorname{tr}\bigl(\Sigma_w \Phi_{t+1}\bigr). \end{aligned} \tag{19.7}

1:11:04 The whole algorithm is to set ΦT=−U\Phi_T = -U and ΨT=0\Psi_T = 0, then apply Equation 19.7 and Equation 19.6 for t=T−1t = T-1 down to 00, and finally act with πt∗(s)=Lts\pi^*_t(s) = L_t s. 1:14:08 What impresses Ng is that nothing in it is approximate. The approximation happens once, when a real system is forced into the form of a linear model with a quadratic cost, by regression or by linearization. After that, the value function really is quadratic and the policy really is linear, and the recursion computes both exactly.

The generator tests each claim by a second route on a cart with position and velocity at 10 Hz and a 60-step horizon. At 20 random times and states, a numerical maximisation of the Bellman bracket lands on LtsL_t s and on s⊤Φts+Ψts^\top \Phi_t s + \Psi_t to within 10−610^{-6}. None of 400 perturbed policies beats LtsL_t s, and half of them add nonlinear terms of the state and time.

WarningTwo signs the 2018 notes get wrong

cs229-notes13 prints the optimal action without the leading minus sign in Equation 19.6. It also prints Ψt=−tr⁡(ΣtΦt+1)+Ψt+1\Psi_t = -\operatorname{tr}(\Sigma_t \Phi_{t+1}) + \Psi_{t+1}, and the board in the lecture shows the same minus sign. Both are wrong, and the notes’ own footnote, E[w⊤Φw]=tr⁡(ΣΦ)\mathbb{E}[w^\top \Phi w] = \operatorname{tr}(\Sigma \Phi), gives the plus sign. The noise should make the value worse, and since Φt+1⪯0\Phi_{t+1} \preceq 0, only +tr⁡+\operatorname{tr} does that. Monte Carlo settles it. From s0=(1,0)s_0 = (1, 0) with Σw=0.25I\Sigma_w = 0.25 I, 4,000 rollouts of the cart under LtL_t average −168.8±1.1-168.8 \pm 1.1. Equation 19.7 predicts −170.4-170.4, and the printed sign predicts +152.3+152.3, a positive value for a problem whose rewards are all negative. The action’s sign matters even more. Without the minus, the controller pushes the cart away from the origin, and the payoff of a single noiseless run is −1.4×1014-1.4 \times 10^{14}. The notes also write BtB_t where Bt⊤B_t^\top is meant, and VtV_t and WtW_t for the same matrix.

NoteIn the official notes

Finite-horizon MDPs, LQR and linearization are cs229-notes13, sections 1, 2 and 3.1. Section 3.2 goes on to differential dynamic programming, which re-linearizes around a trajectory instead of a single point. Section 4 covers LQG, LQR when the state is observed only through noise, with the Kalman filter. The lecture covers neither.

19.7 The noise does not change the policy

1:15:22 Ng ends with a property he calls fun, and warns against generalizing. Look at what each quantity depends on. LtL_t in Equation 19.6 needs Φt+1\Phi_{t+1} but not Ψt+1\Psi_{t+1}, which makes sense: adding a constant to every future value cannot change which action is best. Φt\Phi_t in Equation 19.7 needs only Φt+1\Phi_{t+1}. 1:17:36 The noise covariance Σw\Sigma_w appears in exactly one place, the update for Ψ\Psi. Delete the Ψ\Psi line from the code and the optimal policy is computed perfectly without Σw\Sigma_w ever being used. The optimal LQR policy does not depend on the noise. The value does: a helicopter in a gale does worse than one in still air. But the best response to any state is the same in both.

Figure 19.3 shows both effects on the cart. The gains computed with Σw=0\Sigma_w = 0 and with Σw=0.25I\Sigma_w = 0.25 I are identical to the last bit, while Ψ0\Psi_0 goes from 0 to −161.4-161.4. The figure also shows the finite horizon at work. For the first half of the horizon the gain is flat at L≈(−2.76,−2.51)L \approx (-2.76, -2.51), a stationary policy in all but name. Over the last 25 or so steps it relaxes to zero, because there is less and less future in which a correction would pay off. That is the clock-watching of Figure 19.1 in continuous form.

Figure 19.3: The two entries of the LQR gain LtL_t for the cart, on position and on velocity, against the time step for a 60-step horizon. Lines are for Σw=0\Sigma_w = 0; circles, drawn every third step, are for Σw=0.25I\Sigma_w = 0.25 I.

1:19:00 Ng draws two lessons. The narrow one is that, when applying LQR, there is no need to work hard at estimating Σw\Sigma_w. The broader one is about practice. For most MDPs the noise does change the policy, and the form of the noise matters. But in his experience of building robots, remembering to add noise matters more than getting its size exactly right. Ten per cent more or less rarely matters; a factor of two often does. That is the same advice as lecture 18’s (Section 18.3), now with one case where it can be proved.