---
title: "Monte Carlo Methods: Off-Policy Learning"
module: Tabular Solution Methods
moduleNumber: 2
lessonNumber: 4
order: 204
summary: >
  On-policy Monte Carlo can only reach the best exploring policy, not the true
  optimum. Off-policy methods remove that ceiling by learning about a greedy target
  policy from data generated by a soft behavior policy, corrected with importance
  sampling. We derive the importance-sampling ratio, weigh ordinary against weighted
  estimators on real numbers, give the incremental off-policy algorithm, sharpen it
  with discounting-aware sampling, and close by placing Monte Carlo on the
  model/bootstrap map beside DP and temporal-difference learning.
topics: [Tabular Methods]
sources:
  - book: Sutton & Barto
    ref: "§5.5 Off-policy Prediction via Importance Sampling; §5.6 Incremental Implementation"
  - book: Sutton & Barto
    ref: "§5.8 Discounting-aware Importance Sampling; §5.9 Per-decision Importance Sampling; §5.10 Summary"
---

This builds on [Monte Carlo Methods](/reinforcement-learning/tabular-methods/monte-carlo-methods),
which developed prediction by averaging returns and on-policy control with
$\varepsilon$-soft policies. That on-policy approach pays a permanent price: it can
only find the best policy _among the exploring ones_, never the unconstrained
optimum. Off-policy learning removes that ceiling, and this lesson builds the
machinery.

## Off-policy prediction and importance sampling

Every learning-control method faces one dilemma: it wants the value of _optimal_
behavior, but it must behave _non-optimally_ to keep exploring. On-policy methods
compromise — they learn a near-optimal policy that still explores. Off-policy
methods split the difference into two policies outright.[^sb-offpolicy]

> **Definition (Target and behavior policies).** The _target policy_ $\pi$ is the
> one being learned about — often the deterministic greedy policy we ultimately
> want. The _behavior policy_ $b$ is the one generating the episodes — kept soft and
> exploratory. Learning about $\pi$ from data generated by $b \neq \pi$ is
> _off-policy_ learning.

Off-policy methods are more general (on-policy is the special case $\pi = b$) and
more powerful — they can learn from a human demonstrator or an old controller's
logs — but they carry more variance and converge more slowly, since the data comes
from the "wrong" distribution. For that machinery to work at all we need
**coverage**: every action $\pi$ might take must also be taken, at least
occasionally, by $b$. Formally $\pi(a\mid s) > 0$ implies $b(a\mid s) > 0$. Where
$\pi$ is deterministic, $b$ must be stochastic in exactly those states.

### The importance-sampling ratio

The intuition first. We watched the agent behave under $b$, but we want the value
under $\pi$. Some of the trajectories we saw are ones $\pi$ would have produced often;
others are ones $\pi$ would rarely or never produce. So we weight each observed
return by how much more (or less) likely its trajectory was under $\pi$ than under
$b$. Trajectories $\pi$ favors count for more; trajectories $\pi$ would never take
count for nothing.

The returns we collect come from $b$, so they have the wrong expectation:
$\mathbb{E}[G_t \mid S_t = s] = v_b(s)$, not $v_\pi(s)$. **Importance sampling** is
the general fix for estimating an expectation under one distribution from samples of
another: reweight each sample by how much more likely it was under the target than
under the behavior. For a whole trajectory the reweighting is the
**importance-sampling ratio**. Given a start at $S_t$, the probability of the
subsequent action–state sequence under a policy $\pi$ is
$\prod_{k=t}^{T-1} \pi(A_k \mid S_k)\, p(S_{k+1} \mid S_k, A_k)$, so the ratio of
that probability under $\pi$ to under $b$ is

$$
\rho_{t:T-1} \;\doteq\;
\frac{\prod_{k=t}^{T-1} \pi(A_k \mid S_k)\, p(S_{k+1}\mid S_k, A_k)}
     {\prod_{k=t}^{T-1} b(A_k \mid S_k)\, p(S_{k+1}\mid S_k, A_k)}
\;=\;
\prod_{k=t}^{T-1} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}.
$$

The transition probabilities $p(S_{k+1}\mid S_k, A_k)$ — the unknown part of the
world — appear identically in numerator and denominator and _cancel_. The ratio
depends only on the two policies and the action sequence, **not on the MDP's
dynamics**. That cancellation is what makes off-policy Monte Carlo model-free.
Multiplying a behavior-policy return by this ratio corrects its expectation:

$$
\mathbb{E}\!\left[\, \rho_{t:T-1}\, G_t \mid S_t = s \,\right] = v_\pi(s).
$$

