Off-Policy Monte Carlo | Monte Carlo Methods

The ε-greedy agent from the last section learns the value of the policy it follows—exploration mistakes included. What we’d rather have is a split: behave with a policy that explores, but learn the values of the policy we actually care about. That split has a name, and the vocabulary matters far beyond this chapter:

📖Behavior and Target Policies

In off-policy learning, the behavior policy $b$ generates the experience—it’s what the agent actually does, exploration and all. The target policy $\pi$ is the one whose value function we want to learn. On-policy methods are the special case $\pi = b$ .

Hold onto these two words. When we reach Q-learning—the most famous algorithm in RL—its entire identity will be “off-policy: behaves ε-greedily, learns about the greedy policy.” This section shows the Monte Carlo route to off-policy learning: honest, instructive, and, as the numbers will show, painfully expensive. Understanding why it’s expensive is the best motivation for what comes later.

One requirement before anything works: coverage. If the target policy might take action $a$ in state $s$ , the behavior policy must take it with nonzero probability too—you can’t learn about choices you never observe. Coverage is the real reason exploratory behavior policies (like ε-soft ones) pair naturally with off-policy learning.

Reweighting Experience

Here’s the problem with naively averaging returns: episodes generated by $b$ over-represent what $b$ likes doing and under-represent what $\pi$ likes doing. Averaging them estimates $V^b$ , not $V^\pi$ .

The fix is a change of accounting, not a change of data. For each episode, ask: how much more (or less) likely would the target policy have been to produce exactly this trajectory? Multiply the episode’s return by that ratio. Episodes that look like typical $\pi$ behavior get amplified; episodes $\pi$ would rarely produce get discounted toward zero. The reweighted average then estimates $V^\pi$ —values under the target policy, computed from the behavior policy’s episodes.

That ratio is the importance ratio, and conveniently it never requires the environment’s model: transition probabilities appear in both the numerator and denominator of the trajectory likelihoods and cancel. What survives is a product of per-step policy ratios—one factor per action taken.

∑Mathematical Details

For a trajectory segment from time $t$ to termination at $T$ , the importance ratio is:

$\rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}$

The environment’s transition probabilities cancel between numerator and denominator, leaving only policy terms. The ratio corrects expectations: for returns observed under $b$ ,

$\mathbb{E}_b\big[\rho_{t:T-1} \, G_t \mid S_t = s\big] = V^\pi(s)$

Given returns $G^{(1)}, \ldots, G^{(n)}$ from $n$ episodes (first visits to $s$ ), with ratios $\rho^{(1)}, \ldots, \rho^{(n)}$ , there are two estimators:

Ordinary importance sampling — divide by the number of episodes:

$\hat{V}_{\text{ord}}(s) = \frac{1}{n} \sum_{i=1}^{n} \rho^{(i)} G^{(i)}$

Weighted importance sampling — divide by the total weight:

$\hat{V}_{\text{wtd}}(s) = \frac{\sum_{i=1}^{n} \rho^{(i)} G^{(i)}}{\sum_{i=1}^{n} \rho^{(i)}}$

The two estimators stake out opposite corners of the bias–variance tradeoff:

Ordinary IS

Unbiased at every sample size — but the variance is driven by the ratios themselves, which can be enormous (or zero). Variance may even be unbounded.

One lucky episode with a huge weight can swing the whole estimate.

Weighted IS

Biased in finite samples (with one episode it just returns $G^{(1)}$ , whatever the weight) — but consistent, and its estimates stay inside the range of observed returns, giving much lower variance.

The practical default. Bias fades as data accumulates; wild swings don’t.

The Experiment

Let’s make the tradeoff concrete on the GridWorld. The behavior policy is uniform random—maximum exploration, guaranteed coverage. The target policy is ε-soft ( $\epsilon = 0.1$ ) around the shortest path to the goal: a near-optimal policy we never actually follow. With four actions:

