Body: <p>In reinforcement learning, what guarantees that policy iteration would find the globally optimal solution and not just any local maximum?</p>
  <p>I'm reading the book &quot;Reinforcement Learning: An Introduction (second edition)&quot; by Richard S. Sutton and Andrew G. Barto.</p>
  <p>In chapter 4 they are discussing dynamic programming methods and on several occasions they mention that policy iteration is guaranteed to converge to the optimal policy because it satisfies the bellman optimality equation.</p>
  <p>From <a href="https://en.wikipedia.org/wiki/Bellman_equation" rel="nofollow noreferrer">wikipedia</a>:</p>
  <blockquote>
  <p>Bellman equation ... is a necessary condition for optimality</p>
  </blockquote>
  <p>Necessary, but not sufficient. The bellman equation is non-linear so I don't see why there couldn't be multiple local maxima for the policy.</p>
  <p>Why is policy iteration guaranteed to converge to the global optimum?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-12-11T16:02:25.923Z
Comments.Text: I think this is a duplicate of [this](https://ai.stackexchange.com/q/34244/2444), or, at least, your question should be answered there too. Let me know if that's the case, so that we can link the 2.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><convergence><policy-iteration>
Title: Why is policy iteration guaranteed to converge to the global optimum?
UserDisplayName: martinkunev
ThreadText: # Why is policy iteration guaranteed to converge to the global optimum?
  
  (Asked by: username_0 on 2022-11-08)
  
  In reinforcement learning, what guarantees that policy iteration would find the globally optimal solution and not just any local maximum?
  
  I'm reading the book "Reinforcement Learning: An Introduction (second edition)" by Richard S. Sutton and Andrew G. Barto.
  
  In chapter 4 they are discussing dynamic programming methods and on several occasions they mention that policy iteration is guaranteed to converge to the optimal policy because it satisfies the bellman optimality equation.
  
  From [wikipedia](https://en.wikipedia.org/wiki/Bellman_equation):
  
  > Bellman equation ... is a necessary condition for optimality
  
  Necessary, but not sufficient. The bellman equation is non-linear so I don't see why there couldn't be multiple local maxima for the policy.
  
  Why is policy iteration guaranteed to converge to the global optimum?
  
  **Tags:** reinforcement-learning, convergence, policy-iteration
  > **Comments:**
  > **username_1**: I think this is a duplicate of [this](https://ai.stackexchange.com/q/34244/2444), or, at least, your question should be answered there too. Let me know if that's the case, so that we can link the 2.  
  
  ---
  
  ## 0 answers
  
  