Planning: Focusing Updates and Decision-Time Search

This builds on Planning and Learning, which showed that planning and learning are the same backup applied to simulated versus real experience, and built the Dyna architecture around that idea. Dyna replays remembered transitions chosen uniformly at random — and most of those replays do no useful work. This lesson makes planning efficient, then turns from background planning to planning done afresh at each decision.

Prioritized sweeping

Dyna-Q starts its simulated transitions at pairs chosen uniformly at random, wasting effort. In the second maze episode only the pair leading into the goal has nonzero value, so an update anywhere else backs up zero onto zero and changes nothing. Under uniform sampling the agent performs many null updates before finding a useful one.

To address this, work backward from states whose value just changed. When $V(s^{\prime })$ changes, the only one-step updates that can do useful work are those on actions leading into $s^{\prime }$; updating them may change their predecessors, so the frontier of useful updates propagates backward from the change. This is backward focusing. The frontier grows fast, and not every pair matters equally — some values would change by a lot, others barely. Prioritized sweeping orders the work by urgency: keep a queue of state–action pairs keyed by the magnitude of the Bellman error they would incur, and always process the top first.

On maze tasks prioritized sweeping reaches the optimal policy with 5-to-10 times fewer updates than unprioritized Dyna-Q, and the advantage widens with the grid size. It extends to stochastic environments by keeping transition counts and using expected updates over all possible successors — which is also its main limitation, since expected updates can waste computation on low-probability transitions. That tension is the next topic.

Expected vs. sample updates

A backup can be computed two ways. An expected update considers all possible next states and rewards, weighting each by its probability; a sample update considers a single sampled successor. For the action-value $q_{\ast }$ with a distribution model $\hat{p}(s^{\prime },r\mid s,a)$, the expected update is

while the sample update, given one sampled $S^{\prime },R$, is the Q-learning form

The expected update is thorough but slow (it visits every successor); the sample update is cheap but noisy (it visits one). Under a fixed compute budget, which wins?

They coincide when the environment is deterministic (one successor, $\alpha =1$). With many successors they diverge: the expected update is exact — its new $Q(s,a)$ is limited in error only by the errors at the successors — while the sample update carries sampling error. So an expected update yields the better estimate but costs more. Let $b$ be the branching factor, $b=|\{s^{\prime }:\hat{p}(s^{\prime }\mid s,a)>0\}|$. One expected update costs about $b$ times as much computation as one sample update.

If there is time to finish an expected update its estimate is generally better. But with large $b$, the $b$ units of compute for one expected update instead buy $b$ sample updates spread over $b$ pairs, improving each a little. The RMS error of sample updating falls roughly as

after $t$ sample updates, so for moderately large $b$ the error drops to within a few percent of the expected result after only a small fraction of $b$ sample updates. On large stochastic problems with many state–action pairs, spreading cheap sample updates across many pairs beats spending the same effort on a few exact ones; and because the successor estimates become accurate sooner, later backups off those successors compound the advantage.¹

Trajectory sampling and real-time DP

A second axis governs not what an update looks like but which states get updated. Classical DP sweeps the whole state space, updating every state once per pass. On large tasks this is hopeless: most states are irrelevant — visited only under poor policies or with tiny probability — yet the sweep spends equal effort on them. The alternative is to draw states from the on-policy distribution: follow the current policy $\pi$ in simulation and update the states it visits. This is trajectory sampling, and it needs no explicit representation of the distribution — the trajectory generates it for free. Empirically it speeds early planning, at some risk of neglecting the rest of the space in the long run.

Real-time dynamic programming (RTDP) is the on-policy trajectory-sampling version of value iteration: it applies expected value-iteration updates to the states visited along real or simulated trajectories, in whatever order those visits occur. RTDP is a form of asynchronous DP — no systematic sweeps, updates in trajectory order — and it has a strong guarantee. On stochastic optimal-path problems (undiscounted episodic tasks with an absorbing goal, zero goal value, negative step rewards, and a policy guaranteed to reach the goal), RTDP converges to a policy optimal on the relevant states — those reachable from a start state under some optimal policy — without ever visiting the irrelevant ones, and sometimes without visiting some relevant states at all. On a racetrack task with over 9,000 reachable states, RTDP reached near-optimal control with about half the updates that sweep-based value iteration needed, leaving a large fraction of states barely touched or untouched.²

Beyond the table: model-based deep reinforcement learning

Dyna's claim — that a learned model plus replayed simulated experience extracts more policy improvement from scarce interaction — is the founding idea of model-based deep RL, and the modern versions keep the Dyna skeleton while replacing its tabular pieces with neural networks.

Prioritized sweeping, generalized. Moore and Atkeson's prioritized sweeping, the backward-focusing method above, predates Dyna's tabular limits and was designed precisely for reinforcement learning with less data and less time.³ Its priority-queue idea survives in deep RL as prioritized experience replay: sample stored transitions in proportion to their TD error rather than uniformly, so the network spends gradient steps where the TD error — and thus the learning signal — is largest.⁴

