The complexity of Policy Iteration is exponential for discounted Markov Decision Processes. Hollanders, R., Delvenne, J., & Jungers, R. M. In CDC, pages 5997-6002, 2012. IEEE.
bibtex   
@inproceedings{HDJ12,
	Author = {Hollanders, Romain and Delvenne, Jean-Charles and Jungers, Raphael M.},
	Booktitle = {CDC},
	Date-Added = {2014-11-14 04:04:26 +0000},
	Date-Modified = {2014-11-14 04:04:43 +0000},
	Keywords = {dblp},
	Pages = {5997-6002},
	Publisher = {IEEE},
	Title = {The complexity of Policy Iteration is exponential for discounted Markov Decision Processes.},
	Year = 2012,
	Bdsk-Url-1 = {http://dblp.uni-trier.de/db/conf/cdc/cdc2012.html#HollandersDJ12}}

Downloads: 0