Why is there an inconsistency between my calculations of Policy Iteration and this Sutton & Barto's diagram?

Question

In equation 4.9 of Sutton and Barto's book 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:

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?

Answer 1

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.