$$
% caption: The importance-sampling ratio $\rho_{t:T-1}$ is a running product of
% per-step likelihood ratios $\pi(A_k\mid S_k)/b(A_k\mid S_k)$ along the sampled
% trajectory. The environment's transition probabilities cancel between target and
% behavior, so only the policy ratios survive.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=6.5mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st] (s0) at (0,0)   {S\_t};
  \node[st] (s1) at (2.6,0) {S\_t+1};
  \node[st] (s2) at (5.2,0) {S\_t+2};
  \node (sd) at (7.2,0) {. . .};
  \node[st] (sT) at (9.0,0) {S\_T};
  \draw[acc, thick, ->] (s0) -- node[above, font=\scriptsize] {A\_t} (s1);
  \draw[acc, thick, ->] (s1) -- node[above, font=\scriptsize] {A\_t+1} (s2);
  \draw[acc, thick, ->] (s2) -- (sd);
  \draw[acc, thick, ->] (sd) -- (sT);
  \node[anchor=north, font=\scriptsize] at (1.3,-0.55) {ratio pi/b};
  \node[anchor=north, font=\scriptsize] at (3.9,-0.55) {ratio pi/b};
  \node[anchor=north, align=center, font=\scriptsize] at (6.6,-0.9)
    {multiply the per-step ratios:\\rho = product along the path};
\end{tikzpicture}
$$

### Ordinary versus weighted importance sampling

To estimate $v_\pi(s)$ we now scale the returns and average. Number time steps so
they increase across episode boundaries; let $\mathcal{T}(s)$ be the set of steps at
which $s$ is visited (first visits only, for a first-visit method), and let $T(t)$
be the first termination after $t$. Two averages are possible.[^sb-offpolicy]
**Ordinary importance sampling** divides by the count:

$$
V(s) \;\doteq\; \frac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1}\, G_t}{|\mathcal{T}(s)|}.
$$

**Weighted importance sampling** divides by the sum of the weights (or is zero if
that sum is zero):

$$
V(s) \;\doteq\; \frac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1}\, G_t}
                     {\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t)-1}}.
$$

The two differ in bias and variance, and the difference is stark. Consider observing
a single return from $s$. In the weighted estimate the lone ratio cancels top and
bottom, leaving exactly the observed return — expectation $v_b(s)$, so it is
_biased_. The ordinary estimate for that single return is $\rho \cdot G_t$; if the
ratio is, say, ten, the estimate is ten times the observed return — _unbiased_ in
expectation but wildly off from one sample.[^sb-offpolicy]

> **Definition (Ordinary vs. weighted importance sampling).** _Ordinary_ importance
> sampling averages the ratio-scaled returns (divide by the count): unbiased, but
> its variance is in general **unbounded**, since the ratios can be arbitrarily
> large. _Weighted_ importance sampling normalizes by the total weight: biased (the
> bias vanishes asymptotically), but with **far lower**, bounded variance — the
> largest weight any single return can carry is one.

That variance gap decides practice. Ordinary importance sampling can have infinite
variance whenever the scaled returns do — easy to trigger when trajectories contain
loops — so its estimates may fail to converge in any usable number of episodes even
though they are unbiased. Weighted importance sampling has dramatically lower
variance and is strongly preferred; on the off-policy blackjack estimation it
reaches low error after roughly a thousand episodes where ordinary importance
sampling is still far off.[^sb-offpolicy]

### The two estimators on real numbers

Put numbers to the difference. Suppose the target $\pi$ is deterministic (it always
takes the action it prefers) and the behavior $b$ is $\varepsilon$-greedy with
$\varepsilon = 0.2$ over two actions, so $b$ takes $\pi$'s action with probability
$0.9$ and the other with probability $0.1$. A three-step trajectory in which the
behavior _happened_ to follow $\pi$ at every step earns the ratio

$$
\rho \;=\; \frac{\pi}{b}\cdot\frac{\pi}{b}\cdot\frac{\pi}{b}
     \;=\; \frac{1}{0.9}\cdot\frac{1}{0.9}\cdot\frac{1}{0.9}
     \;=\; \frac{1}{0.729} \;\approx\; 1.372,
$$

because each on-target step was slightly _more_ likely under $\pi$ (probability $1$)
than under $b$ (probability $0.9$). Say this trajectory returned $G = 4$. If instead
even one step had taken $\pi$'s _non-preferred_ action — an action $\pi$ gives
probability $0$ — the ratio would be exactly $0$: that trajectory is not something
$\pi$ could have produced, so it is discarded.

Now collect three trajectories from $s$ with weights and returns
$(\rho_1, G_1) = (1.372,\, 4)$, $(\rho_2, G_2) = (0,\, -1)$, and
$(\rho_3, G_3) = (1.372,\, 6)$. **Ordinary** importance sampling divides the
weighted sum by the _count_:

