Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming

Eugene A. Feinberg; Jefferson Huang; Bruno Scherrer

doi:10.1016/j.orl.2014.07.006

Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming

Eugene A. Feinberg
, Jefferson Huang
, Bruno Scherrer

Applied Mathematics and Statistics

Stony Brook University

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

4 Scopus citations

Abstract

This note shows that the number of arithmetic operations required by any member of a broad class of optimistic policy iteration algorithms to solve a deterministic discounted dynamic programming problem with three states and four actions may grow arbitrarily. Therefore any such algorithm is not strongly polynomial. In particular, the modified policy iteration and λ-policy iteration algorithms are not strongly polynomial.

Original language	English
Pages (from-to)	429-431
Number of pages	3
Journal	Operations Research Letters
Volume	42
Issue number	6-7
DOIs	https://doi.org/10.1016/j.orl.2014.07.006
State	Published - Sep 2014

Keywords

Algorithm
Markov decision process
Modified policy iteration
Policy
Strongly polynomial

Access to Document

10.1016/j.orl.2014.07.006

Cite this

@article{a059793c50614bdf903f2332e4e90064,

title = "Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming",

abstract = "This note shows that the number of arithmetic operations required by any member of a broad class of optimistic policy iteration algorithms to solve a deterministic discounted dynamic programming problem with three states and four actions may grow arbitrarily. Therefore any such algorithm is not strongly polynomial. In particular, the modified policy iteration and λ-policy iteration algorithms are not strongly polynomial.",

keywords = "Algorithm, Markov decision process, Modified policy iteration, Policy, Strongly polynomial",

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

year = "2014",

month = sep,

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

language = "English",

volume = "42",

pages = "429--431",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "6-7",

}

TY - JOUR

T1 - Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming

AU - Feinberg, Eugene A.

AU - Huang, Jefferson

AU - Scherrer, Bruno

PY - 2014/9

Y1 - 2014/9

N2 - This note shows that the number of arithmetic operations required by any member of a broad class of optimistic policy iteration algorithms to solve a deterministic discounted dynamic programming problem with three states and four actions may grow arbitrarily. Therefore any such algorithm is not strongly polynomial. In particular, the modified policy iteration and λ-policy iteration algorithms are not strongly polynomial.

AB - This note shows that the number of arithmetic operations required by any member of a broad class of optimistic policy iteration algorithms to solve a deterministic discounted dynamic programming problem with three states and four actions may grow arbitrarily. Therefore any such algorithm is not strongly polynomial. In particular, the modified policy iteration and λ-policy iteration algorithms are not strongly polynomial.

KW - Algorithm

KW - Markov decision process

KW - Modified policy iteration

KW - Policy

KW - Strongly polynomial

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

U2 - 10.1016/j.orl.2014.07.006

DO - 10.1016/j.orl.2014.07.006

M3 - Article

SN - 0167-6377

VL - 42

SP - 429

EP - 431

JO - Operations Research Letters

JF - Operations Research Letters

IS - 6-7

ER -

Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this