Howard termine après au plus n(m?1) (?? t log n? t ? + ?? r log n? r ?) itérations tandis que IP-Simplexe termine après au plus n(m ? 1) (?n? t log n? t ? + ?? r log n? r ?) itérations ,
analyse de la deuxième phase (convergence sur les états transients) est similaire à celle du cas avec facteur d'actualisation ? (Théorèmes 3 et 5) En d'autres termes, si ce dernier résultat contribue à nous éclairer sur l'efficacité pratique usuelle de IP-Howard et IP-Simplexe, une analyse plus générale de IP-Howard est encore à faire ,
le but est de minimiser l'espérance de la somme actualisée des coûts. La fonction valeur optimale satisfait v * (i) = ?p N pour tout i, avec N = p 2 + p. Les politiques générées par IP-Howard ont des fonctions valeur satisfaisant v? k (i) ? [p N ?k?1 , p N ?k ]. On en déduit que pour toute itération k et tout état i, v * (i)?v? k+1 (i) v * (i)?v? k (i) ? ,
Neurodynamic Programming, 1996. ,
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor, J. ACM, vol.60, issue.1, pp.1-1, 2013. ,
Lower bounds for howard's algorithm for finding minimum mean-cost cycles, pp.415-426, 2010. ,
The complexity of policy iteration is exponential for discounted markov decision processes, 51st IEEE conference on Decision and control (CDC'12), 2012. ,
On the complexity of policy iteration, UAI, pp.401-408, 1999. ,
On the complexity of the policy improvement algorithm for markov decision processes, INFORMS Journal on Computing, vol.6, issue.2, pp.188-192, 1994. ,
The simplex method is strongly polynomial for deterministic Markov decision processes, Rapport interne, 2012. ,