Value Iteration

Two Processes in Feedback

Value iteration is best understood through generalized policy iteration, or GPI. GPI is not one fixed algorithm. It is a feedback relationship between two processes: policy evaluation improves the value function for the current policy, while policy improvement changes the policy using the current value function.

Evaluation Versus Improvement

During policy evaluation, the policy is treated as the current policy and the value function is updated so that it better reflects that policy. The policy itself is not the object being improved during this process.

During policy improvement, the current value function is used to change the policy. The new policy becomes greedy with respect to that value function. In this process, the policy changes because the value function provides the basis for selecting better behavior.

Scheduling the Interaction

Different reinforcement learning methods can implement the same two broad processes with different schedules and levels of granularity. The distinction is not whether evaluation and improvement exist, but how much of one process occurs before the other resumes.

• Policy iteration alternates the processes: one process completes before the other begins.
• Value iteration performs only a single iteration of policy evaluation between policy improvements.
• Asynchronous dynamic programming can interleave the processes at an even finer level, including updating one state in one process before returning to the other.

This makes value iteration a middle point in the scheduling picture. It does not wait for a complete policy evaluation before improving the policy. Instead, it uses a limited amount of evaluation before the next improvement. Asynchronous methods make the schedule still more fine-grained.

When Both Processes Stabilize

The stopping idea for GPI is stabilization. If policy evaluation stops producing changes, the value function is consistent with the policy. If policy improvement also stops producing changes, the policy is no longer improved with respect to that value function.

When both conditions hold, the value function and policy are optimal. The value function is consistent with the policy, and the policy cannot be improved using that value function. Stability therefore connects the two local stopping conditions to the global conclusion of optimality.

Asynchronous State Updates

A full value-iteration sweep suggests updating every state before beginning the next round. Asynchronous value iteration uses a different update pattern: at each step, it selects one state and applies the value iteration backup to that state only. The update is made in place, and the selected state may change from step to step.

The convergence guarantee is about coverage, not synchronization. In the discounted setting, states do not need to be selected equally often, and they do not need to be updated in a coordinated sweep. The required condition is that no state is permanently left out.

Discounted Convergence

For asynchronous value iteration, the stated asymptotic convergence guarantee has two conditions. The discount parameter must satisfy 0 ≤ γ < 1, and every state must occur in the selected-state sequence infinitely many times.

When both conditions hold, asynchronous value iteration converges asymptotically to the optimal value function v*. A stochastic state-selection sequence can satisfy the requirement if it continues to include every state.

Why Backup Order Matters

Asynchronous updates are made in place. Therefore, a later backup can use a value that was updated earlier in the same sequence. Changing the order changes which newly updated values are available to later backups.

This ordering effect is especially important in the undiscounted episodic case. Some backup orderings may fail to converge there. Consequently, the sequence of backups is not merely an implementation detail in every setting; it can affect whether convergence occurs.

• Assuming asynchronous updates are equivalent to a full sweep.

  In-place asynchronous updates allow later backups to use values produced by earlier backups.

  Fix: Track the selected state and remember that the order determines which updated values are available.

• Assuming any backup order converges in every setting.

  Some backup orderings may fail to converge in the undiscounted episodic case.

  Fix: Treat the discounted guarantee and the undiscounted episodic case as distinct situations.

Mixed Backup Strategies

Asynchronous dynamic programming does not have to use only one kind of backup. Policy evaluation backups and value iteration backups can be interspersed, allowing information to propagate through the state values while the two GPI processes are interleaved.

This procedure is described as a kind of asynchronous truncated policy iteration. The important point is that evaluation-style and value-iteration-style backups need not be separated into large, completed phases. They can be mixed at a fine-grained level.

Practice and Diagnosis

Key Takeaways

1. Generalized policy iteration is the interaction between policy evaluation and policy improvement, not one fixed algorithm.
2. Evaluation updates the value function for the current policy; improvement updates the policy using the current value function.
3. Policy iteration, value iteration, and asynchronous dynamic programming differ in how finely they schedule and interleave these processes.
4. Asynchronous value iteration updates one selected state at a time, and discounted convergence requires every state to be selected infinitely often when 0 ≤ γ < 1.
5. In-place backup order matters, especially in the undiscounted episodic case, and evaluation backups can be interspersed with value-iteration backups.