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:

enter image description here

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?


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .