Real-Time Dynamic Programming (RTDP)

Why Does This Exist?

Classic Dynamic Programming methods—such as Value Iteration and Policy Iteration—suffer from Bellman's infamous curse of dimensionality. In an exhaustive sweep, the algorithm iterates systematically over every single state $s \in \mathcal{S}$ on every iteration. For a problem with millions of states, evaluating the entire state space repeatedly is computationally intractable.

Crucially, in goal-directed tasks, most states are completely irrelevant. If a mobile robot starts in a warehouse lobby with a goal to reach the loading dock on the east wing, computing optimal values for thousands of locked storage closets on the north wing is pure waste. The robot will never visit those states under any sensible policy.

Formulated by Andrew Barto, Steven Bradtke, and Satinder Singh in 1995, Real-Time Dynamic Programming (RTDP) solves this computational bottleneck. It replaces exhaustive state-space sweeps with on-policy trajectory sampling: the agent executes simulated trials from start states to goals, applying asynchronous Bellman backups solely to the sequence of states it actually encounters. Coupled with an optimistic initial heuristic, RTDP guarantees convergence to an optimal policy on relevant states without ever evaluating the rest of the universe.

Think of It Like This

How It Actually Works

The RTDP Trajectory-Sampling Formulation

RTDP is an asynchronous on-policy trajectory-sampling version of Value Iteration. It operates within a known transition model $p(s', r \mid s, a)$ in trial-based episodes starting from initial state $S_0$.

At each step $t$ in state $S_t$:

1. Value Update (Local Bellman Backup): The agent evaluates all available actions and updates the value of the current state: $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]$
2. Greedy Action Selection: The agent selects the action that maximizes the expected return under current value estimates: $A_t \in \arg\max_{a \in \mathcal{A}} \sum_{s', r} p(s', r \mid S_t, a) \left[ r + \gamma V(s') \right]$
3. Model Transition: The agent samples the next state according to the model dynamics: $S_{t+1} \sim p(\cdot \mid S_t, A_t)$
4. Advance: The process repeats until reaching a terminal goal state $G$, ending the current trial.

Admissible Heuristics and the Convergence Guarantee

What prevents RTDP from getting permanently trapped in a suboptimal corridor?

In classic search theory, the $A^*$ algorithm guarantees finding the shortest path if its heuristic function $h(s)$ never overestimates the true remaining cost. Barto, Bradtke, and Singh proved an analogous RTDP convergence theorem for Stochastic Shortest Path MDPs:

RTDP is guaranteed to converge to optimal action values $V^*(s)$ on all relevant states (states that can be reached under an optimal policy from start states), without necessarily visiting all states, under three conditions:

1. Goal Reachability: The goal state is reachable from every state with non-zero probability under some policy.
2. Negative Transition Rewards: All transition costs are strictly positive ($R \le -c < 0$ per step), or costs are discounted ($\gamma < 1$), ensuring that wandering infinitely in loops is penalized.
3. Admissible (Optimistic) Initial Values: The initial value estimates $V_0(s)$ are admissible, meaning they are optimistic upper bounds on the true optimal values: $V_0(s) \ge V^*(s) \quad \forall s \in \mathcal{S}$

Because initial values are optimistic, unexplored states look enticingly promising. If an agent tries an action that leads to an unpromising result, its Bellman update drops $V(S_t)$ downward toward reality, driving subsequent trials to explore alternative paths until the optimal policy stabilizes.

Worked numerical example

Consider a 4-state stochastic shortest-path MDP:

• States: $\{S_0, S_1, S_2, G\}$, where $G$ is the absorbing terminal goal ($V(G) = 0$).
• Step cost: $R = -1.0$ per transition, undiscounted ($\gamma = 1.0$).
• Transitions from start state $S_0$:
  • Action $a_{\text{risky}}$: $80\%$ chance transitions to $S_1$, $20\%$ chance transitions to $S_2$.
  • Action $a_{\text{safe}}$: $100\%$ chance transitions to $S_2$.
• Transitions from $S_1$ and $S_2$:
  • From $S_1$: single action leads directly to $G$ with prob $1.0$.
  • From $S_2$: single action leads directly to $G$ with prob $1.0$.
• Initial values (admissible heuristic $V_0(s) = 0.0 \ge V^*(s)$ for all non-terminal states): $V_0(S_0) = 0.0, \quad V_0(S_1) = 0.0, \quad V_0(S_2) = 0.0, \quad V(G) = 0.0$

Trial 1

1. At state $S_0$:
   • Compute Q-values: $Q(S_0, a_{\text{risky}}) = -1.0 + 0.8 V(S_1) + 0.2 V(S_2) = -1.0 + 0.8(0) + 0.2(0) = -1.0$ $Q(S_0, a_{\text{safe}}) = -1.0 + 1.0 V(S_2) = -1.0 + 1.0(0) = -1.0$
   • Update $V(S_0) \leftarrow \max(-1.0, -1.0) = \mathbf{-1.0}$.
   • Tie-break greedily chooses $a_{\text{risky}}$. Transition samples $S_1$.
2. At state $S_1$:
   • Compute Q-value: $Q(S_1, \text{exit}) = -1.0 + 1.0 V(G) = -1.0 + 0.0 = -1.0$
   • Update $V(S_1) \leftarrow \mathbf{-1.0}$.
   • Advances to terminal goal $G$. Trial 1 terminates!
   • Key observation: State $S_2$ was never visited; its value remains untouched at $0.0$.

Trial 2

1. At state $S_0$:
   • Re-evaluate actions using updated values ($V(S_1) = -1.0, V(S_2) = 0.0$): $Q(S_0, a_{\text{risky}}) = -1.0 + 0.8(-1.0) + 0.2(0.0) = -1.0 - 0.8 = -1.8$ $Q(S_0, a_{\text{safe}}) = -1.0 + 1.0(0.0) = -1.0$
   • Update $V(S_0) \leftarrow \max(-1.8, -1.0) = \mathbf{-1.0}$.
   • Greedy choice is now $a_{\text{safe}}$ (since $S_2$ still looks optimistically cost-free).
   • Transition lands in $S_2$.
2. At state $S_2$:
   • Compute Q-value: $Q(S_2, \text{exit}) = -1.0 + 0.0 = -1.0$.
   • Update $V(S_2) \leftarrow \mathbf{-1.0}$.
   • Advances to $G$. Trial 2 terminates!

Trial 3

1. At state $S_0$:
   • Both states now reflect real costs ($V(S_1) = -1.0, V(S_2) = -1.0$): $Q(S_0, a_{\text{risky}}) = -1.0 + 0.8(-1.0) + 0.2(-1.0) = -2.0$ $Q(S_0, a_{\text{safe}}) = -1.0 + 1.0(-1.0) = -2.0$
   • Update $V(S_0) \leftarrow \mathbf{-2.0}$.
   • Both policies achieve identical optimal expected return $-2.0$. The values have converged to exact $V^*$ in only three short trajectory runs!

Code

1from typing import Dict, List, Set, Tuple2
3
4class GridWorldSSP:5    """Stochastic Shortest Path GridWorld for RTDP benchmarking."""6
7    def __init__(self, size: int = 7, goal: Tuple[int, int] = (6, 6)):8        self.size = size9        self.goal = goal10        self.states = [(r, c) for r in range(size) for c in range(size)]11        self.actions = ["up", "down", "left", "right"]12
13    def transitions(14        self, s: Tuple[int, int], a: str15    ) -> List[Tuple[Tuple[int, int], float, float]]:16        """Return list of (next_state, reward, probability) tuples."""17        if s == self.goal:18            return [(self.goal, 0.0, 1.0)]19
20        r, c = s21        deltas = {"up": (-1, 0), "down": (1, 0), "left": (0, -1), "right": (0, 1)}22        dr, dc = deltas[a]23        nr = max(0, min(self.size - 1, r + dr))24        nc = max(0, min(self.size - 1, c + dc))25        next_state = (nr, nc)26        reward = 0.0 if next_state == self.goal else -1.027        return [(next_state, reward, 1.0)]28
29
30def run_rtdp(31    env: GridWorldSSP,32    start: Tuple[int, int] = (0, 0),33    max_trials: int = 35,34    max_steps_per_trial: int = 50,35) -> Tuple[Dict[Tuple[int, int], float], Set[Tuple[int, int]]]:36    """Execute Real-Time Dynamic Programming on the given SSP environment.37
38    Uses an admissible heuristic (negative Manhattan distance to goal).39    """40    # Admissible heuristic: V_0(s) = -manhattan_distance(s, goal) >= V*(s)41    V: Dict[Tuple[int, int], float] = {42        s: -float(abs(s[0] - env.goal[0]) + abs(s[1] - env.goal[1]))43        for s in env.states44    }45    visited_states: Set[Tuple[int, int]] = set()46
47    for trial in range(max_trials):48        s = start49        step = 050        while s != env.goal and step < max_steps_per_trial:51            visited_states.add(s)52
53            # 1. Local Bellman backup across all actions54            best_q = -float("inf")55            best_action = env.actions[0]56
57            for a in env.actions:58                q_val = 0.059                for next_s, r, prob in env.transitions(s, a):60                    q_val += prob * (r + V[next_s])61
62                if q_val > best_q:63                    best_q = q_val64                    best_action = a65
66            V[s] = best_q67
68            # 2. Advance greedily along the model transition69            next_state, _, _ = env.transitions(s, best_action)[0]70            s = next_state71            step += 172
73    return V, visited_states74
75
76if __name__ == "__main__":77    env = GridWorldSSP(size=7, goal=(6, 6))78    start_pos = (0, 0)79
80    values, visited = run_rtdp(env, start=start_pos, max_trials=30)81
82    total_states = len(env.states)83    touched_count = len(visited)84    coverage_pct = (touched_count / total_states) * 100.085
86    print("=== Real-Time Dynamic Programming (RTDP) Results ===")87    print(f"Total State Space Size:   {total_states} states")88    print(89        f"States Touched by RTDP:   {touched_count} states ({coverage_pct:.1f}% coverage)"90    )91    print(f"Learned Value at Start:   {values[start_pos]:.1f}")92
93    # Optimal shortest path in 7x7 grid from (0,0) to (6,6) is 12 steps (cost -11.0 to goal transition)94    expected_start_val = -11.095    assert (96        values[start_pos] == expected_start_val97    ), f"Expected optimal value {expected_start_val}, got {values[start_pos]}"98    assert (99        coverage_pct < 50.0100    ), f"RTDP should evaluate less than half the states! Got {coverage_pct:.1f}%"101
102    print("\nVerification passed: RTDP found the optimal policy while skipping >75% of state space.")103
104# Expected Output:105# === Real-Time Dynamic Programming (RTDP) Results ===106# Total State Space Size:   49 states107# States Touched by RTDP:   12 states (24.5% coverage)108# Learned Value at Start:   -11.0109#110# Verification passed: RTDP found the optimal policy while skipping >75% of state space.

Watch Out For

The Quick Version

• Trajectory sampling: RTDP replaces exhaustive sweeps by updating only states encountered during simulated on-policy rollouts from start to goal.
• Asynchronous backups: Each visited state undergoes an immediate local Bellman backup ($V(S_t) \leftarrow \max_a \sum p [r + \gamma V]$) before the agent takes its greedy step.
• Admissible convergence: If initial values are optimistic ($V_0 \ge V^*$) and step costs are negative, RTDP is mathematically guaranteed to converge to an optimal policy on relevant states.
• Immense efficiency gains: RTDP bypasses unreachable, irrelevant, or highly suboptimal state clusters, achieving optimal control with a small fraction of the computation needed by full Dynamic Programming.

What to Read Next

• Trajectory Sampling
• Dynamic Programming in RL
• Value Iteration