Decision-Time Planning

The planning-and-learning lesson built Dyna: a model generates simulated experience, and the same backups that learn from real experience improve a global value function state by state. That is background planning. When a state $S_t$ finally arrives, its action is already stored in the table; reading it off is a lookup. All the computation happened earlier, spread across the whole state space.

There is a second way to use a model. Wait until $S_t$ arrives, then run a computation whose only output is the single action $A_t$ — a deep, focused lookahead from this state — and discard everything the moment you have played. The next state $S_{t+1}$ starts the computation over. This is decision-time planning, and it is how a chess engine spends its clock: not on a policy for all of chess, but on the best move in the position on the board right now. This lesson takes the compressed treatment from the planning lesson and works it out in full — real-time DP, heuristic search, and rollout algorithms — building toward Monte Carlo Tree Search, the search behind AlphaZero, which the next lesson develops.¹

Background versus decision-time planning

The distinction is when the planning happens relative to the moment of action, and what it produces.

Background planning improves the value function or policy over many states, ahead of demand, so that action selection is cheap.¹ Dyna and prioritized sweeping are background planners: their updates are not aimed at the current state in particular. By the time $S_t$ is encountered, planning has already shaped the table entries used to choose $A_t$, and possibly the entries for a great many other states too.

Decision-time planning begins and completes after encountering each new state, as a computation whose output is one action. The values and policy it produces are specific to $S_t$ and its likely successors, and they are usually discarded once the action is chosen — you rarely return to the exact same state soon enough for saved values to help. In exchange, every unit of computation is spent on the decision immediately at hand.

The two blend in practice — you can focus planning on the current state and save a little of it so a later return is cheaper — but they are cleanest understood apart. The trade is latency against depth: background planning suits control that must respond in milliseconds; decision-time planning suits settings where you can afford seconds or minutes per move, and a deep lookahead buys a much better action.

Real-time dynamic programming

Before decision-time planning proper, there is a method between the two categories, and it illustrates why focusing on the states the agent actually visits helps. Real-time dynamic programming (RTDP) is an on-policy trajectory-sampling version of the value-iteration algorithm of dynamic programming.²

Conventional value iteration sweeps the entire state set, applying the expected value-iteration update

to every state, over and over, until the values stop changing. RTDP applies the same update, but not in systematic sweeps. It is an instance of asynchronous dynamic programming: the update order is dictated by the order in which states are visited along real or simulated trajectories. At each step of a trajectory, the agent is in some state $S$; it applies the value-iteration update to $S$ (and optionally to a few other states, such as those in a limited look-ahead search), takes a greedy action, and moves on. States that the agent never visits are never updated.

The close tie to conventional DP lets convergence results carry over. If trajectories can start only from a designated set of start states, then for a prediction problem, on-policy trajectory sampling lets RTDP skip every state that the given policy cannot reach from any start — those states are irrelevant to the prediction problem. For control, the goal is an optimal partial policy: one that is optimal on the relevant states (reachable from some start under some optimal policy) but may be arbitrary, or even undefined, on the irrelevant ones. There is no need to specify optimal actions where an optimal policy never goes.

The key result: for a class of problems, RTDP converges to a policy optimal on the relevant states without visiting every state infinitely often — sometimes without visiting some states at all. When only a small fraction of a very large state set is relevant, that is decisive; even a single full sweep may be infeasible, yet RTDP never needs one.

In plain terms: as long as the agent can always reach the goal, every step costs something, and the values start out optimistic, RTDP will settle on the right action for every state that matters — even though it never updates the states that do not. The formal statement lists exactly those conditions.

These are the stochastic optimal-path problems — cost-minimization tasks such as minimum-time control, where each step costs $-1$ and the objective is to reach the goal as cheaply as possible. The convergence proof combines asynchronous-DP results with results on learning real-time A* (Korf, 1990), the heuristic-search algorithm RTDP generalizes.

RTDP on the racetrack

Sutton and Barto compare RTDP against conventional (sweep-based, Gauss–Seidel) value iteration on a racetrack: an agent must drive around a turn and cross the finish line in as few steps as possible, $-1$ per step, restarting from a random start state on a crash. A small racetrack has $9,115$ states reachable from the start states, but only about $599$ of them are relevant — reachable under some optimal policy. That gap is where RTDP wins.

Both methods reach policies averaging 14–15 steps to the finish, but RTDP does it with roughly half the updates. Conventional value iteration updates every state on every sweep; RTDP focuses updates on the states relevant to the objective, and that focus narrows as learning continues. There is a second, subtler advantage: because RTDP is always greedy with respect to its current values, the policy it uses to generate trajectories approaches an optimal policy as the values approach $v_{\ast }$ — whereas conventional value iteration keeps updating every state right up to termination and only checks the policy afterward.

Planning at decision time

