Consider a state $x_t$ that probabilistically evolves over time according to a controlled Markov chain, i.e., according to known probabilities

$$\mathbb P(x_{t+1}=x' \,|\, x_t=x,a_t=a)$$

where $a_t$ is the control action at time $t$. To each state $x$, a known reward $r(x)$ is assigned. Actions have no cost. Our objective is to find the sequence of actions so as to maximize the expected reward at a given final time, $\mathbb E[r(x_T)]$. We do not care about rewards before the final time.

It seems that this problem can naturally be addressed by dynamic programming. I've defined the final value function as follows

\begin{align} V_T(x_T) = r(x_T) \end{align}

and value functions for each $t<T$ as

\begin{align} V_t(x) &= \max_{a\in A}\mathbb{E} \Big( V_{t+1}(f(x_t,a_t)) \mid x_t=x,a_t=a \Big)\\ &= \max_{a\in A}\sum_{x'} \mathbb P(x_{t+1}=x' \,|\, x_t=x,a_t=a) V_{t+1}(x') \end{align}

I am confused about how to actually implement this (I'm trying to write the pseudocode). I don't know how to initialize the problem. In a lot of dynamic programming approaches they set the value function at the final time to be zero, but that doesn't seem to make any sense here.

Question: How do I implement the dynamic programming equations above?

My ideas so far: Since we know the reward function, perhaps we can initialize $V_T(x)$ to $r(x)$ for every possible $x$? Then using the value functions $V_t(x)$, $t<T$, we can step back all the way to $V_0(x)$. Doing this for every possible $x$ and keeping track of the optimizers will give us a table of optimal actions $a$ for any state $x$ that we may encounter. Is this correct?

  • $\begingroup$ For each state $x$, you want to find the sequence of actions $a_1,\ldots,a_{T-1}$ which maximizes $$\left[\prod_{i=1}^{T-1} P^{a_i}\right]_{x\cdot} r, $$ where $P^a$ denotes the transition matrix corresponding to action $a_i$, $P^a_{x\cdot}$ denotes the row of $P^a$ corresponding to state $x$, and $r$ is a row vector of the $r(x)$. $\endgroup$ – Math1000 Jun 13 '18 at 5:46
  • $\begingroup$ @Math1000 Hmm, is there a way to address this using dynamic programming? $\endgroup$ – jonem Jun 13 '18 at 14:36
  • $\begingroup$ Have you heard of / read about Markov Decision Processes (MDPs)? $\endgroup$ – David M. Jun 22 '18 at 17:37
  • $\begingroup$ And why do you say that having a terminal value of zero doesn’t make sense? Worst case you can add a dummy absorbing state at time $T$. $\endgroup$ – David M. Jun 22 '18 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.