Learned models you can plan in. Ha and Schmidhuber's World Models trained a recurrent latent dynamics model from pixels and then trained a controller almost entirely inside that model's dream, transferring the result back to the real environment — Dyna's indirect route with a deep generative model as the sample model.⁵ Hafner and colleagues' Dreamer line made this a strong general method: learn a latent world model, then optimize the policy by backpropagating value gradients through imagined (simulated) trajectories rolled out in the model, achieving state-of-the-art data efficiency on continuous control and, in DreamerV3, across a wide span of domains with fixed hyperparameters.⁶

Planning in a learned model at decision time. MuZero closes the loop with the decision-time methods below: it learns a latent dynamics model and runs Monte Carlo tree search over it, with no access to the environment's rules, matching AlphaZero on Go, chess, and shogi and setting records on Atari.⁷ The Dyna picture — experience improves a model, the model generates simulated experience, and the same backups improve the policy — is intact; every box is now a network.

Planning at decision time

Everything so far is background planning: use simulated experience to improve a policy or value function over all states ahead of time, so that when $S_t$ arrives its action is already cached and reading it off is trivial. Planning is not focused on the current state; it has already happened.

The alternative is decision-time planning: on encountering $S_t$, run a planning computation whose only output is the single action $A_t$, then discard the values it produced and start over at $S_{t+1}$. The values and policy are specific to $S_t$ and its likely successors — usually wasteful to save (you rarely revisit the exact state soon), but concentrating all computation on the decision at hand.

Heuristic search and rollouts

Heuristic search is the classical decision-time method from artificial intelligence. At each state it builds a large tree of continuations, applies a stored approximate value function at the leaves, and backs those values toward the root exactly as the expected $v_{\ast }$/$q_{\ast }$ updates do throughout this course — then picks the best root action and discards the rest. Deeper search improves action selection by pushing the imperfect value function further from the decision; if the search reaches terminal states, the value-function error vanishes entirely. Its main advantage is focus: the tree concentrates on the states and actions that might immediately follow $S_t$, so computation and memory are spent where they most affect the imminent decision.

Rollout algorithms are decision-time planners built on Monte Carlo control. At state $s$, for each candidate action $a$ the algorithm simulates many trajectories that start with $a$ and thereafter follow a fixed rollout policy$\pi$, estimating $q_{\pi }(s,a)\approx \frac{1}{m}{\sum }_{i=1}^m{G}_i$ by the mean of the $m$ sampled returns. It then plays

This is one step of policy improvement: by the policy improvement theorem, acting greedily w.r.t. $q_{\pi }$ at $s$ and following $\pi$ after yields a policy at least as good as $\pi$. A rollout algorithm does not learn an optimal value function; it improves over $\pi$ on the fly, then discards the estimates. Better rollout policies and more trajectories give better decisions, at more computation per move.

Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is a rollout algorithm with memory. Plain rollouts throw away every simulated trajectory; MCTS accumulates the value estimates from successive simulations to steer later ones toward high-reward parts of the space. It is the method that carried computer Go from weak amateur in 2005 to grandmaster by 2015, and, combined with a deep neural network, it is the search inside AlphaGo and AlphaZero.⁸

MCTS maintains a tree rooted at the current state, holding Monte Carlo value estimates for the state–action pairs most likely to be reached in a few steps. Inside the tree it selects actions by an informed tree policy (e.g. $\epsilon$-greedy or a UCB rule) that balances exploration and exploitation — a UCB tree policy selects

with $N(s,a)$ the edge visit count and $N(s)={\sum }_{a}N(s,a)$; outside the tree it falls back to the simple rollout policy. Each iteration runs four steps, repeated until the move-time budget is exhausted.

The root action is chosen by accumulated statistics — usually the largest visit count $N(S_t,a)$ (robust to outliers) or the largest $Q$. The environment then advances, and MCTS runs again, reusing the surviving subtree and discarding the rest.

MCTS is a decision-time rollout algorithm, so it inherits online, incremental, sample-based value estimation and the policy-improvement guarantee of acting greedily on Monte Carlo estimates. Beyond that, by saving edge statistics and expanding along high-return trajectories, it grows a partial action-value table concentrated on the initial segments of promising trajectories — the benefit of a learned $Q$ without approximating a value function globally, while still using past experience to guide exploration.

Finally, the leaf-node evaluation and the rollout policy need not stay simple. Replace the hand-written rollout with a deep neural network that evaluates leaf positions and suggests moves, train that network by self-play, and MCTS becomes the search inside AlphaGo and AlphaZero — the subject of the deep-RL case studies. The tree search supplies the deep, focused lookahead; the network supplies the value and policy priors that make the search tractable.