Is value iteration stopped after one update of each state?

In section 4.4 Value Iteration, the authors write

One important special case is when policy evaluation is stopped after just one sweep (one update of each state). This algorithm is called value iteration.

After that, they provide the following pseudo-code

It is clear from the code that updates of each state occur until $$\Delta$$ is sufficiently small. Not one update of each state as the authors write in the text. Where is the mistake?

Where the author mentions the policy evaluation being stopped after one state, they are referring to the part of the algorithm that evaluates the policy -- the pseudocode you have listed is the pseudocode for Value Iteration, which consists of iterating between policy evaluation and policy improvement.

In normal policy evaluation, you would apply the update $$v_{k+1}(s) = \mathbb{E}_\pi[R_{t+1} + \gamma v_k(S_{t+1})|S_t = s]$$ until convergence. In the policy iteration algorithm, you perform policy evaluation until the value functions converge in each state, then apply policy improvement, and repeat. Value iteration will perform policy evaluation for one update, i.e. not until convergence, and then improve the policy, and repeat this until the value functions converge.

The line

$$V(s) \leftarrow \max_a \sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]$$

perform both the early stopping policy evaluation and policy improvement. Lets examine how:

The $$\sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]$$ is the same as the expectation I wrote earlier, so we can see clearly that is policy evaluation for just one iteration. Then, we take a max over the actions -- this is policy improvement. Policy improvement is defined as (for a deterministic policy) \begin{align} \pi'(s) &= \arg\max_a q_\pi(s,a) \\ &= \arg\max_a \sum_{s', r} p(s',r|s,a)[r + \gamma V(s')]\;. \end{align} Here, we assign the action that satisfies the $$\mbox{argmax}$$ to the improved policy in state $$s$$. This is essentially what we are doing in the line from your pseudo when we take the max. We are evaluating our value function for a policy that is greedy with respect to said value function.

If you keep applying the line from the pseudocode of value iteration it will eventually converge to the optimal value function as it will end up satisfying the Bellman Optimality Equation.

• Thank you for your explanation! Could you please point out the line in the code that does policy evaluation and the line that does "...then improve the policy..."? – Alex Aug 13 '20 at 21:23
• the line under $v \leftarrow V(s)$ does both. you should familiarise yourself with policy eval and policy improvement and you will see why this is so. -- I can edit my answer in about 30 mins to reflect this. – David Ireland Aug 13 '20 at 21:32
• Thank you! It is clear now. – Alex Aug 13 '20 at 21:55