Markov Decision Process and its generality

Question

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.

Answer 1

To answer your questions:

1) Is MDP the most general type of stochastic decision process? No, there also exist various kinds of non-markovian processes. Semi-Markov Decision Processes are also popular to model stochastic control problems where the time spent in each state is not constant but itself a continuous random variable

2) Can the MDP be solved by dynamic programming with other "metrics" than MEU? Well, the maximisation of expected utility does not by itself constitute a particular metric, as there are many ways of definining the utility w.r.t. the reward function. For instance, you may or may not used a discount factor, you may use a finite or infinite horizon, etc. All these variants can be solved by dynamic programming. If you define "metrics" outside this family of functions, of course it may be necessary to use other types of solution methods than dynamic programming.