Monte Carlo Methods: Off-Policy Learning

This builds on Monte Carlo Methods, which developed prediction by averaging returns and on-policy control with $\epsilon$-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.¹

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

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:

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.¹Ordinary importance sampling divides by the count:

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

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

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

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 $\epsilon$-greedy with $\epsilon =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

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:

Weighted importance sampling divides by the sum of the weights:

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.

Incremental implementation

Monte Carlo need not store every return. Just as bandit 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.²

Suppose returns $G_1,G_2,\dots$ 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

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:

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.

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

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

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,

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.

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.

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:

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.

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:

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

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.

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

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

Where Monte Carlo sits

Monte Carlo departs from 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.⁵

That empty corner — model-free and bootstrapping — is 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.