 Classification Problems in MDPsL. C. M. Kallenberg
Chapter Chapter 9 in Markov Processes and Controlled Markov Chains, 2002, pp 151-165 from Springer Abstract: Abstract 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. Date: 2002 There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-0265-0_9 Ordering information: This item can be ordered from DOI: 10.1007/978-1-4613-0265-0_9 Access Statistics for this chapter More chapters in Springer Books from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.