Polynomial classification algorithms for Markov decision processes

Eugene A. Feinberg; Fenghsu Yang

doi:10.1109/CDC.2008.4739391

Polynomial classification algorithms for Markov decision processes

Eugene A. Feinberg
, Fenghsu Yang

Applied Mathematics and Statistics

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

Original language	English
Title of host publication	Proceedings of the 47th IEEE Conference on Decision and Control, CDC 2008
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4485-4490
Number of pages	6
ISBN (Print)	9781424431243
DOIs	https://doi.org/10.1109/CDC.2008.4739391
State	Published - 2008
Event	47th IEEE Conference on Decision and Control, CDC 2008 - Cancun, Mexico Duration: Dec 9 2008 → Dec 11 2008

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	47th IEEE Conference on Decision and Control, CDC 2008
Country/Territory	Mexico
City	Cancun
Period	12/9/08 → 12/11/08

Access to Document

10.1109/CDC.2008.4739391

Cite this

Feinberg, E. A., & Yang, F. (2008). Polynomial classification algorithms for Markov decision processes. In Proceedings of the 47th IEEE Conference on Decision and Control, CDC 2008 (pp. 4485-4490). Article 4739391 (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2008.4739391

@inproceedings{82a768b0a9554c3192dbdefdc3d0cb58,

title = "Polynomial classification algorithms for Markov decision processes",

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.",

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

year = "2008",

doi = "10.1109/CDC.2008.4739391",

language = "English",

isbn = "9781424431243",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "4485--4490",

booktitle = "Proceedings of the 47th IEEE Conference on Decision and Control, CDC 2008",

note = "47th IEEE Conference on Decision and Control, CDC 2008 ; Conference date: 09-12-2008 Through 11-12-2008",

}

Feinberg, EA & Yang, F 2008, Polynomial classification algorithms for Markov decision processes. in Proceedings of the 47th IEEE Conference on Decision and Control, CDC 2008., 4739391, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 4485-4490, 47th IEEE Conference on Decision and Control, CDC 2008, Cancun, Mexico, 12/9/08. https://doi.org/10.1109/CDC.2008.4739391

Polynomial classification algorithms for Markov decision processes. / Feinberg, Eugene A.; Yang, Fenghsu.
Proceedings of the 47th IEEE Conference on Decision and Control, CDC 2008. Institute of Electrical and Electronics Engineers Inc., 2008. p. 4485-4490 4739391 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Polynomial classification algorithms for Markov decision processes

AU - Feinberg, Eugene A.

AU - Yang, Fenghsu

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

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

U2 - 10.1109/CDC.2008.4739391

DO - 10.1109/CDC.2008.4739391

M3 - Conference contribution

AN - SCOPUS:62949138893

SN - 9781424431243

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 4485

EP - 4490

BT - Proceedings of the 47th IEEE Conference on Decision and Control, CDC 2008

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 47th IEEE Conference on Decision and Control, CDC 2008

Y2 - 9 December 2008 through 11 December 2008

ER -

Polynomial classification algorithms for Markov decision processes

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this