Does RTDP update the entire state space each iteration?

No. It focuses updates along selected trajectories, unlike full synchronous sweeps.

Is a sampled successor the same as an expected backup?

No. The trial samples one successor, while the model-based backup sums over possible successors with their probabilities.

Does “real-time” guarantee a fixed response deadline?

No. Timing depends on the model, computation, implementation, and surrounding system.

AI Glossary / Graphs and symbolic AI / Advanced

Real-time dynamic programming

Definition

Real-time dynamic programming, or RTDP, is a method for improving decisions by updating value estimates along trajectories through a decision problem. It combines dynamic-programming updates with the selective focus of search. Instead of repeatedly updating every possible state, it concentrates computation on states encountered during actual or simulated interaction, depending on the formulation.

What it means

Dynamic programming evaluates what actions are worth by considering their immediate consequences and the value of future states. RTDP uses that idea while focusing attention on states relevant to the starting situation and the current policy.

The original work by Barto, Bradtke, and Singh connects planning and learning under uncertainty. This entry focuses on planning with a known transition model and simulated trials. Despite its name, RTDP does not by itself provide a hardware-level deadline guarantee or mean that every state update has negligible cost.

How it works

Maintain a value estimate for each relevant state. In a minimum-expected-cost formulation, evaluate each available action by adding its immediate cost to the probability-weighted values of possible successors. Select a greedy action using those estimates and replace the current state's value with the best such estimate.

Then sample a successor according to the chosen action's transition probabilities and continue the trial. Repeated trials revise values along the trajectories they encounter. Importantly, sampling a successor for the trial is different from using all possible successors in the expected-value backup.

Convergence claims depend on the problem class, initial estimates, and other assumptions. For stochastic shortest-path settings, admissible initial estimates and suitable goal-reachability conditions are central. Labeled RTDP is a related extension that marks solved regions to reduce repeated work; it is not identical to basic RTDP.

Three practical examples

Stochastic navigation models: simulated movement outcomes guide value updates along paths relevant to a robot's starting state.
Workflow planning: a model represents actions that sometimes require a recovery step, allowing a planner to compare expected completion costs.
Research benchmarks: investigators compare how focused trial-based updates and full-state value iteration allocate computation in a finite decision problem.

Think of it this way

Think of updating a route notebook mainly while rehearsing trips from a particular starting point, rather than revising every route in a whole atlas. The notebook gradually improves where the rehearsal takes it. The analogy is limited: RTDP's updates use mathematical expectations from a transition model, and a rarely visited branch may still matter to the quality of the resulting policy.

Worked example

Consider three states: start S, recovery R, and goal G. Reaching G ends the task and its remaining cost is zero. At R, the only action costs four and reaches G. At S, action A costs one and reaches G with probability 0.8 or R with probability 0.2. Action B costs two and reaches G certainly.

Initialize all value estimates to zero. The first backup at S estimates A as 1 + 0.8 × 0 + 0.2 × 0 = 1. It estimates B as 2. The greedy choice is A and S's stored value becomes one.

Suppose this trial samples R. At R, its backup becomes 4 + 0 = 4, and the trial then reaches G. On a later visit to S, action A's estimate becomes 1 + 0.8 × 0 + 0.2 × 4 = 1.8. Action B remains two, so A is still preferred, but its earlier optimistic cost estimate has been corrected.

The sampled path through R costs five in that trial. This does not contradict A's expected cost of 1.8: most outcomes go directly to G at cost one. The expected backup averages outcomes; a realized trial follows one of them. If trials repeatedly sample G directly, R's value may remain uncorrected for a while. Less frequent outcomes matter.

Illustrative case study

Fictional case: Cedar Workflow models a document-conversion service with a normal path and an occasional recovery operation. Its researchers test a trial-based planner from the state corresponding to a newly submitted job.

They notice that the initial trials rarely enter recovery. Rather than treating a stable-looking start-state estimate as conclusive, they inspect the recovery model and the evidence supporting convergence. They compare policies by expected cost and also report the range of possible realized costs.

It supplies no measured runtime advantage and makes no claim that a simplified model captures every failure mode of a real service.

Common misconceptions and mistakes

Do not confuse a Bellman backup with merely recording the cost of the last sampled outcome. In the model-based formulation described here, the backup considers the action's possible successors and their probabilities.

Do not assume that a greedy action is already optimal when its value estimates are incomplete. Greedy means best according to the current estimates.

Avoid interpreting focused computation as permission to ignore every unlikely branch. Such branches can affect expected cost and convergence. Also distinguish a useful intermediate policy from a proved stopping condition. Basic RTDP may improve early behavior while taking much longer to settle all values relevant to its final policy.

Business use

For an organization considering stochastic planning, RTDP raises a practical question: can computation be focused on the situations the system is likely to encounter from its actual starting point? Answer that through representative modeling and evaluation.

In the worked example, expected cost and the occasional cost-five path are both relevant. A report containing only the average would conceal important operational variation. Teams should document transition assumptions, initial heuristic values, stopping criteria, and what happens if the real process differs from the model used for planning.

Check your understanding

Why is action A's expected cost 1.8 even though the illustrated recovery trial costs five?

Answer: A costs one immediately and incurs the additional recovery cost of four only with probability 0.2, giving 1 + 0.2 × 4 = 1.8.

Related terms

Dynamic programming
Greedy policy
Heuristic search
Bellman backup
value function
stochastic shortest path
asynchronous value iteration
LRTDP

Learn next

increase the recovery probability in the example and find when action B becomes preferable. Then trace which states are updated during several hypothetical trials. Study LRTDP's solved-state checks before making claims about reliable termination.

Sources

Primary sources: Barto, Bradtke, and Singh, “Learning to act using real-time dynamic programming”: https://ai.dmi.unibas.ch/research/reading_group/barto-etal-ai1995.pdf Bonet and Geffner, “Labeled RTDP,” model and basic RTDP sections: https://bonetblai.github.io/reports/lrtdp.pdf Relevant primary passages were consulted. The three-state calculation and Cedar Workflow case are original.

Previous: Real-time data Next: Real-Time Machine Learning