---
title: Planning and Learning
module: Tabular Solution Methods
moduleNumber: 2
lessonNumber: 9
order: 209
summary: >
  Planning and learning are the same operation run on two kinds of experience.
  A model turns states and actions into simulated transitions; planning backs up
  values over that simulated experience exactly as learning backs them up over
  real experience. We build the Dyna architecture that interleaves acting,
  model-learning, direct RL, and planning in one loop, trace a single Dyna-Q step
  by hand, and patch the architecture for when the model goes stale.
topics: [Tabular Methods]
sources:
  - book: Sutton & Barto
    ref: "Ch. 8 — Planning and Learning with Tabular Methods; §8.1 Models and Planning; §8.2 Dyna"
  - book: Sutton & Barto
    ref: "§8.3 When the Model Is Wrong"
---

[Dynamic programming](/reinforcement-learning/tabular-methods/dynamic-programming)
needs a model of the environment and never touches it;
[Monte Carlo](/reinforcement-learning/tabular-methods/monte-carlo-methods) and
[temporal-difference](/reinforcement-learning/tabular-methods/temporal-difference-learning)
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.[^sb-unify]

## 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.

> **Definition (Distribution vs. sample model).** A **distribution model**
> returns the full conditional $p(s',r \mid s,a)$ — every possible next state and
> reward with its probability. A **sample model** returns just _one_ next state
> and reward $(S', R)$, drawn according to those probabilities. A distribution
> model is strictly stronger: it can always produce samples, but not the reverse.

The dynamics $p(s',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.[^sb-models] 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.

$$
% caption: Planning in the broadest sense — any computation that turns a model of
% the environment into an improved policy.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=22mm, minimum height=10mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (model)  at (0,0)   {model};
  \node[box, draw=acc, text=acc, thick] (policy) at (5.2,0) {policy};
  \draw[->, acc, thick] (model) -- (policy) node[midway, above, font=\footnotesize] {planning};
\end{tikzpicture}
$$

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.

$$
% caption: The common structure of state-space planning: a model generates
% simulated experience, backup operations turn that experience into value
% updates, and the values define an improved policy. Learning shares this
% structure, differing only in that its experience is real, not simulated.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=20mm, minimum height=9mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (model)  at (0,0)     {model};
  \node[box] (exp)    at (3.4,0)   {simulated\\experience};
  \node[box] (val)    at (6.8,0)   {values};
  \node[box, draw=acc, text=acc, thick] (pol) at (10.0,0) {policy};
  \draw[->, thick] (model) -- (exp);
  \draw[->, thick] (exp) -- (val) node[midway, above, font=\footnotesize] {backups};
  \draw[->, acc, thick] (val) -- (pol);
\end{tikzpicture}
$$

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](/reinforcement-learning/tabular-methods/temporal-difference-learning)
and feed it samples from a model instead of the environment.

```algorithm
caption: $\textsc{Random-Sample-One-Step-Tabular-Q-Planning}$
loop // forever
  select a state $S \in \mathcal{S}$ and action $A \in \mathcal{A}(S)$ at random
  send $S, A$ to a sample model, obtain a sample reward $R$ and next state $S'$
  $Q(S,A) \gets Q(S,A) + \alpha\big[R + \gamma \max_a Q(S',a) - Q(S,A)\big]$
```

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.

$$
% caption: The two roles of real experience inside a planning agent. Along the
% left, direct reinforcement learning improves value and policy straight from
% experience. Along the right, model-learning fits a model from experience and
% planning uses it to improve value and policy — the indirect route.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=24mm, minimum height=10mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc, thick] (vp)  at (0,2.2)  {value / policy};
  \node[box] (mo)  at (-3.0,0)  {model};
  \node[box] (ex)  at (3.0,0)   {experience};
  % right column: experience -> model (model-learning), experience -> value (direct RL)
  \draw[->, thick] (ex) -- (mo) node[midway, below, font=\scriptsize] {model-learning};
  \draw[->, acc, thick] (ex) -- (vp) node[midway, right, font=\scriptsize] {direct RL};
  % left column: model -> value (planning)
  \draw[->, acc, thick] (mo) -- (vp) node[midway, left, font=\scriptsize] {planning};
\end{tikzpicture}
$$

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.

$$
% caption: The general Dyna architecture. Real experience (center) improves the
% policy and value functions directly (direct RL, left) and also feeds
% model-learning (right); search control picks starting pairs for the model,
% which generates simulated experience that a planning update backs up into the
% same value functions. The reinforcement-learning update is the final common
% path for both real and simulated experience.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=22mm, minimum height=9mm, align=center, font=\footnotesize},
  pill/.style={draw, fill=black!6, minimum width=18mm, minimum height=7mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, draw=acc, text=acc, thick] (pv)  at (0,3.0)   {policy / value};
  \node[pill] (real) at (0,1.2)   {real\\experience};
  \node[pill] (sim)  at (4.4,1.2) {simulated\\experience};
  \node[box] (model) at (4.4,-0.6) {model};
  \node[box] (env)   at (0,-1.6)  {environment};
  % environment <-> real experience (two-way trajectory)
  \draw[<->, acc, very thick] (env) -- (real);
  % direct RL update
  \draw[->, thick] (real) .. controls (-2.2,2.1) .. (pv.west)
    node[pos=0.45, left, font=\scriptsize, align=center] {direct RL\\update};
  % planning update
  \draw[->, acc, thick] (sim) .. controls (2.6,2.4) .. (pv.east)
    node[pos=0.5, right, font=\scriptsize] {planning update};
  % model-learning
  \draw[->, thick] (real) -- (model) node[midway, below, font=\scriptsize] {model-learning};
  % search control
  \draw[->, thick] (model) -- (sim) node[midway, right, font=\scriptsize] {search control};
