Why is update rule of the value function different in policy evaluation and policy iteration?

Question

In the textbook "Reinforcement Learning: An Introduction", by Richard Sutton and Andrew Barto, the pseudo code for Policy Evaluation is given as follows:

The update equation for $V(s)$ comes from the Bellman equation for $v_{\pi}(s)$ which is mentioned below (the update equation) for your convenience: $$v_{k+1}(s) = \sum_{a} \pi(a|s)\sum_{s',r}p(s',r|s,a)[r+\gamma v_{k}(s')]$$

Now, in Policy Iteration, the Policy Evaluation comes in stage 2, as mentioned in the following pseudo code:

Here, in the policy Evaluation stage, $V(s)$ is updated using a different equation: $$\begin{align} v_{k+1}(s) = \sum_{s',r}p(s',r|s,\pi (s))[r + \gamma v_{k}(s)] \end{align}$$ where $a = \pi(s)$ is used.

Can someone please help me in understanding why this change is made in Policy Iteration? Are the two equations the same?

Answer 1

Yes, the two update equations are equivalent. As an aside, technically the equation you give is not the Bellman equation, but the update step re-written as an equation - in the Bellman equation instead of $v_{k+1}(s)$ or $v_{k}(s)$ (showing iterations of approximate value functions), you would have $v_{\pi}(s)$ (representing the true value of a state under policy $\pi$).

The difference between the equations is that

• In the first case of Policy Evaluation, in order to be general, a stochastic policy $\pi(a|s): \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R} = Pr\{A_t = a|S_t =s\}$ is used. That means to get the expected value, you must sum over all possible actions $a$ and weight them by the policy function output.

• In the case of Policy Iteration, a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$ is used. For that, you don't need to know all possible values of $a$ for probabilities, but use the output of the policy function directly as the action that is taken by the agent. That action therefore has a probability of $1$ of being chosen by the policy in the given state.

The equation used in Policy Iteration is simplified for a deterministic policy. If you want you could represent the policy using $\pi(a|s)$ and use the same equation as for Policy Evaluation. If you do that, you would also need to alter the Policy Improvement policy update step to something like:

$a_{max} \leftarrow \text{argmax}_a\sum_{r,s'}p(r,s'|s,a)[r + \gamma V(s')]$

$\text{ for each } a \in \mathcal{A(s)}$:

$\qquad \pi(a|s) \leftarrow 1 \text{ if } a = a_{max}, 0 \text{ otherwise }$

Doing this will result in exactly the same value function and policy as before. The only reason to do this would be to show the equivalence between the two sets of update equations when dealing with a deterministic policy.