Homework 3

You are welcome (and encouraged) to work with others, but each individual must submit their own writeup.

You are welcome to use your preferred computational toolkit – upload the commented sourcecode alongside your writeup.

You are welcome to consult research articles and other materials – upload a .pdf of the article alongside your writeup and indicate which references were used where in the writeup.

Markov decision process (MDP) (14 pts)

Let \((X,U,P,c)\) be an MDP:

\(X\) is a finite set of \(N\) states;
\(U\) is a finite set of \(M\) actions;
\(P:X\times U\rightarrow \Delta(X)\) specifies transition probabilities;
\(c:X^T\times U^T\rightarrow \mathbb{R}\) specifies trajectory cost on time interval \(T\subset[0,\infty)\).

Recall that \(\Delta(S) = \{p : S \rightarrow [0,1] : \sum_{s\in S} p(s) = 1\}\) is the set of probability distributions over the finite set \(S\).

Implement an algorithm that generates a random MDP given finite sets \(X\) and \(U\) (i.e. let \(N = |X|\), \(M = |U|\) be parameters that are easy to vary, and generate \(P\) and \(c\) randomly).
Implement an algorithm that simulates an MDP (i.e. write a function that inputs transition probabilities \(P\), cost \(c\), initial state distribution \(p_0\), policy \(\pi:X\rightarrow\Delta(U)\), and time horizon \(t\) and returns the state distribution \(p_t\)).
Test your algorithm from (b.) (i.e. design one or more tests, explain why these tests are exhaustive, and provide summary statistics and/or visualizations that convince a skeptical reader that your algorithm is correct).

Let us now consider the problem of minimizing the infinite-horizon exponentially-discounted cost \[c(x,u) = \sum_{t=0}^\infty \gamma^t \mathcal{L}(x_t,u_t),\] where \(\gamma\in(0,1)\) is a discount factor.

Any policy \(\pi : X\rightarrow\Delta(U)\) has an associated value \(v^\pi : X\rightarrow\mathbb{R}\) defined by \[\forall x\in X : v^\pi(x) = E[c \mid x = x_0]\] that satisfies the Bellman equation \[\forall x\in X : v^\pi(x) = \sum_{u\in U}\pi(u|x)\sum_{x^+\in X} P(x^+|x,u)\left[\mathcal{L}(x,u) + \gamma \cdot v^\pi(x^+)\right].\]

Noting that \(v^\pi\) appears linearly in this Bellman equation, implement a policy evaluation* algorithm that computes \(v^\pi\) using linear algebra (i.e. determing \(L\) and \(b\) such that \(L v^\pi = b\) and use this equation to solve for \(v^\pi\)).*
Test your policy evaluation algorithm from (d.) (i.e. design one or more tests, explain why these tests are exhaustive, and provide summary statistics and/or visualizations that convince a skeptical reader that your algorithm is correct).
Using your policy evaluation algorithm from (d.), implement value iteration* and policy iteration algorithms.*
Test your value iteration and policy iteration algorithms from (f.) (i.e. design one or more tests, explain why these tests are exhaustive, and provide summary statistics and/or visualizations that convince a skeptical reader that your algorithm is correct).

linear quadratic regulation (6 pts)

Consider the linear-quadratic regulation (LQR) problem for the discrete-time linear time-invariant system \[x^+ = A x + B u\] with infinite-horizon cost \[c(x,u) = \frac{1}{2}\sum_{t=0}^\infty x^T Q x + u^T R u\] where \(Q = Q^T > 0\) and \(R = R^T > 0\). We know that the optimal policy is linear in state, \[u = - K x,\] where \(K = (R + B^T Y B)^{-1} (B^T Y A)\) and \(Y\) satisfies the discrete algebraic Riccati equation \[Y = A^T Y A - (A^T Y B)(R + B^T Y B)^{-1}(B^T Y A) + Q.\]

For this problem, we’ll consider a one-dimensional system, so \(x,u\in\mathbb{R}\), with the values \(A, B, Q, R = 1\).

If the state distribution starts out Gaussian, \[x \sim \mathcal{N}(\xi, \Sigma),\] and we apply zero input but add a state disturbance with zero mean and covariance \(W\), then (so long as the disturbance is uncorrelated with the state) the state distribution after one step is Gaussian: \[x^+ \sim \mathcal{N}(A\xi, A\Sigma A^T + W),\] i.e. the covariance gets updated via \[\Sigma^+ = A\Sigma A^T + W.\] Since \(A\) is stable, so long as \(W\) is constant, this iteration will converge to a solution of the Lyapunov equation \[S = A S A^T + W.\] Also, since \(A\) is stable, the steady-state mean is zero, thus we can determine the steady-state distribution in closed-form: \[\lim_{t\rightarrow\infty} x(t) \sim \mathcal{N}(0, S).\]

In this problem, you’ll make use of the facts above to build a finite MDP that approximates the LQR, solve the MDP using your algorithms from the previous problem, then make use of the facts above again to validate the solution you’ve obtained.

Construct a finite MDP by discretizing the state and action spaces of the linear system and computing transition probabilities and transition costs to obtain \((X,U,P,C)\) where:

\(X\) is a finite set of \(N\) states;
\(U\) is a finite set of \(M\) actions;
\(P:X\times U\rightarrow \Delta(X)\) specifies transition probabilities;
\(c:X^T\times U^T \rightarrow \mathbb{R}\) specifies trajectory costs on time horizon \(T\subset[0,\infty)\).

Compare the steady-state distribution of the MDP with the steady-state distribution of the linear system subject to zero-mean disturbance with covariance \(W\). Discuss how the comparison varies with respect to \(|X|\).

Now consider the problem of minimizing the infinite-horizon discounted cost \[c(x,u) = \sum_{t=0}^\infty \gamma^t \mathcal{L}(x_t,u_t),\] where \(\gamma\in(0,1]\) is a discount factor.

The un-discounted case \(\gamma = 1\) corresponds exactly to LQR; unfortunately, policy iteration won’t converge when \(\gamma = 1\)! So you’ll need to choose \(\gamma\) close (but not equal) to \(1\).

Compare the optimal value and control for the MDP obtained using value or policy iteration with the optimal value and control for the original LQR problem. Discuss how the comparison varies with respect to \(|X|\), \(|U|\), and \(\gamma\).

paper / project presentation (4 pts)

You will give a combined paper / project presentation during the final two weeks of class meetings.

The paper presentation constitutes 30% of the course grade.

The project constitutes 50% of the course grade, with the project presentation constituting 1/5 of that portion, so 10% of the course grade.

The presentations will be evaluated according to a simple rubric: what did we learn, and how do we know we learned it? Your goal should be to (i) teach us something new (i.e. not covered in the course) and (ii) provide simple examples or exercises we can use to assess our understanding. You should endeavor to adopt the notation and terminology from lecture (this may require translation from source material), and all new concepts and techniques must be defined and explained.

Each presenter will be allotted 15min of lecture time, including answering questions that arise during or after the presentations – there will be a hard stop after 15min. To satisfy this constraint while maximizing your expected grade, you should prepare < 10min of material for the paper portion of the presentation and < 5min of material for the project presentation. (Hint: you probably need to prepare less material than you expect – to calibrate, I encourage you to practice your presentations with a colleague who actively asks questions.)

Update your availability in the shared document accessible via Canvas -> Collaborations.
Specify whether you are planning a solo or group project – if group, specify your group members.