# How to model history-dependent dynamic program?

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.

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.

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.

• Thank you so much Dylan. I am wondering if you can recommend some papers dealing with this issue and how they handled the problem? Thanks
– Amin
Jun 12, 2022 at 6:22
• Aug 3, 2022 at 11:23
• My thesis should be ready by the end of this year. It discusses all the caveats of the above-mentioned approach and how to model situations with many asynchronous and concurrent process that produce history dependence. I will link it when it has been marked. The main issue with the phase-type distribution approach is that one now actually has a Partially Observable Markov Decision Process. Aug 3, 2022 at 11:26