Dynamic Programming State Backups

Asynchronous DP methods are in-place iterative methods that back up states in an arbitrary order.

Programming

The Update Order Matters

Many dynamic programming methods are described as though every state must be processed in one complete pass. Asynchronous dynamic programming takes a different route: it updates states in place, and the next state may be selected in an arbitrary order. A backup may also use information that is not fully up to date. The method is therefore defined not only by what a backup does, but also by when each state is selected and which state information is available at that moment.

How does an arbitrary sequence of state backups change the collection of state values over time?

Reading the Changing Collection

The most useful mental model is a changing collection of state information. At any point, some states may already have been backed up while others have not. Because the method is in place, the collection itself is modified as the process continues. It is not necessary to wait for a complete pass and then replace the entire collection. Because the order is arbitrary, the next state is not determined by a required left-to-right or first-to-last traversal.

Worked example

Tracing Three State Backups

Suppose an asynchronous method has three states: A, B, and C. Trace the effect of the arbitrary backup order C, A, C, B.

1
Initial collection
The collection contains information for A, B, and C. No required traversal order has yet selected a state.
2
First selection: C
State C is backed up in place. The collection now contains the updated information for C together with the existing information for A and B.
3
Second selection: A
State A is backed up next. The collection now contains the updated information for C and A, while B has not yet been backed up in this trace.
4
Third selection: C
C may be selected again. An asynchronous method does not require each state to appear exactly once before another backup occurs.
5
Fourth selection: B
B is then backed up. The trace has updated states in an arbitrary order rather than completing one orderly sweep.

Result

The collection changes after each in-place backup, and the selection sequence may revisit a state or postpone another state.

How can states be updated without visiting every state exactly once in a complete sweep?

Fresh and Out-of-Date Information

Information freshness describes what a backup can see when it is performed. A backup may use information that was updated earlier in the same process, or it may use information that is not fully up to date. Since updates happen in place, a state selected later can encounter a collection that has already been partly modified. The exact freshness depends on the update order and on which information has already been changed.

When a state is updated, does its backup use an old value or a value that was updated earlier in the same process?

Situation	What the next backup may encounter	Why it matters
Earlier state was already backed up	Information that has been updated in place	The collection is partly changed
Related information has not yet been updated	Information that is not fully up to date	The backup may use older information
Selection order changes	A different mixture of updated and older information	State order changes the information available at each backup

Asynchronous backups are understood by tracking which parts of the state collection have already changed.

Two Familiar Special Cases

Jacobi-style and Gauss-Seidel-style dynamic programming algorithms are special cases within the asynchronous dynamic programming family. They can be understood as particular choices about update timing and information use. A Jacobi-style method performs simultaneous updates using one snapshot of the state information. A Gauss-Seidel-style method performs sequential in-place updates, so a later update can immediately reuse information produced by an earlier update.

How do simultaneous updates using one snapshot differ from sequential in-place updates that immediately reuse fresh values?

Style	Update pattern	Relation to asynchronous DP
Jacobi-style	Simultaneous updates use one snapshot	A special case of the asynchronous DP family
Gauss-Seidel-style	Sequential in-place updates can immediately reuse fresh information	A special case of the asynchronous DP family
General asynchronous	States may be backed up in an arbitrary order and may encounter information of mixed freshness	The broader family

The special cases differ in how update timing controls the information available to a backup.

Finer Than a State Backup

Asynchronous behavior can occur at more than one level. In the basic description, an entire state is selected and backed up in an arbitrary order. A fine-grained asynchronous method goes further by dividing the backup operation itself into smaller steps. Those smaller steps can then be performed asynchronously. The defining difference is therefore the size of the asynchronous unit: an ordinary asynchronous method treats a state backup as the unit, while a fine-grained method treats smaller parts of that backup as units that may proceed asynchronously.

What changes when updates occur at an even smaller granularity than ordinary state-by-state backups?

Order as the Method's Trace

How does changing the order of state updates alter which information is available at each backup?

Worked example

Comparing Two Arbitrary Traces

Compare the state-selection orders A, B, C and C, A, B.

