Title: II Optimisation and Control

Q: The principle of optimality
A: \begin{thm}[The principle of optimality]
Define the functions
\[
G(U_{t-1}, t) = \inf_{u_t,u_{t+1},\cdots,u_{h-1}} G(U_{h-1}).
\]
Then these obey the recursion
\[
G(U_{t-1}, t) = \inf_{u_t} G(U_t, t + 1) \quad (t < h),
\]
with terminal evaluation $G(U_{h-1}, h) = G(U_{h-1})$.
\end{thm}
\begin{proof}
Swapping the order of minima:
\[
G(U_{t-1}, t) = \inf_{u_t}  \left[ \inf_{u_{t+1},...,u_{h-1}} G(U_{h-1}) \right] = \inf_{u_t} G(U_t, t + 1).
\]
\end{proof}

Q: Dynamic Programming (Bellman) Equation
A: In the state-structured case, the state variable $x$ obeys a plant equation (or law of motion)
 \[
x_{t+1} = a(x_t, u_t, t)
\]
and the cost function $C=C_0$ is separable, given by
\[
C_t = \sum_{\tau=t}^{h-1} c(x_\tau, u_\tau, \tau) + C_h(x_h)
\]
with minimum (called the \emph{value function})
\[
F(x, t) = \inf_{u_t,\cdots u_{h-1}} C_t.
\]
The optimality equation is then
\[
F(x, t) = \inf_u [c(x, u, t) + F(a(x, u, t), t + 1)] \quad (t < h).
\]

Q: Bang-bang control
A: When the dynamics are linear, the optima are extrema. We consume nothing or everything.

Q: Optimisation of consumption
A: In year $t$, an investor receives annual income $x_t$, consumes $u_t$ and adds $x_t-u_t$ to his capital ($0\leq u_t\leq x_t$) earning interest at rate $\theta$ such that
\[
x_{t+1} =x_t + \theta(x_t-u_t).
\]
His total consumption is
\[
C= \sum_{t=0}^{h-1} u_t.
\]
Let $F_s(x)$ be the max reward attainable from state $x=x_s$ with \emph{time to go} $s=h-t$, i.e. for $s\geq 1$:
\[
F_s(x) = \max_{0\leq u \leq x} \left[ u + F_{s-1}(x+\theta(x-u))\right]
\]
and $F_0(x)=0$. By back substitution $F_1(x)=x, F_2(x)=\max[1+\theta, 2]x$, motivating ansatz $F_{s-1}(x) = \rho_{s-1}(x)$. Substituting in (and using linearity)
\[
F_s(x) = \max_{0\leq u \leq x} \left[ u + \rho_{s-1}(x+\theta(x-u))\right] = \max [(1+\theta)\rho_{s-1}, 1+\rho_{s-1} ]x.
\]
So $\rho_s = \rho_{s-1} + \max[\theta\rho_{s-1}, 1]$ is verified. Therefore
\[
\rho_s = \begin{cases}
s \quad & s\leq s^* \\
(1+\theta)^{s-s^*}s^* \quad & s> s^*
\end{cases}
\]
where $s^*$ is the least integer such that $\theta s \geq 1$, i.e. $s^*=\lceil \frac{1}{\theta} \rceil$.
This maximum is obtained by investing for years $t<h-s^*$ and consuming for years $t\geq h-s^*$.

Q: MDP
A: Let $X_t = (x_0,\cdots x_t)$ and $U_t = (u_0, \cdots u_t)$ denote $x$ and $u$ histories at time t. A \emph{Markov decision process} has the Markov dynamics
\[\]
\P(x_{t+1} | X_t, U_t) = \P(x_{t+1} | x_t, u_t).
A \emph{Markov decision problem} has a separable (or decomposable) cost function.
We assume perfect state observation, i.e. $x_t$ is known when choosing $u_t$. Hence $W_t = (X_t, U_{t-1})$ is known at time $t$.
The future minimal expected cost is
\[\]
F(W_t) = \inf_\pi \E_\pi[C_t | W_t]
where $\pi$ denotes a policy.

Q: MDP equation
A: The DP equation becomes
\[
F(x_t, t) = \begin{cases}
\inf_{u_t} \lbrace c(x_t, u_t, t) + \E[ F(x_{t+1}, t+1) | x_t, u_t ]\rbrace \quad & (t<h) \\
C_h(x_h) \quad & (t=h).
\end{cases}
\]

Q: Optimal exercise of American options
A: Assume strike price $p$, expiry time $h$, stock price $x_t$ where $x_{t+1}=x_t+\varepsilon_t$, $\varepsilon_t$ are iid and $\E|\varepsilon|<\infty$. The value function $F_s(x)$ obeys
\begin{enumerate}
\item $F_s(x)$ is increasing in $s$
\item $F_s(x)-x$ is decreasing in $x$
\item $F_s(x)$ is increasing in $x$
\item $F_s(x)\geq x-p$
\item $F_s(x)$ is continuous in $x$.
\end{enumerate}
Moreover $\exists(a_s)\uparrow$ such that we exercise when $x\geq a_s$.
\begin{proof}
The DP equation is
\[
F_s(x) =
\begin{cases}
\max \lbrace x-p, \E[F_{s-1}(x+\varepsilon)] \rbrace & (s\geq 1) \\
\max\{ x-p, 0\} & (s=0).
\end{cases}
\]
\begin{enumerate}
\item Check $F_1(x)=\max \{ x-p, \E F_0(x+\varepsilon)\} \geq \max \{ x-p, 0\}=F_0(x)$, then
\[
F_s(x) = \max \lbrace x-p, \E[F_{s-1}(x+\varepsilon)] \rbrace \geq  \max \lbrace x-p, \E[F_{s-2}(x+\varepsilon)] \rbrace= F_{s-1}(x) .
\]
\item $F_0(x)-x=\max\{ -p, -x\}$ is decreasing and this follows through
\[
F_s(x) - x = \max\lbrace -p, \E[F_{s-1}(x+\varepsilon)-(x+\varepsilon)] +\E[\varepsilon] \rbrace.
\]
\end{enumerate}
(iii)-(iv) are immediate from the DP equation and (v) follows from (ii)-(iii). Then (ii) and (iv) imply
\[
F_s(x) \begin{cases}
> x- p \quad & (x<a_s) \\
= x-p \quad & (x \geq a_s).
\end{cases}
\]
(i)$\implies (a_s)\uparrow$.
\end{proof}

Q: Marriage problem
A: You interview $h$ candidates. Let $x_t=\mathbbm{1}[\text{ cand } t \text{ best of first } t]$ and $F(t-1)$ the probability of selecting the best candidate given that we passed on the first $t-1$. The DP equation for $F$ is
\[
F(t-1) = \frac{t-1}{t}F(t) + \frac{1}{t} \max\left\lbrace \frac{t}{h}, F(t) \right\rbrace =\max\left\lbrace \frac{t-1}{t}F(t)+\frac{1}{h}, F(t) \right\rbrace.
\]
So $F(t-1)\geq F(t)$. Since $t/h$ is increasing and $F(t)$ is decreasing, for $t$ large $F(t)\leq t/h$ . Let $t_0=\min\{ t: F(t)\leq t/h \}$. Then
\[
F(t-1)=\begin{cases}
F(t_0)  & t < t_0 \\
\frac{t-1}{t}F(t) + \frac{1}{h} & t \geq t_0.
\end{cases}
\]
By back-substitution, using $F(h)=0$, for $t\geq t_0$:
\[
\frac{F(t-1)}{t-1} = \frac{1}{h(t-1)} + \frac{F(t)}{t}=\cdots = \frac{1}{h(t-1)} + \frac{1}{ht} + \cdots + \frac{1}{h(h-1)}
\]
so
\[
F(t-1) = \frac{t-1}{h}\sum_{\tau=t-1}^{h-1} \frac{1}{\tau} \quad t\geq t_0.
\]
In particular
\[
F(t_0) / (t_0/h) = \sum_{\tau=t_0}^{h-1} \frac{1}{\tau} \leq  1.
\]
For large $h$ the sum is about $\log(h/t_0)\approx 1$ (by minimality) so $t_0\approx h/e$.
Hence we choose the best after the first $1/e$ of the candidates giving $F(0)=F(t_0)\sim t_0/h\approx 1/e$.

Q: Serial job scheduling
A: There are $n$ jobs to complete where job $i$ has processing time $t_i$ and reward $r_i$. Let $S_k$ be the uncompleted jobs and $|S_k|=k$. The DP equation is
\[
F_k(S_k) = \max_{i\in S_k} \left[ r_i\beta^{t_i} + \beta^{t_i}F_{k-1}(S_k \setminus\{ i \}) \right]
\]
for $k\geq 1$ and $F_0(\emptyset)=0$.
We solve by an interchange argument. Consider
\begin{align*}
F_k((i,j), S_k) &= \beta^{t_i} r_i + \beta^{t_i+t_j} r_j + \beta^{t_i+t_j} F_{k-2}(S_k\setminus\{ i, j \}) \\
F_k((j, i), S_k) &= \beta^{t_j} r_j + \beta^{t_i+t_j} r_i + \beta^{t_i+t_j} F_{k-2}(S_k\setminus\{ i, j \}).
\end{align*}
By comparison
\[
F_k((i,j), S_k) < F_k((j, i), S_k) \iff \frac{\beta^{t_i} r_i}{1-\beta^{t_i}} < \frac{\beta^{t_j} r_j}{1-\beta^{t_j}}.
\]
Hence the optimal policy must schedule jobs in decreasing order of the \emph{index}
\[
\frac{\beta^{t_i} r_i}{1-\beta^{t_i}} .
\]
Alternatively, the Gittins Index is
\[
G_i = \frac{r_i\beta^{t_i}}{(1-\beta^{t_i}) / (1-\beta)}.
\]