$$
V_{\text{ord}}(s) = \frac{1.372\cdot 4 + 0\cdot(-1) + 1.372\cdot 6}{3}
                  = \frac{13.72}{3} \approx 4.57.
$$

**Weighted** importance sampling divides by the _sum of the weights_:

$$
V_{\text{wt}}(s) = \frac{1.372\cdot 4 + 0\cdot(-1) + 1.372\cdot 6}{1.372 + 0 + 1.372}
                 = \frac{13.72}{2.744} = 5.0.
$$

The weighted estimate is the plain average of the two surviving returns,
$(4 + 6)/2 = 5$, unaffected by the magnitude of the ratio — the $1.372$ cancels top
and bottom. The ordinary estimate, $4.57$, is dragged down by dividing by $3$ even
though the discarded trajectory contributed nothing to the numerator; had a rare
trajectory carried a ratio of $50$ instead of $1.372$, the ordinary estimate would
have leapt while the weighted one stayed bounded. This is the variance gap in
miniature: the weighted estimator caps any single return's influence at $1$, the
ordinary one does not.

$$
% caption: Ordinary versus weighted importance sampling on three trajectories with
% weights $(1.372, 0, 1.372)$ and returns $(4, -1, 6)$. Both share the numerator
% $13.72$; ordinary divides by the count $3$ (giving $4.57$), weighted divides by
% the weight sum $2.744$ (giving $5.0$, the plain average of the two surviving
% returns). The zero-weight trajectory is discarded by both.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  trow/.style={draw, minimum width=13mm, minimum height=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % three trajectory rows
  \node[trow] (w1) at (0,1.5) {w=1.372}; \node[trow, anchor=west] at (1.3,1.5) {G=4};
  \node[trow, draw=black, text=black] (w2) at (0,0.6) {w=0}; \node[trow, anchor=west, draw=black, text=black] at (1.3,0.6) {G=-1};
  \node[trow] (w3) at (0,-0.3) {w=1.372}; \node[trow, anchor=west] at (1.3,-0.3) {G=6};
  \node[anchor=west, font=\scriptsize, text=black] at (2.9,0.6) {(discarded)};
  % ordinary
  \node[align=center, font=\scriptsize] at (6.2,1.4)
    {ordinary: 13.72 / 3};
  \node[font=\small, text=red] at (6.2,0.85) {= 4.57};
  % weighted
  \node[align=center, font=\scriptsize] at (6.2,0.0)
    {weighted: 13.72 / 2.744};
  \node[font=\small, text=acc] at (6.2,-0.55) {= 5.0};
\end{tikzpicture}
$$

$$
% caption: Sketch of off-policy learning curves (mean squared error versus episodes,
% log scale). Ordinary importance sampling starts with large, erratic error from
% extreme ratios; weighted importance sampling is lower and steadier throughout,
% though biased early. Both approach zero as episodes grow.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (7.4,0) node[anchor=north east, font=\scriptsize] {episodes (log scale)};
  \draw[->, black] (0,0) -- (0,3.7) node[anchor=south east, font=\scriptsize, align=center] {mean\\squared error};
  % ordinary: high, erratic, decays slowly
  \draw[red, thick]
    (0.2,3.3) .. controls (0.9,1.4) and (1.2,3.0) .. (1.7,2.2)
    .. controls (2.4,1.3) and (3.2,1.9) .. (4.0,1.0)
    .. controls (5.0,0.55) and (6.0,0.5) .. (7.0,0.35);
  \node[red, anchor=west, font=\scriptsize] at (4.1,1.45) {ordinary};
  % weighted: low, smooth
  \draw[acc, thick]
    (0.2,1.5) .. controls (0.7,0.95) and (1.1,1.05) .. (1.7,0.8)
    .. controls (2.6,0.6) and (3.6,0.45) .. (7.0,0.28);
  \node[acc, anchor=west, font=\scriptsize] at (3.0,0.72) {weighted};
\end{tikzpicture}
$$

## Incremental implementation

Monte Carlo need not store every return. Just as
[bandit](/reinforcement-learning/foundations/multi-armed-bandits) value estimates
were kept as a running mean, MC estimates update episode-by-episode. For ordinary
importance sampling (and for on-policy averaging) the update is the familiar
sample-mean recursion applied to the scaled returns. Weighted importance sampling
needs a slightly different rule, because it is a _weighted_ average.[^sb-incremental]

Suppose returns $G_1, G_2, \ldots$ all start in the same state, each with a weight
$W_i$ (here $W_i = \rho_{t_i:T(t_i)-1}$). The weighted average of the first $n-1$ is

$$
V_n \;\doteq\; \frac{\sum_{k=1}^{n-1} W_k G_k}{\sum_{k=1}^{n-1} W_k}, \qquad n \ge 2.
$$

Maintaining a running cumulative weight $C_n = \sum_{k=1}^{n} W_k$, a new return
$G_n$ updates the estimate in constant time and memory:

$$
V_{n+1} \;\doteq\; V_n + \frac{W_n}{C_n}\big[\, G_n - V_n \,\big],
\qquad
C_{n+1} \;\doteq\; C_n + W_{n+1},
$$

with $C_0 \doteq 0$. This is the same error-correction shape as every other
incremental update in the course — old estimate plus a step-size times a (return
minus estimate) error — here with step size $W_n/C_n$. The off-policy prediction
algorithm walks each episode backward, accumulating $G$, the cumulative weight $C$,
and the running product $W = \prod \pi(A_k\mid S_k)/b(A_k\mid S_k)$ together.

```algorithm
caption: $\textsc{Off-Policy-MC-Prediction}$ — weighted IS, estimate $Q \approx q_\pi$
input: a target policy $\pi$
$Q(s,a) \in \mathbb{R}$ arbitrarily, $C(s,a) \gets 0$, for all $s,a$
for each episode do
  $b \gets$ any policy with coverage of $\pi$
  generate an episode following $b$: $S_0, A_0, R_1, \ldots, S_{T-1}, A_{T-1}, R_T$
  $G \gets 0$
  $W \gets 1$
  for $t = T-1, T-2, \ldots, 0$ do
    $G \gets \gamma G + R_{t+1}$
    $C(S_t, A_t) \gets C(S_t, A_t) + W$
    $Q(S_t, A_t) \gets Q(S_t, A_t) + \frac{W}{C(S_t, A_t)}\,[\,G - Q(S_t, A_t)\,]$
    $W \gets W \cdot \frac{\pi(A_t \mid S_t)}{b(A_t \mid S_t)}$
    if $W = 0$ then
      break // exit to next episode
```

Choosing $b = \pi$ makes $W \equiv 1$ and collapses this to on-policy evaluation, so
one routine covers both cases. Swap the fixed target for the greedy policy in $Q$
and add a policy-improvement step and this becomes off-policy MC _control_: it learns
the deterministic optimal target while a soft behavior policy keeps exploring. Its
known weakness is that it learns only from the _tail_ of each episode — from the last
point where the behavior policy happened to agree with greedy onward — so learning
can be slow when nongreedy actions are common.[^sb-offpolicy]

## Discounting-aware importance sampling

Every off-policy estimator so far has treated a return as an indivisible whole:
form one ratio $\rho_{t:T-1}$ for the entire trajectory and scale the entire
return $G_t$ by it. That ignores the return's internal structure as a sum of
discounted rewards, and the oversight can inflate the variance enormously.[^sb-discaware]

For example, suppose episodes last $100$ steps and the
discount is $\gamma = 0$. Then the return from time $0$ is just the first reward,
$G_0 = R_1$, because every later reward is multiplied by a power of zero. Its
importance-sampling ratio, though, is the full product of $100$ per-step factors,

$$
\rho_{0:99} \;=\;
\frac{\pi(A_0 \mid S_0)}{b(A_0 \mid S_0)}\,
\frac{\pi(A_1 \mid S_1)}{b(A_1 \mid S_1)}
\cdots
\frac{\pi(A_{99} \mid S_{99})}{b(A_{99} \mid S_{99})}.
$$

Ordinary importance sampling scales $R_1$ by that whole product. But only the
first factor $\pi(A_0\mid S_0)/b(A_0\mid S_0)$ is relevant: after the first reward
the return is already fully determined. The other $99$ factors are independent of
the return, each has expected value $1$, and so they leave the _expected_ update
unchanged — while contributing wildly to its _variance_. In some cases they can
make the variance infinite. The remedy is to reweight only the part of the
trajectory that actually influenced each piece of the return.

$$
% caption: Under $\gamma = 0$ the length-100 return is just $R_1$, yet ordinary
% importance sampling multiplies it by all 100 policy ratios. Only the first
% (solid) affected the return; the other 99 (faded) are noise of mean 1 that only
% inflate variance.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st] (s0) at (0,0)   {S0};
  \node[st] (s1) at (2.2,0) {S1};
  \node[st] (s2) at (4.4,0) {S2};
  \node (sd) at (6.2,0) {. . .};
  \node[st] (s3) at (8.0,0) {S99};
  \draw[acc, very thick, ->] (s0) -- node[above, font=\scriptsize, text=acc] {ratio 0} (s1);
  \draw[red!45, thick, ->] (s1) -- node[above, font=\scriptsize, text=black] {ratio 1} (s2);
  \draw[red!45, thick, ->] (s2) -- (sd);
  \draw[red!45, thick, ->] (sd) -- node[above, font=\scriptsize, text=black] {ratio 99} (s3);
  \node[acc, anchor=north, font=\scriptsize] at (1.1,-0.5) {kept: determines R1};
  \node[anchor=north, align=center, font=\scriptsize, text=black] at (5.6,-0.5)
    {mean-1 noise:\\adds only variance};
