Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
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.
