Title :
Polynomial classification algorithms for Markov decision processes
Author :
Feinberg, Eugene A. ; Yang, Fenghsu
Author_Institution :
Dept. of Appl. Math & Stat., State Univ. of New York at Stony Brook, Stony Brook, NY, USA
Abstract :
The unichain classification problem detects whether an MDP with finite states and actions is unichain or not under all deterministic policies. This problem has been proven to be NP-hard. This paper provides polynomial algorithms for this problem while there exists a state in an MDP, which is either recurrent under all deterministic policies or absorbing under some action.
Keywords :
Markov processes; optimisation; pattern classification; polynomials; Markov decision processes; NP-hard problem; polynomial classification algorithms; unichain classification problem; Classification algorithms; Inventory control; Polynomials; State-space methods; Statistics; Stochastic processes;
Conference_Titel :
Decision and Control, 2008. CDC 2008. 47th IEEE Conference on
Conference_Location :
Cancun
Print_ISBN :
978-1-4244-3123-6
Electronic_ISBN :
0191-2216
DOI :
10.1109/CDC.2008.4739391