\end{tikzpicture}
$$

### Discounting as partial termination

The clean way to isolate the relevant ratios is to reinterpret discounting.
Instead of viewing $\gamma$ as a per-step attenuation of reward, view it as a
_probability of continuing_ — equivalently, $1 - \gamma$ as a degree of
termination at each step. Under that reading the return $G_t$ is a mixture of
truncated returns. With degree $1 - \gamma$ the episode "partly terminates" after
one step, yielding just $R_{t+1}$; with degree $(1-\gamma)\gamma$ it partly
terminates after two steps, yielding $R_{t+1} + R_{t+2}$; and so on, the factor
$\gamma^{k}$ in front of the $(k{+}1)$-step piece recording that termination did
_not_ occur on any of the first $k$ steps. The truncated pieces are the **flat
partial returns**.

> **Definition (Flat partial return).** For $0 \le t < h \le T$, the flat partial
> return is $\bar G_{t:h} \doteq R_{t+1} + R_{t+2} + \cdots + R_h$. "Flat" marks
> the absence of discounting inside the sum; "partial" marks that it stops at the
> **horizon** $h$ rather than running to termination $T$. The full discounted
> return decomposes into a $\gamma$-weighted mixture of these pieces.

Intuitively, the discount $\gamma$ acts as a coin flipped each step
that decides whether the episode keeps going. Then the true return is an average
over all the places the episode _might_ have stopped — stop after one reward, after
two, after three, and so on — each weighted by the chance of stopping exactly there.
Writing the decomposition out, the ordinary discounted return is exactly a
weighted sum of flat partial returns:

