Study plan

The course is one idea told six ways: pick actions now by thinking about the cost they cause later. MPC does it online over a short window, DP solves it exactly backwards in time, infinite-horizon DP removes the end of time, approximate DP cuts the computation, and RL learns it from data without a model.

9-day plan

Tick items as you finish them. Ticks are saved in this browser only.

Notation you will see everywhere

01 · Model Predictive Control

MPC is a feedback controller that, at every time step, solves a small optimisation problem: "given where I am now, what is the best plan for the next N steps?" It applies only the first move of that plan, then measures again and re-plans.

1.1 The setup

1.2 What Q, R and Q_F do

Only the ratio matters for the shape of the response. With \(R=\rho I\): small ρ (Q large relative to R) ⇒ fast convergence with large inputs; large ρ ⇒ slow convergence with small inputs. The notes show this with a double integrator (ρ = 0.3 vs ρ = 10): the input and output energies \(J_{in}\) and \(J_{out}\) trade off along a curve.

1.3 Receding horizon optimisation

1. Measure the current state \(x_k\).
2. Solve \(\vec u^*_k=\arg\min_{\vec u\in\mathbb U^N}J(x_k,\vec u)\): a full N-step plan.
3. Apply only the first element: \(u_k=u^*_{k|k}=[I_m\ 0\ \cdots\ 0]\,\vec u^*_k\).
4. Move to k+1, measure \(x_{k+1}\), and solve again over a window shifted one step forward.

Because it re-solves from the measured state each time, MPC is a feedback law \(u_k=\kappa(x_k)\), even though each optimisation produces an open-loop sequence. In general \(u^*_{k+1|k}\neq u^*_{k+1|k+1}\): the plan made at k for time k+1 is not what is applied at k+1.

Comments from the notes: MPC works for nonlinear, constrained, even stochastic or simulation-based models. Longer N is usually better (considers long-term impact) but costs more computation; moderate N is often close to infinite-horizon performance. Nonlinear models need numerical optimisation. Integral action can be added by penalising increments \(u_{k+\ell+1|k}-u_{k+\ell|k}\). With both state and input constraints the problem can become infeasible.

1.4 LTI system, quadratic cost: the explicit solution

With constraints (on position gaps, velocity, acceleration, input) the problem becomes a quadratic programme: \(\min_{\vec u}\ \vec u^\top H\vec u+\vec u^\top f\) subject to \(A_{in}\vec u\le B_{in}\), \(A_{eq}\vec u=B_{eq}\). Constraints on predicted states are converted to constraints on \(\vec u\) by substituting \(\vec x=\Phi\vec u+\Lambda x_k\) (the notes build them with Kronecker products, e.g. \(\mathbf 1_N\otimes[1\ 0\ 0]\) picks out the position).

Discretisation: double integrator \(A=\begin{bmatrix}1&\Delta t\\0&1\end{bmatrix}\), \(B=\begin{bmatrix}\Delta t^2/2\\ \Delta t\end{bmatrix}\). In general \(\begin{bmatrix}A&B\\0&I\end{bmatrix}=\exp\!\Big(\begin{bmatrix}A_c&B_c\\0&0\end{bmatrix}T_s\Big)\).

1.5 Stability (optional in notes, good for theory marks)

1.6 Case study: vehicle platooning (optional)

Each car: \(\dot p=v,\ \dot v=a,\ \dot a=-a/\tau+u/\tau\) (τ ≈ 1.5 actuation lag). Track the gap error \(e_{i,k}=x_{i-1,k}-x_{i,k}\), which has the same dynamics \(e_{k+1}=Ae_k+B\bar u_k\), with \(u_i=u_{i-1}-\bar u_i\). Infinite-horizon LQR (DARE) ignores constraints: in the notes vehicle 3 crashes into vehicle 2 and speeds reach 288 km/h. MPC adds \(p_{min}=3\) m, \(0\le v\le25\) m/s, \(-6\le a\le3\) m/s² and solves a QP, so the cars keep their gaps and respect the speed limit.

02 · Deterministic Dynamic Programming

DP solves a multi-stage decision problem by solving it backwards from the end. The best decision at every state and every time comes out of one backward sweep.

2.1 Principle of optimality

2.2 Example: shortest path

Define dist(X) = minimum cost from X to E. Work backwards from the goal:

