Question: How to establish an explicit characterization of both the optimal value functions and the optimal control policy for a controlled random walk?


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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.