$$
\begin{aligned}
G_t \;&=\; R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-t-1} R_T \\[2pt]
&=\; (1-\gamma)\,\bar G_{t:t+1} \\
&\quad+\; (1-\gamma)\gamma\,\bar G_{t:t+2} \\
&\quad+\; (1-\gamma)\gamma^2\,\bar G_{t:t+3} \\
&\quad\;\; \vdots \\
&\quad+\; (1-\gamma)\gamma^{\,T-t-2}\,\bar G_{t:T-1} \\
&\quad+\; \gamma^{\,T-t-1}\,\bar G_{t:T} \\[2pt]
&=\; (1-\gamma) \sum_{h=t+1}^{T-1} \gamma^{\,h-t-1}\,\bar G_{t:h}
     \;+\; \gamma^{\,T-t-1}\,\bar G_{t:T}.
\end{aligned}
$$

The last term collects the probability mass that survives all the way to
termination — the trajectory never terminated early, an event of degree
$\gamma^{T-t-1}$ — so it carries the full undiscounted tail $\bar G_{t:T}$ with no
$(1-\gamma)$ factor. A quick check: at $\gamma = 1$ every mixture weight
$(1-\gamma)\gamma^{h-t-1}$ vanishes and only $\bar G_{t:T} = G_t$ survives,
recovering the undiscounted return.

$$
% caption: The discounted return as a mixture of flat partial returns. Each
% horizon $h$ contributes the undiscounted sum $\bar G_{t:h}$ (a bar of rewards)
% weighted by the probability the episode "terminates" exactly at $h$, namely
% $(1-\gamma)\gamma^{h-t-1}$; the final bar to $T$ carries the surviving mass
% $\gamma^{T-t-1}$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % reward cells reused per row: R1 R2 R3 R4
  % row for horizon t+1
  \node[anchor=east, font=\scriptsize] at (-0.2,3.0) {weight (1-g)};
  \draw[acc, fill=acc!12] (0,2.75) rectangle (1.0,3.25);
  \node[font=\scriptsize] at (0.5,3.0) {R1};
  \node[anchor=west, font=\scriptsize] at (4.6,3.0) {= partial return to t+1};
  % row for horizon t+2
  \node[anchor=east, font=\scriptsize] at (-0.2,2.2) {(1-g) g};
  \draw[acc, fill=acc!12] (0,1.95) rectangle (1.0,2.45);
  \node[font=\scriptsize] at (0.5,2.2) {R1};
  \draw[acc, fill=acc!12] (1.0,1.95) rectangle (2.0,2.45);
  \node[font=\scriptsize] at (1.5,2.2) {R2};
  \node[anchor=west, font=\scriptsize] at (4.6,2.2) {to t+2};
  % row for horizon t+3
  \node[anchor=east, font=\scriptsize] at (-0.2,1.4) {(1-g) g g};
  \foreach \i/\lab in {0/R1,1/R2,2/R3} {
    \draw[acc, fill=acc!12] (\i,1.15) rectangle (\i+1.0,1.65);
    \node[font=\scriptsize] at (\i+0.5,1.4) {\lab};
  }
  \node[anchor=west, font=\scriptsize] at (4.6,1.4) {to t+3};
  % dots
  \node[font=\scriptsize] at (2.2,0.75) {. . .};
  % final full-tail row to T
  \node[anchor=east, font=\scriptsize, text=red] at (-0.2,0.25) {g to the T};
  \foreach \i/\lab in {0/R1,1/R2,2/R3,3/R4} {
    \draw[red, fill=red!10] (\i,0.0) rectangle (\i+1.0,0.5);
    \node[font=\scriptsize] at (\i+0.5,0.25) {\lab};
  }
  \node[anchor=west, font=\scriptsize, text=red] at (4.6,0.25) {full tail to T};
