Value Iteration for Optimal Policies

Policy iteration is often described as a repeating outer process: evaluate a policy, then improve it. The important detail is that policy evaluation is itself a computation. It may require several sweeps through the entire state set before the value estimates approach their limiting values. Therefore, one apparently simple policy-iteration step can contain much more work than the outer loop suggests.

This nested computation explains why policy iteration can be lengthy. The outer loop may appear to make one decision at a time, but the evaluation phase can repeatedly update values for every state before the policy-improvement phase is allowed to use them.

Iterative policy evaluation reaches the exact limiting value function only in the limit. Successive sweeps improve the estimates, but at a finite point the estimates may still differ from their exact limiting values. Exact convergence and policy stability are therefore different ideas.

A policy decision depends on which available action has the greatest expected return. That ordering can become stable before every value estimate has reached its exact limit. Truncating evaluation means stopping before exact convergence when later sweeps no longer affect the corresponding greedy policy. The source example reports that evaluation iterations after the first three had no effect on the corresponding greedy policy. This observation motivates a method that avoids waiting for unnecessary full evaluation.

Value iteration avoids waiting for a separate policy-evaluation phase to reach exact convergence. It begins with an arbitrary value assigned to each state and repeatedly improves the value function. During each sweep, the algorithm visits states, examines the available actions, and replaces a state's value with the greatest expected return among those actions.

Value iteration does not stop merely because one state changed by a small amount. At the start of each sweep, the algorithm sets Δ to zero. For every state, it saves the old value, performs the update, and compares the old and new values. The sweep records the largest absolute change seen anywhere.

After the value function reaches the stopping condition, value iteration extracts a deterministic policy. For each state, it evaluates the same expected-return expression used during the value update and selects the single action that produced the largest expected return.

The value update and policy extraction are closely connected. During the update, the algorithm stores the maximum expected return as the state's value. During extraction, it identifies which action produced that maximum and assigns that action to the state. Because one maximizing action is selected for each state, the resulting policy is deterministic.

Full policy evaluation waits for value estimates to reach their limiting values before the policy-improvement phase uses them. Value iteration instead repeatedly applies the maximum-over-actions update while the value function is being improved. This directly addresses the motivation from truncated evaluation: later evaluation sweeps may no longer change the greedy policy even though they would continue changing the numerical values.