| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
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 $\lambda$-policy iteration algorithms are not strongly polynomial.
Cited literature [16 references]
https://hal.inria.fr/hal-01091370
Contributor : Bruno Scherrer <>
Submitted on : Friday, December 5, 2014 - 11:48:44 AM
Last modification on : Tuesday, August 13, 2019 - 11:22:21 AM
Long-term archiving on: : Monday, March 9, 2015 - 6:02:58 AM
Contributor : Bruno Scherrer <>
Submitted on : Friday, December 5, 2014 - 11:48:44 AM
Last modification on : Tuesday, August 13, 2019 - 11:22:21 AM
Long-term archiving on: : Monday, March 9, 2015 - 6:02:58 AM
Files
Feinberg_Huang_Scherrer.pdf
Files produced by the author(s)