My major is CS and I have a question about Markov decision process.
I have been reading a book, planning with markov decision process an AI perspective. While reading it, I have a question regarding the definition of MDP and its generality.
The 2nd order Markov chain can be transformed into 1st order Markov chain. So any stochastic process that is depend on limited length history can be eventually 1st order Markov chain.
I think Markov Decision Process is the most general one when we consider discrete and finite state space. I don't know if there is non-Markovian decision process.
If we want to find optimal policy of an MDP with respect to maximum total expected utility (M.E.U) using value iteration, dynamic programming; if connectivity graph of MDP is acyclic, value iteration is same as Bellman-Ford shortest path finding algorithm.
I am curious about if there is something different decision process that can't be solved by dynamic programming when we are still finding an optimal policy w.r.t. M.E.U?
The question itself is confusing, but simply my question is MDP is the most general one if the state space is finite?
The additional question is when we are optimizing w.r.t. other metrics than M.E.U, the MDP can be solved by dynamic programming?
I hope someone suggest directions to explore this field.
Thanks in advance.