Q: Infinite-horizon cost
A: The discounted $s$-horizon cost is
\[
F_s(\pi, x) = \E_\pi\left[\left. \sum_{t=0}^{s-1} \beta^t c(x_t, u_t) \right| x_0 = x\right]
\]
with DP equation
\[
F_s(x)= \inf_u \left\lbrace c(x,u) + \beta\E[F_{s-1}(x_1) | x_0=x, u_0=u]\right\rbrace.
\]
The infinite-horizon cost is naturally defined as
\[
F(\pi, x) = \lim_{s\to\infty} F_s(\pi, x) = \E_\pi\left[\left. \sum_{t=0}^{\infty} \beta^t c(x_t, u_t) \right| x_0 = x\right]
\]
and satisfies
\[
F(\pi, x) =c(x,u) + \beta\E[F(\pi, x_1) | x_0=x, u_0=u].
\]
The (possibly infinite) limit is guaranteed to exist in the following 3 cases:
\begin{enumerate}
\item D (discounted programming): $0<\beta<1$, $|c|<B$.
\item N (negative programming): $0<\beta\leq 1$, $c \geq 0$.
\item P (positive programming): $0<\beta\leq 1$, $c\leq 0$.
\end{enumerate}
Note N, P are named for maximising a reward. D implies convergence by comparison with geometric series and N,P by monotonicity.

Q: Optimality equation in the infinite-horizon case
A: Assume D, N or P holds. Then $F(x)$ satisfies the DP equation
\[
F(x) = \inf_u \left\lbrace c(x,u) + \beta\E[F(x_1) | x_0=x, u_0=u]\right\rbrace
\]
\begin{proof}
($\geq$) For $\pi$ choosing $u_0=u$ when $x_0=x$:
\begin{align*}
F(\pi, x) &= c(x,u) + \beta\E[F(\pi, x_1) | x_0=x, u_0=u] \\
&\geq c(x,u) + \beta\E[F(x_1) | x_0=x, u_0=u] \\
&\geq \inf_u \left\lbrace c(x,u) + \beta\E[F(x_1) | x_0=x, u_0=u]  \right\rbrace.
\end{align*}
($\leq$) Given $\varepsilon>0$, let $\pi$ follow $\pi^1$ after reaching $x_1$ such that $F(\pi^1, x_1)< F(x_1) + \frac{\varepsilon}{\beta} $. Then
\begin{align*}
F(x) &\leq F(\pi, x) \\
 &= c(x,u) + \beta\E[F(\pi^1, x_1) | x_0=x, u_0=u] \\
&\leq c(x,u) + \beta\E\left[\left.F(x_1) + \frac{\varepsilon}{\beta} \right| x_0=x, u_0=u\right] \\
&\leq c(x,u) + \beta\E[F(x_1)| x_0=x, u_0=u]  + \varepsilon.
\end{align*}
Taking the infimum of the RHS over $u$ and $\varepsilon$ gives the result.
\end{proof}

Q: Selling an asset
A: Each day, a speculator receives an offer with pdf $g(y), y\geq 0$. Let the state be $x=\mathbbm{1}[\text{asset owned}]$. The DP equation is then
\begin{align*}
F(1) &= \int_{y=0}^\infty \max[y, \beta F(1)]g(y) \; \d y \\
(1-\beta) F(1) &= \int_{y=0}^\infty \max[y-\beta F(1), 0]g(y) \; \d y \\
&= \int_{y=\beta F(1)}^\infty (y-\beta F(1)) g(y) \; \d y.
\end{align*}
Now the LHS, RHS are increasing, decreasing in $F(1)$. Hence it has a unique root $F(1)=F^*$. We sell if $y\geq \beta F^*$ and the supremal reward is $F^*$.

Q: Non-existence of optimal policy
A: Suppose states are $0,1,2\ldots$ and in state $x\geq 1$ we may either move to state $x+1$ and receive no reward, or move to absorbing state 0 and obtain reward $1-\frac{1}{x}$. The DP equation is $F(0)=0$ and for $x\geq 1$:
\[
F(x) = \max \left\{ 1 - \frac{1}{x}, F(x+1)\right\}.
\]
In particular $F(x)\geq 1 - \frac{1}{x}$. By translation $F(x+1)\geq 1 - \frac{1}{x+1} > 1 - \frac{1}{x}$. Substituting back in gives $F(x+1) = F(x)$. That is, $F$ is constant.
We can bound the reward by
\[
1-\frac{1}{x} \leq F(1) \leq 1
\]
for all $x\geq 0$. Letting $x\to \infty$ gives $F(1)=1$. So $F(1) > 1 - \frac{1}{x}$ for all $x\geq 1$, i.e. the value function is greater than any possible reward.