\end{tikzpicture}
$$

### The discounting-aware estimators

The payoff of the decomposition is that a flat partial return $\bar G_{t:h}$ only
involves rewards up through horizon $h$, so correcting it requires only the
_truncated_ ratio $\rho_{t:h-1}$ — the product of policy ratios up to $h$, and no
further. Applying an appropriately truncated ratio to each piece and re-summing
gives the **ordinary discounting-aware importance-sampling** estimator, the
horizon-aware analogue of the ordinary estimator from earlier:

$$
V(s) \;\doteq\; \frac{\displaystyle\sum_{t \in \mathcal{T}(s)}
  \Bigl[(1-\gamma)\sum_{h=t+1}^{T(t)-1} \gamma^{\,h-t-1}\, \rho_{t:h-1}\,\bar G_{t:h}
  \;+\; \gamma^{\,T(t)-t-1}\, \rho_{t:T(t)-1}\,\bar G_{t:T(t)}\Bigr]}
  {|\mathcal{T}(s)|},
$$

and the corresponding **weighted** estimator normalizes by the truncated ratios
themselves in place of the count:

$$
V(s) \;\doteq\; \frac{\displaystyle\sum_{t \in \mathcal{T}(s)}
  \Bigl[(1-\gamma)\sum_{h=t+1}^{T(t)-1} \gamma^{\,h-t-1}\, \rho_{t:h-1}\,\bar G_{t:h}
  \;+\; \gamma^{\,T(t)-t-1}\, \rho_{t:T(t)-1}\,\bar G_{t:T(t)}\Bigr]}
  {\displaystyle\sum_{t \in \mathcal{T}(s)}
  \Bigl[(1-\gamma)\sum_{h=t+1}^{T(t)-1} \gamma^{\,h-t-1}\, \rho_{t:h-1}
  \;+\; \gamma^{\,T(t)-t-1}\, \rho_{t:T(t)-1}\Bigr]}.
$$

Each flat partial return is now multiplied only by the ratio of the segment that
produced it, so the mean-1 tail factors that plagued the whole-return estimators
never enter. In the $\gamma = 0$ example the first piece $R_1$ is scaled by the
single factor $\rho_{0:0}$ and nothing else — exactly what the earlier argument
said we should want — instead of by the full length-$100$ product.

> **Definition (Discounting-aware importance sampling).** Off-policy Monte Carlo
> estimators that scale each flat partial return $\bar G_{t:h}$ by a ratio
> $\rho_{t:h-1}$ truncated to its horizon $h$, rather than scaling the whole return
> by the full trajectory ratio. They exploit the return's structure as a
> $\gamma$-weighted mixture of partial returns to strip out later, irrelevant
> ratios, cutting variance without changing the expectation. They reduce exactly to
> the [ordinary and weighted](/reinforcement-learning/tabular-methods/monte-carlo-off-policy)
> whole-return estimators when $\gamma = 1$ (all mixture weight sits on the full tail).

The gain is real only when $\gamma < 1$: the smaller the discount, the more the
return is dominated by its early rewards, the more late ratios there are to
discard, and the larger the variance reduction. At $\gamma = 1$ the mixture
collapses onto the single full-tail term and the discounting-aware estimators
_are_ the ordinary and weighted estimators from
[off-policy prediction](/reinforcement-learning/tabular-methods/monte-carlo-off-policy).
A separate idea, **per-decision importance sampling**, removes still more variance
by reweighting each reward $R_{t+k}$ by only $\rho_{t:t+k-1}$, and works even at
$\gamma = 1$; the two ideas are complementary, both mining the return's additive
structure for ratios that are safe to drop.

