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

Eugene A. Feinberg 1 Jefferson Huang 1 Bruno Scherrer 2
1 SBU - Stony Brook University [The State University of New York]
2 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
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.
Keywords : Markov decision process Modified policy iteration Strongly polynomial Policy Algorithm
Type de document :
Article dans une revue
Operations Research Letters, Elsevier, 2014, 42, pp.429 - 431. 〈10.1016/j.orl.2014.07.006〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01091370
Contributeur : Bruno Scherrer <>
Soumis le : vendredi 5 décembre 2014 - 11:48:44
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : lundi 9 mars 2015 - 06:02:58

Fichiers

Feinberg_Huang_Scherrer.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | UNIV-LORRAINE | LORIA-AIS | LORIA

Citation

Eugene A. Feinberg, Jefferson Huang, Bruno Scherrer. Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming. Operations Research Letters, Elsevier, 2014, 42, pp.429 - 431. 〈10.1016/j.orl.2014.07.006〉. 〈hal-01091370〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

752

Téléchargements de fichiers

168

Contact


archive-ouverte@inria.fr