On polynomial cases of the unichain classification problem for Markov Decision Processes

Eugene A. Feinberg; Fenghsu Yang

doi:10.1016/j.orl.2008.06.002

On polynomial cases of the unichain classification problem for Markov Decision Processes

Eugene A. Feinberg
, Fenghsu Yang

Applied Mathematics and Statistics

Stony Brook University

Stony Brook University

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

The Unichain classification problem detects whether a finite state and action MDP is unichain under all deterministic policies. This problem is N P-hard. This paper provides polynomial algorithms for this problem when there is a state that is either recurrent under all deterministic policies or absorbing under some action.

Original language	English
Pages (from-to)	527-530
Number of pages	4
Journal	Operations Research Letters
Volume	36
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2008.06.002
State	Published - Sep 2008

Keywords

Markov Decision Process
Recurrent state
Unichain condition

Access to Document

10.1016/j.orl.2008.06.002

Cite this

@article{6ce58da84abb49ee9eeebfeb8abcd6c4,

title = "On polynomial cases of the unichain classification problem for Markov Decision Processes",

abstract = "The Unichain classification problem detects whether a finite state and action MDP is unichain under all deterministic policies. This problem is N P-hard. This paper provides polynomial algorithms for this problem when there is a state that is either recurrent under all deterministic policies or absorbing under some action.",

keywords = "Markov Decision Process, Recurrent state, Unichain condition",

author = "Feinberg, \{Eugene A.\} and Fenghsu Yang",

year = "2008",

month = sep,

doi = "10.1016/j.orl.2008.06.002",

language = "English",

volume = "36",

pages = "527--530",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - On polynomial cases of the unichain classification problem for Markov Decision Processes

AU - Feinberg, Eugene A.

AU - Yang, Fenghsu

PY - 2008/9

Y1 - 2008/9

N2 - The Unichain classification problem detects whether a finite state and action MDP is unichain under all deterministic policies. This problem is N P-hard. This paper provides polynomial algorithms for this problem when there is a state that is either recurrent under all deterministic policies or absorbing under some action.

AB - The Unichain classification problem detects whether a finite state and action MDP is unichain under all deterministic policies. This problem is N P-hard. This paper provides polynomial algorithms for this problem when there is a state that is either recurrent under all deterministic policies or absorbing under some action.

KW - Markov Decision Process

KW - Recurrent state

KW - Unichain condition

UR - https://www.scopus.com/pages/publications/50249167647

U2 - 10.1016/j.orl.2008.06.002

DO - 10.1016/j.orl.2008.06.002

M3 - Article

SN - 0167-6377

VL - 36

SP - 527

EP - 530

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

On polynomial cases of the unichain classification problem for Markov Decision Processes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this