# Equation not satisfied in Policy Iteration Algorithm

In equation 4.9 of Sutton and Barto's book on page 79, we have(for policy iteration algo):

$$\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:

Now for the concerned state marked in red -

So $$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.

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.
• 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.