RTDP still improves values it might revisit; it leans toward background. Genuine decision-time planning discards its work. On encountering $S_t$, it begins and completes a planning computation whose output is the single action $A_t$; on the next step it begins anew with $S_{t+1}$ to produce $A_{t+1}$, and so on.¹

Even done only at decision time, planning is still what it always was — computing updates and values from simulated experience, and ultimately a policy — except the values and the policy are now specific to $S_t$ and thrown away after selecting the action. In many applications that is no great loss: the state space is huge and you are unlikely to return to the same state soon. You can mix the two (focus on the current state and store some of the result), but decision-time planning is most useful when fast responses are not required. A chess engine may take minutes per move and plan dozens of moves ahead in that time; if low-latency selection is the priority, background planning is the better choice.

Heuristic search

The classical state-space planners of artificial intelligence — game-tree search and its relatives — are decision-time planning methods, collectively heuristic search.³ For each state encountered, heuristic search considers a large tree of possible continuations. It applies an approximate value function to the leaf nodes and backs those values up toward the current state at the root. The backing-up reuses the expected updates with maxes (the ones for $v_{\ast }$ and $q_{\ast }$) from throughout this course — nothing new. The backup stops at the state–action nodes for the current state; the best of those is chosen as $A_t$, and all the backed-up values are then discarded.

In conventional heuristic search no effort is made to save the backed-up values; the value function is designed by people and left unchanged. (One can allow it to learn — that is essentially what we have been doing all along.) The one-step greedy, $\epsilon$-greedy, and UCB action-selection rules are heuristic search on a smaller scale: to pick the greedy action given a model and a state-value function, you look ahead one step to each possible next state, add rewards and estimated values, and take the best. Heuristic search is that greedy computation extended beyond a single step.

Why does deeper search help? With a perfect model and an imperfect value function, deeper search yields better policies. Search all the way to the end of the episode and the imperfect value function is eliminated entirely — the action is optimal. Search to depth $k$ with ${\gamma }^k$ small and the actions are near-optimal, because the leftover value-function error is discounted away. The cost is compute: deeper search means a slower response. Tesauro's grandmaster-level backgammon player, TD-Gammon, illustrated the trade — the deeper its heuristic search, the better its moves, but the longer each took.

The most important effect of heuristic search is not depth but focus. Its search tree is tightly concentrated on the states and actions that might immediately follow $S_t$. Those states are the ones where you most want the value function to be accurate, and where updates matter most for the imminent decision. In chess there are far too many positions to store a value for each, but a program can easily store distinct estimates for the millions it encounters while looking ahead from a single position. Any state-space search can be viewed as piecing together a large number of individual one-step updates, ordered to concentrate on states downstream of the current one — which is where the performance gain of deeper search actually comes from.

Rollout algorithms

Rollout algorithms are decision-time planners built on Monte Carlo control, applied to simulated trajectories that all begin at the current state.⁴ They estimate action values for a given policy by averaging the returns of many simulated trajectories that start with each possible action and thereafter follow that policy — the rollout policy. When the estimates are good enough, the action with the highest value is played, and the whole process repeats from the resulting next state. The name comes from backgammon: rolling out a position means playing it out to the end many times with random dice.

Unlike the Monte Carlo control of the Monte Carlo lesson, a rollout algorithm does not aim to estimate a complete optimal action-value function $q_{\ast }$, nor even a complete $q_{\pi }$. It produces Monte Carlo estimates of action values only for the current state and a given rollout policy $\pi$. That is what makes rollouts simple: no need to sample every state–action pair, and no need to approximate a function over the whole space.

What does that accomplish? The policy-improvement theorem tells us that if two policies $\pi$ and ${\pi }^{\prime }$ are identical except that ${\pi }^{\prime }(s)=a\ne \pi (s)$ for one state $s$, and $q_{\pi }(s,a)\ge v_{\pi }(s)$, then ${\pi }^{\prime }$ is at least as good as $\pi$ — strictly better if the inequality is strict. Take $s$ to be the current state and $\pi$ the rollout policy. Averaging the simulated returns estimates $q_{\pi }(s,a^{\prime })$ for each $a^{\prime }\in \mathcal{A}(s)$; the policy that plays the best of these and then follows $\pi$ improves on $\pi$. A rollout is therefore one step of policy improvement, applied on the fly to the current state and then discarded — like one step of asynchronous value iteration that changes the action for a single state.

The aim is to improve over the rollout policy, not to find an optimal policy. The better the rollout policy and the more accurate the value estimates, the better the resulting decision (though better rollout policies also take longer to simulate). Because the Monte Carlo trials are independent, they parallelize trivially across processors; and one can truncate trajectories short of termination, correcting the truncated return with a stored evaluation function — which brings the whole apparatus of truncated returns back into play.

This continues in Monte Carlo Tree Search, which turns the rollout algorithm into a planner with memory: it accumulates value estimates across simulations, steers later ones with the UCT rule, and — combined with a deep network — becomes the search behind AlphaGo, AlphaZero, and MuZero.