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

Eugene A. Feinberg 1 Jefferson Huang 1 Bruno Scherrer 2
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.
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

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〉

Partager

Métriques

Consultations de la notice

689

Téléchargements de fichiers

157