\end{tikzpicture}
$$

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.

```algorithm
caption: $\textsc{Tabular-Dyna-Q}$
$Q(s,a), \mathit{Model}(s,a) \gets$ arbitrary, for all $s \in \mathcal{S}, a \in \mathcal{A}(s)$
loop // forever
  $S \gets$ current (nonterminal) state
  $A \gets \varepsilon\text{-greedy}(S, Q)$
  take action $A$, observe $R$, $S'$
  $Q(S,A) \gets Q(S,A) + \alpha\big[R + \gamma \max_a Q(S',a) - Q(S,A)\big]$ // direct RL
  $\mathit{Model}(S,A) \gets R, S'$ // model learning (deterministic environment)
  repeat $n$ times // planning
    $S \gets$ a random previously observed state
    $A \gets$ a random action previously taken in $S$
    $R, S' \gets \mathit{Model}(S,A)$
    $Q(S,A) \gets Q(S,A) + \alpha\big[R + \gamma \max_a Q(S',a) - Q(S,A)\big]$
```

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.[^sb-dyna]

### 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
\xrightarrow{\text{right}} G$ with reward $1$. The **direct RL** update fires:

$$
Q(s_3, \texttt{right}) \gets 0 + 1\cdot\big[\,1 + 0.9 \cdot 0 - 0\,\big] = 1.
$$

