State-Value Backups

The Flexibility of Asynchronous Updates

Asynchronous dynamic programming changes how states are selected for backup. Instead of following a systematic sweep through the state set, it can select states in an arbitrary or changing order. This flexibility allows one state to be backed up several times before another state is backed up once.

A Backup Sequence in Action

The sequence A, A, B, C is useful because it separates two ideas that are easy to confuse. First, asynchronous dynamic programming permits an uneven order: A can be updated more than once before B or C is updated. Second, that permission is not a reason to abandon B or C. The sequence is illustrative, not a prescribed strategy. The important property is continued coverage of the state set.

What a State-Value Backup Uses

A state-value backup updates a selected state's value estimate using values currently available from other states. Because asynchronous dynamic programming can select states in any order, the values available at the moment of a backup can reflect earlier updates. This is why the order can be flexible: a backup does not require all states to have been updated the same number of times first.

The visual shows the role of a backup without imposing a fixed schedule. State A is selected, and the backup uses values currently available from other states to update A's estimate. Another state may be selected next, or A may be selected again. The source of flexibility is the selection order, not the removal of value information from the other states.

Coverage Over Time

Correct convergence depends on backups continuing to cover every state. Coverage does not require equal timing or equal update counts. One state may receive several backups while another waits, but the waiting state must eventually continue receiving backups as the process proceeds.

Suppose A and B continue to receive backups while C is permanently set aside. More updates to A and B do not compensate for the missing backups to C. This is the key limit on asynchronous selection: the algorithm may vary the order and the number of updates, but it may not turn flexible scheduling into permanent neglect if correct convergence is required.

Mistakes About State Selection

• Treating asynchronous dynamic programming as a fixed sweep with a different name.

  Asynchronous dynamic programming does not follow systematic sweeps of the state set. It allows states to be selected in any order, including revisiting one state before another state has been backed up once.

  Fix: Separate order flexibility from coverage. The order can be uneven and changing, while every state must still continue to receive backups.

• Assuming every state must receive the same number of updates at the same time.

  Unequal update counts are allowed in asynchronous dynamic programming.

  Fix: Ask whether the process continues to cover every state, not whether all states have identical update counts at every moment.

• Permanently setting aside states that do not currently seem useful.

  Correct convergence requires backups to continue to cover every state. Repeated updates to A and B do not remove the need to update C.

  Fix: Use flexible selection without permanent omission.

• Treating one illustrative sequence as a required policy.

  An example of an allowed order demonstrates flexibility; it does not establish that the order is required.

  Fix: Read the example for the property it illustrates: uneven revisits are permitted, but continued state coverage remains necessary.

Practice and Final Check

1. Asynchronous dynamic programming does not use systematic sweeps through the state set. It can select states in any order, use currently available values from other states, and update one state multiple times before updating another. That flexibility concerns timing and order only. For correct convergence, backups must continue to cover every state; repeatedly updating a few states cannot replace updating the states that have been left out.