// the one-minute version
Planning applies value updates to model-generated experience. A distribution model provides probabilities; a sample model generates transitions. Dyna unifies acting, direct RL, model learning, and planning with the same Q-learning update. When a model becomes stale, Dyna can plan confidently in a world that no longer exists; Dyna-Q+ adds time-based exploration bonuses. Prioritized sweeping backs up predecessors whose values are likely to change most. Sample backups can beat full expectations when branching is high and compute is limited. Trajectory sampling, RTDP, rollouts, heuristic search, and MCTS focus planning on reachable or currently relevant states.
Real deliveries are expensive, but Asha's robot experiences each transition only once. After learning that aisle B is blocked, ordinary Q-learning updates the junction immediately before B; upstream routes remain optimistic until revisited. Asha already has enough evidence to imagine those routes ending at the blockage. If she learns a model, one real surprise can generate many useful hypothetical updates while the robot charges.
01 Models turn experience into reusable predictions
A model predicts environment responses. A distribution model returns p(s′,r|s,a), enabling expected backups. A sample model returns one possible s′,r when queried, enabling sample backups. Planning means computing or improving a policy with this model.
Model-based and model-free methods use the same value targets; they differ in where transitions come from. Real transitions support direct RL and model learning. Simulated transitions support planning.
02 Dyna: one architecture, four jobs
Dyna-Q repeats this loop: (1) observe S, choose A, receive R,S′; (2) update Q from the real transition; (3) store the transition in a model; (4) repeat n planning steps by sampling a previously observed S,A, querying the model, and applying the same Q-learning update.
The equation does not reveal whether the transition was real or imagined. More planning steps per real action usually reduce real experience needed, at the cost of computation and exposure to model error.
Fig 1 — Dyna learns from reality once, records it, then spends computation replaying model consequences.
03 Maze learning and the price of computation
In the Dyna maze, zero planning steps reduce to Q-learning. Five or fifty planning updates after each real step propagate reward through the model much faster, so the agent reaches the goal with fewer environment interactions.
This does not mean planning is free. Compare wall-clock compute, model-query cost, and real-sample cost. In robotics, a millisecond simulation may replace a second of motion; in a slow learned world model, planning may itself dominate latency.
04 When the model is wrong: blocking and shortcuts
If a learned deterministic model stores the last observed transition, it assumes the world stays fixed. When a route becomes blocked, direct experience corrects the encountered edge, and planning spreads the bad news. But when a new shortcut opens, the agent may never try it because the old model and policy agree it is useless.
Dyna-Q+ treats actions not tried for τ steps as potentially improved, adding exploration bonus κ√τ to modeled reward. The bonus makes stale actions attractive enough to retest. It can adapt to shortcuts but may waste effort revisiting genuinely stable poor actions.
05 Prioritized sweeping
Uniform Dyna samples previously seen pairs randomly. Many backups have tiny TD errors and change nothing. Prioritized sweeping maintains a priority queue keyed by expected update magnitude. When a state's value changes, find predecessor pairs that can lead to it and raise their priorities.
Pop the largest priority, perform its backup, then propagate priority backward. This follows surprise against causal direction—from changed outcome to decisions that depend on it. A blockage near delivery rapidly revises upstream junctions instead of replaying unrelated aisles.
The model must store predecessor links or derive them. Queue maintenance adds overhead, so priority helps most when important changes are sparse relative to the state space.
06 Expected versus sample backups
An expected backup sums over all possible outcomes of an action; a sample backup uses one model-generated outcome. Expected backups remove transition-sampling variance but cost proportional to branching factor.
With high branching and fixed compute, many cheap sample backups across relevant pairs can produce more progress than a few exhaustive expectations. Early in planning, breadth of updates may matter more than precision of each one.
This comparison unifies planning and learning: model-free TD is necessarily sample-based; a sample model makes planning look identical; a distribution model offers the option of expectation.
07 Trajectory sampling and real-time dynamic programming
Uniform sweeps spend equal compute on unreachable states. Trajectory sampling starts from states of interest and follows model trajectories under a policy, concentrating backups on states likely to be visited.
Real-time dynamic programming (RTDP) uses greedy simulated trajectories with value iteration backups. Under suitable initialization and reachability conditions, it can solve relevant states without exhaustively solving the entire MDP.
The tradeoff is coverage: focusing on the current policy can miss valuable alternatives. Exploration, optimistic initialization, or occasional broader planning protects against tunnel vision.
08 Planning at decision time: rollouts, search, and MCTS
Background planning improves a stored policy before a decision. Decision-time planning spends computation from the current state. A rollout algorithm simulates each candidate action followed by a base policy and selects the action with best estimated return. Even a modest base policy can improve through lookahead.
Heuristic search expands promising paths and uses an approximate value at leaf states. Monte Carlo tree search repeats four phases: select actions through an existing tree (balancing value and visit uncertainty), expand a new node, simulate or evaluate from it, and back up the outcome. Search becomes deeper where evidence says it matters.
MCTS is not the same as Chapter 5 MC control. It builds a temporary, state-rooted search tree using a model at decision time; Monte Carlo control learns persistent policy values from environment episodes.
Background planning
Dyna, prioritized sweeping, sweeps. Improve values broadly between decisions.
Decision-time planning
Rollouts, heuristic search, MCTS. Focus compute on the current choice.
common catches & gotchas
- Equating a model with a neural world model — A table of observed transitions is already a model.
- Counting simulated samples as new evidence — Planning reuses assumptions; it does not add independent real information.
- Planning harder in a wrong model — Monitor model error and retest stale actions.
- Uniformly replaying everything — Priorities and reachability can spend compute where value changes matter.
- Assuming expected backups are always superior — Their branching cost may lose to many sample backups.
- Confusing MCTS with model-free MC — MCTS is model-based decision-time search rooted at the current state.
09 Questions master's students should answer
Is Dyna model-based or model-free?
It is an architecture containing both: direct model-free updates from real experience plus model learning and model-based planning updates.
Why can a sample model be enough?
Many RL updates need transition samples, not explicit probabilities. Querying a generative model produces the same input shape as real experience.
What does prioritized sweeping prioritize?
An estimate of how much a backup will change value, then predecessors of changed states. It prioritizes computational consequence, not raw visit frequency.
When is planning at decision time attractive?
When the current state matters more than a globally solved policy, a model is available, and latency permits targeted lookahead—games are the classic case.
How should model error change planning?
Reduce trust or horizon in uncertain regions, compare predictions with real transitions, maintain uncertainty, and deliberately gather data where errors affect decisions.
10 Key takeaways
- Planning applies familiar backups to model-generated experience.
- Dyna integrates direct RL, model learning, and planning in one loop.
- Planning reduces real interactions but spends computation and can amplify model bias.
- Dyna-Q+ retests stale actions with a time-based bonus when the environment may change.
- Prioritized sweeping propagates important changes backward through predecessors.
- Sample versus expected backups trade variance for branching cost.
- Trajectory sampling and RTDP focus on reachable states; rollouts and MCTS focus on the current decision.
Dyna loop
where compute goes
11 Part I synthesis and source trail
Tabular RL now forms a single map: DP uses full models and expectations; MC uses complete sampled returns; TD uses sampled transitions and bootstrap estimates; n-step methods interpolate; Dyna learns a model and turns computation into extra updates; search spends those updates at decision time. Part II begins with on-policy prediction with approximation, because Asha's real warehouse cannot fit in a value table.
These are independent companion notes written in original language. Primary references: the authors' book page, the author-hosted open-access draft, the MIT Press edition page, and the official contents.