Optimal route S → C → D → E, cost 6. Notice the greedy first step (S → A costs only 1) is wrong. DP sees that A leads to an expensive tail. Unlike A*, DP is guaranteed optimal with no heuristic needed.

2.3 The DP algorithm

2.4 LQR solved by DP

03 · Stochastic Dynamic Programming

Now the next state depends on a random disturbance: \(x_{k+1}=f_k(x_k,u_k,w_k)\). We can't control exactly where we go, so we minimise the expected cost and choose a policy (a rule) instead of a fixed list of actions.

3.1 Policies, not sequences

A policy is \(\pi=\{\mu_0,\dots,\mu_{N-1}\}\) with \(u_k=\mu_k(x_k)\). It uses the state we will actually observe later, so it reacts to the noise that happened. For stochastic systems policies typically beat fixed sequences. For deterministic systems they are equivalent. We minimise

Assumption: \(w_k\)'s distribution may depend on \(x_k,u_k\) but not on earlier w's.

3.2 The stochastic DP algorithm

The only change from tab 02 is the expectation. If \(u_k^*=\mu_k^*(x_k)\) minimises the right side for every x and k, then \(\pi^*=\{\mu_0^*,\dots\}\) is optimal. You can compute the policy offline and store it, or store \(J_k\) and minimise online.

3.3 LQR with noise and with packet dropouts

3.4 Markov Decision Processes

04 · Infinite Horizon Dynamic Programming

For systems that run "forever" (continuing tasks), we discount future costs. The optimal policy then stops depending on time: one rule for all k. Two algorithms find it: Value Iteration and Policy Iteration.

4.1 Discounted cost

• α = 0: myopic, only today's cost counts. α near 1: far-sighted, future costs matter almost as much (and algorithms converge more slowly).
• Discounting keeps the infinite sum finite: if \(|g|\le M\) then \(|J|\le M/(1-\alpha)\). Useful identity: \(\sum_{k\ge0}\alpha^k=\frac1{1-\alpha}\). Example: cost 1 every step with α = 0.9 ⇒ total 10.
• Key recursive property: \(J_\pi(x_0)=\mathbb E\{g(x_0,\mu(x_0),w_0)\}+\alpha J_\pi(x_1)\). Today's cost plus the discounted cost from tomorrow.
• For shortest-path problems that end in finite time, α = 1 is allowed.

4.2 Bellman's equation

\(J^*\) is the fixed point of the Bellman operator \(TJ(x)=\min_u\mathbb E\{g+\alpha J(f)\}\). The minimising u at each x is the optimal stationary policy \(\mu^*\). For a fixed policy μ: \(J_\mu=T_\mu J_\mu\), i.e. \(J_\mu(i)=g(i,\mu(i))+\alpha\sum_jp_{ij}(\mu(i))J_\mu(j)\).

4.3 Value Iteration (VI)

4.4 Policy Iteration (PI)

1. Policy evaluation (critic): for the current policy μ, solve the linear equations \(J_\mu=g_\mu+\alpha P_\mu J_\mu\), i.e. \(J_\mu=(I-\alpha P_\mu)^{-1}g_\mu\). Or iterate \(J_{\mu,k+1}=g_\mu+\alpha P_\mu J_{\mu,k}\) until it settles.
2. Policy improvement (actor): \(\mu^{new}(i)=\arg\min_u\{g(i,u)+\alpha\sum_jp_{ij}(u)J_\mu(j)\}\).
3. If the policy didn't change, stop: it is optimal. Otherwise go to 1.

There are finitely many policies and each iteration improves, so PI stops in finitely many steps. For the Rover with α = 0.96 it converges within 2 improvements (notes, Table 1): μ = (0,0,0) → (0,1,0) → (0,1,1).

4.5 VI vs PI

Variants: limit the number of evaluation sweeps in PI (optimistic/truncated PI). Asynchronous methods update only some states each step (e.g. those visited often), which suits real-time use. Average-cost problems minimise \(\lim\frac1N\mathbb E\sum g\) (optional).

Rover results: α = 0.9 ⇒ μ = (T:0, R:1, B:0), same as the N = 3 finite-horizon policy. α = 0.96 ⇒ μ = (0, 1, 1): when you value the future more, it becomes worth driving up from the bottom.

05 · Approximate Dynamic Programming

