Improved and Generalized Upper Bounds on the Complexity of Policy Iteration
Given a Markov Decision Process (MDP) with n states and m actions per state, we study the number of iterations needed by Policy Iteration (PI) algorithms to converge to the optimal "-discounted optimal policy. We consider two variations of PI: Howard's PI that changes the actions in all states with a positive advantage, and Simplex-PI that only changes the action in the state with maximal advantage. We show that Howard's PI terminates after at most n(m ≠ 1)
improving by a factor O(log n) a result by [3], while Simplex-PI terminates after at most n 2 (m ≠ 1)
iterations, improving by a factor O(log n) a result by [11]. Under some structural assumptions of the MDP, we then consider bounds that are independent of the discount factor ": given a measure of the maximal transient time · t and the maximal time · r to revisit states in recurrent classes under all policies, we show that Simplex-PI terminates after at most n 2 (m≠ 1) (Á· r log(n· r )Ë + Á· r log(n· t )Ë)
iterations. This generalizes a recent result for deterministic MDPs by [8], in which · t AE n and · r AE n. We explain why similar results seem hard to derive for Howard's PI. Finally, under the additional (restrictive) assumption that the state space is partitioned in two sets, respectively states that are transient and recurrent for all policies, we show that Howard's PI terminates after at most n(m ≠ 1) (Á· t log n· t Ë + Á· r log n· r Ë) =Õ(nm(· t + · r )) iterations while Simplex-PI terminates after n(m ≠ 1) (Án· t log n· t Ë + Á· r log n· r Ë) = O(n 2 m(· t + · r )) iterations.
improving by a factor O(log n) a result by [3], while Simplex-PI terminates after at most n 2 (m ≠ 1)
iterations, improving by a factor O(log n) a result by [11]. Under some structural assumptions of the MDP, we then consider bounds that are independent of the discount factor ": given a measure of the maximal transient time · t and the maximal time · r to revisit states in recurrent classes under all policies, we show that Simplex-PI terminates after at most n 2 (m≠ 1) (Á· r log(n· r )Ë + Á· r log(n· t )Ë) # (m ≠ 1)Án· t log(n· t )Ë + Án· t log(n 2 · t )Ë
iterations. This generalizes a recent result for deterministic MDPs by [8], in which · t AE n and · r AE n. We explain why similar results seem hard to derive for Howard's PI. Finally, under the additional (restrictive) assumption that the state space is partitioned in two sets, respectively states that are transient and recurrent for all policies, we show that Howard's PI terminates after at most n(m ≠ 1) (Á· t log n· t Ë + Á· r log n· r Ë) =Õ(nm(· t + · r )) iterations while Simplex-PI terminates after n(m ≠ 1) (Án· t log n· t Ë + Á· r log n· r Ë) = O(n 2 m(· t + · r )) iterations.
Summary: The paper considers the complexity of 
      policy iteration (PI) for finite MDPs with n states and m actions per 
      state in a number of settings. The following results are derived: 
      For Howard's PI, a previous bound is improved by removing a log(n) 
      factor. For Simplex PI, a previous bound is improved by halving its 
      multiplicative constant. When the MDP is deterministic, a previous 
      bound for Simplex PI is improved by decreasing the power of 
      dependence on n by one. This result is generalized to stochastic 
      MDPs under additional restrictions on the MDP. Originality and 
      significance: The complexity of PI is of major interest to the RL 
      community. Even though the finite setting is not practical, it is 
      important to have a good understanding of this simple case before 
      moving to more complicated settings. This paper essentially picks up 
      the previous line of research that started with a paper by Yinyu Ye in 
      2011 and continued by Post and Ye, as well as by Hansen, Miltersen and 
      Zwick. Some of the improvements are marginal and the core ideas of the 
      proofs go back to the 2011 work of Ye. However, the proofs are much 
      more streamlined and are way more accessible to RL researchers than 
      those of Ye (who prefers to use the language of linear programming). 
      The extension of strong polynomial results to stochastic MDPs under 
      structural assumptions are the most important novel parts of the paper. 
      Clarity: The paper is relatively well-written, though the 
      authors should check it carefully as it contains a few typos (lines 
      285, 292). Also, at times fluency could be improved (e.g., "However, 
      on the other hand" on line 303 is awkward). Soundness: I 
      believe that the results are sound (I did not have time to check all the 
      details). Minor issues: - line 367: specify the lemma used