State-Value Backups
A state being updated repeatedly means that its estimate is receiving more backup operations at that point in the process. It does not mean that the other states have become unnecessary.
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
Unequal update counts
Consider a state set containing states A, B, and C. Construct an update sequence that illustrates asynchronous selection without permanently omitting any state.
- 1First selection
Select state A for a backup.
- 2Repeated selection
Select state A again before selecting B or C. This is allowed because asynchronous updates do not require a systematic sweep.
- 3Broader coverage
Select state B and then state C. The sequence has revisited A unevenly, but it has also continued to cover the rest of the state set.
- 4Interpretation
The sequence demonstrates flexibility of order and unequal update counts. It does not show that A should always be selected first or that this exact order is required.
A, A, B, C is an example of flexible asynchronous selection, provided the process continues to back up every state rather than permanently omitting one.
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.
A state being updated repeatedly means that its estimate is receiving more backup operations at that point in the process. It does not mean that the other states have become unnecessary.
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
Common mistake Treating asynchronous dynamic programming as a fixed sweep with a different name.
What it looks likeAssuming that the algorithm must visit the entire state set in one predetermined order before any state can be revisited.
Why it failsAsynchronous 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.
Do this insteadSeparate order flexibility from coverage. The order can be uneven and changing, while every state must still continue to receive backups.
Common mistake Assuming every state must receive the same number of updates at the same time.
What it looks likeRejecting the sequence A, A, B, C because A appears twice before B and C appear.
Why it failsUnequal update counts are allowed in asynchronous dynamic programming.
Do this insteadAsk whether the process continues to cover every state, not whether all states have identical update counts at every moment.
Common mistake Permanently setting aside states that do not currently seem useful.
What it looks likeContinuing to back up A and B while never backing up C again.
Why it failsCorrect convergence requires backups to continue to cover every state. Repeated updates to A and B do not remove the need to update C.
Do this insteadUse flexible selection without permanent omission.
Common mistake Treating one illustrative sequence as a required policy.
What it looks likeConcluding that A must always be selected first because an example begins with A.
Why it failsAn example of an allowed order demonstrates flexibility; it does not establish that the order is required.
Do this insteadRead the example for the property it illustrates: uneven revisits are permitted, but continued state coverage remains necessary.
Practice and Final Check
A state set contains A, B, and C. Compare these two update patterns: Pattern 1 is A, B, C, A, B, C. Pattern 2 is A, A, A, B, A, B. Which pattern demonstrates asynchronous selection more clearly, and what additional condition must be checked before calling either pattern compatible with correct convergence?
Hints
- Look for whether the order is a fixed sweep or an uneven sequence.
- Then check whether every state continues to receive backups.
What do you think happens?
If state A has been backed up three times before state B is backed up once, is that unequal timing by itself disallowed?
Reveal answer
No, unequal update counts are allowed.
Asynchronous dynamic programming permits one state to be backed up multiple times before another is backed up once. The necessary follow-up is that backups must continue to cover every state for correct convergence.
- 1Asynchronous 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.
Key Takeaways
- Asynchronous dynamic programming does not follow a fixed systematic sweep.
- States may be selected in any order, and unequal update counts are allowed.
- A backup can use values currently available from other states.
- Repeatedly updating some states does not remove the need to update the remaining states.
- Correct convergence requires backups to continue covering every state.