## Monte Carlo in modern reinforcement learning

The two ideas at the core of this lesson — average full sampled returns, and correct
for the wrong distribution with importance sampling — both grew into machinery that
carries much of modern reinforcement learning. Following each forward shows how
little the underlying logic changed.

**Monte Carlo tree search.** The clean idea of estimating a value by averaging
sampled returns becomes a decision-time planner when the samples are drawn from a
_learned or simulated model_ and used to build a search tree. **Monte Carlo tree
search** (MCTS), introduced by Coulom (2006) and given its exploration rule by Kocsis
and Szepesvári (2006, the UCT algorithm), runs many simulated games from the current
state, averages their returns exactly as first-visit MC does, and grows the tree
toward the branches those averages rate highly. Sutton and Barto treat it in §8.11 as
a rollout method built on Monte Carlo control. Its consequences run past that treatment:
**AlphaGo** (Silver et al., 2016, _Nature_) combined MCTS with deep value and policy
networks to beat a professional Go player; **AlphaZero** (Silver et al., 2018,
_Science_) learned Go, chess, and shogi from self-play with the same search; and
**MuZero** (Schrittwieser et al., 2020, _Nature_) ran MCTS inside a _learned_ model
of the environment, so it needed no rules at all. Each is the Monte Carlo average of
returns, wrapped in a search and scaled by a neural network.

