Value Iteration for Optimal Policies

The Hidden Work Inside Policy Iteration

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.

Exact Values and Stable Decisions

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.

One Value-Iteration Sweep

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.

V(s) ← max over a of the sum over s′ and r of p(s′, r | s, a)[r + γV(s′)]

Tracking the Largest Change

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.

Δ ← max(Δ, |v − V(s)|)

From Values to Actions

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.

Incremental Improvement Instead of Waiting

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.

Mistakes to Avoid

• Treating a small change in one state as sufficient evidence to stop.

  The stopping test uses the largest change across the complete sweep.

  Fix: Track every state change and stop only when the sweep-wide maximum Δ satisfies the stopping condition.

• Assuming that a stable greedy policy means the value function is exact.

  Exact convergence and policy stability are different ideas.

  Fix: Describe the policy as stable while recognizing that the value estimates may not yet have reached their exact limiting values.

• Choosing an action before comparing all available actions.

  The update must use the maximum expected return over the available actions.

  Fix: Evaluate each action, compare their expected returns, and retain the maximizing action for policy extraction.

• Confusing the value stored for a state with the action selected by the policy.

  The value update stores a number, while policy extraction identifies the action that produced that number.

  Fix: Keep the state value and the maximizing action as separate outputs.

Check Your Understanding

Key Takeaways

1. Policy evaluation can require several complete state sweeps, making one policy-iteration step computationally lengthy.
2. Exact convergence of values and stability of greedy policy decisions are different conditions.
3. Value iteration updates each state's value with the maximum expected return over available actions.
4. The algorithm records the largest value change Δ during each complete sweep and compares it with θ.
5. After stopping, a deterministic policy selects the maximizing action in each state.