Dynamic Programming State Backups

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.

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.

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.

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.

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.

Order as the Method's Trace

Mistakes in Interpretation

• Assuming that every asynchronous method must complete a sweep before another update can occur.

  Asynchronous methods do not require a complete sweep through all states, and a state may be selected again before another state is selected.

  Fix: Track the actual selection sequence and allow arbitrary or stochastic choices.

• Assuming that every backup uses a completely current collection of information.

  A backup may use out-of-date information.

  Fix: Mark which states have already been backed up and recognize that the collection can contain information of mixed freshness.

• Treating asynchronous as meaning only random.

  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.

  Fix: Describe both the update location and the information freshness, then mention stochastic selection only when relevant.

• Confusing fine-grained asynchronous DP with ordinary state-level asynchronous DP.

  Fine-grained methods divide backup operations into smaller steps that can themselves be performed asynchronously.

  Fix: Identify whether the asynchronous unit is an entire state backup or a smaller part of that backup.

• Treating Jacobi-style and Gauss-Seidel-style methods as unrelated to asynchronous DP.

  Both are special cases within the asynchronous dynamic programming family.

  Fix: Use their update timing and information-use patterns to identify them as particular cases.

Practice the Trace

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.