Answers.Body: <p>Base on the fantastic answer by @nbro, let me complement a little bit clue which may help understand Policy Iteration's optimality convergence.</p>
  <p>So Danny you said:</p>
  <blockquote>
  <p>However, I cannot accept the word &quot;Optimal.&quot; I think, to claim an algorithm converges to an optimal stationary point, we need to show not only its monotonic improving property but also &quot;its locally non-stopping property.&quot;</p>
  </blockquote>
  <p>I think here you actually worry about it may miss some possible cases which contains the optimal one in the process of iteration. However it won't. Here is a excerpt on page 75 in <em>Reinforcement Learing: An Introduction</em> written by Richard S. Sutton:</p>
  <blockquote>
  <p>All the updates done in DP algorithms are called expected updates because they are based on an expectation over all possible next states rather than on a sample next state.</p>
  </blockquote>
  <p>So it's about all possible next states rather than on a sample next state, which won't miss some possible cases in the iteration.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-12T02:16:16.507Z
Answers.LastActivityDate: 2022-10-12T02:17:28.147Z
Answers.LastEditDate: 2022-10-12T02:17:28.147Z
Answers.UserDisplayName: yunfeng
Answers.Body: <p>These two algorithms converge to the optimal value function because</p>
  <ol>
  <li><p>they are instances of the <a href="https://ai.stackexchange.com/a/20624/2444">generalization policy iteration</a>, so they iteratively perform one <strong>policy evaluation (PE)</strong> step followed by a <strong>policy improvement (PI)</strong> step</p>
  </li>
  <li><p>the PE step is an iterative/numerical implementation of the <strong>Bellman expectation operator (BEO)</strong> (i.e. it's numerical algorithm equivalent to solving a system of equations); <a href="https://ai.stackexchange.com/a/11133/2444">here</a> you have an explanation of what the Bellman operator is</p>
  </li>
  <li><p>the BEO is a contraction (proof <a href="https://ai.stackexchange.com/a/22970/2444">here</a>), so the iterative application of the BEO makes the approximate value function closer to the optimal one, which is <strong>unique</strong>, i.e. PE convergences to the optimal value function of the current policy (proof <a href="https://ai.stackexchange.com/a/20327/2444">here</a>)</p>
  </li>
  <li><p>Policy improvement is guaranteed to generate a policy that is better than the one in the previous iteration, unless the policy in the previous iteration was already optimal (see the <strong>policy improvement theorem</strong> in <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=98" rel="nofollow noreferrer">section 4.2 of the RL bible</a>)</p>
  </li>
  </ol>
  <p>One thing that may confuse you is that you don't exactly know or have in mind the definition of the value function. A value function <span class="math-container">$v_\pi(s)$</span> is defined as the expected return that you will get starting in state <span class="math-container">$s$</span>, then following policy <span class="math-container">$\pi$</span>. So, if you have some policy <span class="math-container">$\pi$</span>, then you perform one PE step until convergence, then you know that that value function is the optimal value function for <span class="math-container">$\pi$</span>. Now, if <span class="math-container">$\pi_{t+1}$</span> is guaranteed to be a strict improvement over <span class="math-container">$\pi_{t}$</span>, then it basically means that you will get more rewards with <span class="math-container">$\pi_{t+1}$</span> (which is the goal).</p>
  <p>If you read the linked proofs and chapter 4 of the bible, then you should understand why these algorithms converge.</p>
  <p>To address your last point, yes, we assume that we have an MDP. That's an assumption that most famous DP and RL algorithms make.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-22T17:40:22.713Z
Answers.Text: Thank you for your great answer. I have one more question. Can I say that "only if the system follows an MDP, the greedy-based policy iterative algorithm (despite not the epsilon-greedy-based one) provides an optimal policy as well as the corresponding optimal value functions for all states."?
Answers.UserDisplayName: Danny_Kim
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-22T17:51:08.573Z
Answers.Text: For the $\epsilon$-greedy case we can do exploration with a probability of $\epsilon$, but for the greedy case we can't do. (I know, this does not imply that greedy cannot find an optimal solution, but it also does not imply that it will find an optimal solution.) Anyhow, is there no chance of getting stuck at $\pi$ such that $\pi<\pi^*$, where $\pi^*$ is the optimal policy? That is, is there a case where all the optimal value functions are found at a given $\pi$, and the policy improvement algorithm is executed based on them, but getting stuck at $\pi$ despite $\pi<\pi^*$.
Answers.UserDisplayName: Danny_Kim
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-22T17:56:48.173Z
Answers.Text: I agree that if the $\epsilon$-soft (e.g., $\epsilon$-greedy)-based policy improvement is executed, a better policy will be found one day as long as it exists for a given set of value functions of all states. However, my intuition makes me think that if the greedy-based policy improvement is used, there might be the case where a better policy will not be found for a given current set of value functions of all states. Is my intuition totally wrong?
Answers.UserDisplayName: Danny_Kim
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-22T21:36:50.723Z
Answers.Text: @Danny_Kim Did you understand why policy evaluation converges? Note that this happens only in the limit, i.e. if you execute "enough" iterations. Once you find the value function for a given policy, then you generate a new policy that is **guaranteed to be a strict improvement over the previous one** (if you read section 4.2 of the mentioned book, you will understand why). If you do this enough times, then (in the limit) you will get to the optimal policy. In practice, I am not sure how well policy iteration converges (it depends on $\gamma$ I think), but, in theory, they should converge.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-22T21:38:20.237Z
Answers.Text: Why can't you get stuck in a local optima? Because there's only one optimum. Note that we're not talking about Q-learning or SARSA, which are RL algorithms that do not use the model of the environment, while policy iteration does. Q-learning and SARSA do need to explore the environment (e.g. using the $\epsilon$-greedy policy) because they do not have the model of the environment, i.e. the probability distribution $p(s', r \mid s, a)$. The intuition of the convergence of PI can be found in the last diagram [here](http://incompleteideas.net/book/first/ebook/node46.html).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-22T21:42:15.690Z
Answers.Text: To address your first question in the comments, I've never seen policy iteration being described in a context outside of MDPs, so I don't know if something similar exists for other mathematical frameworks. Which ones do you have in mind?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-21T23:02:27.283Z
Answers.LastActivityDate: 2022-01-21T23:02:27.283Z
Answers.UserDisplayName: nbro
Body: <p>I am reading <em><a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a></em>  by Sutton &amp; Barto. According to this textbook, as far as I understood, the authors claim that the policy and value iteration methods converge to an optimal stationary point. Actually, I now understand the procedure of these two iterative algorithms, but I can't accept why they converge to an optimal point.</p>
  <p>In the textbook and many posts that I found by googling, many people say that &quot;The value functions are monotonically increased as the iteration progresses. Thus, it will go to the optimal policy, as well as optimal value functions.&quot;</p>
  <p>I strongly agree that &quot;only if the algorithm's performance is monotonically improved and there exist an upper bound in terms of performance, the algorithm will converge to a stationary point.&quot; However, I cannot accept the word &quot;Optimal.&quot; I think, to claim an algorithm converges to an optimal stationary point, we need to show not only <em>its monotonic improving property</em> but also &quot;its locally non-stopping property.&quot; (Sorry, I made these words myself, but I believe you experts can understand what I mean.)</p>
  <p>I believe that there must be some points that I was not able to understand. Can someone let me know why the policy and value iteration methods converge to an &quot;OPTIMAL&quot; solution?</p>
  <p>ps. Only if the system can be represented as a Markovian decision process, are either the policy or the value iteration method optimal algorithm?</p>
  
Tags: <reinforcement-learning><convergence><value-iteration><policy-iteration><policy-improvement-theorem>
Title: Why and how can the policy and value iteration methods converge to the OPTIMAL point?
UserDisplayName: Danny_Kim
ThreadText: # Why and how can the policy and value iteration methods converge to the OPTIMAL point?
  
  (Asked by: username_0 on 2022-01-21)
  
  I am reading *[Reinforcement Learning: An Introduction](http://incompleteideas.net/book/RLbook2020.pdf)* by Sutton & Barto. According to this textbook, as far as I understood, the authors claim that the policy and value iteration methods converge to an optimal stationary point. Actually, I now understand the procedure of these two iterative algorithms, but I can't accept why they converge to an optimal point.
  
  In the textbook and many posts that I found by googling, many people say that "The value functions are monotonically increased as the iteration progresses. Thus, it will go to the optimal policy, as well as optimal value functions."
  
  I strongly agree that "only if the algorithm's performance is monotonically improved and there exist an upper bound in terms of performance, the algorithm will converge to a stationary point." However, I cannot accept the word "Optimal." I think, to claim an algorithm converges to an optimal stationary point, we need to show not only *its monotonic improving property* but also "its locally non-stopping property." (Sorry, I made these words myself, but I believe you experts can understand what I mean.)
  
  I believe that there must be some points that I was not able to understand. Can someone let me know why the policy and value iteration methods converge to an "OPTIMAL" solution?
  
  ps. Only if the system can be represented as a Markovian decision process, are either the policy or the value iteration method optimal algorithm?
  
  **Tags:** reinforcement-learning, convergence, value-iteration, policy-iteration, policy-improvement-theorem
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2022-01-21. Score: 3 | Accepted answer
  
  These two algorithms converge to the optimal value function because
  
  1. they are instances of the [generalization policy iteration](https://ai.stackexchange.com/a/20624/2444), so they iteratively perform one **policy evaluation (PE)** step followed by a **policy improvement (PI)** step
  2. the PE step is an iterative/numerical implementation of the **Bellman expectation operator (BEO)** (i.e. it's numerical algorithm equivalent to solving a system of equations); [here](https://ai.stackexchange.com/a/11133/2444) you have an explanation of what the Bellman operator is
  3. the BEO is a contraction (proof [here](https://ai.stackexchange.com/a/22970/2444)), so the iterative application of the BEO makes the approximate value function closer to the optimal one, which is **unique**, i.e. PE convergences to the optimal value function of the current policy (proof [here](https://ai.stackexchange.com/a/20327/2444))
  4. Policy improvement is guaranteed to generate a policy that is better than the one in the previous iteration, unless the policy in the previous iteration was already optimal (see the **policy improvement theorem** in [section 4.2 of the RL bible](http://incompleteideas.net/book/RLbook2020.pdf#page=98))
  
  One thing that may confuse you is that you don't exactly know or have in mind the definition of the value function. A value function $v\_\pi(s)$ is defined as the expected return that you will get starting in state $s$, then following policy $\pi$. So, if you have some policy $\pi$, then you perform one PE step until convergence, then you know that that value function is the optimal value function for $\pi$. Now, if $\pi\_{t+1}$ is guaranteed to be a strict improvement over $\pi\_{t}$, then it basically means that you will get more rewards with $\pi\_{t+1}$ (which is the goal).
  
  If you read the linked proofs and chapter 4 of the bible, then you should understand why these algorithms converge.
  
  To address your last point, yes, we assume that we have an MDP. That's an assumption that most famous DP and RL algorithms make.
  
  > **Comments:**
  > **username_0**: Thank you for your great answer. I have one more question. Can I say that "only if the system follows an MDP, the greedy-based policy iterative algorithm (despite not the epsilon-greedy-based one) provides an optimal policy as well as the corresponding optimal value functions for all states."?  
  > **username_0**: For the $\epsilon$-greedy case we can do exploration with a probability of $\epsilon$, but for the greedy case we can't do. (I know, this does not imply that greedy cannot find an optimal solution, but it also does not imply that it will find an optimal solution.) Anyhow, is there no chance of getting stuck at $\pi$ such that $\pi<\pi^*$, where $\pi^*$ is the optimal policy? That is, is there a case where all the optimal value functions are found at a given $\pi$, and the policy improvement algorithm is executed based on them, but getting stuck at $\pi$ despite $\pi<\pi^*$.  
  > **username_0**: I agree that if the $\epsilon$-soft (e.g., $\epsilon$-greedy)-based policy improvement is executed, a better policy will be found one day as long as it exists for a given set of value functions of all states. However, my intuition makes me think that if the greedy-based policy improvement is used, there might be the case where a better policy will not be found for a given current set of value functions of all states. Is my intuition totally wrong?  
  > **username_2**: @Danny_Kim Did you understand why policy evaluation converges? Note that this happens only in the limit, i.e. if you execute "enough" iterations. Once you find the value function for a given policy, then you generate a new policy that is **guaranteed to be a strict improvement over the previous one** (if you read section 4.2 of the mentioned book, you will understand why). If you do this enough times, then (in the limit) you will get to the optimal policy. In practice, I am not sure how well policy iteration converges (it depends on $\gamma$ I think), but, in theory, they should converge.  
  > **username_2**: Why can't you get stuck in a local optima? Because there's only one optimum. Note that we're not talking about Q-learning or SARSA, which are RL algorithms that do not use the model of the environment, while policy iteration does. Q-learning and SARSA do need to explore the environment (e.g. using the $\epsilon$-greedy policy) because they do not have the model of the environment, i.e. the probability distribution $p(s', r \mid s, a)$. The intuition of the convergence of PI can be found in the last diagram [here](http://incompleteideas.net/book/first/ebook/node46.html).  
  > **username_2**: To address your first question in the comments, I've never seen policy iteration being described in a context outside of MDPs, so I don't know if something similar exists for other mathematical frameworks. Which ones do you have in mind?  
  
  ---
  
  ### Answer by username_1 on 2022-10-12. Score: 0
  
  Base on the fantastic answer by @nbro, let me complement a little bit clue which may help understand Policy Iteration's optimality convergence.
  
  So Danny you said:
  
  > However, I cannot accept the word "Optimal." I think, to claim an algorithm converges to an optimal stationary point, we need to show not only its monotonic improving property but also "its locally non-stopping property."
  
  I think here you actually worry about it may miss some possible cases which contains the optimal one in the process of iteration. However it won't. Here is a excerpt on page 75 in *Reinforcement Learing: An Introduction* written by Richard S. Sutton:
  
  > All the updates done in DP algorithms are called expected updates because they are based on an expectation over all possible next states rather than on a sample next state.
  
  So it's about all possible next states rather than on a sample next state, which won't miss some possible cases in the iteration.
  
  
  ---
  
  