Q: Sufficient condition for optimal policy: P case
A: Suppose $P$ or $D$ holds and $\exists\pi$ satisfying the DP equation
\[
F(\pi, x) = \sup_u \left\{ r(x,u) + \beta\E[F(\pi, x_1) | x_0 = x, u_0=u]\right\}.
\]
Then $\pi$ is optimal.
\begin{proof}
Let $\pi'$ be any policy, choosing controls $u_0, u_1, \cdots$ as the state evolves through $x_0, x_1 \cdots$. Then
\[
F(\pi, x_0) \geq r(x_0,u_0) + \beta\E_{\pi'} [F(\pi, x_1) | x_0].
\]
By repeated substitution into itself $s$ times
\[
F(\pi, x) \geq \E_{\pi'}\left[\left.\sum_{t=0}^{s-1} \beta^t r(x_t,u_t)\right| x_0\right] + \beta^s\E_{\pi'} [F(\pi, x_s) | x_{0}].
\]
In case $P$ the final term is non-negative and in $D$ it will vanish. Letting $s\to\infty$ gives $F(\pi, x) \geq F(\pi', x)$.
\end{proof}

Q: Timid strategy
A: With wealth $i$, we can bet $j\leq i$. Then with probability $p\geq \frac{1}{2}$ this increases to $i+j$ and $q=1-p$ decreases to $i-j$. Let 0 and $N$ be absorbing. Also $r(N)=1$. The DP equation is
\[
F(i) = \max_{j\in \{1,2,\cdots i \} } \left\{ pF(i+j) + qF(i-j)\right\}.
\]
Let $\pi$ always pick $j=1$. Write $G(i)=F(\pi,x)$. Then $G(i)=pG(i+1)+qG(i-1)$ with $G(0)=0, G(N)=1$. This recurrence gives (writing $\lambda=\frac{q}{p}$):
\[
G(i) = \begin{cases}
\frac{1-\lambda^i}{1-\lambda^N} \quad & p \neq \frac{1}{2} \\
\frac{i}{N} \quad & p = \frac{1}{2}.
\end{cases}
\]
If $p=\frac{1}{2}$, then $G(i) = \frac{i}{N}$ clearly satisfies the DP equation.
If $p>\frac{1}{2}$, then we must verify that $G(i) = \max_{j\leq i } W_j$ where
\[
W_j = p\left[ \frac{1-\lambda^{i+j}}{1-\lambda^N}\right] + q \left[ \frac{1-\lambda^{i-j}}{1-\lambda^N}\right]= \frac{p}{1-\lambda^N} \left(1-\lambda^{i+j} + \lambda (1-\lambda^{i-j})\right).
\]
Subtracting gives
\[
W_j - W_{j+1} = \frac{p}{1-\lambda^N} \left(\lambda^{i+j+1} - \lambda^{i+j} + \lambda^{i-j}-\lambda^{i-j+1}\right) =  \frac{p\lambda^{i-j}(1-\lambda)}{1-\lambda^N} \left(1 - \lambda^{2j} \right).
\]
So $W_{j+1}<W_j$ and $j=1$ maximises $W_j$ with $W_1=G(i)$.

Q: Value Iteration (successive approximation)
A: Suppose that D,P, or NF hold. Then we can swap limits, i.e. $F_\infty(x):=\lim_{s\to\infty} F_s(x) = \lim_{s\to\infty} \mathcal{L}^s(0) = F(x)$ where $F_s=\mathcal{L}F_{s-1}$, is the finite horizon DP equation.
\begin{proof}
The limit exists by monotonicity or geometric bound.
($\leq$) For any particular $\pi$:
\[
F_\infty(x) = \lim_{s\to\infty}\inf_\pi F_s(\pi,x) \leq \lim_{s\to\infty} F_s(\pi,x) = F(\pi, x).
\]
Taking infima gives $F_\infty(x) \leq F(x)$.
($\geq$) In case P, $c(x,u)\leq 0$ so $F_s(x)\geq F(x)$. Let $s\to\infty$.
In case D, let $s\to\infty$ in the bound
\[
F(x) \leq F_s(x) + \frac{\beta^sB}{1-\beta}.
\]
In case NF, by finiteness and MCT (as $F_s\nearrow$):
\begin{align*}
F_\infty(x) &= \lim_{s\to\infty} \min_u \left\{ c(x,u) + \E[F_{s-1}(x_1) | x_0=x, u_0=u]\right\} \\
&=  \min_u \left\{ c(x,u) + \lim_{s\to\infty}\E[F_{s-1}(x_1) | x_0=x, u_0=u]\right\} \\
&=  \min_u \left\{ c(x,u) + \E[F_{\infty}(x_1) | x_0=x, u_0=u]\right\}.
\end{align*}
Let $\pi$ minimise the RHS. By repeated substitution
\[
F_\infty(x) = \E_\pi\left[\left. \sum_{t=0}^{s-1} c(x_t, u_t) + F_\infty(x_s) \right| x_0=x\right].
\]
As N implies $F_\infty\geq 0$, this gives $F_\infty(x) \geq F(\pi, x) \geq F(x)$.
\end{proof}

Q: Discounted case is equivalent to N/P
A: Suppose $|c|<B$. Construct the dual P problem with $\tilde c(x,u) = c(x,u) - B$. Then for any $\pi$
\[
\tilde F(\pi, x) = F(\pi, x) - \frac{B}{1-\beta}.
\]
So the optimal policy is unchanged.

Q: Bernoulli Bandits
A: Drug 1 has known probability $p$ of success. Drug 2 has prior $\Theta\sim U[0,1]$, $s$ successes and $f$ failures. The posterior is $\Theta\sim\mathrm{Beta}(s+1,f+1)$ with mean $\bar\theta=\frac{s+1}{s+f+2}$. Since resorting to drug 1 is an irreversible decision, the DP equation is
\[
F(s,f) = \max \left\{ \frac{p}{1-\beta}, \bar\theta(1+\beta F(s+1, f)) + (1-\bar\theta)\beta F(s, f+1) \right\}.
\]
This can be computed by value iteration. Alternatively, if $s+f >> 1$, then $\bar\theta\approx \theta=$ constant. Therefore
\[
F= \max \left\{ \frac{p}{1-\beta}, \bar\theta(1+\beta F )+ (1-\bar\theta)\beta F \right\}= \max \left\{ \frac{p}{1-\beta}, \bar\theta+ \beta F \right\}.
\]
This reduces to
\[
F = \frac{1}{1-\beta} \max \left\{ p, \bar\theta \right\}.
\]
We can now work backwards to compute smaller values.

Q: Myopic policy
A: The policy which maximises the immediate reward.

Q: Hidden object moving between two locations (POMDP)
A: Let $S=\{1,2\}$, $P=(p_{ij})$, $x_i=\P(\text{object now at }i)$. Searching $i$ costs $c_i$ with $\P(\text{success})=\alpha_i$. Value iteration of the DP equation gives for $s\geq 1$:
\[
F_s(x_1) = \min \begin{cases} c_1+(1-\alpha_1x_1) F_{s-1} \left( \frac{(1-\alpha_1)x_1p_{11} + x_2p_{21}}{1-\alpha_1x_1}\right), \\
c_2 + (1-\alpha_2x_2) F_{s-1} \left( \frac{(1-\alpha_2)x_2p_{21} + x_1p_{11}}{1-\alpha_2x_2}\right).
\end{cases}
\]
Base case: $F_0(x_1)=0$.
By induction $F_s$ (and thus $F$, by NF case) is concave.
Case: $\alpha_1=1$ and $c_1=c_2=c$. Then
\[
F(x_1) = c+\min \begin{cases} (1-x_1) F(p_{21}), \\
(1-\alpha_2x_2) F \left( \frac{(1-\alpha_2)x_2p_{21} + x_1p_{11}}{1-\alpha_2x_2}\right).
\end{cases}
\]
This line and concave curve map to $[c+F(p_{21}), c]$ and $[c+(1-\alpha_2)F(p_{21}), c+F(p_{11})]$ for $x_1\in[0,1]$. Hence they have a unique root $x_1^*$. The optimal policy is thus to search 1 iff $x_1\geq x_1^*$.

Q: Markov policy
A: A \emph{Markov policy} is a policy $\pi$ such that $u_t=f_t(x_t)$ is independent of previous states and decisions.
We write $\pi=(f_0, f_1, \cdots )$.

Q: Deterministic stationary Markov policy
A: A Markov policy $\pi$ which is independent of time and non-randomising.
Write $\pi=(f, f, \cdots)=f^\infty$.

Q: Sufficient condition for optimal policy: N case
A: Suppose N or D holds. If $\pi=f^\infty$ minimises the DP equation, i.e.
\[
f(x) = \arg\min_u \left\{ c(x,u) + \beta\E[F(x_1) | x_0=x, u_0=u]\right\},
\]
then $\pi$ is optimal. In particular, in case F an optimal policy exists.
\begin{proof}
By repeated substitution into itself
\[
F(x) = \E_{\pi}\left[\left.\sum_{t=0}^{s-1} \beta^t c(x_t,u_t)\right| x_0=x\right] + \beta^s\E_{\pi} [F(x_s) | x_{0}=x].
\]
In case N the final term is non-negative and in case D it will vanish. Letting $s\to\infty$ gives $F(x)\geq F(\pi,x)$.
\end{proof}

Q: One-step look-ahead rule
A: Consider a stopping problem with stopping cost $k(x)$ and continuation cost $c(x)$. Value iteration gives
\[
F_s(x) = \min\left\{ k(x), c(x) + \E[F_{s-1}(x_1) | x_0=x]\right\}.
\]
Define the class of states where it is better to stop now than next time:
\[
S = \{ x: k(x) \leq c(x) + \E[k(x_1) | x_0=x]]\}
\]
If $S$ is a closed class, then $\{\text{stop} \iff x\in S \}$ is an optimal policy for all finite horizons.
\begin{proof}
Basis: $s=1$, true by definition.
Let $s>1$. If $x\not\in S$, then it is better to continue (at least once more). If $x\in S$, then $x_1\in S$ so by inductive hypothesis $F_{s-1}(x_1)=k(x_1)$. Substituting in the DP equation above gives $F_s(x)=k(x)$. So stop.
\end{proof}

Q: Optimal parking
A: Each space is free with probability $p$. Parking $s$ spaces from the destination incurs cost $s$. Failing to park costs $D$. An optimal policy is to park in the first free space $s^*$ away where $s^*$ is the greatest integer with $(Dp+1)q^s\geq 1$.
\begin{proof}
Let $x=\mathbbm{1}[\text{space free}]$. The DP equation is
\begin{align*}
F_s(0) &= qF_{s-1}(0) + pF_{s-1}(1) \\
F_s(1) &= \min\left\{ s, F_s(0)\right\},
\end{align*}
where $F_0(0)=D, F_0(1)=0$.
The stopping set is
\[
S=\{ s: s\leq k(s-1)\}
\]
where $k(s)$ is the cost of parking asap within $s$. This obeys the recurrence
\[
k(s) = ps + qk(s-1), \quad k(0)=qD,
\]
with solution
\[
k(s) = -\frac{q}{p} + s + \left(D+\frac{1}{p}\right)q^{s+1}.
\]
So
\[
S=\{ s: (Dp+1)q^s \geq 1\}.
\]
Since $s\searrow 0$, $q^s\nearrow 1$, so $S$ is closed. Done by OSLA rule.
\end{proof}

Q: Bruss's odds algorithm
A: Let $X_1, \cdots X_n$ be independent rvs in $\{0,1\}$ with $p_k=\P(X_k=1)$, $q_k = 1-p_k$, $r_k=\frac{p_k}{q_k}$. We want to maximise the probability of stopping at the last 1.
The stopping set is
\begin{align*}
S &= \{ i: q_{i+1}\cdots q_n \geq (p_{i+1}q_{i+2} \cdots q_n) + \cdots + (q_{i+1}q_{i+2} \cdots p_n) \} \\
&= \{ i: 1 \geq r_{i+1} + r_{i+2} + \cdots + r_n\} \\
&= \{ s^*, s^*+1, \ldots n\}
\end{align*}
where $s^*$ is the greatest integer for which $R_{s^*}:= r_{s^*} + r_{s^*+1} + \cdots + r_n > 1$.
Clearly $S$ is closed so by OSLA the optimal policy is to stop the first time that $s\geq s^*$ and $X_s=1$. In words: sum the odds to one and stop. Then (assuming $\sum r_i \geq 1$)
\begin{align*}
\P(\text{success}) &= \P(\text{1 then 0s after $s^*$}) \\
&= (q_{s^*}\cdots q_n)(r_{s^*} + \cdots +r_n) \\
&= R_{s^*}\prod_{i\geq s^*} \frac{1}{1+r_i} \\
&\geq Re^{-R}.
\end{align*}
We can tighten the bound by induction. Indeed for $r\geq 1$
\[
\frac{r}{1+r} \geq \frac{1}{2}\geq\frac{1}{e}
\]
and for $R<1, R+r\geq 1$
\[
\frac{R+r}{e^{R}(1+r)} =g(R, r) \geq e^{-1}
\]
where by partial differentiation
\[
g(x, y) = \frac{x+y}{(1+y)e^x} \geq g(x, 1-x) = \frac{1}{(2-x)e^x}
\]
whence
\[
\log g(x, y) \geq -x - \log(1 + (1-x))> -x - (1-x) = -1.
\]

Q: OSLA existence counter-example
A: Let $S=\{0, \cdots N\}$, $x_t$ a rw on $S$ with $\{0\}$ and $\{N\}$ absorbing. Stopping at $x\in S$ gives reward $r(x)\geq 0$. The DP equation is
\[
F(x) = \max\left\{ r(x), \frac{1}{2} F(x-1) + \frac{1}{2} F(x+1)\right\} \quad (0<x<N)
\]
with $F(0)=r(0), F(N)=r(N)$. We stop iff $F(x)=r(x)$. Immediately we have that $F$ is a concave majorant of $r$, i.e. $F\geq r$ and $F$ is concave. In fact, $F$ is the smallest concave majorant of $r$.
\begin{proof}
Let $G$ be another. We use value iteration to first show $G\geq F_s$.  Clearly $G \geq F_0 = 0$. Then by induction
\begin{align*}
F_s(x) &= \max\left\{ r(x), \frac{1}{2} F_{s-1}(x-1) + \frac{1}{2} F_{s-1}(x+1)\right\} \\
&\leq \max\left\{ r(x), \frac{1}{2} G(x-1) + \frac{1}{2} G(x+1)\right\} \\
&\leq \max\{r(x), G(x)\} \\
&= G(x).
\end{align*}
For case P, we know $F_s\to F$ so $F\leq G$.
\end{proof}

Q: Optimal stopping over infinite horizon: general case
A: Let $F_s(x)$ be the infimal cost given that we must stop in time $s$ and $F$ be the infimal cost given that we must stop. Then
\[
F_s \searrow F_\infty \geq F.
\]
Equality need not hold.
\begin{eg}
Consider the symmetric rw on $\Z$ with $c(x)=0$, $k(x)=e^{-x}$. By convexity and induction, $F_s(x)=e^{-x}$. However, by recurrence, we can minimise the stopping cost arbitrarily and thus $F(x)=0$.
\end{eg}
This example also shows that satisfying the DP equation is not sufficient for optimality in the N case.

Q: Optimal stopping over infinite horizon: bounded case
A: Suppose all costs are bounded by
\[
K=\sup_x k(x) < \infty, \qquad C=\inf_x c(x) >0.
\]
Then $F_s\to F$.
\begin{proof}
NF $\implies \exists \pi$ optimal, say stopping at random time $\tau$. If $\tau>s$, then $\pi$ must suffer less cost in the $(s+1)$-horizon than stopping immediately, i.e.
\[
(s+1)C\P(\tau > s) < k < K.
\]
Conditioning on $\tau\leq s$:
\[
F(x) \leq F_s(x) \leq F(x) + K\P(\tau>s) \leq F(x) + \frac{K^2}{(s+1)C} \to F(x).
\]
\end{proof}

Q: OSLA for infinite horizon
A: Suppose the stopping set $S$ is closed in a bounded case infinite horizon stopping problem. Then an optimal policy is stop $\iff$ $x\in S$.
\begin{proof}
If $x\not\in S$, then clearly it is not optimal to stop.
If $x\in S$, then by the finite horizon case $F_s(x)=k(x)$. By boundedness, $F_s\to F$.
\end{proof}

Q: Sequential probability ratio test
A: Let $x_1, \cdots x_n$ be iid with density $f$. Let $\{H_0: f=f_0\}$, $\{H_1: f=f_1\}$ have priors $p_i$. The posterior LRs are
\[
\ell_n = \frac{\P(f=f_1 | x_1, \cdots x_n)}{\P(f=f_0 | x_1, \cdots x_n)} = \frac{f_1(x_1) \cdots f_1(x_n) p_1}{f_0(x_1)\cdots f_0(x_n)p_0} = \frac{f_1(x_n)}{f_0(x_n)}\ell_{n-1}.
\]
A sample costs $\gamma$ and incorrectly guessing $H_i$ costs $c_i$. The DP equation is
\[
F(\ell) = \min\left\{ c_0 \frac{\ell}{1+\ell}, c_1 \frac{1}{1+\ell} , \gamma + \frac{\ell}{1+\ell} \int F\left(\frac{\ell f_1(y)}{f_0(y)}\right) f_1(y) \d y +  \frac{1}{1+\ell} \int F\left(\frac{\ell f_1(y)}{f_0(y)}\right) f_0(y) \d y\right\}.
\]
Writing $H(\ell) = (1+\ell) F(\ell)$, this becomes
\[
H(\ell) = \min\left\{ c_0 \ell, c_1 , (1+\ell) \gamma +  \int H\left(\frac{\ell f_1(y)}{f_0(y)}\right) f_0(y) \d y \right\}.
\]
By boundedness, we can apply value iteration to show $H$ is increasing concave by induction. The two linear bounds imply that $\exists a_0\leq a_1$ such that the optimal policy is
\[
\pi=\begin{cases}
\text{guess $H_0$} \quad &\ell_n \leq a_0 \\
\text{buy a sample} \quad &a_0 < \ell_n < a_1 \\
\text{guess $H_1$} \quad &\ell_n > a_1.
\end{cases}
\]

Q: Bandit process
A: A bandit process is a special type of MDP in which there are just two possible actions:
\begin{itemize}
\item $u = 0$ (freeze). No reward or change.
\item $u = 1$ (continue). Reward $r(x_t)$ and state changes to $x_{t+1}=\{(x_{t+1} | x_t, u_t = 1\}$.
\end{itemize}
A simple family of alternative bandit processes (SFABP) is a collection of n
such bandit processes.

Q: Gittins Index
A: We define the index
\[
G(x) = \sup_{\tau \geq 1}\left\{ \frac{\E\left[\left. \sum_{t=0}^{\tau - 1} \beta^t r(x(t)) \right| x(0)=x \right]}{\E\left[\left. \sum_{t=0}^{\tau - 1} \beta^t\right| x(0)=x \right]} \right\}.
\]
Intuitively, this is the maximum reward achievable per unit time (both discounted), given a choice of stopping time $\tau$.

Q: Calibrating bandit process
A: Let $\Lambda$ always pay $\lambda$ and $B_i$ be of general type. Parmeterising by the state of $B_i$, the DP equation is
\[
F(x) = \max \left\{ \lambda\sum_{t=0}^{\infty} \beta^t, \sup_{\tau\geq 1} \E \left[ \left.\sum_{t=0}^{\tau - 1} \beta^t r(x(t)) + \lambda\sum_{t=\tau}^\infty \beta^t \right| x(0)=x \right]\right\}.
\]
These terms are $\nearrow$ and linear/convex respectively in $\lambda$. Hence $\exists !\gamma$ for which they are equal where
\[
\gamma_i(x) = \max \left\{ \lambda: 0 \leq \sup_{\tau\geq 1} \E \left[ \left.\sum_{t=0}^{\tau - 1} \beta^t\left( r(x(t)) - \lambda \right)\right| x(0)=x \right]\right\}
\]
which we recognise as $\gamma_i(x)=G_i(x)$. This is the \emph{fair charge}: the greatest cost we would be willing to pay per step to start playing $B_i$.
Hence we stop the first time that $G_i(x_i(\tau)) < G_i(x_i(0))$, i.e. the first time at which the initial fair charge now seems too rich.

Q: Gittins Index Theorem
A: The MABP is solved by always playing the bandit of greatest Gittins Index.
\begin{proof}
Consider an $n$-bandit problem where we pay the prevailing charge $g_{i_t}(x_{i_t}(t))$ at each step.
Observation 1.  We at best break even, i.e. for any policy $\pi$:
\[
\E_\pi\left[ \left. \sum_{t=0}^\infty \beta^t( r_{i_t}(x_{i_t}(t)) - g_{i_t}(x_{i_t}(t))\right| x(0)\right] \leq 0.
\]
Observation 2. We maximise the total expected cost by $\pi^*$: always continue the bandit with the greatest $g_{i}(x_i(t))$ (or equivalently, greatest $G_i(x_i(t))$). Since the prevailing charges for each bandit are decreasing, $\pi^*$ interleaves the $n$ decreasing sequences into one decreasing sequence, which maximises the sum after discounting.
Observation 3. Using $\pi^*$ just breaks even (because by continuing $B_i$ until $g_i(x_i(t))$ decreases is the way to break even).
Rearranging O1:
\[
\E_\pi\left[ \left. \sum_{t=0}^\infty \beta^tr_{i_t}(x_{i_t}(t)\right| x(0)\right] \leq \E_\pi\left[ \left. \sum_{t=0}^\infty \beta^t g_{i_t}(x_{i_t}(t)\right| x(0)\right].
\]
By O2 the RHS is maximised under $\pi^*$. By O3 we have equality if $\pi=\pi^*$. Hence the LHS is maximised under $\pi^*$.
\end{proof}

Q: Prevailing charge
A: The \emph{prevailing charge} is the maximum we can charge a gambler to keep him at $B_i$, i.e.
\[
g_i(t) = \min_{s\leq t} G_i(x_i(s)).
\]
This is decreasing.

Q: Weitzman's problem
A: Pandora must take one of $n$ boxes with reward in box $i$ drawn from cdf $F_i$ at a cost of $c_i$.
Model as a SFABP with $B_i$ starting in state 0, moving to state $x_i$ when opened (at a cost of $c_i$). Afterwards the reward is $r(x_i)=(1-\beta)x_i$. Pandora seeks to maximise the EV of
\[
-\sum_{t=1}^\tau \beta^{t-1} c_{i_t} + \max\{r(x_{i_1}), \cdots r(x_{i_t})\} \sum_{t=\tau}^\infty \beta^t = -\sum_{t=1}^\tau \beta^{t-1} c_{i_t} + \beta^\tau \max\{x_{i_1}, \cdots x_{i_t}\}.
\]
For an opened box, $G_i = \frac{r(x_i)}{1-\beta}=x_i$. For an unopened box
\[
\frac{G_i}{1-\beta} = -c_i + \frac{\beta}{1-\beta} \E[\max\{r(x_i), G_i\}].
\]
Hence the optimal policy is to open boxes in decreasing $G_i$ until a revealed prize is greater than the remaining $G_i$.
Letting $g=\frac{G}{1-\beta}$ and $\beta\to 1$ gives an index solution to the original problem solving $g=-c_i+\E[\max\{x_i, g\}]$.

Q: Average cost optimality equation
A: For a stationary policy $\pi$, define the \emph{average cost}
\[
\lambda(\pi, x) = \lim_{t\to\infty} \frac{1}{t} \E_\pi\left[\left. \sum_{\tau = 0} ^{t-1} c(x_\tau, u_\tau) \right| x_0=x\right].
\]
Then the optimal average cost is
\[
\lambda = \lambda(x) = \inf_\pi \lambda(\pi, x).
\]
So we guess $F_s(x) = s\lambda + \varphi(x)$ where $\varphi$ is the relative value function. The the DP equation is
\[
s\lambda + \varphi(x) = \min_u \{ c(x,u) + \E[(s-1)\lambda + \varphi(x_1) | x_0=x, u_0=u]\}
\]
which gives
\[
\lambda + \varphi(x) = \min_u \{ c(x,u) + \E[\varphi(x_1) | x_0=x, u_0=u]\}.
\]

Q: Optimal average cost lower bound
A: Suppose $\exists\lambda$ constant and $\varphi$ bounded such that $\forall x, u$:
\[
\lambda + \varphi(x) \leq c(x,u) + \E[\varphi(x_1) | x_0 = x, u_0=u].
\]
Then $\lambda\leq \inf_\pi \lambda(\pi, x)$.
\begin{proof}
For any policy $\pi$, by repeated substitution into itself
\[
\varphi(x) \leq -t\lambda + \E_\pi \left[\left.\sum_{\tau=0}^{t-1} c(x_\tau, u_\tau)\right| x_0=x \right] + \E_\pi[\varphi(x_t) | x_0=x].
\]
Divide by $t$, let $t\to\infty$ and take the infimum over $\pi$.
\end{proof}

Q: Optimal average cost upper bound
A: Suppose $\exists\lambda$ constant and $\varphi$ bounded such that $\forall x, \exists u=f(x)$ such that
\[
\lambda + \varphi(x) \geq c(x,u) + \E[\varphi(x_1) | x_0=x, u_0=f(x)].
\]
Let $\pi=f^\infty$. Then $\lambda\geq \lambda(\pi, x) \geq \inf_\pi \lambda(\pi, x)$.
\begin{proof}
By repeated substitution into itself
\[
\varphi(x) \geq -t\lambda + \E_\pi \left[\left.\sum_{\tau=0}^{t-1} c(x_\tau, u_\tau)\right| x_0=x \right] + \E_\pi[\varphi(x_t) | x_0=x].
\]
Divide by $t$ and let $t\to\infty$ to give $\lambda\geq \lambda(\pi, x)$.
\end{proof}

Q: Average-cost optimality theorem
A: Suppose $\exists\lambda$ constant and $\varphi$ bounded satisfying the average-cost optimality equation. Let $\pi$ be the policy which chooses the minimum on the RHS. Then $\lambda$ is the minimal average-cost and $\pi$ is the optimal stationary policy.

Q: Admission control at a queue
A: $n$ job types are on offer with $\P(\text{type }i)=a_i$, $r(i)=R_i$, $T_i\sim\mathrm{Geo}(p_i)$.
Parameterise by current job. Then the average-cost equation is
\begin{align}
\lambda + \varphi(0) &= \sum_{i=1}^n a_i \max\{\varphi(0), \varphi(i)\}  \\
\lambda + \varphi(i) &= (1-p_i)\varphi(i) + p_i(R_i + \varphi(0)) \quad (i\geq 1).
\end{align}
Pick $\varphi(0)=0$. Then (ii) gives $\varphi(i) = R_i-\lambda / p_i$ and (i) gives
\[\]
\lambda = \sum_{i=1}^n a_i \max\{ 0, R_i-\lambda / p_i\}.
LHS $\nearrow$ and RHS $\searrow$ in $\lambda$. Hence $\exists!\lambda^*$ for which they are equal.
The optimal policy is then accept only jobs for which $p_iR_i \geq \lambda^*$.

Q: Value iteration bounds for average-cost
A: Assume finite state/action spaces. Define
\[
m_s= \min_x\{ F_s(x) - F_{s-1}(x)\}, \quad M_s = \max_x\{F_s(x) - F_{s-1}(x)\}.
\]
Then $m_s\leq \lambda \leq M_s$.
\begin{proof}
For any $x,u$:
\begin{align*}
F_{s-1}(x) + m_s &\leq F_s(x) \\
&\leq c(x,u) + \E[F_{s-1}(x_1) | x_0=x, u_0=u].
\end{align*}
Similarly, for $u=f_s(x)$ minimising the DP equation
\begin{align*}
F_{s-1}(x) + M_s &\geq F_s(x) \\
&= c(x,u) + \E[F_{s-1}(x_1) | x_0=x, u_0=f_s(x)].
\end{align*}
\end{proof}

Q: Value iteration algorithm for average-costs
A: Calculate $F_s$ until $M_s-m_s\leq \varepsilon m_s$. Then $f_s^\infty$ has average-cost within $\varepsilon \times 100\%$ of optimal.

Q: Policy improvement for rates
A: Assume finite state/action spaces and that all stationary policies induce an irreducible MC. Suppose $\pi_0=f_0^\infty$, $\pi_1=f_1^\infty$ where $f_0\neq f_1$ obey
\begin{align}
\lambda+\varphi(x) &= c(x,f_0(x)) + \E_{\pi_0} [\varphi(x_1) | x_0=x] \\
\lambda+\varphi(x) &\geq c(x,f_1(x)) + \E_{\pi_1}[\varphi(x_1) | x_0=x]
\end{align}
with (2) strict for some $x$. Then $\lambda(\pi_0)=\lambda$ and $\lambda(\pi_1) < \lambda$.
Indeed, let $\gamma$ be the invariant distribution under $\pi_1$. Multiply (2) by $\gamma(x)$ and sum over $x$
\begin{align*}
\lambda + \sum_x \varphi(x)\gamma(x) &> \sum_x c(x,f_1(x))\gamma(x) + \sum_{x,y} \varphi(y)p_{xy} \gamma(x) \\
\lambda &> \sum_x c(x,f_1(x))\gamma(x) =\lambda(\pi_1).
\end{align*}
If $\neg\exists\pi_1$, then $\pi_0$ minimises the RHS of the DP equation so is optimal.
So use (1) to solve for $\varphi, \lambda$. Next let $u_0=f_1(x_0)$ minimise the RHS. Then $\pi_1$ is an improvement or $\pi_0$ is optimal. Iterating, this must terminate at the optimal stationary policy.

Q: Parallel job scheduling
A: We seek to minimise the makespan of $n$ jobs on $m=2$ machines with processing time $X_i\sim \mathcal{E}(\lambda_i)$ MI. Note that
\[
\min(X_i, X_j) \sim \mathcal{E}(\lambda_i+\lambda_j), \quad \P(X_i<X_j | \min(X_i, X_j)) = \frac{\lambda_i}{\lambda_i+\lambda_j}.
\]
Writing $S^i=S\setminus\{ i \}$, $\Lambda = \sum_i \lambda_i$, the DP equations after uniformisation are
\begin{align*}
F(\{ i \}) &= \frac{1}{\lambda_i} \\
F(\{ i, j \}) &= \frac{1}{\lambda_i + \lambda_j} [1+\lambda_i F(\{ j \}) + \lambda_j F(\{ i \})] \\
F(S) &= \min_{i,j\in S} \frac{1}{\lambda_i + \lambda_j} [1+\lambda_i F(S^i) + \lambda_j F(S^j)] \\
&= \min_{i,j\in S} \frac{1}{\Lambda} \left[1+\lambda_i F(S^i) + \lambda_j F(S^j) + \sum_{k\neq i, j} \lambda_k F(S)\right] \\
&= \min_{u_i \in \{0,1\}, i \in S, \sum u_i \leq 2} \frac{1}{\Lambda} \left[1+\Lambda F(S) + \sum_{i} u_i \lambda_i (F(S^i) - F(S))\right].
\end{align*}
An event occurs after a time $\mathcal{E}(\Lambda)$ (where with probability $\lambda_k/\Lambda$ for each $k\neq i, j$ this is a dummy event).
The optimal policy selects the jobs minimising $\delta_i(S) =\lambda_i (F(S^i) - F(S))$.

Q: Makespan, flow time and time to idle
A: Let $C_i$ be the completion time of job $i\leq n$ on $m$ machines. Then
\begin{itemize}
\item $\max_i C_i$ is the makespan (time when all jobs are complete)
\item $\sum_i C_i$ is called the flow time (total processing time)
\item $C_{n-m+1}$ is the time until a machine is first idle.
\end{itemize}

Q: Lowest Hazard Rate first policy
A: We minimise expectations as follows:
\begin{enumerate}
\item Makespan $\to$ LHR.
\item Flow time $\to$ HHR.
\item $C_{n-m+1}$ $\to$ LHR.
\end{enumerate}

Q: Controlled Markov jump process
A: Given a control $u$, the state jumps after time $\mathcal{E}(q_i(u))$ where
\[
q_i(u) = \sum_{j\neq i} q_{i,j}(u)
\]
and the new state is $j$ with probability $q_{i,j}(u)/q_i(u)$. The DP equation (assuming $q_i(u)\leq B$ for all $i,u$) under uniformisation is
\begin{align*}
F(i) &= \min_{u\in A(i)}\left\{ \frac{1}{q_i(u)} \left[ c(i,u) + \sum_j q_{ij}(u) F(j)\right]\right\} \\
F(i) &= \min_{u\in A(i)}\left\{ \frac{1}{B} \left[ c(i,u) + (B-q_i(u))F(i) + \sum_j q_{ij}(u) F(j)\right]\right\}
\end{align*}
which is of the form of a discrete-time DP equation.
We can add discounting by assuming the process ends after time $\sim\mathcal{E}(\alpha)$.

Q: Minimum of a quadratic form
A: The symmetric quadratic form
\[
Q(u):=\begin{pmatrix}x\\u\end{pmatrix}^T \begin{pmatrix}\Pi_{xx} & \Pi_{xu} \\ \Pi_{ux} & \Pi_{uu}\end{pmatrix} \begin{pmatrix}x\\u\end{pmatrix}.
\]
with $\Pi_{uu}$ postive definite, achieves the minimum
\[
x^T[\Pi_{xx} - \Pi_{xu}\Pi_{uu}^{-1} \Pi_{ux}]x
\]
at
\[
u = - \Pi_{uu}^{-1}\Pi_{ux} x.
\]
\begin{proof}
Completing the square
\[
Q(u) = (u+\Pi_{uu}^{-1}\Pi_{ux} x)^T \Pi_{uu} (u+\Pi_{uu}^{-1}\Pi_{ux} x) + x^T(\Pi_{xx} - \Pi_{xu}\Pi_{uu}^{-1} \Pi_{ux}) x.
\]
Alternatively, varying $u$ gives
\[
Q(u+h)-Q(u) =  2h^T\Pi_{ux}x + 2h^T \Pi_{uu} u + o(h).
\]
\end{proof}

Q: LQG model
A: Linear dynamics, quadratic costs and Gaussian noise. The plant equation is
\[
x_t = Ax_{t-1} + Bu_{t-1}
\]
where $x_t\in \R^n, u_t\in \R^m$, with one-step cost
\[
c(x,u) = \begin{pmatrix}x\\u\end{pmatrix}^T \begin{pmatrix}R & S^T\\ S & Q\end{pmatrix} \begin{pmatrix}x\\u\end{pmatrix}
\]
and terminal cost $C_h(x) = x^T\Pi_h x$, where $R,Q,\Pi_h$ are symmetric.

Q: Regulation
A: Steering to a critical value, e.g. $(x,u)$ to $(0,0)$.

Q: Riccati Equation
A: The value functon is $F_s(x)=x^T\Pi_s x$ where $\Pi_s$ obeys the Riccati equation
\[
\Pi_s = R + A^T \Pi_{s-1} A - (S^T + A^T\Pi_{s-1} B)(Q+B^T\Pi_{s-1} B)^{-1}(S+B^T\Pi_{s-1} A)
\]
and optimal control is $u_s = K_s x_s$ where
\[
K_s = -(Q+B^T\Pi_{s-1}B)^{-1} (S+B^T\Pi_{s-1}A).
\]
\begin{proof}
By induction
\begin{align*}
F_s(x) &= \inf_u \left[ c(x,u) + (Ax+Bu)^T\Pi_{s-1}(Ax+Bu)\right] \\
&= \inf_u \left[  \begin{pmatrix}x\\u\end{pmatrix}^T \begin{pmatrix}R+A^T\Pi_{s-1} A & S^T + A^T\Pi_{s-1}B\\ S+B^T\Pi_{s-1}A & Q+B^T\Pi_{s-1}B\end{pmatrix} \begin{pmatrix}x\\u\end{pmatrix}\right].
\end{align*}
\end{proof}

Q: Gain matrix
A: The optimally controlled process obeys $x_{t+1}=\Gamma_t x_t$ where
\[
\Gamma_t = A + B K_t
\]
is the \emph{gain matrix}.

Q: White noise disturbance
A: Consider the plant equation
\[
x_{t+1} = Ax_t + Bu_t + \varepsilon_t
\]
where $\E\varepsilon_t=0$ and $\E[\varepsilon_t\varepsilon_s^T]=\delta_{st}N$. The DP equation is
\[
F_s(x) = \inf_u \left\{ c(x,u) + \E[F_{s-1}(Ax+Bu+\varepsilon)] \right\}
\]
where $F_0(x)=x^T\Pi_0 x$. Then $F_s(x)=x^T\Pi_s x + \gamma_s$ where $\gamma_s=\sum_{j=0}^{s-1} \tr(N\Pi_j)$.
\begin{proof}
By induction and centredness
\begin{align*}
F_s(x) &= \inf_u \left\{ c(x,u) + \E[(Ax+Bu+\varepsilon)^T\Pi_{s-1}(Ax+Bu+\varepsilon) + \gamma_{s-1}] \right\} \\
&= \inf_u \left\{ c(x,u) + \E[(Ax+Bu)^T\Pi_{s-1}(Ax+Bu)+ \E[\underbrace{\varepsilon^T \Pi_{s-1} \varepsilon}_{=\tr(\varepsilon^T\Pi_{s-1} \varepsilon)}] + \gamma_{s-1}] \right\} \\
&= \inf_u \left\{ c(x,u) + \E[(Ax+Bu)^T\Pi_{s-1}(Ax+Bu)+ \tr(N\Pi_{s-1}) + \gamma_{s-1}] \right\}.
\end{align*}
\end{proof}

Q: Controllability
A: A system is $r$-controllable if it can be brought from any initial state $x_0$ to any final state $x_r$ by choice of controls $u_0,\cdots u_{r-1}$.
A system is controllable if it is $r$-controllable for some $r$.

Q: Controllability matrix criterion
A: The system $[A,B,\ph]$ with dynamical equation
\[
x_t = Ax_{t-1}+Bu_{t-1} \tag{$*$}
\]
is $r$-controllable iff $M_r=[B \cdots A^{r-1}B]$ has rank $n$ iff $M_rM_r^T$ is positive definite.
Moreover, if the system is $r$-controllable then it is $s$-controllable for $s\geq \min(n,r)$.
Finally, the cost $\sum_{t=0}^{r-1}u_t^Tu_t$ is minimised by controls
\[
u_t=B^T(A^T)^{r-t-1}(M_rM_r^T)^{-1}(x_r-A^rx_0).
\]
\begin{proof}
Repeated substitution of ($*$) into itself gives
\[
\triangle := x_r-A^rx_0 = Bu_{r-1} + \cdots + A^{r-1}Bu_0 = M_rU_r.
\]
So the system is $r$-controllable iff the rows of $M_r$ span $\R^n$.
rank($M_r$) $\nearrow$ to a max at $r=n$ by Cayley-Hamilton.
Differentating the Lagrangian
\[
\sum_{t=0}^{r-1} u_t^T u_t + \lambda^T(\triangle - \sum_{t=0}^{r-1} A^{r-t-1}Bu_t)
\]
wrt $u_t$ gives $u_t=\tfrac{1}{2}B^T(A^T)^{r-t-1} \lambda$ and hence $U_r=\frac{1}{2}M_r^T\lambda$. Substituting into $\triangle$ fixes $\lambda$.
\end{proof}

Q: Continuous-time Riccati equation
A: The plant equation is $\dot{x}=Ax+Bu$ and the cost is
\[
\int_0^h \begin{pmatrix} x \\ u\end{pmatrix}^T \begin{pmatrix} R & S^T \\ S & Q\end{pmatrix} \begin{pmatrix} x \\ u\end{pmatrix} \; \d t + \left.(x^T\Pi x)\right|_{t=h}.
\]
We modify the discrete-time solution by
\[
x_{t} \mapsto x (t\delta) , \quad A \mapsto I + A\delta, \quad (B,R,S,Q) \mapsto \delta(B,R,S,Q).
\]
Then $F(x,t)=x^T\Pi x$, $u=Kx$, $\dot{x}= \Gamma x $ where $\Pi(t)$ obeys the Riccati equation
\[
0=\frac{\partial\Pi}{\partial t} +R + A^T\Pi + \Pi A - (S^T+\Pi B)Q^{-1}(S+B^T\Pi )
\]
and $K(t)=-Q^{-1}(S+B^T\Pi)$.

Q: Controllability in continuous time
A: $[A,B,\ph]$ is controllable iff $r(M_n)=n$ iff
\[
G(t) = \int_0^t e^{As} BB^T e^{A^Ts} \; \d s
\]
is positive definite for all $t>0$.
The control minimising the cost $\int_0^t u_s^Tu_s \; \d s$ is
\[
u(s) = B^T e^{A^T(t-s)} G(t)^{-1} (x(t) - e^{At} x(0)).
\]

Q: Stabilisability
A: The gain matrix $\Gamma=A+BK$ is called a \emph{stability matrix} if $x\to 0$ as $t\to\infty$. The system $[A,B,\ph]$ is stabilisable if $\Gamma$ is a stability matrix for some $K$.
In discrete time, $x_t=\Gamma x_{t-1}$ so $x_t=\Gamma^t x_0$. Hence all eigenvalues of $\Gamma$ need to lie in the open unit ball.
In continuous time, $\dot{x}=\Gamma x$ so $x_t = e^{\Gamma t} x_0$. So all eigenvalues need negative real part.

Q: Finite Riccati limit
A: Suppose $\Pi_0=0$, $R\geq 0$, $Q\geq 0$, $S=0$ and $[A,B,\ph]$ is controllable or stabilisable. Then $(\Pi_s)\to \Pi<\infty$.
\begin{proof}
Costs are $\geq 0$ so $x^T\Pi_sx \nearrow$ in $s$ ($\forall x$).
\textbf{Case: controllable}. We can force $x_r=0$ and incur no further cost.
\textbf{Case: stabilisable}. Let $\Gamma=A+BK$ be a stability matrix. Then $u_t=Kx_t$ forces $x_t=\Gamma^t x_0$ and we have the geometric bound
\[
x^T\Pi_sx \leq \sum_{t=0}^\infty (x_t^TRx_t+u_t^TQu_t) = x^T \left[ \sum_{t=0}^\infty (\Gamma^T)^t(R+K^TQK)\Gamma^t \right]x < \infty.
\]
In either case $x^T\Pi_sx$ is bounded. Taking $x=e_j$ gives convergence along the diagonal. Taking $x=e_j+e_k$ gives the rest.
\end{proof}

Q: Observable
A: The \emph{observation equation} is $y_t=Cx_{t-1}$.
The system $[A,B,C]$ is $r$-observable if any $x_0$ can be inferred from $y_1,\cdots y_r$ and $u_0, \cdots u_{r-2}$.
It is observable if it is $r$-observable for some $r$.

Q: Reduced observation: noiseless case
A: Repeated substitution of the equation of motion gives
\[
x_t = A^tx_0 + \sum_{s=0}^{t-1} A^sBu_{t-s-1}.
\]
Substituting this in the observation equation gives
\[
y_t = C\left[ A^{t-1}x_0 + \sum_{s=0}^{t-2} A^sBu_{t-s-2} \right].
\]
Now we subtract the effect of our controls to define the \emph{reduced observation}
\[
\tilde{y}_t = y_t - C\left[\sum_{s=0}^{t-2} A^s B u_{t-s-2} \right].
\]
Then $x_0$ is to be determined from the equations
\[
\tilde{y}_t = CA^{t-1}x_0 \quad 1\leq t\leq r.
\]

Q: Observability matrix criterion
A: $[A,\ph,C]$ is $r$-observable iff
\[
N_r = \begin{pmatrix} C \\ CA \\ \vdots \\ CA^{r-1}\end{pmatrix}
\]
has rank $n$ iff $N_r^TN_r\in\R^{n\times n}$ is nonsingular; determined by
\[
x_0 = (N_r^TN_r)^{-1} \sum_{t=1}^{r} (A^T)^{t-1} C^T \tilde{y}_t.
\]
In particular, $r$-observable $\implies$ $s$-observable for $s\geq \min(n,r)$.
\begin{proof}
$x_0\in\R^n$ is determined by $\tilde{y}_r$ iff $N_r$ has rank $n$.
Define the deviations $\eta_t=\tilde{y}_t-CA^{t-1}x_0$ which vanish. We minimise $q(x_0)=\sum_{t=1}^{r}\eta_t^T \eta_t$, i.e.
\begin{align*}
q(x_0) &= \sum_{t=1}^{r} \|\tilde{y}_t - CA^{t-1}x_0 \|^2 \\
&=\text{const} -2 \sum_{t=1}^{r} x_0^T(A^T)^{t-1} C^T \tilde{y}_t + x_0^TN_r^TN_rx_0 \\
\nabla q(x_0)&=-2 \sum_{t=1}^{r} (A^T)^{t-1} C^T \tilde{y}_t + 2N_r^TN_rx_0.
\end{align*}
\end{proof}

Q: Observability in continuous-time
A: $[A,\ph, C]$ is observable iff $N_n$ has rank $n$ iff
\[
H(t)=\int_0^t e^{A^Ts}C^TCe^{As} \; \d s
\]
is positive definite for all $t>0$; with determination
\begin{align*}
x(0) &= H(t)^{-1}\int_0^t e^{A^Ts}C^T\tilde{y}(s) \; \d s \\
\tilde{y}(t) &= y(t) - \int_0^t Ce^{A(t-s)} Bu(s) \; \d s.
\end{align*}

Q: LQ with imperfect observation
A: The equations are
\begin{align*}
x_t &= Ax_{t-1} + Bu_{t-1} + \varepsilon_t \\
y_t &= Cx_{t-1} + \eta_t.
\end{align*}
Wlog assume white noise
\[
\E\begin{pmatrix}
\varepsilon \\
\eta
\end{pmatrix} = \begin{pmatrix}
0 \\
0
\end{pmatrix}, \quad \cov\begin{pmatrix}
\varepsilon \\
\eta
\end{pmatrix} = \begin{pmatrix}
N & L \\
L^T & M
\end{pmatrix}.
\]
We know $W_t=(Y_t, U_{t-1})$ when choosing $u_t$.
In LQG, $x_0\sim N(\hat{x}_0, V_0)$ a priori.

Q: Estimation error is independent of control
A: By repeated substitution of the equation of motion
\[
x_t = A^tx_0 + A^{t-1}Bu_0 + \cdots + Bu_{t-1} + A^{t-1} \varepsilon_1 + \cdots  + \varepsilon_t.
\]
Let $\tilde{x}$, $\tilde{y}$ be the trajectory of zero control. Let $\hat{x}_t=\E[x_t|W_t]$. Then
\begin{align*}
\Delta_t &= x_t - \E[x_t | W_t] \\
&= \tilde{x}_t - \E[\tilde{x}_t | W_t] \\
&= \tilde{x}_t - \E[\tilde{x}_t | \tilde{W}_t].
\end{align*}

Q: Certainty equivalence
A: The optimal cost for the imperfect LQ problem is
\[
F(W_s) = \E [ x_s^T\Pi_sx_s | W_s ]  + \sum_{i=1}^{s} \E[\Delta_i^T\tilde{\Pi}_i \Delta_i | W_i] + \gamma_s.
\]
The optimal control is $u_s=K_s\hat{x}_s$ and $\tilde{\Pi}_s=R+A^T\Pi_{s-1}A-\Pi_s \geq 0$.
\begin{proof}
By backward induction and tower property of expectation, we can reduce to the perfect case
\begin{align*}
F(W_s) &= \min_u \E\left[\left. x^TRx + u^TQu + \E[(Ax+Bu+\varepsilon)^T\Pi_{s-1} (Ax+Bu+\varepsilon)| W_{s-1}] + \Sigma (s-1) +\gamma_{s-1} \right| W_s \right] \\
&= \min_u \left[ \E[x^TRx | W_s]+ u^TQu + \E[(Ax+Bu)^T\Pi_{s-1} (Ax+Bu) | W_{s}] + \Sigma(s-1)  +\gamma_{s} \right]\\
&= \min_u \left[ \hat{x}^TR\hat{x} + u^TQu + \E[(A\hat{x}+Bu)^T\Pi_{s-1} (A\hat{x}+Bu) | W_{s}] + \E[\Delta_s^T(R+A^T\Pi_{s-1}A)\Delta_s|W_s]+ \Sigma(s-1) +\gamma_{s} \right]\\
&= \hat{x}^T\Pi_s\hat{x}  + \E[\Delta_s^T(R+A^T\Pi_{s-1}A)\Delta_s|W_s]+\Sigma(s-1)  +\gamma_{s} \\
&= \E[x^T\Pi_s x |W_s] + \E[\Delta_s^T(R+A^T\Pi_{s-1}A-\Pi_s)\Delta_s|W_s]+\Sigma(s-1) +\gamma_{s}  \\
&= \E[x^T\Pi_s x |W_s] +\Sigma (s) +\gamma_{s} .
\end{align*}
\end{proof}

Q: Quadratics in estimation error
A: For any $M\geq 0$:
\begin{align*}
\E[\Delta_t^T M \Delta_t | W_t ] &= \E[(x_t-\hat{x}_t)^T M (x_t-\hat{x}_t) | W_t ] \\
&= \E[x_t^T M x_t | W_t ] - 2 \hat{x}_t^TM\hat{x}_t + \hat{x}_t^T M \hat{x}_t \\
&= \E[x_t^T M x_t | W_t ] - \hat{x}_t^TM\hat{x}_t.
\end{align*}

Q: Separation principle
A: The fact that the problems of optimal estimation and optimal control can be decoupled.

Q: Conditional distribution of normals
A: Let $(x, y)^T \sim N(0, V)$ where
\[
V = \begin{pmatrix} V_{xx} & V_{xy} \\ V_{yx} & V_{yy} \end{pmatrix}.
\]
Then
\[
x|y \sim N(Hy, V_{xx} - V_{xy}V_{yy}^{-1} V_{yx})
\]
where $Hy=V_{xy}V_{yy}^{-1}y$ is the BLUE and normal MLE.
\begin{proof}
Both $y$ and $x-V_{xy}V_{yy}^{-1}y$ are linear and centred with correlation
\[
\E[(x-V_{xy}V_{yy}^{-1}y)y^T] = V_{xy} - V_{xy}V_{yy}^{-1}V_{yy} = 0
\]
and variance
\[
\E[(x-V_{xy}V_{yy}^{-1}y)(x-V_{xy}V_{yy}^{-1}y)^T]=V_{xx}-2V_{xy}V_{yy}^{-1}V_{yx}+V_{xy}V_{yy}^{-1}V_{yx}.
\]
\end{proof}

Q: Kalman filter
A: Let $x_t| W_t\sim N(\hat{x}_t, V_t)$ in LQG. Then the means obey the Kalman filter
\[
\hat{x}_t = A\hat{x}_{t-1} + Bu_{t-1} + H_t(y_t-C\hat{x}_{t-1})
\]
where $V_{t-1}=V$ obeys the forward Riccati equation
\[
V_t = N+AVA^T - (L+AVC^T)(M+CVC^T)^{-1}(L^T+CVA^T)
\]
and
\[
H_t = (L+AVC^T)(M+CVC^T)^{-1}.
\]
\begin{proof}
Let $u_{t-1}$ be chosen but $y_t$ not observed. Consider the innovations
\begin{align*}
\xi_t &= x_t - \E[x_t | W_{t-1}, u_{t-1}] = x_t - (A\hat{x}_{t-1}+Bu_{t-1}) = \varepsilon_t + A\Delta_{t-1} \\
\zeta_t &= y_t - \E[y_t | W_{t-1}, u_{t-1}] = y_t - C\hat{x}_{t-1} = \eta_t + C\Delta_{t-1}.
\end{align*}
Then
\[
\left.\begin{pmatrix}
\xi_t \\
\zeta_t
\end{pmatrix} \right| W_{t-1}, u_{t-1} \sim (0,V)
\]
where
\[
V = \cov \begin{pmatrix} \varepsilon_t + A\Delta_{t-1} \\ \eta_t + C\Delta_{t-1} \end{pmatrix} = \begin{pmatrix} N+AV_{t-1}A^T & L+AV_{t-1}C^T \\ L^T+CV_{t-1}A^T & M+CV_{t-1}C^T\end{pmatrix} = \begin{pmatrix} V_{\xi\xi} & V_{\xi\eta} \\ V_{\eta\xi} & V_{\eta\eta} \end{pmatrix}.
\]
Hence
\[
\xi_t | W_t  \sim N(V_{\xi\eta}V_{\eta\eta}^{-1}\zeta_t, V_{\xi\xi} - V_{\xi\eta}V_{\eta\eta}^{-1}V_{\eta\xi}).
\]
\end{proof}

Q: Dynamic programming in continuous time
A: \textbf{Method 1}. Discretise the problem to a small time-step $\delta$. Taylor expand to linear terms, cancel and let $\delta\to 0$.
\textbf{Method 2}. Introduce a Lagrange multiplier $\lambda(t)$ to constrain the relationship between $u(t)$ and $x(t)$. To remove derivatives, integrate by parts or use alternating sign formula. Then differentiate wrt $x(t)$ and $u(t)$ to obtain EL equations. Also differentiate wrt $x(T)$ if free.

Q: Hamilton-Jacobi-Bellman equation
A: Consider plant equation
\[
\dot x = a(x,u,t)
\]
and discounted cost
\[
C = \int_0^h e^{-\alpha t} c(x,u,t) \; \d t + e^{-\alpha h} C(x(h), h).
\]
The discretised optimality equation is
\[
F(x,t) = \inf_u \left[ c(x,u,t)\delta + (1-\alpha\delta) F( x+a(x,u,t)\delta, t+\delta) + o(\delta)\right].
\]
Expanding to $O(\delta)$ gives the HJB equation
\[
0=\inf_u \left\{ c(x,u,t) - \alpha F + \frac{\partial F}{\partial t} + a(x,u,t)\frac{\partial F}{\partial x} \right\}
\]
for $t<h$ and $F(x,h)=C(x,h)$.

Q: Solutions of HJB equation
A: Suppose control $u$ has value function $F$ satisfying HJB. Then $u$ is optimal.
\begin{proof}
For another control $v$, along the trajectory $\dot{x}=a(x,v,t)$:
\begin{align*}
-\frac{\d}{\d t} e^{-\alpha t} F(x,t) &= e^{-\alpha t} (\alpha F - F_t - a(x,v,t)F_x) \quad (\text{product and chain rule})\\
&= e^{-\alpha t} \left[ c(x,v,t) - \underbrace{\left( c(x,v,t)-\alpha F + F_t + a(x,v,t)F_x \right)}_{\geq 0}\right] \\
&\leq  e^{-\alpha t} c(x,v,t). \\
\intertext{Integrating from $0$ to $h$ gives}
F(x(0),0) - e^{-\alpha h} C(x(h),h) &\leq \int_0^h e^{-\alpha t} c(x,v,t) \; \d t \\
F(x(0),0)  &\leq \int_0^h e^{-\alpha t} c(x,v,t) \; \d t + e^{-\alpha h} C(x(h),h).
\end{align*}
\end{proof}

Q: Chattering
A: Chattering about the operating point $\bar{x}$ means that $u$ will switch between max and min values either side of $\bar x$.

Q: Pontryagin's Maximum Principle by Hamiltonian
A: Let $S$ be a stopping set with terminal cost $K(x)$ and stopping time $T$. Assuming time-homogeneity, the HJB equation is
\[
0=\inf_{u\in U} \left\{ c(x,u) + \frac{\partial F}{\partial x}a(x,u)\right\}
\]
for $x\not\in S$ and $F(x)=K(x)$ otherwise. Writing $\lambda(t)=-F_x$ (the \emph{adjoint trajectory}), this is equivalent to maximising the Hamiltonian
\[
H(x,u,\lambda)=\lambda^Ta(x,u) - c(x,u).
\]
Let $x(t),u(t)$ be optimal. Then $ \forall t\in[0,T]$:
\begin{align}
\dot x &= H_\lambda = a(x,u) \\
\dot \lambda &= -H_x = -\lambda^Ta_x + c_x
\end{align}
and $H$ is maximised with value 0. Moreover, if $x(T)$ is unconstrained, then at time $T$, $\forall\sigma$ such that $d(x+\varepsilon\sigma,S)=o(\varepsilon)$, we have the transversality condition
\[
(\lambda(T)+K_x)^T\sigma=0.
\]
\begin{proof}
(1) is just the plant equation. For (2), we differentiate the DP equation using summation convention
\begin{align*}
F(x,t) &= c\delta + F(x+a\delta, t+\delta) + o(\delta) \\
\frac{\partial F}{\partial x_i} &=  \delta \frac{\partial c}{\partial x_i} + \frac{\partial F}{\partial x_j}(x+a\delta,t+\delta) \frac{\partial }{\partial x_i} (x_j+a_j\delta) \\
-\lambda_i(t) &=  \delta \frac{\partial c}{\partial x_i} -\lambda_i(t+\delta)-\delta \lambda_j(t+\delta) \frac{\partial a_j}{\partial x_i} + o(\delta) \\
\frac{\d\lambda_i}{\d t} &=  \frac{\partial c}{\partial x_i} - \lambda_j \frac{\partial a_j}{\partial x_i}.
\end{align*}
If $x+\varepsilon\sigma+o(\varepsilon)\in S$, then
\begin{align*}
0 &= F(x+\varepsilon\sigma + o(\varepsilon)) - K(x+\varepsilon\sigma+o(\varepsilon)) \\
&= F-K + (F_x-K_x)^T\varepsilon\sigma + o (\varepsilon) \\
&= - (\lambda+K_x)^T\sigma\varepsilon + o (\varepsilon).
\end{align*}
\end{proof}

Q: PMP by Lagrangian methods
A: We seek to maximise the Lagrangian
\[
L=-K(x(T)) + \int_0^T [-c-\lambda^T(\dot{x}-a)] \; \d t
\]
where $x(t)$ has stopping time $T$ for set $S$. Integrating $\lambda^T\dot{x}$ by parts
\[
L=-K(x(T)) +\lambda(0)x(0)- \lambda(T)^Tx(T) +  \int_0^T [\dot{\lambda}^Tx +\lambda^T a - c] \; \d t.
\]
Differentiating wrt $x(t)$ gives that $\frac{\partial }{\partial x}$ of the integrand vanishes, i.e. $\dot\lambda=-H_x$.
Differentiating wrt $x(T)$ gives the transversality conditions $(K_x+\lambda)^T\sigma=0$ if $d(x+\varepsilon\sigma, S)=o(\varepsilon)$.

Q: Pontryagin with explicit time
A: Let $x_0=t$, $\lambda_0=-F_t$. Then $\dot{x}_0=a_0=1$ and the Hamiltonian becomes
\[
H(x,u,\lambda)=\lambda_0 + \sum_{i=1}^n \lambda_i a_i - c.
\]

Q: Equilibrium solution
A: An equilibrium solution is $u=\bar u, x = \bar x$ where $\dot{x}=0$.

Q: Turnpike theory
A: For sufficiently large $T$, the optimal trajectory will move from $x(0)$ to within an arbitrary neighbourhood of the balanced growth path (\emph{the turnpike}), stay there for all but an arbitrary small fraction of the time and finally leave the path for $x(T)$.