Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems

Eugene A. Feinberg; Jefferson Huang

doi:10.1016/j.orl.2013.02.002

Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems

Eugene A. Feinberg
, Jefferson Huang

Applied Mathematics and Statistics

Stony Brook University

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

8 Scopus citations

Abstract

This note considers an average-cost Markov Decision Process (MDP) with finite state and action sets and satisfying the additional condition that there is a state to which the system jumps from any state and under any action with a positive probability. The main result is that the policy iteration algorithm is strongly polynomial for such MDPs, which are often used to model replacement and maintenance problems.

Original language	English
Pages (from-to)	249-251
Number of pages	3
Journal	Operations Research Letters
Volume	41
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2013.02.002
State	Published - May 2013

Keywords

Average cost
Linear program
Markov Decision Process
Policy iteration algorithm
Simplex method
Strongly polynomial

Access to Document

10.1016/j.orl.2013.02.002

Cite this

@article{2a8a874615a54279b8c5e115a6bbb3d9,

title = "Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems",

abstract = "This note considers an average-cost Markov Decision Process (MDP) with finite state and action sets and satisfying the additional condition that there is a state to which the system jumps from any state and under any action with a positive probability. The main result is that the policy iteration algorithm is strongly polynomial for such MDPs, which are often used to model replacement and maintenance problems.",

keywords = "Average cost, Linear program, Markov Decision Process, Policy iteration algorithm, Simplex method, Strongly polynomial",

author = "Feinberg, \{Eugene A.\} and Jefferson Huang",

year = "2013",

month = may,

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

language = "English",

volume = "41",

pages = "249--251",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "3",

}

TY - JOUR

T1 - Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems

AU - Feinberg, Eugene A.

AU - Huang, Jefferson

PY - 2013/5

Y1 - 2013/5

N2 - This note considers an average-cost Markov Decision Process (MDP) with finite state and action sets and satisfying the additional condition that there is a state to which the system jumps from any state and under any action with a positive probability. The main result is that the policy iteration algorithm is strongly polynomial for such MDPs, which are often used to model replacement and maintenance problems.

AB - This note considers an average-cost Markov Decision Process (MDP) with finite state and action sets and satisfying the additional condition that there is a state to which the system jumps from any state and under any action with a positive probability. The main result is that the policy iteration algorithm is strongly polynomial for such MDPs, which are often used to model replacement and maintenance problems.

KW - Average cost

KW - Linear program

KW - Markov Decision Process

KW - Policy iteration algorithm

KW - Simplex method

KW - Strongly polynomial

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

U2 - 10.1016/j.orl.2013.02.002

DO - 10.1016/j.orl.2013.02.002

M3 - Article

AN - SCOPUS:84874943318

SN - 0167-6377

VL - 41

SP - 249

EP - 251

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this