# How to establish the optimal value functions and optimal control policy for a controlled random walk problem?

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.