Asynchronous Dynamic Programming

Update one state at a time in place, reusing fresh values at once. The good news spreads in the same pass instead of waiting for the next full sweep.

A 3-state chain with reward 10 reaches 9.00 at the start in 2 in-place backups, while sync sweeps need 4 backups across 2 passes

Why Does This Exist?

Classic dynamic programming sweeps every state with two buffers. Read from $V_k$ , write to $V_{k+1}$ , repeat. That is clean but wasteful. Rare states get equal work, memory doubles, and a goal reward needs one full sweep per hop to walk backward.

Async DP drops the lockstep. Keep one array $V$ and back up whichever state you pick:

V(s) \leftarrow \max_a \sum_{s', r} p(s', r \mid s, a)[r + \gamma V(s')]

Here $p$ holds transition probabilities, $r$ the reward, and $\gamma$ the discount. Fresh writes are visible at once, so one well ordered pass can push a reward across many hops. This page covers the in place trick and ordering. Neighbors cover the full theory in dynamic programming, the optimality sweep in value iteration, and the evaluate improve loop in policy iteration.

You need Bellman equations first: values defined in terms of successor values.

Think of It Like This

Spot cleaning a house versus a locked whole house pass

A strict cleaner must finish rooms 1 to 50 in order before starting pass two, even when guests keep dirtying the entry. Mud waits a full pass before the hallway notices the clean entry.

Spot cleaning fixes the entry the moment it gets dirty, and the next room benefits right away. High traffic rooms get extra visits, spare rooms get skipped, and one bucket set stays in use.

Where it stops: cleaning one room never dirties another, but Bellman backups couple states. Updating $s'$ changes the target for every predecessor $s$ , which is why order matters here and not in the house.

How It Actually Works

Sync keeps $V_k$ frozen while it builds $V_{k+1}$ . Async overwrites $V$ in place. Pick $s_1$ then $s_0$ in a chain and the second backup already sees the first result.

Three orderings cover most uses. Cyclic sweeps walk a fixed order but write in place. Prioritized sweeping queues states by Bellman error $|\text{backup} - V(s)|$ and processes predecessors of big movers first. Real time DP backs up only states the agent actually visits, ignoring unreachable branches.

Convergence still holds for discounted tasks when every state keeps getting picked. The Bellman operator contracts with factor $\gamma < 1$ , so arbitrary orders with infinite visits reach $V^*$ .

Worked example

Chain $s_0 \to s_1 \to s_2$ with one action, $\gamma = 0.90$ , start $V = [0.0, 0.0, 0.0]$ , terminal $V(s_2) = 0$ . Rewards: $0$ from $s_0$ , $10$ from $s_1$ . True values are:

V^*(s_1) = 10 + 0.90 \times 0 = 10.0

V^*(s_0) = 0 + 0.90 \times 10.0 = 9.0

Sync sweep one reads $[0.0, 0.0, 0.0]$ and writes $V(s_0) = 0.0$ , $V(s_1) = 10.0$ . The start learns nothing because it read the stale $V(s_1)$ . Sweep two then gives $V(s_0) = 9.0$ . Cost: $2$ sweeps, $4$ backups.

Async in reverse order writes in place. First $V(s_1) \leftarrow 10 + 0.90 \times 0.0 = 10.0$ , memory becomes $[0.0, 10.0, 0.0]$ . Then $V(s_0) \leftarrow 0 + 0.90 \times 10.0 = 9.0$ . Cost: $2$ backups in one pass, exact.

Code

Minimal replay of the chain above.

1from typing import List2
3
4def backup(reward: float, gamma: float, v_next: float) -> float:5    """One deterministic Bellman backup: r plus discounted next value."""6    return reward + gamma * v_next7
8
9gamma = 0.9010v = [0.0, 0.0, 0.0]11v[1] = backup(10.0, gamma, v[2])12print(v)  # -> [0.0, 10.0, 0.0]13v[0] = backup(0.0, gamma, v[1])14print(v)  # -> [9.0, 10.0, 0.0]

The prints show the in place cascade: $[0.0, 10.0, 0.0]$ then $[9.0, 10.0, 0.0]$ .

Watch Out For

Starving states you stopped visiting

Async converges only when each reachable state keeps getting updates. A greedy rollout plus trajectory backups can loop on one path while a shortcut keeps stale zeros.

Symptom: Bellman error looks zero on visited states yet the policy sticks in a loop. Fix: mix epsilon greedy visits or schedule background sweeps so no reachable state waits forever.

The Quick Version

Sync DP reads one buffer and writes another across all states each sweep.
Async DP writes in place to one buffer, so fresh values feed the next backup at once.
Order by cycle, by Bellman error queue, or by live trajectory depending on the task.
The 3-state chain with $\gamma = 0.90$ hits $[9.0, 10.0, 0.0]$ in 2 backups async versus 4 sync.
Keep visiting every reachable state or the guarantee lapses.