Classification Problems in MDPs

In this paper we investigate classification problems for Markov deci-sion processes (MDPs). These MDPs can be classified in several ways. One way is based on the concept communicating, and distinguishes between communicating, weakly communicating and noncommunicating. Another way of classification is based on the ergodic structure. In this approach the distinction between completely ergodic, unichain and multichain is made. Furthermore, there is a classification based on decomposition of the state space. This decomposition distinguishes between several levels. At each level there is a set of recurrent classes and a (perhaps empty) set of transient states. Classification of an MDP may be of interest, e.g. for undiscounted MDPs both in the unconstrained as in the constrained case. We review all these classification problems and present old and new results. It turns out that these problems, except one, can be solved in polynomial time; algorithms and complexity results are given. The only problem for which, to our knowledge, no polynomial-time algorithm is known, is the distinction between a unichain and a multichain MDP. For this problem, we have some partial results which can be obtained in polynomial time.