Answers.Body: <p>Your calculations are correct, but you have misinterpreted the equations and the diagram. The index <span class="math-container">$k$</span> in <span class="math-container">$v_k$</span> for the diagram refers to the policy evaluation update iteration only, and is not related to the policy update step (which uses the notation <span class="math-container">$\pi'$</span> and does not mention <span class="math-container">$k$</span>).</p>
  
  <p>Policy improvement consists of multiple sweeps through states to fully evaluate the current policy and estimate the value function for it. After that, it updates the policy in a separate policy improvement step. There are two loops - an <em>inner</em> loop indexed by <span class="math-container">$k$</span> in the equations and diagram, plus an <em>outer</em> loop which is not given an index notation.</p>
  
  <p>The diagram is not showing incremental <span class="math-container">$\pi'$</span> policies from outer loops over policy iteration. Instead it is showing "Greedy Policy w.r.t. <span class="math-container">$v_k$</span>" steps in the inner loop - you can think of that as the policy <span class="math-container">$\pi'$</span> that you would get inside the <em>first</em> outer loop, if you terminated the policy evaluation stage after that iteration <span class="math-container">$k$</span> of the inner loop. </p>
  
  <p>The diagram only shows behaviour of policy iteration for a single outer loop. It demonstrates at least two interesting things:</p>
  
  <ul>
  <li><p>In the case of this very simple environment, if you ran a single outer loop with long enough policy evaluation stage (<span class="math-container">$k \ge 3$</span>) you would find the optimal policy.</p></li>
  <li><p>Even before the value function estimate is close to convergence (with a high <span class="math-container">$k$</span>), the policy that could be derived from the new estimates could be used to improve the policy. That leads to the idea of the <em>value iteration</em> method.</p></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-06T09:36:33.363Z
Answers.LastActivityDate: 2020-06-06T10:07:39.963Z
Answers.LastEditDate: 2020-06-06T10:07:39.963Z
Answers.UserDisplayName: Neil Slater
Body: <p>In <a href="http://incompleteideas.net/book/bookdraft2017nov5.pdf#page=68" rel="nofollow noreferrer">equation 4.9 of Sutton and Barto's book</a> on page 79, we have (for the policy iteration algorithm):</p>
  <p><span class="math-container">$$\pi'(s) = arg \max_{a}\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi}(s')]$$</span></p>
  <p>where <span class="math-container">$\pi$</span> is the previous policy and  <span class="math-container">$\pi'$</span> is the new policy. Hence in iterations <span class="math-container">$k$</span> it must mean</p>
  <p><span class="math-container">$$\pi_{k+1}(s) = arg \max_{a}\sum_{s',r}p(s',r|s,a)[r+\gamma v_{\pi_{k}}(s')]$$</span></p>
  <p>But in the example given in the same book on page 77 we have:</p>
  <p><a href="https://i.sstatic.net/EKr8W.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/EKr8W.jpg" alt="enter image description here" /></a></p>
  <p>Now, for the concerned state marked in red -</p>
  <ul>
  <li><span class="math-container">$v_{\pi_{1}} = -1$</span> for all four surrounding states</li>
  <li><span class="math-container">$r = -1$</span> for all four surrounding states</li>
  <li><span class="math-container">$p(s',r|s,a) = 1$</span> for all four surrounding states</li>
  <li><span class="math-container">$\pi_{2}(s) = arg \max_{a}[1*[-1+1*-1],1*[-1+1*-1],1*[-1+1*-1],1*[-1+1*-1]]$</span></li>
  <li><span class="math-container">$\pi _{2}(s) = arg \max_{a}(-2,-2,-2,-2)$</span></li>
  </ul>
  <p>Hence this should give us a criss-cross symbol (4 directional arrow) in <span class="math-container">$\pi_{2}$</span>(s) but here a left arrow symbol is given.</p>
  <p>What's wrong with my calculations?</p>
  
Tags: <value-functions><policies><sutton-barto><policy-iteration>
Title: Why is there an inconsistency between my calculations of Policy Iteration and this Sutton & Barto's diagram?
UserDisplayName: ZERO NULLS
ThreadText: # Why is there an inconsistency between my calculations of Policy Iteration and this Sutton & Barto's diagram?
  
  (Asked by: username_0 on 2020-06-06)
  
  In [equation 4.9 of Sutton and Barto's book](http://incompleteideas.net/book/bookdraft2017nov5.pdf#page=68) on page 79, we have (for the policy iteration algorithm):
  
  $$\pi'(s) = arg \max\_{a}\sum\_{s',r}p(s',r|s,a)[r+\gamma v\_{\pi}(s')]$$
  
  where $\pi$ is the previous policy and $\pi'$ is the new policy. Hence in iterations $k$ it must mean
  
  $$\pi\_{k+1}(s) = arg \max\_{a}\sum\_{s',r}p(s',r|s,a)[r+\gamma v\_{\pi\_{k}}(s')]$$
  
  But in the example given in the same book on page 77 we have:
  
  [![enter image description here](https://i.sstatic.net/EKr8W.jpg)](https://i.sstatic.net/EKr8W.jpg)
  
  Now, for the concerned state marked in red -
  
  * $v\_{\pi\_{1}} = -1$ for all four surrounding states
  * $r = -1$ for all four surrounding states
  * $p(s',r|s,a) = 1$ for all four surrounding states
  * $\pi\_{2}(s) = arg \max\_{a}[1\*[-1+1\*-1],1\*[-1+1\*-1],1\*[-1+1\*-1],1\*[-1+1\*-1]]$
  * $\pi \_{2}(s) = arg \max\_{a}(-2,-2,-2,-2)$
  
  Hence this should give us a criss-cross symbol (4 directional arrow) in $\pi\_{2}$(s) but here a left arrow symbol is given.
  
  What's wrong with my calculations?
  
  **Tags:** value-functions, policies, sutton-barto, policy-iteration
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-06. Score: 3 | Accepted answer
  
  Your calculations are correct, but you have misinterpreted the equations and the diagram. The index $k$ in $v\_k$ for the diagram refers to the policy evaluation update iteration only, and is not related to the policy update step (which uses the notation $\pi'$ and does not mention $k$).
  
  Policy improvement consists of multiple sweeps through states to fully evaluate the current policy and estimate the value function for it. After that, it updates the policy in a separate policy improvement step. There are two loops - an *inner* loop indexed by $k$ in the equations and diagram, plus an *outer* loop which is not given an index notation.
  
  The diagram is not showing incremental $\pi'$ policies from outer loops over policy iteration. Instead it is showing "Greedy Policy w.r.t. $v\_k$" steps in the inner loop - you can think of that as the policy $\pi'$ that you would get inside the *first* outer loop, if you terminated the policy evaluation stage after that iteration $k$ of the inner loop.
  
  The diagram only shows behaviour of policy iteration for a single outer loop. It demonstrates at least two interesting things:
  
  * In the case of this very simple environment, if you ran a single outer loop with long enough policy evaluation stage ($k \ge 3$) you would find the optimal policy.
  * Even before the value function estimate is close to convergence (with a high $k$), the policy that could be derived from the new estimates could be used to improve the policy. That leads to the idea of the *value iteration* method.
  
  
  ---
  
  