Exact DP needs \(J_k\) for every state, which is impossible for big problems. Instead, use an approximation \(\tilde J\) of the cost-to-go and choose actions by a one-step (or multi-step) lookahead. This loses guaranteed optimality but gains speed.

5.1 Approximation in value space

No backward pass: the controls are computed going forward, because \(\tilde J\) is assumed available. If \(\tilde J=J\) exactly, you get the optimal control. The better \(\tilde J\), the better the policy. \(\tilde J\) can come from intuition (a heuristic), from rollout, or from a trained parametric model.

5.2 Rollout

5.3 Stochastic problems and certainty-equivalent control

5.4 Multistep lookahead and truncated rollout

Look ℓ steps ahead instead of one: optimise \(u_k,\mu_{k+1},\dots,\mu_{k+\ell-1}\) for \(\mathbb E\{\sum_{j=k}^{k+\ell-1}g_j+\tilde J_{k+\ell}(x_{k+\ell})\}\), apply only the first control, and repeat (exactly the MPC idea). Large ℓ compensates for a poor \(\tilde J\) but costs more computation. Truncated rollout: run the base policy for ℓ−1 steps, then add a terminal approximation \(\tilde J_{k+\ell}\). If ℓ is large, \(\tilde J=0\) often works. For infinite horizon: \(\tilde\mu(x)\in\arg\min_u\mathbb E\{g(x,u,w)+\alpha\tilde J(f(x,u,w))\}\).

5.5 Parametric approximation

06 · Reinforcement Learning

Everything so far needed a model (f or p_ij). RL learns good actions directly from experience: try an action, see the cost and the next state, and nudge a table of estimates. These are tabular methods for finite states and actions.

The traditional alternative is system identification (fit a model from data, then use MPC/DP). RL skips the explicit model. It is also called neuro-dynamic programming.

6.1 Temporal-difference (TD) prediction

6.2 Action-value functions (Q-factors)

6.3 Sarsa (on-policy)

Uses the quintuple (x, u, g, x′, u′): State, Action, Reward, State, Action. Here u′ is the action actually taken next. Algorithm 1: measure x, pick u (ε-greedy); loop: apply u, observe g and x′, pick u′ (ε-greedy), update Q(x,u), set x←x′, u←u′. Only the visited entry changes. Terminal states start (and stay) at Q = 0.

6.4 Exploration: ε-greedy

With probability 1−ε pick the greedy action \(\arg\min_uQ(x,u)\) (exploit). With probability ε pick a random action (explore). Since the random pick can also land on the greedy action, P(greedy) = 1 − ε + ε/|U|. ε usually decreases over time, e.g. \(\varepsilon_k=1/k\) or \(\max(1/k,0.01)\). Without exploration some actions are never tried and their Q stays wrong.

6.5 Q-learning (off-policy)

