Value Iteration

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.

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.

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.

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.

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.

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.

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.

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.

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.