Consider the scalar system with plant equation $x_{t+1}=x_{t}+u_{t}, t=0,1, \ldots$ and cost

$$C_{s}\left(x_{0}, u_{0}, u_{1}, \ldots\right)=\sum_{t=0}^{s}\left[u_{t}^{2}+\frac{4}{3} x_{t}^{2}\right]$$

Show from first principles that $\min _{u_{0}, u_{1}, \ldots} C_{s}=V_{s} x_{0}^{2}$, where $V_{0}=4 / 3$ and for $s=0,1, \ldots$

$$V_{s+1}=4 / 3+V_{s} /\left(1+V_{s}\right)$$

Show that $V_{s} \rightarrow 2$ as $s \rightarrow \infty$.

Prove that $C_{\infty}$ is minimized by the stationary control, $u_{t}=-2 x_{t} / 3$ for all $t$.

Consider the stationary policy $\pi_{0}$ that has $u_{t}=-x_{t}$ for all $t$. What is the value of $C_{\infty}$ under this policy?

Consider the following algorithm, in which steps 1 and 2 are repeated as many times as desired.

1. For a given stationary policy $\pi_{n}$, for which $u_{t}=k_{n} x_{t}$ for all $t$, determine the value of $C_{\infty}$ under this policy as $V^{\pi_{n}} x_{0}^{2}$ by solving for $V^{\pi_{n}}$ in

$$V^{\pi_{n}}=k_{n}^{2}+4 / 3+\left(1+k_{n}\right)^{2} V^{\pi_{n}}$$

2. Now find $k_{n+1}$ as the minimizer of

$$k_{n+1}^{2}+4 / 3+\left(1+k_{n+1}\right)^{2} V^{\pi_{n}}$$

and define $\pi_{n+1}$ as the policy for which $u_{t}=k_{n+1} x_{t}$ for all $t$.

Explain why $\pi_{n+1}$ is guaranteed to be a better policy than $\pi_{n}$.

Let $\pi_{0}$ be the stationary policy with $u_{t}=-x_{t}$. Determine $\pi_{1}$ and verify that it minimizes $C_{\infty}$ to within $0.2 \%$ of its optimum.