Answers.Body: <p>Where the author mentions the policy evaluation being stopped after one state, they are referring to the part of the algorithm that evaluates the policy -- the pseudocode you have listed is the pseudocode for <em>Value Iteration</em>, which consists of iterating between policy evaluation and policy improvement.</p>
  <p>In normal policy evaluation, you would apply the update <span class="math-container">$v_{k+1}(s) = \mathbb{E}_\pi[R_{t+1} + \gamma v_k(S_{t+1})|S_t = s]$</span> until convergence. In the <em>policy iteration</em> algorithm, you perform policy evaluation until the value functions converge in each state, then apply policy improvement, and repeat. <em>Value iteration</em> will perform <em>policy evaluation</em> for one update, i.e. not until convergence, and then improve the policy, and repeat this until the value functions converge.</p>
  <p>The line</p>
  <p><span class="math-container">$$V(s) \leftarrow \max_a \sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]$$</span></p>
  <p>perform both the early stopping policy evaluation and policy improvement. Lets examine how:</p>
  <p>The <span class="math-container">$\sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]$</span> is the same as the expectation I wrote earlier, so we can see clearly that is policy evaluation for just one iteration. Then, we take a max over the actions -- this is policy improvement. Policy improvement is defined as (for a deterministic policy)
  <span class="math-container">\begin{align}
  \pi'(s) &amp;= \arg\max_a q_\pi(s,a) \\ &amp;= \arg\max_a \sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]\;.
  \end{align}</span>
  Here, we assign the action that satisfies the <span class="math-container">$\mbox{argmax}$</span> to the improved policy in state <span class="math-container">$s$</span>. This is essentially what we are doing in the   line from your pseudo when we take the max. We are evaluating our value function for a policy that is greedy with respect to said value function.</p>
  <p>If you keep applying the line from the pseudocode of value iteration it will eventually converge to the optimal value function as it will end up satisfying the Bellman Optimality Equation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-13T21:23:12.817Z
Answers.Text: Thank you for your explanation! Could you please point out the line in the code that does policy evaluation and the line that does "...then improve the policy..."?
Answers.UserDisplayName: Alex
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-13T21:32:44.240Z
Answers.Text: the line under $v \leftarrow V(s)$ does both. you should familiarise yourself with policy eval and policy improvement and you will see why this is so. -- I can edit my answer in about 30 mins to reflect this.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-16T19:20:04.623Z
Answers.Text: +1 But strictly speaking, isn't the authors wrong in their claim?  Policy iteration where the evaluation is stopped after one sweep progresses very differently from value iteration as far as I can see. The similarity seems very superficial if one actually goes through the algorithms step by step.
Answers.UserDisplayName: Paradox
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-13T21:01:20.183Z
Answers.LastActivityDate: 2020-08-13T21:51:58.877Z
Answers.LastEditDate: 2020-08-13T21:51:58.877Z
Answers.UserDisplayName: David
Body: <p>In section <a href="http://www.incompleteideas.net/book/4/node5.html" rel="nofollow noreferrer">4.4 Value Iteration</a>, the authors write</p>
  <blockquote>
  <p>One important special case is when policy evaluation is stopped after just one sweep (<strong>one update of each state</strong>). This algorithm is called value iteration.</p>
  </blockquote>
  <p>After that, they provide the following pseudo-code</p>
  <p><a href="https://i.sstatic.net/kvMKn.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kvMKn.jpg" alt="enter image description here" /></a></p>
  <p>It is clear from the code that updates of each state occur until <span class="math-container">$\Delta$</span> is sufficiently small. Not <strong>one update of each state</strong> as the authors write in the text. Where is the mistake?</p>
  
Tags: <reinforcement-learning><value-iteration><policy-evaluation><pseudocode><policy-improvement>
Title: Is value iteration stopped after one update of each state?
UserDisplayName: Alex
ThreadText: # Is value iteration stopped after one update of each state?
  
  (Asked by: username_0 on 2020-08-13)
  
  In section [4.4 Value Iteration](http://www.incompleteideas.net/book/4/node5.html), the authors write
  
  > One important special case is when policy evaluation is stopped after just one sweep (**one update of each state**). This algorithm is called value iteration.
  
  After that, they provide the following pseudo-code
  
  [![enter image description here](https://i.sstatic.net/kvMKn.jpg)](https://i.sstatic.net/kvMKn.jpg)
  
  It is clear from the code that updates of each state occur until $\Delta$ is sufficiently small. Not **one update of each state** as the authors write in the text. Where is the mistake?
  
  **Tags:** reinforcement-learning, value-iteration, policy-evaluation, pseudocode, policy-improvement
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-08-13. Score: 3 | Accepted answer
  
  Where the author mentions the policy evaluation being stopped after one state, they are referring to the part of the algorithm that evaluates the policy -- the pseudocode you have listed is the pseudocode for *Value Iteration*, which consists of iterating between policy evaluation and policy improvement.
  
  In normal policy evaluation, you would apply the update $v\_{k+1}(s) = \mathbb{E}\_\pi[R\_{t+1} + \gamma v\_k(S\_{t+1})|S\_t = s]$ until convergence. In the *policy iteration* algorithm, you perform policy evaluation until the value functions converge in each state, then apply policy improvement, and repeat. *Value iteration* will perform *policy evaluation* for one update, i.e. not until convergence, and then improve the policy, and repeat this until the value functions converge.
  
  The line
  
  $$V(s) \leftarrow \max\_a \sum\_{s', r} p(s',r|s,a)[r + \gamma V(s')]$$
  
  perform both the early stopping policy evaluation and policy improvement. Lets examine how:
  
  The $\sum\_{s', r} p(s',r|s,a)[r + \gamma V(s')]$ is the same as the expectation I wrote earlier, so we can see clearly that is policy evaluation for just one iteration. Then, we take a max over the actions -- this is policy improvement. Policy improvement is defined as (for a deterministic policy)
  \begin{align}
  \pi'(s) &= \arg\max\_a q\_\pi(s,a) \\ &= \arg\max\_a \sum\_{s', r} p(s',r|s,a)[r + \gamma V(s')]\;.
  \end{align}
  Here, we assign the action that satisfies the $\mbox{argmax}$ to the improved policy in state $s$. This is essentially what we are doing in the line from your pseudo when we take the max. We are evaluating our value function for a policy that is greedy with respect to said value function.
  
  If you keep applying the line from the pseudocode of value iteration it will eventually converge to the optimal value function as it will end up satisfying the Bellman Optimality Equation.
  
  > **Comments:**
  > **username_0**: Thank you for your explanation! Could you please point out the line in the code that does policy evaluation and the line that does "...then improve the policy..."?  
  > **username_1**: the line under $v \leftarrow V(s)$ does both. you should familiarise yourself with policy eval and policy improvement and you will see why this is so. -- I can edit my answer in about 30 mins to reflect this.  
  > **username_2**: +1 But strictly speaking, isn't the authors wrong in their claim?  Policy iteration where the evaluation is stopped after one sweep progresses very differently from value iteration as far as I can see. The similarity seems very superficial if one actually goes through the algorithms step by step.  
  
  ---
  
  