When the behavior’s random action matches the target’s preferred action: per-step ratio $\frac{0.925}{0.25} = 3.7$
Otherwise: per-step ratio $\frac{0.025}{0.25} = 0.1$

Each episode’s weight is a product of these factors, one per step—remember that, it’s about to matter enormously.

</>Implementation

import numpy as np

ROWS, COLS = 4, 4
WALL, GOAL, START = (1, 1), (3, 3), (0, 0)
ACTIONS = ['up', 'down', 'left', 'right']
MOVES = {'up': (-1, 0), 'down': (1, 0), 'left': (0, -1), 'right': (0, 1)}
GAMMA = 0.9
EPS = 0.1


def step(state, action):
    """One environment step. Returns (next_state, reward, done)."""
    dr, dc = MOVES[action]
    nxt = (state[0] + dr, state[1] + dc)
    if not (0 <= nxt[0] < ROWS and 0 <= nxt[1] < COLS) or nxt == WALL:
        nxt = state
    reward = -1.0 + (10.0 if nxt == GOAL else 0.0)
    return nxt, reward, nxt == GOAL


def greedy_action(state):
    """Shortest-path policy: head down, detour right around the wall."""
    r, c = state
    if r < ROWS - 1 and (r + 1, c) != WALL:
        return 'down'
    return 'right'


def target_prob(state, action):
    """pi(a|s): epsilon-soft around the shortest-path action."""
    if action == greedy_action(state):
        return 1 - EPS + EPS / 4   # 0.925
    return EPS / 4                 # 0.025


def behavior_prob(state, action):
    """b(a|s): uniform random."""
    return 0.25


def run_behavior_episode(rng):
    """One episode under b. Returns (return G, importance ratio W)."""
    state, done = START, False
    rewards, ratio_terms = [], []
    while not done:
        action = ACTIONS[rng.integers(4)]
        next_state, reward, done = step(state, action)
        rewards.append(reward)
        ratio_terms.append(target_prob(state, action) / behavior_prob(state, action))
        state = next_state
    G = 0.0
    for reward in reversed(rewards):
        G = reward + GAMMA * G
    W = np.prod(ratio_terms)  # product of per-step ratios
    return G, W


def is_estimates(num_episodes, seed=0):
    """Ordinary and weighted IS estimates of V^pi(START)."""
    rng = np.random.default_rng(seed)
    Gs, Ws = zip(*(run_behavior_episode(rng) for _ in range(num_episodes)))
    Gs, Ws = np.array(Gs), np.array(Ws)
    ordinary = np.mean(Ws * Gs)
    weighted = np.sum(Ws * Gs) / np.sum(Ws) if np.sum(Ws) > 0 else 0.0
    return ordinary, weighted


for n in (100, 1_000, 10_000):
    ordinary, weighted = is_estimates(n)
    print(f"{n:>6} episodes:  ordinary IS = {ordinary:8.2f}   "
          f"weighted IS = {weighted:6.2f}")

Output:

   100 episodes:  ordinary IS =    -0.24   weighted IS =  -0.92
  1000 episodes:  ordinary IS =    -0.22   weighted IS =  -1.56
 10000 episodes:  ordinary IS =     0.69   weighted IS =   0.61

The exact answer, computed by a DP linear solve with the ε-soft target policy, is $V^\pi(\text{start}) = 0.56$ (for reference, $V^*(\text{start}) = 1.22$ ; the target’s exploration costs it the rest).

Reading the Damage

Even at 10,000 episodes, the estimates (0.69 and 0.61) are only near the true 0.56—and a single seed hides the real story. Running the whole experiment 30 times with different seeds:

Episodes	Std of ordinary IS	Std of weighted IS
100	5.92	1.52
1,000	1.48	1.06
10,000	0.50	0.55

