Equation not satisfied in Policy Iteration Algorithm

Question

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.

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.