1
$\begingroup$

Suppose there is a dynamic program that the state of the problem grows over time (more info is added to the state of the problem over time) and at each time, we need all historical data, full history. My first question is if this model can be considered a Markov decision process? In an MDP, the state of current time should be based on the state of the problem in the former time period. Here, this is true but we have gathered all information.

My second question is what are the general approaches to solve history-dependent dynamic programs? I would be thankful if you can share some references for discrete and continuous-time problems.

$\endgroup$
1

1 Answer 1

2
$\begingroup$

First question answer

Yes, a history-dependent process can be considered as a Markov decision process. Consider a history recalling states, costs and actions taken up to the current state $\mathcal {H}(x_k) = \{ x_0,c_0,a_0,\cdots ,x_{k-1},c_{k-1},a_{k-1} \}$. The usual first-order Markov property states that the conditional probability of future states depends only on the current state. In other words, given the current state the future is independent of the past. Moreover, $x_k$ is a sufficient statistic of the history as to predict the future. Hence, $x_k = S(\mathcal {H}(x_k))$ in the case of a first-order Markov system. Such memory-less system are quite common as you might know.

The general Markov property asks for the conditional probability of future states to be independent of the past given a sufficient statistic of the history. Hence, $p_{i,j} = \mathscr{P}(x_{k+1}=j \mid S(\mathcal{H}(x_k=i)))$ instead of $p_{i,j} = \mathscr{P}(x_{k+1}=j \mid x_k=i)$. Two extremes exist now: the current state is a sufficient statistic or the entire history is a sufficient statistic.

Second question answer

The first order Markov property is great as it makes problems computationally tractable. More specifically, only one nuisance parameter exist in the Chapman-Kolmogorov equation which means only one summation or integration is required to make predictions about the future. To see this consider predicting $x_{n+1}$ but it depends on $S(\mathcal {H}(x_n)) = (x_0,x_1,\cdots,x_n)$ then $$ \mathscr{P}(x_{n}) = \sum_{x_1 \in X} \cdots \sum_{x_n \in X} \mathscr{P}(x_{n+1}|x_{n}) \mathscr{P}(x_{n}|x_{n-1})\cdots , \mathscr{P}(x_{2}|x_{1}) \mathscr{P}(x_{1}|x_{0}). $$ So one can conclude that a high-dimensional summation or integral renders most history-dependent problems intractable to compute. A sufficient statistic of either small size or one with nice structural properties needs to be identified as to solve a history-dependent process

In the former, a few statistics can be concatenated along with the current states to build an augmented state or some tuple e.g. $\tilde{x}_k =(x_k,f_k,g_k)$. Hence, $\mathscr{P}(\tilde{x}_k\mid \tilde{x}_{k-1})$ is first-order Markov. Note how the size of the state-space explodes. Hence, this is only reserved for a few problems. An interesting application of state-space augmentation is storing the lifetimes of non-memory-less (not exponentially distributed) processes along with the current state as to predict the future though the conditional probability distributions. See A Formalism for Stochastic Decision Processes with Asynchronous Events.

The second approach has to do with Partially Observable Markov Decision Processes (POMDPs). The current state depends on the entire history of states, actions and observations. However, a sufficient statistic is a belief distribution computed iteratively using Bayes formula. Hence a POMDP is solved as a MDP over belief space. But belief space is continuous. However, the value functions are piece-wise linear and convex which is a structural property that allows for exact solutions. Unfortunately, this approach is limited to small problems.

Conclusion

Incorporating history into a MDP is possible. It is computationally demanding and does not always produce much a benefit in predictions anyways.

$\endgroup$
3

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .