Question: How to establish an explicit characterization of both the optimal value functions and the optimal control policy for a controlled random walk?
Background:
Assume our system is a perfectly-observed stochastic control system whose state-transition map (STM) is: $$x_{t+1} = x_t + u_t + w_t.$$
We know that $x_0 \sim \mathcal{N}(0, \lambda^2)$ and $w_t \sim \mathcal{N}(0, \sigma^2)$ are normally distributed variables that are independent from one another.
The goal is to find the control policy $\pi = (\mu_0, ..., \mu_{T-1})$ that takes the random walk closer to a target $\tau$. The expected minimum cost for the optimal policy is expressed by:
$$J(\pi^*) = \inf\limits_{\pi \in \Pi} \mathbb{E}\left[(x_T^\pi - \tau)^2 + \sum_{t=0}^{T-1} (u_t^\pi)^2\right]$$
My work so far:
First, let's establish some facts.
- $J(\pi^*)$ is the expected cost of the optimal policy $\pi^*_t \in \Pi_M$.
- The optimal policy $\pi^*_t$ is such that: {$\pi^*_t \in \text{argmin}_{\pi \in \Pi} J(\pi)$}
- Ergo, $J(\pi^*) = J^*$ is the expected minimum cost.
- $J(\pi^*) = \mathbb{E}[J^{\pi^*}_0]$
- The optimal value function $\{V^*_t\}_{t=0}^T$ is a sequence of functions such that: $$V^*_T(x) = g_{_T}(x)$$ $$V^*_t(x) = \inf\limits_{u \in \mathbb{U}_t(x)} \{g_t(x_t,u_t) + \mathbb{E}_{w_t}[V_{t+1}^*(f_t(x_t,u_t,w_t))]\}$$
Breaking down the optimal expected cost structure, we have:
$g_{_T}(x_{_T}^{\pi^*}) = (x_{_T}^{\pi^*} - \tau)^2$
$g_t(x_t,u_t) = g_t(u_t) = (u_t^{\pi^*})^2$
With that, the optimal value function can be characterized as for its last stage $t = T$ and for intermediate time steps $t = 0, ..., T-1$.
For $t = T$:
- $V^*_T(x) = g_{_T}(x) = (x_{_T}^{\pi^*} - \tau)^2$
For $t = 0, ..., T-1$
- $V_t^*(x) = \inf\limits_{u \in \mathbb{U}_t(x)} \{g_t(x_t,u_t) + \mathbb{E}_{w_t}[V_{t+1}^*(f_t(x_t,u_t,w_t))]\}$
I worked out the DP equation for stage $t = T-1$, where $T+1$ will be my final stage.
$V_{T-1}^*(x) = \inf\limits_{u \in \mathbb{U}_t(x)} \{ (u_{T-1}^{\pi})^2 + \mathbb{E}_{w_t}[V_{t+1}(x_{t+1})]\}$
$V_{T-1}^*(x) = \inf\limits_{u \in \mathbb{U}_t(x)} \{ (u_{T-1}^{\pi})^2 + \mathbb{E}_{w_t}[(x_{_T}^{\pi} - \tau)^2]\}$
$V_{T-1}^*(x) = \inf\limits_{u \in \mathbb{U}_t(x)} \{ (u_{T-1}^{\pi})^2 + (x_{_T}^{\pi} - \tau)^2\}$
$V_{T-1}^*(x) = \inf\limits_{u \in \mathbb{U}_t(x)} \{ (x_{T} - x_{T-1} - w_{T-1})^2 + (x_{_T}^{\pi} - \tau)^2\}$
$V_{T-1}^*(x) = \inf\limits_{u \in \mathbb{U}_t(x)} \{ 2x_T^2 - 2x_T(x_{T-1} + w_{T-1} + \tau) + x_{T-1}^2 + 2x_{T-1}w_{T-1} + w_{T-1}^2 + \tau^2\}$
Here's where I run into problems. My minimization problem is to be taken over the actions $u_t$, however, my final solution (the last equation above) does not depend on it. If I were to try to find the optimal decision by the first-order optimality condition, I'd fail from the get-go because there's no $u_t$ in my equation. This isn't surprising, after all, I made the substitution. However, I only substitute $u_t$ as I did because, from my understand of the expected (minimum) optimal cost, the stage-cost structure is $(u_t)^2$. And I need that substitution when I have the optimal value function $V_{T-1}$.
Through my STM, I can isolate $u_t$ and plug that result into my cost structure. However, I don't think this is the right way to go. How should I proceed?
I also worked out the same equation for $t = T-2$ and, although different, I also ended with an equation that does not depend on $u$, ergo, not useful for a first-order optimality condition that depends on $u$. This is part of an assignment; therefore, feel free to give me hints or point me into the right direction rather than writing a full answer.
