Planning and Learning

Dynamic programming needs a model of the environment and never touches it; Monte Carlo and temporal-difference methods need no model and learn from raw interaction. The two families are closer than they appear. Both estimate value functions, both do it by backing up values from successor states, and they differ in exactly one place: whether the experience they back up is real (sampled from the environment) or simulated (sampled from a model). With that single distinction fixed, every method in the course — DP, TD, Monte Carlo, heuristic search, and the tree search behind AlphaZero — becomes a point in one space.¹

Models and planning

A model of the environment is anything an agent can query to predict how the environment will respond to an action. Given a state and an action, the model answers with a next state and reward. There are two kinds, and the difference matters throughout the chapter.

The dynamics $p(s^{\prime },r\mid s,a)$ that DP assumes is a distribution model; the blackjack simulator that a Monte Carlo method rolls out is a sample model. Distribution models carry more information, yet sample models are usually far easier to build. To model the sum of a dozen dice you can trivially roll twelve simulated dice and add; writing out the probability of every possible total is harder and more error-prone.² Either way, we say the model is used to simulate the environment and produce simulated experience.

Planning is any computation that takes a model as input and produces or improves a policy for the modeled environment.

The kind of planning studied in reinforcement learning is state-space planning: a search through the space of states for an optimal policy, computing value functions along the way. (The artificial-intelligence tradition of plan-space planning — searching a space of plans, as in partial-order planning — does not transfer well to stochastic sequential problems, so we set it aside.) Every state-space planning method shares one structure: it runs simulated experience through value updates to improve a policy.

Dynamic programming fits this exactly: it sweeps the states, and for each one generates the distribution of possible transitions from the model, computes a backed-up value, and updates the state's estimate. The claim of the chapter is that all state-space planning fits it too, individual methods differing only in the kind of updates they do, the order they do them in, and how long the backed-up information is retained.

Planning and learning are one machine

Viewed this way, planning and learning share their central operation: the estimation of value functions by backup operations. The only difference is the source of experience: planning uses simulated experience from a model, learning uses real experience from the environment. Because the backup operation is otherwise identical, a learning algorithm can be dropped straight into the update step of a planning method — feed it simulated transitions instead of real ones and it plans.

Concretely: take a learning algorithm, and instead of feeding it transitions the environment actually produced, feed it transitions generated by the model. The updates are identical, so the algorithm improves the policy just as it would from real experience — but now offline, as fast as the model can generate samples. The simplest example is one-step tabular Q-planning: take Q-learning and feed it samples from a model instead of the environment.

This converges to the model's optimal policy under the same conditions Q-learning converges to the environment's — provided every pair is selected infinitely often and $\alpha$ decreases appropriately. It is a planning method, yet its inner loop is a learning rule. A second point: planning here proceeds in small, incremental steps, so it can be interrupted or redirected at any moment with little waste. That is what lets planning intermix cheaply with acting.

Dyna: integrated planning, acting, and learning

When planning is done online, while the agent is acting, real experience does double duty. It can improve the model, making it a better replica of the environment — model-learning — and it can improve the value function and policy directly, by the learning methods of the previous lessons — direct reinforcement learning (direct RL). Model-learning feeds planning, which is the indirect route from experience to policy: experience improves the model, and the model improves the policy.

Indirect methods squeeze more policy improvement out of a fixed amount of experience; direct methods are simpler and immune to bias in the model's design. Sutton and Barto treat the two as sides of one mechanism rather than as competing approaches.

Dyna-Q is the simplest architecture that runs all of it — acting, model-learning, direct RL, and planning — continually and together. After each real transition $S_t,A_t\to R_{t+1},S_{t+1}$, three things happen. Direct RL applies one Q-learning update to the real transition. Model-learning records the transition in a table: assuming a deterministic environment, the model entry for $(S_t,A_t)$ simply stores $R_{t+1},S_{t+1}$, and a later query returns the last-observed outcome. Planning then runs $n$ rounds of Q-planning, each sampling a previously-seen state–action pair, querying the model, and applying the same Q-learning update to the simulated transition.