Same as Sarsa except the target uses the best next action, not the one taken. It learns \(Q^*\) (the greedy policy's values) while behaving ε-greedily. That makes it off-policy: the policy being learned differs from the policy being followed. Sarsa learns the values of the policy it actually follows (on-policy), including its exploration, so it tends to be more cautious.

6.6 Convergence conditions

• Every (x,u) pair visited infinitely often (enough exploration).
• Learning rate: \(\delta_k>0,\ \sum_k\delta_k=\infty,\ \sum_k\delta_k^2<\infty\). Example: \(\delta_k=1/k\) works. Constant δ fails the second condition. \(1/k^2\) fails the first (it stops learning too early).
• For Sarsa to reach \(Q^*\), the policy must become greedy in the limit (ε → 0). With constant ε, Sarsa converges to the Q of the ε-greedy policy.
• In the Rover experiments: δ = 0.1, \(\varepsilon_k=\max(1/k,0.01)\), 500 episodes of 1000 steps, with Q carried between episodes.

6.7 Bigger problems and caveats

For large spaces use \(\hat Q(x,u;r)\) (e.g. a neural network) and minimise the squared TD error \(\mathbb E\{(g+\alpha\min_u\hat Q(x',u;r)-\hat Q(x,u;r))^2\}\) by gradient descent. This is deep RL (DQN). Convergence of learning does not guarantee closed-loop stability, because learning and plant dynamics are coupled and discounting doesn't force stability. Use expert knowledge (features, known dynamics) and don't learn what you already know.

Your practicals as exam lessons

Each of your six practical submissions (P1–P6) taught by hand: what the problem was, the equation behind the code you wrote, your results and why they came out that way, a hand-sized version you can do on paper, and exam questions drawn from it.

Mock exam built from your practicals

A second full paper in the same shape as 2024 (3 questions, 100 marks): MPC in words, stochastic DP by hand, then a learning algorithm by hand. Every question is a variation on something you did in P1–P6. Sit it in exam time with only the cheatsheet, then open the solutions.

Question 1 · Model Predictive Control (25 marks)

A gantry crane cart moves along a 12 m track and carries a load modelled as a rigid rod. The state is \(x=[p,\ v,\ \theta,\ \omega]^\top\) and the input is the motor force u. The cart starts at rest at p = 2 m and must stop with no swing at p = 10 m within 10 s. The cart is rated to 3 m/s, the motor gives at most 100 N, and for safety the load must not swing more than 10° or faster than 50°/s. The controller samples at T_s = 0.1 s.

Question 2 · Stochastic dynamic programming (40 marks)

(a) Parking. A driver passes street parks k = 0, 1, 2. Each is free with probability ρ = 0.5, independently. At a free park the driver may park at cost s(k) = 3 − k or drive on at cost c = 0.4; at a full park the driver must drive on (cost c). If no park has been taken after k = 2, the driver must use the multi-storey car park at cost S = 3, so J₃(·) = 3.

(b) Random road closure. From A, Tom chooses East (reaches B with probability 0.6, otherwise C) or West (reaches D with probability p, otherwise E), learning which only at the fork. Leg costs: A→B 333, A→C 282, A→D 230, A→E 300; B→F 553, B→G 280; C→F 470, C→G 404; D→F 268, D→G 606; E→F 807, E→G 370; F→H 450, G→H 603.

Question 3 · Q-learning vs SARSA (35 marks)

A small cliff problem. States 1 (start), 2 (cliff edge), 3 and 4 (safe route), G (goal, terminal, Q(G,·) = 0). Moves: 1–A→2, 1–B→3, 2–A→G, 2–B→1 (falls off, reward −100), 3–A→4, 3–B→1, 4–A→G, 4–B→3. Every move other than the fall gives reward −1. Use learning rate δ = 0.5, discount α = 0.9, Q-table initialised to 0, and the pre-sampled ε-greedy episodes

ep1 = 1 –A→ 2 –B→ 1 –B→ 3 –A→ 4 –A→ G    ep2 = 1 –A→ 2 –B→ 1 –A→ 2 –A→ G

2024 Exam: full worked solutions

Written as you would answer in the exam, with marks in mind. Read the question, try it yourself, then compare.

Question 1 · MPC (25 marks)

Cost \(J(x_k,\vec u)=\sum_{l=0}^{N-1}(x^\top_{k+l|k}Qx_{k+l|k}+u^\top_{k+l|k}Ru_{k+l|k})+x^\top_{k+N|k}Q_Fx_{k+N|k}\).

(a) Role of Q, Q_F and R; how they shape control actions and the closed-loop response (10)

(b) Main idea behind receding horizon optimisation (15)

Question 2 · Stochastic DP (40 marks)

\(x_{k+1}=x_k+u_k+w_k\), \(\mathbb E w_k=0\), \(\mathbb E w_k^2=\sigma^2\), \(\mathbb E\{x_kw_k\}=\mathbb E\{u_kw_k\}=0\), N = 3, \(g_N=\beta x_N^2\), \(g_k=\beta x_k^2\), β > 0.

(a) Cost-to-go functions, optimal controls, J₀(x₀) (25)

(b) Find β so that J₀(x₀) = 1 (15)

Question 3 · Sarsa on the UAV network (35 marks)

(a) Computational process and Q-table (25)

(b) Optimal sequence from 1 to 4 (10)

Practice questions with answers

21 questions covering all six topics, in the style of the 2024 paper. Attempt each on paper first, then open the answer. All numbers have been checked by computer.

Model Predictive Control

Deterministic DP

Stochastic DP

Infinite Horizon DP

Approximate DP

Reinforcement Learning

Exam cheatsheet

Every formula, algorithm, key number and answer recipe from the six topics, plus the key results from your six practicals (section 9), on two A4 pages.