$$
% caption: One iteration of Monte Carlo tree search, the model-based descendant of
% Monte Carlo control. From the root state a tree policy selects a leaf; the tree is
% expanded; a full episode is simulated by a rollout policy to termination; and the
% return is backed up along the traversed edges, updating their averaged action
% values. Repeated many times, the averages steer the next selection.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  phase/.style={draw, minimum width=22mm, minimum height=10mm, align=center},
  nn/.style={circle, draw, fill=white, minimum size=3.6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\lab in {0/Selection, 1/Expansion, 2/Simulation, 3/Backup} {
    \node[phase] (p\i) at (\i*3.0,0) {\lab};
  }
  \draw[->, acc, thick] (p0) -- (p1);
  \draw[->, acc, thick] (p1) -- (p2);
  \draw[->, acc, thick] (p2) -- (p3);
  \draw[->, acc, thick] (p3) to[bend left=32] (p0);
  \node[font=\scriptsize, text=acc] at (4.5,-2.15) {repeat while time remains};
  \node[anchor=north, font=\scriptsize, text=black] at (0,-0.75) {tree policy};
  \node[anchor=north, font=\scriptsize, text=black] at (6.0,-0.75) {rollout policy};
  \node[anchor=north, font=\scriptsize, text=black] at (9.0,-0.75) {average the return};
\end{tikzpicture}
$$

**Off-policy corrections in deep RL.** Every deep reinforcement learner that reuses
stored experience is doing off-policy learning: the data in a replay buffer was
generated by an _older_ version of the policy than the one being trained, so the
behavior and target policies differ, and the importance-sampling ratios of this
lesson reappear. Two problems the tabular case previewed became central. First, the
unbounded variance of ordinary importance sampling forces distributed learners to
_clip_ or _truncate_ the ratios: **Retrace($\lambda$)** (Munos et al., 2016,
_NeurIPS_) clips per-step ratios at $1$ to get a safe, low-variance off-policy return,
and the **IMPALA** actor-learner architecture (Espeholt et al., 2018, _ICML_) uses
truncated ratios ("V-trace") to correct for the lag between the actors generating
data and the learner consuming it. Second, whether to bootstrap or use full returns —
the very axis that separates Monte Carlo from temporal-difference learning — reappears
as a tunable parameter: **generalized advantage estimation** (Schulman et al., 2016, _ICLR_)
interpolates between a high-variance Monte Carlo return and a low-variance one-step
estimate with a single parameter $\lambda$, and **R2D2** (Kapturowski et al., 2019,
_ICLR_) runs recurrent Q-learning over long stored sequences, managing exactly the
correlation-and-staleness issues that make replay off-policy. The names are new; the
tradeoffs are the ordinary-versus-weighted and Monte-Carlo-versus-bootstrap tensions
of this lesson, at scale.[^beyond]

## Where Monte Carlo sits

Monte Carlo departs from
[dynamic programming](/reinforcement-learning/tabular-methods/dynamic-programming)
on two independent axes. It operates on **sample experience**, so it needs no model
— a sample simulator suffices, or real interaction. And it does **not bootstrap** —
each estimate rests on a full realized return, never on other states' estimates,
which also makes it less sensitive to violations of the Markov property. Those two
differences are separable, and separating them opens the next method.[^sb-summary]

$$
% caption: Two independent axes — needing a model, and bootstrapping — place the
% tabular methods. DP needs a model and bootstraps; Monte Carlo needs neither.
% Temporal-difference learning takes the remaining corner: no model, yet it
% bootstraps, updating from one sampled step plus the current estimate of the next
% state.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=34mm, minimum height=15mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axis labels
  \node[font=\small] at (2.6,3.05) {bootstraps};
  \node[font=\small] at (7.0,3.05) {no bootstrap};
  \node[rotate=90, font=\small] at (-1.15,1.55) {needs model};
  \node[rotate=90, font=\small] at (-1.15,-1.35) {model-free};
  % top row (needs model)
  \node[cell] (dp)  at (2.6,1.55)  {dynamic\\programming};
  \node[cell, dashed] (na) at (7.0,1.55) {(sweep returns\\with a model)};
  % bottom row (model-free)
  \node[cell, draw=red, text=red, thick] (td) at (2.6,-1.35) {temporal-dif\/ference\\learning};
  \node[cell, draw=acc, text=acc, thick] (mc) at (7.0,-1.35) {Monte Carlo};
\end{tikzpicture}
$$

That empty corner — model-free _and_ bootstrapping — is
[temporal-difference learning](/reinforcement-learning/tabular-methods/temporal-difference-learning).
It keeps Monte Carlo's freedom from a model but, like DP, updates each estimate from
the reward on _one_ sampled step plus the current estimate of the next state, rather
than waiting for the full return. It need not wait for an episode to end, and it
often learns faster. That is the subject of the next lesson.

[^sb-offpolicy]: **Sutton & Barto**, §5.5 — Off-policy Prediction via Importance Sampling: target versus behavior policy, the coverage assumption, the importance-sampling ratio (5.3) with dynamics cancelling (5.4), ordinary (5.5) versus weighted (5.6) importance sampling and their bias/variance tradeoff, and (§5.7) off-policy MC control learning from episode tails.
[^sb-incremental]: **Sutton & Barto**, §5.6 — Incremental Implementation: episode-by-episode updates for MC prediction, the weighted-average recursion (5.7)–(5.8) with cumulative weight $C_n$, and the off-policy MC prediction algorithm (page 110) that collapses to the on-policy case when $\pi = b$.
[^sb-discaware]: **Sutton & Barto**, §5.8 — Discounting-aware Importance Sampling: the observation that whole-return importance sampling ignores the return's structure as a sum of discounted rewards; the $\gamma = 0$, 100-step example where 99 mean-1 ratios only inflate variance; discounting reinterpreted as a probability of termination; the flat partial returns $\bar G_{t:h}$ and the decomposition of $G_t$ into a $\gamma$-weighted mixture of them; the ordinary (5.9) and weighted (5.10) discounting-aware estimators with horizon-truncated ratios, reducing to the §5.5 estimators at $\gamma = 1$; and (§5.9) the complementary per-decision idea $\mathbb{E}[\rho_{t:T-1} R_{t+k}] = \mathbb{E}[\rho_{t:t+k-1} R_{t+k}]$ that reduces variance even at $\gamma = 1$.
[^sb-summary]: **Sutton & Barto**, §5.10 — Summary: the advantages of MC over DP (model-free learning from actual or simulated experience, focus on a subset of states, robustness to non-Markov violations), that MC does not bootstrap, and the preview of temporal-difference methods that learn from experience yet bootstrap.
[^beyond]: Modern descendants of Monte Carlo return-averaging and off-policy importance sampling. **MCTS**: R. Coulom, "Efficient selectivity and backup operators in Monte-Carlo tree search," _Computers and Games_ (2006); L. Kocsis and C. Szepesvári, "Bandit based Monte-Carlo planning" (UCT), _ECML_ (2006). **AlphaGo/AlphaZero/MuZero**: D. Silver et al., _Nature_ 529 (2016), 484–489; D. Silver et al., _Science_ 362 (2018), 1140–1144; J. Schrittwieser et al., _Nature_ 588 (2020), 604–609. **Off-policy corrections**: R. Munos, T. Stepleton, A. Harutyunyan, M. Bellemare, "Safe and efficient off-policy reinforcement learning" (Retrace), _NeurIPS_ (2016); L. Espeholt et al., "IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures" (V-trace), _ICML_ (2018); S. Kapturowski et al., "Recurrent experience replay in distributed reinforcement learning" (R2D2), _ICLR_ (2019). **Return interpolation**: J. Schulman et al., "High-dimensional continuous control using generalized advantage estimation," _ICLR_ (2016). Monte Carlo tree search is treated in Sutton & Barto itself, §8.11.