P. Si-le, 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

. De, 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

P. Ce and . Un-nombre-pair, 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) ?

B. D. Références and . Tsitsiklis-j, Neurodynamic Programming, 1996.

H. T. and M. P. Zwick-u, 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.

H. T. Zwick-u, Lower bounds for howard's algorithm for finding minimum mean-cost cycles, pp.415-426, 2010.

H. R. and D. J. Jungers-r, The complexity of policy iteration is exponential for discounted markov decision processes, 51st IEEE conference on Decision and control (CDC'12), 2012.

M. Y. Singh-s, On the complexity of policy iteration, UAI, pp.401-408, 1999.

M. M. Condon-a, On the complexity of the policy improvement algorithm for markov decision processes, INFORMS Journal on Computing, vol.6, issue.2, pp.188-192, 1994.

P. I. Ye-y, The simplex method is strongly polynomial for deterministic Markov decision processes, Rapport interne, 2012.