Asynchronous Dynamic Programming

Why Does This Exist?

Classical Dynamic Programming (DP) algorithms—such as standard Value Iteration and Policy Iteration—rely on synchronous sweeps. To compute the value function for iteration $k+1$, the algorithm must iterate systematically across every single state $s \in \mathcal{S}$ in the environment, using values stored in a frozen buffer from iteration $k$.

In practice, this synchronous approach breaks down across three critical axes:

1. Wasted Computation on Irrelevant States: In large Markov Decision Processes (MDPs) containing millions or billions of states (e.g., board games, robotics, routing), performing an exhaustive sweep across the entire state space is computationally prohibitive. Many states are rarely or never reachable from realistic starting conditions, yet synchronous DP spends equal computational budget updating all of them.
2. Buffer Memory Duplication: Synchronous updates require two separate value arrays: a read-only buffer $V_k$ and a write buffer $V_{k+1}$. Memory must be allocated twice, and new estimates cannot be stored in-place until the entire sweep across all states concludes.
3. High Backup Latency: Because updates are locked into rigid batches, a newly discovered reward at a goal state cannot propagate backward to upstream predecessor states within the same iteration. If an optimal trajectory spans $N$ transitions, synchronous value iteration requires at least $N$ complete passes over the entire state space before the reward signal reaches the start state.

Asynchronous Dynamic Programming breaks this rigid lockstep. Instead of exhaustive batch sweeps, it updates state values individually in arbitrary or targeted sequences directly inside a single shared memory buffer. States that change quickly or appear on critical trajectories receive immediate computational attention, while value improvements propagate immediately across downstream backups.

Think of It Like This

How It Actually Works

In-Place Iterative Updates Without Separate Buffers

