Real-Time Dynamic Programming

Sweeping every state is wasteful when most states never matter. RTDP only updates the states its simulated trials actually walk through, and still converges on those.

RTDP walks three short trials from start to goal, updating only visited states until values settle at minus 2.0 while the rest stay untouched

Why Does This Exist?

Classic dynamic programming sweeps every state on every pass. In a warehouse robot with a million states, that means recomputing values for locked closets the robot will never enter, over and over. The cost grows with the size of the whole map, not with the size of the actual job.

The observation behind RTDP is that goal directed tasks only need a slice of the map: the states a good policy can actually reach from the start. Barto, Bradtke, and Singh showed in 1995 that running value iteration style backups only along simulated start to goal trials converges to the optimal policy on exactly those relevant states. This page covers that trajectory sampling mechanism. For the sampling idea on its own, read trajectory sampling.

The one idea you need first

A Bellman backup refreshes one state's value from its successors: $V(s) \leftarrow \max_a \sum p(s', r \mid s, a)[r + \gamma V(s')]$ . Here $p$ is the model giving transition probabilities, $r$ is the immediate reward, and $\gamma$ is the discount factor weighting future value. Full sweeps apply this everywhere. RTDP applies it only where its trials walk.

Think of It Like This

The spelunker who maps only the way out

A surveyor insists on mapping every side cave in the mountain before moving, including flooded pits nowhere near the exit. A spelunker with a compass heading just starts walking. At each fork she scores the options, scribbles the result in her notebook for that junction only, and takes the best looking tunnel. Dead ends get downgraded the moment they disappoint, so later trips avoid them.

After a few trips from entrance to daylight, her notebook holds an optimal route. Thousands of side caves stay blank, and that blankness cost nothing. The compass heading matters: it must be optimistic, treating unknown tunnels as promising, or she settles into the first mediocre corridor and never checks the better one.

Where the analogy stops: the spelunker walks once per trip, while RTDP interleaves its notebook updates with greedy steps inside a known probabilistic model, sampling next states from it rather than physically traveling.

How It Actually Works

RTDP runs repeated trials from a start state to the goal, using a known model $p(s', r \mid s, a)$ . At each visited state $S_t$ it does two things. First, the local backup:

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

Second, it acts greedily with respect to those fresh values and samples the next state from the model. Unvisited states keep their initial heuristic values until a trial reaches them.

Convergence rests on three conditions for stochastic shortest path tasks: the goal stays reachable, lingering costs something (negative step costs or $\gamma < 1$ ), and initial values are optimistic, meaning $V_0(s) \ge V^{\star}(s)$ everywhere. Optimism makes unexplored states look inviting, so trials keep spreading until the values settle. Pessimistic starts trap the agent in the first corridor it tries.

Worked example

Four states $S_0, S_1, S_2, G$ with goal value $V(G) = 0$ . Every move costs $-1.0$ with no discounting. From $S_0$ , action risky reaches $S_1$ with probability 0.8 and $S_2$ with 0.2, while action safe reaches $S_2$ for sure. Both $S_1$ and $S_2$ lead straight to $G$ . Start optimistic with all values at $0.0$ .

Trial 1 at $S_0$ : $Q(risky) = -1.0 + 0.8(0) + 0.2(0) = -1.0$ and $Q(safe) = -1.0 + 0 = -1.0$ . Update $V(S_0) = -1.0$ . Tie goes to risky, the sample lands on $S_1$ , which backs up to $-1.0$ and reaches the goal. $S_2$ stays untouched at $0.0$ .

Trial 2 at $S_0$ : now $Q(risky) = -1.0 + 0.8(-1.0) + 0.2(0.0) = -1.8$ while $Q(safe) = -1.0 + 0.0 = -1.0$ . Greedy picks safe, lands on $S_2$ , which backs up to $-1.0$ .

Trial 3 at $S_0$ : $Q(risky) = -1.0 + 0.8(-1.0) + 0.2(-1.0) = -2.0$ and $Q(safe) = -1.0 + (-1.0) = -2.0$ . Update $V(S_0) = -2.0$ , the true optimum, after three short walks. The diagram draws these three trials and the untouched states around them.

Code

This snippet replays the three trials with plain arithmetic. Check the printed Q values against the hand computation above.

1if __name__ == "__main__":2    V = {"S0": 0.0, "S1": 0.0, "S2": 0.0, "G": 0.0}3
4    # Trial 1 at S0, everything still 0.05    q_risky = -1.0 + 0.8 * V["S1"] + 0.2 * V["S2"]6    q_safe = -1.0 + V["S2"]7    V["S0"] = max(q_risky, q_safe)8    print(f"trial 1: risky={q_risky:.1f} safe={q_safe:.1f} V(S0)={V['S0']:.1f}")9    V["S1"] = -1.0 + V["G"]10    print(f"trial 1: V(S1)={V['S1']:.1f} V(S2) untouched={V['S2']:.1f}")11
12    # Trial 2 at S0, S1 now -1.013    q_risky = -1.0 + 0.8 * V["S1"] + 0.2 * V["S2"]14    q_safe = -1.0 + V["S2"]15    V["S0"] = max(q_risky, q_safe)16    print(f"trial 2: risky={q_risky:.1f} safe={q_safe:.1f} V(S0)={V['S0']:.1f}")17    V["S2"] = -1.0 + V["G"]18    print(f"trial 2: V(S2)={V['S2']:.1f}")19
20    # Trial 3 at S0, both successors known21    q_risky = -1.0 + 0.8 * V["S1"] + 0.2 * V["S2"]22    q_safe = -1.0 + V["S2"]23    V["S0"] = max(q_risky, q_safe)24    print(f"trial 3: risky={q_risky:.1f} safe={q_safe:.1f} V(S0)={V['S0']:.1f}")

1# -> expected output:2trial 1: risky=-1.0 safe=-1.0 V(S0)=-1.03trial 1: V(S1)=-1.0 V(S2) untouched=0.04trial 2: risky=-1.8 safe=-1.0 V(S0)=-1.05trial 2: V(S2)=-1.06trial 3: risky=-2.0 safe=-2.0 V(S0)=-2.0

Watch Out For

Pessimistic starts trap the agent in the first corridor

The symptom: RTDP converges fast to a mediocre route and never improves, no matter how many trials run. The cause is initialization below the true values. Tried states look better than untouched ones simply because untouched ones started gloomy, so greed never wanders.

The fix: start optimistic. For step cost tasks, zero works since true values are negative. For anything else, use a relaxed domain heuristic such as straight line distance that overestimates rather than underestimates. Confirm the goal holds value zero so it keeps pulling trials forward.

Loops with free steps spin forever

The symptom: trials run to the step cap without reaching the goal, values barely move. The cause is zero or positive rewards on non goal transitions with no discounting, which makes wandering costless. The backup then sees no reason to prefer the exit.

The fix: keep step costs strictly negative or set $\gamma < 1$ so every extra loop lowers the estimate until the greedy policy breaks out. Cap trial length as a backstop, but treat frequent cap hits as a modeling flag, not a tuning knob.

The Quick Version

RTDP replaces full sweeps with start to goal trials, backing up only visited states with $V(S_t) \leftarrow \max_a \sum p[r + \gamma V]$ .
With an optimistic start, reachability, and costly lingering, it converges to optimal values on relevant states only.
The worked MDP settles $V(S_0)$ at minus 2.0 across three trials while untouched states cost zero compute.
Pessimistic initialization traps the policy in the first corridor it tries.
Free loops need negative step costs or discounting, or trials wander without learning.