**Model-learning** records every observed transition: $\mathit{Model}(s_1,
\texttt{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, \texttt{right})$, $(s_2,
\texttt{right})$, $(s_1, \texttt{right})$ in that lucky order:

$$
\begin{aligned}
Q(s_3, \texttt{right}) &\gets 1 + [\,1 + 0.9(0) - 1\,] = 1 \quad\text{(already correct)},\\
Q(s_2, \texttt{right}) &\gets 0 + [\,0 + 0.9\,Q(s_3,\cdot) - 0\,] = 0.9,\\
Q(s_1, \texttt{right}) &\gets 0 + [\,0 + 0.9\,Q(s_2,\cdot) - 0\,] = 0.81.
\end{aligned}
$$

$$
% caption: One real transition into the goal, then three planning updates. Direct
% RL sets Q(s3) = 1 from the real step; planning replays the model in the order
% s3, s2, s1 and back-propagates value 0.9 to s2 and 0.81 to s1 within the same
% real step. Without planning only Q(s3) would have moved.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st] (s1) at (0,0)   {s1};
  \node[st] (s2) at (2.4,0) {s2};
  \node[st] (s3) at (4.8,0) {s3};
  \node[st, fill=black!8] (g) at (7.2,0) {G};
  \draw[->, black] (s1) -- (s2) node[midway, above, font=\scriptsize] {0};
  \draw[->, black] (s2) -- (s3) node[midway, above, font=\scriptsize] {0};
  \draw[->, red, thick] (s3) -- (g) node[midway, above, font=\scriptsize, text=red] {+1 real};
  % Q values after the step
  \node[acc, font=\scriptsize, anchor=north] at (0,-0.55)   {Q=0.81};
  \node[acc, font=\scriptsize, anchor=north] at (2.4,-0.55) {Q=0.9};
  \node[red, font=\scriptsize, anchor=north] at (4.8,-0.55) {Q=1};
  % planning replay order
  \node[acc, anchor=west, font=\scriptsize] at (-0.3,-1.4) {planning replay order s3, s2, s1: value f\/lows backward};
\end{tikzpicture}
$$

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.

$$
% caption: Shortcut-maze intuition. A path exists (left) and the agent plans over
% a correct model. When a shorter path opens (right), a plain Dyna-Q model still
% says only the long way exists, so planning keeps routing around the new
% opening; without an exploration incentive the agent may never discover it.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ---- left maze: long path only ----
  \begin{scope}
    \draw[black] (0,0) rectangle (3,2);
    % barrier wall with a gap on the left
    \fill[black] (0.6,0.9) rectangle (3,1.1);
    \node[font=\scriptsize, anchor=south] at (1.5,2.02) {G};
    \node[font=\scriptsize, anchor=north] at (1.5,-0.02) {S};
    \draw[acc, thick, ->] (1.5,0.25) -- (0.35,0.25) -- (0.35,1.75) -- (1.5,1.75);
    \node[acc, anchor=west, font=\scriptsize] at (0.05,0.55) {long};
  \end{scope}
  % ---- right maze: shortcut opens on the right ----
  \begin{scope}[xshift=4.4cm]
    \draw[black] (0,0) rectangle (3,2);
    \fill[black] (0.6,0.9) rectangle (2.6,1.1);
    \node[font=\scriptsize, anchor=south] at (1.5,2.02) {G};
    \node[font=\scriptsize, anchor=north] at (1.5,-0.02) {S};
    % stale model still plans the long way
    \draw[acc, thick, ->] (1.5,0.25) -- (0.35,0.25) -- (0.35,1.75) -- (1.5,1.75);
    % real shortcut on the right, undiscovered (dashed red)
    \draw[red, dashed, thick, ->] (1.5,0.25) -- (2.8,0.25) -- (2.8,1.75) -- (1.5,1.75);
    \node[red, anchor=west, font=\scriptsize] at (2.85,1.0) {shortcut};
  \end{scope}
\end{tikzpicture}
$$

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.[^sb-wrong]

This continues in [Planning: Focusing Updates and Decision-Time Search](/reinforcement-learning/tabular-methods/planning-focusing-and-decision-time), 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.

[^sb-unify]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §8.1 — Models and Planning: distribution vs. sample models, planning as model-to-policy computation, and the common structure (model → simulated experience → backups → values → policy) shared by state-space planning and learning.
[^sb-models]: **Sutton & Barto**, §8.1 — the dozen-dice example showing sample models are often far easier to build than distribution models, and the sense in which a model is used to _simulate_ the environment.
[^sb-dyna]: **Sutton & Barto**, §8.2 — Dyna: the general Dyna architecture (Figure 8.1), Tabular Dyna-Q (direct RL, model-learning, planning as steps d, e, f), and the maze experiment (Figures 8.2–8.3) showing planning steps $n$ sharply reduce episodes to optimality.
[^sb-wrong]: **Sutton & Barto**, §8.3 — When the Model Is Wrong: the blocking- and shortcut-maze examples, and Dyna-Q+ with the $r + \kappa\sqrt{\tau}$ exploration bonus (Figures 8.4–8.5).