Given a Markov Decision Process (MDP) with $n$ states and a totalnumber $m$\nof actions, we study the number of iterations needed byPolicy Iteration (PI)\nalgorithms to converge to the optimal$\\gamma$-discounted policy. We consider\ntwo variations of PI: Howard'sPI that changes the actions in all states with a\npositive advantage,and Simplex-PI that only changes the action in the state\nwith maximaladvantage. We show that Howard's PI terminates after at most\n$O\\left(\\frac{m}{1-\\gamma}\\log\\left(\\frac{1}{1-\\gamma}\\right)\\right)$iterations,\nimproving by a factor $O(\\log n)$ a result by Hansen etal., while Simplex-PI\nterminates after at most\n$O\\left(\\frac{nm}{1-\\gamma}\\log\\left(\\frac{1}{1-\\gamma}\\right)\\right)$iterations,\nimproving by a factor $O(\\log n)$ a result by Ye. Undersome structural\nproperties of the MDP, we then consider bounds thatare independent of the\ndiscount factor~$\\gamma$: quantities ofinterest are bounds $\\tau\\_t$ and\n$\\tau\\_r$---uniform on all states andpolicies---respectively on the\n\\emph{expected time spent in transientstates} and \\emph{the inverse of the\nfrequency of visits in recurrentstates} given that the process starts from the\nuniform distribution.Indeed, we show that Simplex-PI terminates after at most\n$\\tilde O\\left(n^3 m^2 \\tau\\_t \\tau\\_r \\right)$ iterations. This extends\narecent result for deterministic MDPs by Post & Ye, in which $\\tau\\_t\\le 1$ and\n$\\tau\\_r \\le n$, in particular it shows that Simplex-PI isstrongly polynomial\nfor a much larger class of MDPs. We explain whysimilar results seem hard to\nderive for Howard's PI. Finally, underthe additional (restrictive) assumption\nthat the state space ispartitioned in two sets, respectively states that are\ntransient andrecurrent for all policies, we show that both Howard's PI\nandSimplex-PI terminate after at most $\\tilde\nO(m(n^2\\tau\\_t+n\\tau\\_r))$iterations.\n