The center column is the ordinary agent–environment loop generating a trajectory of real experience. The left arrow is direct RL operating on that experience. The right side is the model-based machinery: real experience fits the model, search control selects which state–action pairs to imagine, and planning applies the learning rule to the resulting simulated experience. Typically, as in Dyna-Q, the same learning rule serves both real and simulated experience — it is the final common path, and learning and planning are integrated so deeply that they share almost all their machinery.

Steps (d), (e), (f) are direct RL, model-learning, and planning. Delete (e) and (f) and what remains is plain one-step Q-learning. The parameter $n$ is the number of planning updates per real step; $n=0$ is a non-planning agent. On a gridworld maze, an $n=0$ agent takes about 25 episodes to reach near-optimal play, an $n=5$ agent about five, and an $n=50$ agent only three. Planning propagates each real transition across many simulated ones, so a single episode's experience is reused instead of discarded — the whole point of building a model.³

One Dyna-Q step, traced

For example, take a corridor of four states $s_1\to s_2\to s_3\to G$, one action right from each, reward $0$ everywhere except $+1$ on reaching the goal $G$; use $\gamma =0.9$, $\alpha =1$ (deterministic, so a full step is safe), and $n=3$ planning updates per real step. Start with $Q=0$ and an empty model.

Suppose the agent has already wandered $s_1\to s_2\to s_3$ (learning nothing — all rewards $0$, all targets $0$) and now takes the real transition $s_3\stackrel{\text{right}}{\to }G$ with reward $1$. The direct RL update fires:

Model-learning records every observed transition: $Model(s_1,\text{right})=(0,s_2)$, and likewise for $s_2\to s_3$ and $s_3\to G$. Now planning runs three updates, each sampling a previously-seen pair at random from the model. Plain Q-learning without planning would stop here, having moved only $Q(s_3,\cdot )$; the goal's value would need three more real episodes to propagate back to $s_1$. Planning does it in one step if the random samples fall the right way. Say the three planning samples are $(s_3,\text{right})$, $(s_2,\text{right})$, $(s_1,\text{right})$ in that lucky order:

In a real Dyna-Q run the planning samples are drawn uniformly, so this ideal backward order is rare — most early planning updates back up zero onto zero and waste the step — the inefficiency that prioritized sweeping fixes below. But the trace shows the mechanism: each planning update is an ordinary Q-learning update on a remembered transition, and a few of them per real step let one informative real transition propagate across the whole corridor without waiting for the agent to walk it again.

When the model is wrong

In the maze example the model started empty and filled only with correct information. In general the model can be wrong — the environment is stochastic and only sampled a few times, or it changed and the new behavior has not been seen. A wrong model makes planning compute a wrong policy.

Two cases split by their severity. When the model is pessimistic or merely stale in a way that predicts worse transitions than reality offers, the planned policy encounters the discrepancy quickly: it tries the modeled transition, observes the real one, and corrects. But when the environment changes to become better — a shortcut opens — a model that says the shortcut does not exist will keep planning around it, and the agent may never take the exploratory action that would reveal it. The more it plans on the stale model, the less likely it is to look.

This is the exploration–exploitation conflict again, now over the model: exploring means trying actions that improve the model, exploiting means acting best given the current model. Dyna-Q+ resolves it with a simple heuristic. For each state–action pair it tracks $\tau$, the number of time steps since that pair was last tried in a real interaction. The longer a pair has gone untried, the more its modeled dynamics might have gone stale, so planning rewards revisiting it: if the modeled reward for a transition is $r$ and it has not been tried in $\tau$ steps, planning treats the reward as $r+\kappa \sqrt{\tau }$ for a small $\kappa$. This exploration bonus nudges the agent to keep testing long-untried transitions and to string together the exploratory sequences that uncover a shortcut. The bonus costs occasional wasted moves, but on changing environments the added exploration is worth it.⁴

This continues in Planning: Focusing Updates and Decision-Time Search, which makes Dyna's replay efficient with prioritized sweeping, weighs expected against sample updates, focuses effort with trajectory sampling and real-time DP, and then turns to planning done afresh at each decision — heuristic search, rollouts, and Monte Carlo Tree Search.