Let an MDP be defined by the tuple $(\mathcal{S}, \mathcal{A}, p, r, \gamma)$, where $\mathcal{S}$ is the discrete state space, $\mathcal{A}$ is the action space, $p(s', r \mid s, a)$ is the joint transition and reward probability distribution, and $\gamma \in [0, 1)$ is the discount factor.

The optimal state-value function $V^*(s)$ satisfies the Bellman optimality equation:

$V^*(s) = \max_{a \in \mathcal{A}} \sum_{s' \in \mathcal{S}} \sum_{r} p(s', r \mid s, a) \left[ r + \gamma V^*(s') \right]$

In synchronous Value Iteration, two distinct memory vectors $V_k$ and $V_{k+1}$ are maintained:

$V_{k+1}(s) \leftarrow \max_{a \in \mathcal{A}} \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V_k(s') \right] \quad \forall s \in \mathcal{S}$

In asynchronous dynamic programming, values are backed up in-place into a single shared array $V$:

$V(s_t) \leftarrow \max_{a \in \mathcal{A}} \sum_{s', r} p(s', r \mid s_t, a) \left[ r + \gamma V(s') \right]$

Here, $s_t$ is whichever state is selected at time step $t$. When $V(s_t)$ is updated, its old value is immediately overwritten. If an adjacent predecessor state $s$ is evaluated at step $t+1$, it reads the fresh value $V(s_t)$ directly, allowing value updates to cascade within a single pass.

State Selection Orders and Convergence Guarantees

Asynchronous DP is not a single rigid algorithm, but a general framework governed by how states are chosen for updates. The three most common paradigms are:

1. In-Place Value Iteration (Arbitrary or Cyclic Sweeps): The algorithm iterates through states in a fixed cyclic order ($s_0, s_1, \ldots, s_{|\mathcal{S}|-1}$) or samples states uniformly at random. Because fresh updates overwrite memory in-place, values propagate faster than synchronous buffers without requiring extra bookkeeping.

2. Prioritized Sweeping: Updates are scheduled based on the magnitude of the Bellman error (or Bellman residual): $\Delta(s) = \left| \max_{a \in \mathcal{A}} \sum_{s', r} p(s', r \mid s, a) \left[ r + \gamma V(s') \right] - V(s) \right|$ States with the highest error $\Delta(s)$ are stored in a priority queue (max-heap). When the top state $s$ is updated, its immediate predecessors (all states $p$ that can transition into $s$) have their Bellman errors recalculated and pushed onto the queue if $\Delta(p) > \theta$, focusing computation strictly where values are actively changing.

3. Real-Time Dynamic Programming (RTDP): Backups occur concurrently with an agent's actual experience trajectories. At the current state $S_t$, the agent runs an in-place Bellman backup on $V(S_t)$, selects a greedy action $A_t = \arg\max_a \sum_{s', r} p(s', r \mid S_t, a)[r + \gamma V(s')]$, transitions to $S_{t+1}$, and repeats. Irrelevant states that cannot be reached under the optimal policy from the start state are ignored entirely.

Convergence Theorem

Bertsekas and Tsitsiklis established the formal convergence criterion for asynchronous dynamic programming:

Theorem (Asynchronous DP Convergence): For a discounted MDP with $\gamma \in [0, 1)$ and bounded rewards, if every state $s \in \mathcal{S}$ is updated infinitely often:

$\lim_{k \to \infty} \sum_{t=1}^k \mathbb{I}(s_t = s) = \infty \quad \forall s \in \mathcal{S}$

then for any arbitrary initial value vector $V_0$, the asynchronous value sequence converges to the unique optimal value function:

$\lim_{t \to \infty} V(s) = V^*(s) \quad \forall s \in \mathcal{S}$

Because the Bellman optimality operator remains a contraction mapping under the infinity norm ($\|T(V) - T(U)\|_\infty \le \gamma \|V - U\|_\infty$), asynchronous updates never diverge, even with arbitrary update orders and bounded communication delays.

Worked numerical example

Consider a 3-state deterministic linear corridor MDP:

• States: $s_0, s_1, s_2$ where $s_2$ is an absorbing terminal goal state ($V^*(s_2) = 0$).
• Actions: A single action $\text{move\_right}$.
• Transitions and Rewards:
  • From $s_0$: transitions to $s_1$ with immediate reward $r = 0$.
  • From $s_1$: transitions to $s_2$ with immediate reward $r = 10$.
• Discount factor: $\gamma = 0.90$.
• Initial estimates: $V(s_0) = 0.0$, $V(s_1) = 0.0$, $V(s_2) = 0.0$.

The true optimal values are: $V^*(s_1) = 10 + 0.90 \times V^*(s_2) = 10 + 0 = 10.0$ $V^*(s_0) = 0 + 0.90 \times V^*(s_1) = 0 + 0.90(10.0) = 9.0$

Step 1: Synchronous Sweep (Two Buffers: $V_{old} \to V_{new}$)

Sweep 1: Reads exclusively from $V_{old} = [0.0, 0.0, 0.0]$:

• Update $s_0$: $V_{new}(s_0) = 0 + 0.90 \times V_{old}(s_1) = 0 + 0.90(0.0) = 0.0$
• Update $s_1$: $V_{new}(s_1) = 10 + 0.90 \times V_{old}(s_2) = 10 + 0.90(0.0) = 10.0$
• Result after Sweep 1: $V = [0.0, 10.0, 0.0]$. (Notice: State $s_0$ learned nothing about the reward because it read from frozen $V_{old}$.)

Sweep 2: Reads from $V_{old} = [0.0, 10.0, 0.0]$:

• Update $s_0$: $V_{new}(s_0) = 0 + 0.90 \times V_{old}(s_1) = 0 + 0.90(10.0) = 9.0$
• Update $s_1$: $V_{new}(s_1) = 10 + 0.90 \times V_{old}(s_2) = 10 + 0.90(0.0) = 10.0$
• Result after Sweep 2: $V = [9.0, 10.0, 0.0]$ (Converged).

Synchronous Cost: 2 full sweeps, 4 total state backups.

Step 2: Asynchronous In-Place Update (Single Shared Buffer $V$)

Single array initialized to $V = [0.0, 0.0, 0.0]$. Suppose we update in reverse topological order ($s_1$, then $s_0$):

1. Update $s_1$ in-place: $V(s_1) \leftarrow 10 + 0.90 \times V(s_2) = 10 + 0.90(0.0) = 10.0$ Shared memory is immediately overwritten: $V = [0.0, 10.0, 0.0]$.

2. Update $s_0$ in-place: $V(s_0) \leftarrow 0 + 0.90 \times V(s_1) = 0 + 0.90(10.0) = 9.0$ Shared memory is immediately overwritten: $V = [9.0, 10.0, 0.0]$.

Asynchronous Cost: In just 1 pass of 2 total state backups, the value signal propagated from the goal $s_2$ all the way to start state $s_0$, achieving exact convergence in half the operations.

Code

1import heapq2from typing import Dict, List, Tuple3
4
5class ChainMDP:6    """A linear chain MDP where an agent navigates toward a terminal goal state."""7
8    def __init__(self, n_states: int = 5, goal_reward: float = 10.0, gamma: float = 0.9) -> None:9        self.n_states = n_states10        self.terminal_state = n_states - 111        self.gamma = gamma12        self.actions = [0, 1]  # 0: stay, 1: step right13        self.transitions: Dict[Tuple[int, int], List[Tuple[float, int, float]]] = {}14
15        for s in range(self.terminal_state):16            # Action 0: stay in place (reward 0.0)17            self.transitions[(s, 0)] = [(1.0, s, 0.0)]18            # Action 1: step right (reward 10.0 if reaching terminal state, else 0.0)19            next_state = s + 120            reward = goal_reward if next_state == self.terminal_state else 0.021            self.transitions[(s, 1)] = [(1.0, next_state, reward)]22
23    def bellman_backup(self, s: int, V: List[float]) -> float:24        """Computes max_a sum_{s', r} p(s', r | s, a) [r + gamma * V(s')]."""25        if s == self.terminal_state:26            return 0.027        q_values: List[float] = []28        for a in self.actions:29            q = sum(30                prob * (reward + self.gamma * V[next_s])31                for prob, next_s, reward in self.transitions[(s, a)]32            )33            q_values.append(q)34        return max(q_values)35
36
37def sync_value_iteration(mdp: ChainMDP, theta: float = 1e-4) -> Tuple[List[float], int, int]:38    """Synchronous Value Iteration maintaining dual read/write buffers."""39    V = [0.0] * mdp.n_states40    sweeps = 041    backups = 042
43    while True:44        sweeps += 145        V_new = V.copy()  # Frozen buffer for read operations46        delta = 0.047        for s in range(mdp.terminal_state):48            v_val = mdp.bellman_backup(s, V)49            backups += 150            delta = max(delta, abs(v_val - V[s]))51            V_new[s] = v_val52
53        V = V_new54        if delta < theta:55            break56
57    return V, sweeps, backups58
59
60def async_inplace_value_iteration(61    mdp: ChainMDP, reverse: bool = True, theta: float = 1e-462) -> Tuple[List[float], int, int]:63    """Asynchronous Value Iteration updating directly in a single shared buffer."""64    V = [0.0] * mdp.n_states65    sweeps = 066    backups = 067    state_order = list(reversed(range(mdp.terminal_state))) if reverse else list(range(mdp.terminal_state))68
69    while True:70        sweeps += 171        delta = 0.072        for s in state_order:73            old_v = V[s]74            V[s] = mdp.bellman_backup(s, V)  # In-place overwrite75            backups += 176            delta = max(delta, abs(V[s] - old_v))77
78        if delta < theta:79            break80
81    return V, sweeps, backups82
83
84def async_prioritized_sweeping(mdp: ChainMDP, theta: float = 1e-4) -> Tuple[List[float], int]:85    """Asynchronous Prioritized Sweeping queueing states by Bellman error magnitude."""86    V = [0.0] * mdp.n_states87    backups = 088
89    # Build predecessor map: next_state -> set of states that can reach it90    predecessors: Dict[int, List[int]] = {s: [] for s in range(mdp.n_states)}91    for s in range(mdp.terminal_state):92        predecessors[s].append(s)       # Action 0 (stay)93        predecessors[s + 1].append(s)   # Action 1 (step right)94
95    # Initialize priority queue with states having non-zero error96    pq: List[Tuple[float, int]] = []97    for s in range(mdp.terminal_state):98        err = abs(mdp.bellman_backup(s, V) - V[s])99        if err > theta:100            heapq.heappush(pq, (-err, s))101
102    while pq:103        neg_err, s = heapq.heappop(pq)104        V[s] = mdp.bellman_backup(s, V)105        backups += 1106
107        # Check predecessors and push them if their error exceeds theta108        for p in set(predecessors[s]):109            if p == mdp.terminal_state:110                continue111            p_err = abs(mdp.bellman_backup(p, V) - V[p])112            if p_err > theta:113                heapq.heappush(pq, (-p_err, p))114
115    return V, backups116
117
118if __name__ == "__main__":119    env = ChainMDP(n_states=5, goal_reward=10.0, gamma=0.9)120
121    v_sync, sync_sweeps, sync_backups = sync_value_iteration(env)122    v_async, async_sweeps, async_backups = async_inplace_value_iteration(env, reverse=True)123    v_prio, prio_backups = async_prioritized_sweeping(env)124
125    print("=== Dynamic Programming Benchmark ===")126    print(f"Synchronous DP:          {sync_sweeps} sweeps, {sync_backups} backups -> V = {[round(x, 2) for x in v_sync]}")127    print(f"Asynchronous In-Place:   {async_sweeps} sweeps,  {async_backups} backups -> V = {[round(x, 2) for x in v_async]}")128    print(f"Prioritized Sweeping:    N/A sweeps,  {prio_backups} backups -> V = {[round(x, 2) for x in v_prio]}")

Execution Output

1=== Dynamic Programming Benchmark ===2Synchronous DP:          5 sweeps, 20 backups -> V = [7.29, 8.1, 9.0, 10.0, 0.0]3Asynchronous In-Place:   2 sweeps,  8 backups -> V = [7.29, 8.1, 9.0, 10.0, 0.0]4Prioritized Sweeping:    N/A sweeps,  4 backups -> V = [7.29, 8.1, 9.0, 10.0, 0.0]

Watch Out For

The Quick Version

• Synchronous DP sweeps every state in lockstep: It evaluates the full state space using dual memory buffers ($V_k \to V_{k+1}$), delaying reward propagation across upstream states by entire iterations.
• Asynchronous DP updates in-place: Backups occur individually into a single shared array, cutting memory consumption in half and propagating new values immediately to subsequent updates.
• Order matters for efficiency: Practitioners can update states via cyclic sweeps, prioritized sweeping (ordered by Bellman error magnitude in a heap), or trajectory sampling (RTDP).
• Convergence is guaranteed: As long as the discount factor $\gamma < 1$ and every state is visited infinitely often, asynchronous DP mathematically converges to the true optimal $V^*$.
• Avoid state starvation: Selective or heuristic updating must never permanently neglect reachable states, or global convergence guarantees will fail.

What to Read Next

• Dynamic Programming in RL
• Value Iteration
• Policy Iteration