1
First order
With A, B, C, the backup of B occurs after A has already been updated in place. The backup of C occurs after both earlier selections.
2
Second order
With C, A, B, the backup of A occurs after C has already been updated, and the backup of B occurs after both C and A have been selected.
3
Compare the collections
Both traces use the same collection of states, but the collection has a different history at each selection point. Consequently, the information available to each backup can differ.
4
Interpret the result
The order is part of the method's behavior. An asynchronous description must therefore account for both in-place modification and the order in which states are selected.

Result

Changing the order changes the sequence of partially updated collections that the backups encounter.

Best practice

When tracing an asynchronous method, record three things after every backup: which state was selected, which states have already been backed up, and whether the information available to the current backup may be out of date. This prevents the common mistake of silently replacing the asynchronous process with a complete sweep.

Mistakes in Interpretation

Common mistake
Assuming that every asynchronous method must complete a sweep before another update can occur.
What it looks like
Treating the order A, B, C as mandatory before any state can be selected again.
Why it fails
Asynchronous methods do not require a complete sweep through all states, and a state may be selected again before another state is selected.
Do this instead
Track the actual selection sequence and allow arbitrary or stochastic choices.
Common mistake
Assuming that every backup uses a completely current collection of information.
What it looks like
Describing an asynchronous backup as though every other state had already been updated.
Why it fails
A backup may use out-of-date information.
Do this instead
Mark which states have already been backed up and recognize that the collection can contain information of mixed freshness.
Common mistake
Treating asynchronous as meaning only random.
What it looks like
Defining the method solely by saying that states are chosen randomly.
Why it fails
The defining ideas are in-place updates, arbitrary order, and possible use of information that is not fully up to date. Stochastic selection is one possible way to choose the order.
Do this instead
Describe both the update location and the information freshness, then mention stochastic selection only when relevant.
Common mistake
Confusing fine-grained asynchronous DP with ordinary state-level asynchronous DP.
What it looks like
Calling a method fine-grained merely because it selects states in an unusual order.
Why it fails
Fine-grained methods divide backup operations into smaller steps that can themselves be performed asynchronously.
Do this instead
Identify whether the asynchronous unit is an entire state backup or a smaller part of that backup.
Common mistake
Treating Jacobi-style and Gauss-Seidel-style methods as unrelated to asynchronous DP.
What it looks like
Listing them as alternatives outside the asynchronous family.
Why it fails
Both are special cases within the asynchronous dynamic programming family.
Do this instead
Use their update timing and information-use patterns to identify them as particular cases.

Practice the Trace

MEDIUM

A method has states P, Q, and R. Its observed selection sequence is Q, R, Q, P. Explain why this is compatible with asynchronous dynamic programming. Then describe how the collection of state information differs after the first, second, and third selections.

Hints

Check whether every state must appear exactly once before any state can appear again.
Remember that backups modify the collection in place.
At each point, identify which selected states may already contain updated information and which state has not yet been selected.

Your attempt (not saved)

What do you think happens?

In the sequence Q, R, Q, P, must the second selection of Q wait until P has been backed up?

Yes, every state must be selected once first
No, a complete sweep is not required
Only if the order is stochastic

Reveal answer

Answer:

No, a complete sweep is not required.

Asynchronous DP methods back up states in an arbitrary order, so a state may be selected again before another state has been selected.

Key Takeaways

1
Asynchronous dynamic programming is an in-place iterative method that backs up states in an arbitrary order.
2
A complete sweep through every state is not required, and a state may be selected again before another state is selected.
3
Because updates occur in place, a backup may encounter information updated earlier in the process or information that is not fully up to date.
4
Jacobi-style and Gauss-Seidel-style dynamic programming algorithms are special cases within the asynchronous family.
5
Fine-grained asynchronous methods divide backup operations into smaller steps that can themselves be performed asynchronously.
6
The clearest trace records the selected state, the current partially updated collection, and the freshness of the information available at that point.

At a glance

Asynchronous DP updates states in place and does not require a fixed complete-sweep order.
The state-selection order changes the sequence of partially updated collections encountered by later backups.
A backup may use information that was updated earlier or information that is out of date.
Jacobi-style and Gauss-Seidel-style methods are special cases of asynchronous DP.
Fine-grained asynchronous DP makes the backup operation itself the object of further subdivision.

Related concepts

Dynamic Programming

More concepts starting with D