At 100 episodes, ordinary IS has a standard deviation of 5.92 for a quantity whose true value is 0.56—the estimate is essentially noise, swung by whether a lucky high-weight episode happened to land in the batch. Weighted IS is four times steadier (its estimates are trapped inside the range of observed returns), which is exactly the variance reduction it promises. But keep perspective: at 10,000 episodes both still have std around 0.5. Compare on-policy MC prediction from the first section, which at 10,000 episodes pinned its value to within ±0.02. Off-policy estimation through 60-step importance ratios costs us roughly a factor of twenty-five in precision at the same sample size.

Why so bad? Look at the weights themselves, across 10,000 behavior episodes:

9×10⁻²⁸

median weight

2,570

largest weight

91%

of episodes weigh under 10⁻⁶

89%

of total weight in top 10 episodes

The median episode carries a weight of about $10^{-27}$ —it contributes nothing. Nearly all the estimator’s mass concentrates on the ten episodes (out of ten thousand) that happened to look most like target-policy behavior; the single largest episode alone holds 23% of the total weight. We simulated 10,000 episodes and are effectively averaging ten. That’s the phenomenon called weight degeneracy, and it gets worse the further apart $b$ and $\pi$ are.

The Horizon Blow-Up

Degeneracy here isn’t bad luck—it’s arithmetic. Each step multiplies the weight by 3.7 or by 0.1. A weight stays moderate only if the random behavior policy happens to pick the target’s preferred action at a high rate for the whole episode—and with 60 steps on average, that’s a lottery. The longer the episode, the more extreme the lottery: importance sampling’s variance compounds exponentially with horizon.

∑Mathematical Details

The mean of the per-step ratio under $b$ is exactly 1 (that’s what makes the estimator unbiased):

$\mathbb{E}_b[\rho_{\text{step}}] = 0.25 \times 3.7 + 0.75 \times 0.1 = 1.0$

But its second moment is:

$\mathbb{E}_b[\rho_{\text{step}}^2] = 0.25 \times 3.7^2 + 0.75 \times 0.1^2 = 3.43$

Per-step ratios are independent given the states visited, so over a $T$ -step episode the second moment of the full weight compounds multiplicatively, $\mathbb{E}[W^2] \approx 3.43^T$ . Computing that for realistic lengths (our episodes average $T = 60$ ):

Horizon $T$	$\mathbb{E}[W^2] \approx 3.43^T$
5 steps	4.8 × 10²
10 steps	2.3 × 10⁵
20 steps	5.1 × 10¹⁰
60 steps	1.3 × 10³²

A second moment of $10^{32}$ around a mean of 1 means the distribution is almost all zeros plus vanishingly rare, astronomically large spikes—precisely the degeneracy we measured. No reasonable number of episodes can average that out. This is sometimes called the curse of horizon: full-trajectory importance sampling is only viable when episodes are short or the two policies are close.

⚠️Warning

It’s tempting to fix this with a deterministic target policy (say, the pure greedy one). That makes things worse: any episode where the behavior policy deviates from the target even once gets ratio exactly 0. Under our uniform behavior policy, virtually every 60-step episode would be discarded, and the surviving ones would carry weights in the thousands. Off-policy MC control (Sutton & Barto, Section 5.7) works around this by only using each episode’s tail—the steps after which behavior happened to match the greedy target—which means it learns from the ends of episodes first and can be agonizingly slow.

Where This Leaves Us

Off-policy Monte Carlo gives us something genuinely new—the behavior/target split, coverage, and importance sampling are foundational tools you’ll meet again in off-policy policy gradients and offline RL. But as a practical algorithm, its exponential-in-horizon variance is disqualifying for long episodes.

Notice, though, where the horizon enters: the ratio is a product over every step between the state and the end of the episode, because MC’s target is the full return. If the learning target only reached one step ahead, the correction would only need one factor—or, with the right target, none at all. That’s the door TD learning opens, and walking through it leads to Q-learning: off-policy control with no importance ratios in sight. Keep the words behavior and target loaded; you’ll need them there.