Deep Reinforcement Learning

Off-Policy Monte Carlo Methods and Introduction to Temporal Difference Learning

📅 Published: 2026-07-06

🎓 Level: postgraduate

👥 Audience: Postgraduate students in Reinforcement Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Monte Carlo Methods — on-policy MC control, importance sampling, and ordinary vs. weighted estimators — covered in Lecture 7
Value functions and policies — state-value and action-value functions under a policy — covered in Lectures 4 and 5

9.1 The Role of Reinforcement Learning in Modern AI

Hook: Can you name a modern AI system that does not use some form of trial-and-error learning? From ChatGPT to self-driving cars, the answer is increasingly "none." Reinforcement Learning is the engine behind this shift — and it is no longer confined to niche control problems.

Intuition: Think of RL as the process of learning to cook. You try a recipe, taste the result, adjust the salt, try again. Each iteration makes you a better cook. RL does the same for AI: it takes an action, observes the outcome (reward), and adjusts its strategy to do better next time. The cycle — act, observe, improve — is what drives every RL system.

Formalize: Reinforcement Learning is a computational approach to learning from interaction. An agent takes actions in an environment, receives rewards (scalar feedback signals), and updates its policy (the mapping from situations to actions) to maximize cumulative reward over time.

Key terms:

Agent: the learner/decision-maker
Environment: everything the agent interacts with
State $s$ : the situation the agent is in
Action $a$ : what the agent can do
Reward $R_{t}$ : scalar feedback at time $t$
Return $G_{t}$ : cumulative (possibly discounted) sum of future rewards: $G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots$
Policy $π (a ∣ s)$ : probability of taking action $a$ in state $s$

Reinforcement Learning has become the foundation for almost all modern AI tasks. A few years ago, RL use cases were limited to domains like thermal power plant control — using sensors to measure physical parameters and using RL to keep them in control. Today, RL applications are far more prevalent.

Consider an information retrieval pipeline: you submit a query, the system tries to understand the query, decomposes it, fetches relevant documents, and ranks them so the most relevant appears at the top. With LLMs and RAG (Retrieval-Augmented Generation), there is a need to iteratively refine results. Iterative refinement — keep improving performance — is where RL comes in.

Analogy — the student preparing for an exam: A student solves a practice paper (action), checks the answer key (reward), learns what went wrong (update), and solves the next paper better. The cycle of "attempt → feedback → improve" is RL in human form. The student does not need a mathematical model of the exam — they learn purely from experience. This is the essence of model-free RL.

Even LLM training pipelines now use RL. There are algorithms like DPO (Direct Preference Optimization), but without understanding the basics of RL, it is impossible to adapt such algorithms to specific requirements. Unlike classic algorithms like quicksort — which are done, tested, and simply called — modern RL algorithms are recent and often need to be adapted to particular scenarios. This is why foundations are critical.

Concrete example — LLM alignment with RLHF:

A language model generates a response (action).
A human rates the response as helpful or unhelpful (reward).
A reward model is trained to predict human preferences.
The LLM's policy is updated using RL (specifically PPO) to maximize the predicted reward.
The cycle repeats, and the LLM becomes increasingly aligned with human preferences.

This is RL in production — and it depends on the same concepts (policy, reward, value, return) covered in this lecture.

Scope: The RL methods in this course apply to problems where:

The agent interacts with an environment sequentially
Feedback comes as scalar rewards (not full labels)
The goal is to maximize long-term cumulative reward
The environment may be unknown (model-free setting)

RL is not the right tool when you have a fixed labeled dataset and need one-shot predictions — that is supervised learning's domain.

Visual Intuition: Picture the RL loop as a circle: Agent → Action → Environment → Reward + New State → Agent (update) → ... This agent-environment interaction loop is the central diagram of RL. The agent sits on one side, the environment on the other. The only communication channels are actions (agent → environment) and observations + rewards (environment → agent). Every RL algorithm, from the simplest bandit to the most complex LLM trainer, fits this loop.

Recap: RL is learning what to do (policy) by trying things (actions) and seeing what works (rewards). It powers everything from game-playing AI to LLM alignment. Bridge: Before building optimal policies, we need to evaluate a given policy — which is exactly what Monte Carlo methods do.

9.2 Agenda Overview

Hook: You have already seen on-policy Monte Carlo — one agent doing everything itself. But what if you could learn from someone else's experience? A teacher, a dataset, or a safety manual? That is the promise of off-policy learning.

The plan for this session covers four core topics:

Quick recap of on-policy Monte Carlo methods — the self-made learner that both generates and learns from its own experience.
Foundations of off-policy Monte Carlo methods — separating the explorer (behavior policy) from the learner (target policy) via importance sampling.
Ordinary vs. Weighted Importance Sampling & Control — statistical properties, the infinite variance proof, incremental implementation, and control algorithms.
Advanced Off-Policy Ideas & Introduction to Temporal Difference (TD) learning — discounting-aware & per-decision IS, real-world applications, and the bridge to TD.

Roadmap: On-policy → Off-policy (with importance sampling) → Infinite Variance & Control → Advanced IS & TD Preview. Each builds on the last. Master on-policy first, then off-policy, and TD becomes natural.

9.3 Recap: On-Policy Monte Carlo Methods

9.3.1 What Are Monte Carlo Methods?

Hook: Imagine learning to play chess without ever being told the rules. You just play thousands of games, and after each game, you know whether you won or lost. Over time, you figure out which moves lead to wins. That is Monte Carlo RL — learning solely from the outcomes of complete experiences.

Definition: Monte Carlo (MC) methods are model-free RL techniques that learn value functions and optimal policies by averaging sample returns from complete episodes. They do not require a model of the environment's dynamics — only experience in the form of state-action-reward sequences.

9.3.2 Policy Evaluation with MC

Policy Evaluation (Prediction): Given a fixed policy

π

, estimate the value function

V^{π} (s)

or action-value function

Q^{π} (s, a)

— the expected return starting from state

s

(and taking action

a

) and following

π

thereafter.

V^{π} (s) = E_{π} [G_{t} ∣ S_{t} = s] \approx \frac{1}{N} i = 1 \sum N G_{i} (s)

9.3.3 Symbol Registry — On-Policy MC Control

Symbol	Meaning	Type
$π$	Policy — mapping from states to action probabilities	Function
$Q (s, a)$	Action-value function — expected return from state $s$ taking action $a$	Scalar
$Returns (s, a)$	List of all returns observed for $(s, a)$ pair	List
$G$	Return — cumulative (possibly discounted) sum of rewards: $G_{t} = \sum_{k = 0}^{\infty} γ^{k} R_{t + k + 1}$	Scalar
$γ$	Discount factor $\in [0, 1]$ — trades off immediate vs future rewards	Scalar

9.3.4 On-Policy First-Visit MC Control Algorithm

Initialize π as an arbitrary ε-soft policy
Initialize Q(s,a) arbitrarily for all s, a
Initialize Returns(s,a) as empty list for all s, a

Repeat forever:
    Generate an episode S_0, A_0, R_1, S_1, A_1, R_2, ..., S_T using π
    G ← 0
    For t = T-1 down to 0:
        G ← γ * G + R_{t+1}
        Unless (S_t, A_t) appears in S_0, A_0, ..., S_{t-1}, A_{t-1}:
            Append G to Returns(S_t, A_t)
            Q(S_t, A_t) ← average(Returns(S_t, A_t))
            A* ← argmax_a Q(S_t, a)
            For all a in A(S_t):
                π(a|S_t) ← { 1 - ε + ε/|A|  if a = A*
                           { ε/|A|            otherwise

The fundamental tension of On-Policy MC: The policy

π

plays two roles simultaneously: generating experience (exploration) and being optimized (exploitation). A policy generating experience must explore (cannot always pick the greedy action), but the goal is to become optimal (mostly picking the greedy action). One policy is forced to serve two masters.

9.4 Motivation for Off-Policy Learning

9.4.1 The Two-Role Tension & Decoupling

Off-policy learning solves the exploration-exploitation tension by decoupling the agent into two separate policies:

Off-policy learning separates exploration from optimization using two different policies:

Policy	Role	Description
Behavior policy $b$	Teacher / Explorer	Generates experience. Can bring prior knowledge, safety norms, constraints. Soft policy ( $b (a ∣ s) > 0$ ).
Target policy $π$	Learner / Optimizer	The policy being evaluated or improved. Starts arbitrary, converges to greedy/optimal.

The professor's analogy (Dr. Kalam): The teachers who taught Dr. A.P.J. Abdul Kalam did not become president or rocket scientists. The learner went beyond. The teacher allowed the learner to explore, learn, and improve. The behavior policy is the teacher — it provides the raw material. The target policy is the student — it can surpass the teacher.

9.4.2 Coverage Assumption

The Coverage Assumption: For off-policy evaluation to make sense, the behavior policy

b

must give non-zero probability to every action that the target policy

π

may take:

π (a ∣ s) > 0 ⟹ b (a ∣ s) > 0 for all s, a .

π (a ∣ s) > 0

but

b (a ∣ s) = 0

, then episodes generated by

b

will never take action

a

in state

s

, making it impossible to gather data about

π

's value at that state-action pair.

9.5 Foundations of Importance Sampling

9.5.1 General Expectation Transformation & Proof Idea

General Importance Sampling: Suppose we wish to estimate the expectation of a random variable

X

under a target distribution

Pr_{π} (X)

, but we only have samples drawn from a behavior distribution

Pr_{b} (X)

. Under the coverage assumption, we can transform the expectation as follows:

E_{π} [X] = x \sum x \cdot π Pr (x) = x \sum x \cdot \frac{Pr _{π} ( x )}{Pr _{b} ( x )} b Pr (x) = E_{b} [\frac{Pr _{π} ( X )}{Pr _{b} ( X )} X]

In Monte Carlo RL, the "sample" is a full trajectory

τ = (S_{t}, A_{t}, R_{t + 1}, S_{t + 1}, A_{t + 1}, \dots, S_{T})

, and the random variable is the return

G_{t}

. The expected return under the target policy

π

starting from state

s

is:

v_{π} (s) = E_{b} [ρ_{t : T - 1} G_{t} ∣ S_{t} = s]

where

ρ_{t : T - 1}

is the importance-sampling ratio for the trajectory segment.

9.5.2 Trajectory Probability and Model Dynamics Cancellation

Trajectory Probability under $π$ vs. $b$ : Consider a trajectory segment starting at time

t

and ending at termination

T

A_{t}, S_{t + 1}, A_{t + 1}, \dots, S_{T}

Under policy

π

, the probability of observing this sequence conditioned on

S_{t}

is:

Pr {A_{t}, S_{t + 1}, A_{t + 1}, \dots, S_{T} ∣ S_{t}, A_{t : T - 1} \sim π} = k = t \prod T - 1 π (A_{k} ∣ S_{k}) p (S_{k + 1} ∣ S_{k}, A_{k})

Under behavior policy

b

, the probability is:

Pr {A_{t}, S_{t + 1}, A_{t + 1}, \dots, S_{T} ∣ S_{t}, A_{t : T - 1} \sim b} = k = t \prod T - 1 b (A_{k} ∣ S_{k}) p (S_{k + 1} ∣ S_{k}, A_{k})

Taking the ratio of the two trajectory probabilities:

ρ_{t : T - 1} = \frac{\prod _{k = t}^{T - 1} π ( A _{k} ∣ S _{k} ) p ( S _{k + 1} ∣ S _{k} , A _{k} )}{\prod _{k = t}^{T - 1} b ( A _{k} ∣ S _{k} ) p ( S _{k + 1} ∣ S _{k} , A _{k} )} = k = t \prod T - 1 \frac{π ( A _{k} ∣ S _{k} )}{b ( A _{k} ∣ S _{k} )}

Model-Free Property: The environment transition probabilities

p (S_{k + 1} ∣ S_{k}, A_{k})

cancel completely from numerator and denominator! Thus, computing

ρ_{t : T - 1}

requires knowing only the policy probabilities

π

and

b

, keeping off-policy MC entirely model-free.

9.5.3 Symbol Registry — Importance Sampling

Symbol	Meaning	Type
$τ$	Trajectory segment $A_{t}, S_{t + 1}, A_{t + 1}, \dots, S_{T}$	Sequence
$b (a ∣ s)$	Behavior policy probability of action $a$ in state $s$	Scalar $\in (0, 1]$
$π (a ∣ s)$	Target policy probability of action $a$ in state $s$	Scalar $\in [0, 1]$
$ρ_{t : T - 1}$	Importance sampling ratio covering time steps $t$ through $T - 1$	Scalar $\geq 0$
$p (s^{'} ∣ s, a)$	Environment transition probability (cancels out in $ρ$ )	Scalar $\in [0, 1]$

9.5.4 Numerical Worked Example: Trajectory Probability & Ratio

Problem (Section 3.4 in Lecture Notes): Suppose a trajectory generated by behavior policy

b

follows three decisions:

(s_{0}, a_{1}, s_{1}, a_{2}, s_{0}, a_{1}, T)

Let policy probabilities be:

π (a_{1} ∣ s_{0}) = 0.8, b (a_{1} ∣ s_{0}) = 0.5

π (a_{2} ∣ s_{1}) = 0.7, b (a_{2} ∣ s_{1}) = 0.4

Step 1: Compute importance ratio $ρ$ :

ρ = (\frac{π ( a _{1} ∣ s _{0} )}{b ( a _{1} ∣ s _{0} )}) \cdot (\frac{π ( a _{2} ∣ s _{1} )}{b ( a _{2} ∣ s _{1} )}) \cdot (\frac{π ( a _{1} ∣ s _{0} )}{b ( a _{1} ∣ s _{0} )}) = (\frac{0.8}{0.5}) \times (\frac{0.7}{0.4}) \times (\frac{0.8}{0.5})

ρ = 1.6 \times 1.75 \times 1.6 = 4.48

Step 2: Compute Ordinary Importance-Weighted Return: If the observed return for this trajectory is

G = 3

, then:

Weighted Return ρG = 4.48 \times 3 = 13.44

Interpretation: Because

ρ = 4.48 > 1

, this trajectory is

4.48

times more likely under the target policy

π

than under behavior policy

b

. The observed return of

3

is upweighted to

13.44

to reflect its higher frequency under

π

9.6 Off-Policy Prediction: First-Visit vs. Every-Visit & Estimators

9.6.1 Visit Set Notation: $T_{F V} (s)$ vs. $T_{E V} (s)$

To evaluate $v_{π} (s)$ across multiple episodes, we collect the time steps at which state $s$ is visited:

$T_{E V} (s)$ : The set of all time steps in all episodes at which $S_{t} = s$ (Every-Visit collection).
$T_{F V} (s)$ : The set of only the first time step in each episode at which $S_{t} = s$ (First-Visit collection).

For instance, if one episode visits states $A, B, A, T$ , then $T_{E V} (A)$ receives two time indices from that episode, whereas $T_{F V} (A)$ receives only the first index.

9.6.2 Ordinary vs. Weighted Importance-Sampling Estimators

Using a generic visit set

T (s)

, we define two primary estimators for state-value evaluation:

1. Ordinary Importance-Sampling Estimator ( $V^{O I S} (s)$ ):

V^{O I S} (s) = \frac{\sum _{t \in T (s)} ρ _{t : T (t) - 1} G _{t}}{∣ T ( s ) ∣}

Simple arithmetic average of importance-weighted returns. Divided by total visit count

∣ T (s) ∣

.

2. Weighted Importance-Sampling Estimator ( $V^{W I S} (s)$ ):

V^{W I S} (s) = \frac{\sum _{t \in T (s)} ρ _{t : T (t) - 1} G _{t}}{\sum _{t \in T (s)} ρ _{t : T (t) - 1}}

Weighted average normalized by the sum of importance ratios.

9.6.3 Numerical Comparison: First-Visit vs. Every-Visit Returns

Example (Section 6.1 in Lecture Notes): Consider a single episode:

S_{0} = A, S_{1} = B, S_{2} = A, S_{3} = T

. State

A

is visited twice.
Let observed returns be

G_{0} = 5

and

G_{2} = 2

. Let suffix ratios be

ρ_{0 : 2} = 3

and

ρ_{2 : 2} = 1.5

.

First-Visit Ordinary IS: Uses only the first visit (

t = 0

V_{F V}^{O I S} (A) = ρ_{0 : 2} G_{0} = 3 \times 5 = 15

Every-Visit Ordinary IS: Uses both visits (

t = 0

and

t = 2

V_{E V}^{O I S} (A) = \frac{ρ _{0 : 2} G _{0} + ρ _{2 : 2} G _{2}}{2} = \frac{3 ( 5 ) + 1.5 ( 2 )}{2} = \frac{15 + 3}{2} = 9

First-Visit Weighted IS:

V_{F V}^{W I S} (A) = \frac{3 ( 5 )}{3} = 5

Every-Visit Weighted IS:

V_{E V}^{W I S} (A) = \frac{ρ _{0 : 2} G _{0} + ρ _{2 : 2} G _{2}}{ρ _{0 : 2} + ρ _{2 : 2}} = \frac{15 + 3}{3 + 1.5} = \frac{18}{4.5} = 4

9.7 Off-Policy Prediction Worked Examples

9.7.1 Example 1: Long-Trajectory Weighting Can Dominate

Setup (Section 4.3 in Lecture Notes): Let states be

X

and

Y

, actions be

L, M, R

, and discount

γ = 0.9

. Policy probabilities:

State	$π (L)$	$π (M)$	$π (R)$	$b (L)$	$b (M)$	$b (R)$
$X$	0.6	0.3	0.1	0.3	0.4	0.3
$Y$	0.2	0.5	0.3	0.4	0.3	0.3

Two episodes starting from

X

are observed under

b

:

Episode 1:

X L, 1 Y M, 0 X L, 2 Y R, 1 X M, 0 Y M, 4 T

G_{0}^{(1)} = 1 + 0.9 (0) + 0. 9^{2} (2) + 0. 9^{3} (1) + 0. 9^{4} (0) + 0. 9^{5} (4) = 1 + 1.62 + 0.729 + 2.36196 = 5.71096

ρ^{(1)} = (\frac{0.6}{0.3}) \times (\frac{0.5}{0.3}) \times (\frac{0.6}{0.3}) \times (\frac{0.3}{0.3}) \times (\frac{0.3}{0.4}) \times (\frac{0.5}{0.3}) = 2 \times \frac{5}{3} \times 2 \times 1 \times \frac{3}{4} \times \frac{5}{3} = 8.3333

Episode 2:

X R, 0 Y L, 2 X M, - 1 Y M, 0 X L, 1 Y R, 5 T

G_{0}^{(2)} = 0 + 0.9 (2) + 0. 9^{2} (- 1) + 0. 9^{3} (0) + 0. 9^{4} (1) + 0. 9^{5} (5) = 1.8 - 0.81 + 0.6561 + 2.95245 = 4.59855

ρ^{(2)} = (\frac{0.1}{0.3}) \times (\frac{0.2}{0.4}) \times (\frac{0.3}{0.4}) \times (\frac{0.5}{0.3}) \times (\frac{0.6}{0.3}) \times (\frac{0.3}{0.3}) = \frac{1}{3} \times \frac{1}{2} \times \frac{3}{4} \times \frac{5}{3} \times 2 \times 1 = 0.4167

Ordinary Importance Sampling Estimate:

V^{O I S} (X) = \frac{8.3333 ( 5.71096 ) + 0.4167 ( 4.59855 )}{2} = \frac{47.5913 + 1.9162}{2} = 24.7537

Weighted Importance Sampling Estimate:

V^{W I S} (X) = \frac{8.3333 ( 5.71096 ) + 0.4167 ( 4.59855 )}{8.3333 + 0.4167} = \frac{49.5075}{8.7500} = 5.6580

Takeaway: Ordinary IS is pulled up to

24.7537

(far outside the range of observed returns

[4.6, 5.7]

) because Episode 1 received a large ratio. Weighted IS normalizes by total weight, yielding a stable, bounded estimate of

5.6580

9.7.2 Example 2: Short Trajectory Calculation

Setup (Section 4.4 in Lecture Notes): Two states

X, Y

, actions

L, R

, discount

γ = 0.9

π (L ∣ X) = 0.8, b (L ∣ X) = 0.5, π (R ∣ Y) = 0.7, b (R ∣ Y) = 0.4

Two observed episodes starting at

X

Episode 1: $X L, 0 Y R, 2 X L, 1 T ⟹ G^{(1)} = 0 + 0.9 (2) + 0. 9^{2} (1) = 2.61$ ; $ρ^{(1)} = (\frac{0.8}{0.5}) (\frac{0.7}{0.4}) (\frac{0.8}{0.5}) = 1.6 \times 1.75 \times 1.6 = 4.48$ .
Episode 2: $X R, 0 Y L, 2 X R, 0 T ⟹ G^{(2)} = 0 + 0.9 (2) + 0. 9^{2} (0) = 1.80$ ; $ρ^{(2)} = (\frac{0.2}{0.5}) (\frac{0.3}{0.6}) (\frac{0.2}{0.5}) = 0.4 \times 0.5 \times 0.4 = 0.08$ .

Ordinary IS Estimate:

V^{O I S} (X) = \frac{4.48 ( 2.61 ) + 0.08 ( 1.80 )}{2} = \frac{11.6928 + 0.1440}{2} = 5.9184

Weighted IS Estimate:

V^{W I S} (X) = \frac{4.48 ( 2.61 ) + 0.08 ( 1.80 )}{4.48 + 0.08} = \frac{11.8368}{4.5600} = 2.5958

9.7.3 Worked Grid-World Example

Consider states

W, X, Y, U

and terminal state. Target policy

π

π (Right ∣ W) = 0.99, π (Left ∣ W) = 0.01

. Behavior policy

b

: uniform

0.5/0.5

.

Trajectory

τ_{1}

W Right, 0 X Right, 0 Y Exit, 10 T

ρ_{W} = (\frac{0.99}{0.5}) \times (\frac{0.99}{0.5}) \times (\frac{1}{1}) = 1.98 \times 1.98 \times 1 = 3.9204 ⟹ Weighted return = 39.204

Trajectory

τ_{2}

W Left, 0 U Exit, 1 T

ρ_{W} = (\frac{0.01}{0.5}) \times (\frac{1}{1}) = 0.02 ⟹ Weighted return = 0.02

Weighted IS estimate for

V^{π} (W)

V^{W I S} (W) = \frac{39.204 + 0.02}{3.9204 + 0.02} = \frac{39.224}{3.9404} \approx 9.954

9.8 Bias, Variance, and Infinite Variance in Off-Policy Estimation

9.8.1 Empirical MSE Analysis: Reading the Blackjack Plot

In Sutton & Barto (Figure 5.4), state-value estimation in off-policy Blackjack is analyzed by plotting Mean-Squared Error (MSE) against the number of episodes (log scale):

Ordinary Importance Sampling (Green Curve): Unbiased for first-visit MC, but starts with high error and exhibits extreme variance spikes even after millions of episodes. A single high-ratio trajectory can drastically distort the estimate.
Weighted Importance Sampling (Red Curve): Biased in early finite samples due to random normalization, but error drops rapidly and smoothly. In practice, its variance is dramatically lower.

9.8.2 Summary Comparison Table

Property	Ordinary Importance Sampling	Weighted Importance Sampling
Finite-sample Bias	Unbiased (for First-Visit MC)	Biased (due to random denominator $\sum ρ_{i}$ )
Variance	Can be extremely high; unbounded / infinite	Much lower; bounded by return range when returns bounded
Asymptotic Behavior	Consistent, but practically unstable	Bias $\to 0$ asymptotically; highly preferred in practice
Denominator	Episode count $N$	Cumulative sum of weights $\sum ρ_{i}$

9.8.3 Formal Mathematical Proof of Infinite Variance

The One-State MDP Example (Sutton & Barto §5.5): Consider an MDP with a single non-terminal state

s

and two actions:

left

and

right

Action $right$ transitions to terminal state $T$ with reward $0$ .
Action $left$ transitions back to state $s$ with reward $0$ with probability $0.9$ , and to terminal state $T$ with reward $+ 1$ with probability $0.1$ .
Target policy $π$ : Always chooses $left$ ( $π (left ∣ s) = 1, π (right ∣ s) = 0$ ). Under $π$ with $γ = 1$ , $v_{π} (s) = 1$ .
Behavior policy $b$ : Chooses $left$ and $right$ with equal probability ( $b (left ∣ s) = 0.5, b (right ∣ s) = 0.5$ ).

Consider episodes that consist of

k

consecutive

left

actions followed by termination with reward

+ 1

.
Under behavior policy

b

, the probability of observing an episode with

k

left

actions ending in reward

+ 1

is:

b Pr (k) = (0.5)^{k} \times (0.1 \times 0.5) = 0.1 \times (0.5)^{k + 1}

The importance sampling ratio for such an episode is:

ρ = i = 1 \prod k \frac{π ( left ∣ s )}{b ( left ∣ s )} = (\frac{1}{0.5})^{k} = 2^{k}

The return for this episode is

G = 1

. Thus,

ρG = 2^{k}

.

Evaluating the Second Moment $E_{b} [(ρG)^{2}]$ :

E_{b} [(ρG)^{2}] = k = 0 \sum \infty b Pr (k) \cdot (ρG)^{2} = k = 0 \sum \infty (0.1 \times 0. 5^{k + 1}) \cdot (2^{k})^{2}

= 0.05 k = 0 \sum \infty (0.5)^{k} \cdot 4^{k} = 0.05 k = 0 \sum \infty 2^{k} = \infty

Because the second moment diverges to infinity, the variance

Var (ρG) = E_{b} [(ρG)^{2}] - (E_{b} [ρG])^{2} = \infty - 1 = \infty

.

Conclusion: Ordinary importance sampling has infinite variance in this simple MDP. This formally proves why ordinary IS can fail to converge in finite time, necessitating Weighted Importance Sampling.

9.9 Incremental Implementation of Weighted Importance Sampling

9.9.1 Incremental Derivation

Suppose we observe a sequence of returns

G_{1}, G_{2}, \dots, G_{n}

with corresponding importance weights

W_{1}, W_{2}, \dots, W_{n}

.
The weighted estimate after

n - 1

returns is:

V_{n} = \frac{\sum _{k = 1}^{n - 1} W _{k} G _{k}}{\sum _{k = 1}^{n - 1} W _{k}}, n \geq 2

Let

C_{n} = \sum_{k = 1}^{n} W_{k}

be the cumulative sum of weights. The update rule for

V_{n + 1}

upon receiving weight

W_{n}

and return

G_{n}

is:

V_{n + 1} = V_{n} + \frac{W _{n}}{C _{n}} [G_{n} - V_{n}], n \geq 1

where

C_{n} = C_{n - 1} + W_{n}

with

C_{0} = 0

9.9.2 Numerical Step-by-Step Trace

Suppose weighted returns arrive as

(W, G) = (2, 5), (1, 2), (3, 4)

. Initialize

V_{1} = 0, C_{0} = 0

Observation $(W, G)$	Cumulative Weight $C_{n}$	Incremental Update Formula	New Estimate $V_{n + 1}$
$(2, 5)$	$C_{1} = 0 + 2 = 2$	$V_{2} = 0 + \frac{2}{2} (5 - 0)$	5.0
$(1, 2)$	$C_{2} = 2 + 1 = 3$	$V_{3} = 5 + \frac{1}{3} (2 - 5) = 5 - 1$	4.0
$(3, 4)$	$C_{3} = 3 + 3 = 6$	$V_{4} = 4 + \frac{3}{6} (4 - 4) = 4 + 0$	4.0

Verification with Batch Calculation:

V_{batch} = \frac{W _{1} G _{1} + W _{2} G _{2} + W _{3} G _{3}}{W _{1} + W _{2} + W _{3}} = \frac{2 ( 5 ) + 1 ( 2 ) + 3 ( 4 )}{2 + 1 + 3} = \frac{10 + 2 + 12}{6} = \frac{24}{6} = 4.0

The incremental update matches the batch result exactly!

9.10 The Off-Policy MC Control Algorithm

9.10.1 Deterministic Target Policy & Break Condition

In Off-Policy MC Control, the target policy

π

is maintained as deterministic greedy with respect to

Q

π (s) = ar g a max Q (s, a)

Since

π (A_{t} ∣ S_{t})

1

A_{t} = π (S_{t})

and

0

A_{t} \neq = π (S_{t})

, the importance sampling ratio becomes zero whenever the behavior action disagrees with the target policy action.

The Break Condition: If

A_{t} \neq = π (S_{t})

, the algorithm immediately exits the inner episode loop. Earlier state-action pairs in that episode receive weight

0

, so no further updates are performed for that episode.

9.10.2 Algorithm Pseudocode

Initialize, for all s ∈ S, a ∈ A(s):
    Q(s, a) ∈ ℜ (arbitrarily)
    C(s, a) ← 0
    π(s) ← argmax_a Q(s, a)

Loop forever (for each episode):
    b ← any soft policy with coverage of π
    Generate an episode using b: S_0, A_0, R_1, S_1, A_1, R_2, ..., S_T
    G ← 0
    W ← 1
    Loop for each step of episode, t = T-1, T-2, ..., 0:
        G ← γ * G + R_{t+1}
        C(S_t, A_t) ← C(S_t, A_t) + W
        Q(S_t, A_t) ← Q(S_t, A_t) + (W / C(S_t, A_t)) * [G - Q(S_t, A_t)]
        π(S_t) ← argmax_a Q(S_t, a)
        If A_t ≠ π(S_t) then exit inner loop
        W ← W * (1 / b(A_t | S_t))

9.10.3 Worked Walkthrough: Line World Control

Line World Setup (Section 8.2 in Lecture Notes): States:

w, x, y, z

. Exits from

w

(reward

- 100

) and

z

(reward

+ 10

). From

x

and

y

, actions are

L, R

. Discount

γ = 0.9

. Behavior policy

b (L) = b (R) = 0.5

.

Episode 1 under $b$ :

x R, 0 y R, 0 z Exit, + 10 T

Backward scan (

t = 2, 1, 0

At $z$ ( $t = 2$ ): $G = 10 ⟹ Q (z, Exit) = 10, C (z, Exit) = 1$ . $π (z) = Exit$ . $W \leftarrow 1 \times \frac{1}{1} = 1$ .
At $y$ ( $t = 1$ ): $G = 0 + 0.9 (10) = 9 ⟹ Q (y, R) = 9, C (y, R) = 1$ . $π (y) = R$ . Since $A_{1} = R = π (y)$ , continue! $W \leftarrow 1 \times \frac{1}{0.5} = 2$ .
At $x$ ( $t = 0$ ): $G = 0 + 0.9 (9) = 8.1 ⟹ Q (x, R) = 8.1, C (x, R) = 2$ . $π (x) = R$ .

Episode 2 under $b$ :

x L, 0 w Exit, - 100 T

At $w$ : $G = - 100 ⟹ Q (w, Exit) = - 100$ .
At $x$ : $G = 0 + 0.9 (- 100) = - 90 ⟹ Q (x, L) = - 90$ .
Target policy check at $x$ : $Q (x, R) = 8.1 > Q (x, L) = - 90 ⟹ π (x) = R$ .
Observed action $A_{0} = L \neq = π (x) = R ⟹$ Exit inner loop!

Result: The target policy learns optimal deterministic path

π (x) = R, π (y) = R

, ignoring sub-optimal exploratory actions taken by

b

9.10.4 Worked Walkthrough: Five-State Grid Control

States

A, B, C, D, E

D

exits with

+ 10

A

exits with

- 10

, step penalty

- 1

γ = 0.9

.
Episode 1:

B E, - 1 C E, - 1 D Exit, + 10 T ⟹ Q (C, E) = 8, π (C) = E

.
Episode 2:

E N, - 1 C N, - 1 A Exit, - 10 T ⟹ Q (C, N) = - 10

. At

C

, greedy choice is

E

(

Q = 8 > - 10

). Action

N \neq = π (C) ⟹

inner loop breaks! Target policy keeps

π (C) = E

9.11 Advanced Off-Policy Ideas

9.11.1 Discounting-Aware Importance Sampling

Standard importance sampling applies a single ratio $ρ_{t : T - 1}$ to the entire return $G_{t}$ . If $γ < 1$ and episodes are long, late rewards have negligible impact on $G_{t}$ , but their action ratios still multiply into $ρ_{t : T - 1}$ , inflating variance unnecessarily. Discounting-aware IS decomposes the return by horizon to omit ratios for heavily discounted future steps.

9.11.2 Per-Decision Importance Sampling

Per-Decision Importance Sampling: Note that reward

R_{t + k + 1}

depends only on decisions up to step

t + k

. Therefore, it needs correction ratios only up to

t + k

G ~_{t} = k = 0 \sum T - t - 1 γ^{k} ρ_{t : t + k} R_{t + k + 1} = ρ_{t : t} R_{t + 1} + γ ρ_{t : t + 1} R_{t + 2} + \dots + γ^{T - t - 1} ρ_{t : T - 1} R_{T}

By avoiding multiplying early rewards by later action ratios, per-decision IS significantly reduces variance in long episodes.

9.12 Real-World Applications of Off-Policy Learning

9.12.1 Logged Recommendation Systems

Reference: Chen, Beutel, Covington, Jain, Belletti, and Chi, "Top-K Off-Policy Correction for a REINFORCE Recommender System", ACM WSDM 2019.

In industrial recommendation (e.g., YouTube/Netflix), historical logs were generated by a production recommender (behavior policy

b

). The target policy

π

is a new neural model. Off-policy correction reweights logged clicks/watch-time to eliminate popularity bias and train

π

without live user risk.

9.12.2 Logged Bandit Feedback in Healthcare & Advertising

Reference: Dudik, Langford, and Li, "Doubly Robust Policy Evaluation and Learning", ICML 2011.

In medical treatment evaluation, historical treatments were chosen by clinicians (behavior policy). Evaluating a new treatment policy from medical records requires importance sampling to adjust for doctor preferences. Doubly robust estimators combine IS with outcome modeling for ultra-low variance.

9.13 Student Questions and Answers

Q: Why multiply the return by the importance sampling ratio? What is the intuition?

A (Professor): Think of three entities: teacher (behavior

b

), learner (target

π

), and exam authority (environment rewards). The teacher acts and gets a return. As the learner, you reason: "The teacher took these actions and earned this return. But I act differently — taking some actions more often and others less." If you would take an action more often than the teacher, multiply by a factor

> 1

. If less often, multiply by

< 1

. That factor is

ρ

Q: How are we learning $π$ if we only observe data from $b$ ?

A (Professor): Target policy

π

is greedy with respect to

Q

. Behavior policy

b

collects experience. After each episode, we update

Q (s, a)

using importance-weighted returns from

b

, and re-orient

π

greedily towards the updated

Q

. Thus,

π

improves continuously and can surpass

b

9.14 Introduction to Temporal Difference (TD) Learning

TD(0) Learning: Updates value estimates after every single step by bootstrapping:

V (S_{t}) \leftarrow V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]

Where

R_{t + 1} + γ V (S_{t + 1})

is the TD Target and

δ_{t} = R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})

is the TD Error.

Method	Target	Waits for	Bootstraps?
Dynamic Programming (DP)	$\sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V (s^{'})]$	Nothing (1-step lookahead)	Yes
Monte Carlo (MC)	$G_{t}$ (full episode return)	End of episode	No
Temporal Difference (TD)	$R_{t + 1} + γ V (S_{t + 1})$	One step	Yes

9.15 Review Questions and Practice Problems

1. Explain the difference between on-policy and off-policy Monte Carlo learning.
Solution: On-policy learning evaluates/improves the same policy that generates the data. Off-policy learning evaluates/improves a target policy

π

using data generated by a separate behavior policy

b

2. State the coverage assumption. Why is it necessary?
Solution:

π (a ∣ s) > 0 ⟹ b (a ∣ s) > 0

for all

s, a

. If

b (a ∣ s) = 0

when

π (a ∣ s) > 0

, the behavior policy will never sample action

a

, leaving no data to estimate its value under

π

3. Show how environment dynamics cancel out in the trajectory ratio.
Solution:

ρ = \frac{\prod π ( A _{k} ∣ S _{k} ) p ( S _{k + 1} ∣ S _{k} , A _{k} )}{\prod b ( A _{k} ∣ S _{k} ) p ( S _{k + 1} ∣ S _{k} , A _{k} )} = \prod \frac{π ( A _{k} ∣ S _{k} )}{b ( A _{k} ∣ S _{k} )}

. The transition probabilities

p (S_{k + 1} ∣ S_{k}, A_{k})

are identical in numerator and denominator.

4. Compute $ρ$ for $π (a_{1} ∣ s) = 0.8, b (a_{1} ∣ s) = 0.4, π (a_{2} ∣ s^{'}) = 0.3, b (a_{2} ∣ s^{'}) = 0.6$ .
Solution:

ρ = (\frac{0.8}{0.4}) \times (\frac{0.3}{0.6}) = 2 \times 0.5 = 1.0

5. Returns $G_{1} = 6, G_{2} = 2$ with ratios $ρ_{1} = 4, ρ_{2} = 0.5$ . Compute OIS and WIS.
Solution:

V^{O I S} = \frac{4 ( 6 ) + 0.5 ( 2 )}{2} = \frac{25}{2} = 12.5

V^{W I S} = \frac{4 ( 6 ) + 0.5 ( 2 )}{4 + 0.5} = \frac{25}{4.5} \approx 5.56

6. Why can Ordinary IS yield estimates far outside the range of observed returns?
Solution: Ordinary IS divides by

N

(episode count) instead of the sum of weights. A single trajectory with a large

ρ

inflates the numerator without scaling the denominator, pulling the average far above any observed return.

7. Give an example episode where First-Visit and Every-Visit use different sample counts.
Solution: Episode

A \to B \to A \to T

. First-visit uses only the first occurrence of

A

(

t = 0

). Every-visit uses both occurrences (

t = 0

and

t = 2

8. Why is Weighted IS biased in finite samples but preferred in practice?
Solution: The denominator

\sum ρ_{i}

is a random variable, introducing finite-sample bias. However, normalization bounds estimates to the range of returns, dramatically reducing variance compared to Ordinary IS.

9. Explain the infinite variance proof for the one-state MDP.
Solution: In the 1-state MDP, taking

k

left actions yields ratio

2^{k}

with probability

0.1 \times 0. 5^{k + 1}

. The second moment

E_{b} [(ρG)^{2}] = 0.05 \sum 2^{k} = \infty

, proving variance is infinite.

10. In off-policy MC control, why stop the backward scan when $A_{t} \neq = π (S_{t})$ ?
Solution: Target policy

π

is deterministic greedy. If

A_{t} \neq = π (S_{t})

, then

π (A_{t} ∣ S_{t}) = 0

, making

ρ = 0

for all earlier time steps. Further updates in that episode would have zero weight.

11. Uniform behavior policy over 4 actions. Deterministic target policy. Compute $ρ$ for 3 target steps.
Solution: Per step ratio

= \frac{1}{1/4} = 4

. For 3 steps,

ρ = 4^{3} = 64

12. Line World trace: $x R, 0 y R, 0 z Exit, + 10 T$ with $γ = 0.9$ . Compute returns.
Solution: At

z

G = 10

. At

y

G = 0 + 0.9 (10) = 9

. At

x

G = 0 + 0.9 (9) = 8.1

13. Difference between trajectory IS and per-decision IS?
Solution: Trajectory IS applies the full ratio

ρ_{t : T - 1}

to the whole return. Per-decision IS applies ratios only up to each reward's step (

ρ_{t : t + k}

for

R_{t + k + 1}

), reducing variance.

14. Formulate off-policy evaluation for a recommender system.
Solution: State

s

: user context/history. Action

a

: recommended item slate. Reward

r

: click/watch time. Behavior

b

: old recommender. Target

π

: new model. Importance sampling corrects for historical recommendation bias.

15. Medical decision system evaluation: Why off-policy?
Solution: Behavior policy

b

represents past doctor decisions. Target policy

π

is a new treatment guideline. Off-policy evaluation measures

π

's expected clinical outcome without executing untested treatments on live patients.

9.16 Exam Guidance Summary

Exam Essentials:

Manual $ρ$ calculation: Multiply per-step ratios $\frac{π ( a ∣ s )}{b ( a ∣ s )}$ . Remember dynamics cancel out!
OIS vs WIS formulas: OIS divides by $N$ ; WIS divides by $\sum ρ_{i}$ .
Off-Policy Control Scan: Work right-to-left, update $C (s, a) \leftarrow C + W$ , $Q \leftarrow Q + \frac{W}{C} (G - Q)$ , and break immediately if $A_{t} \neq = π (S_{t})$ .
Infinite Variance Proof: Be prepared to write down the 1-state MDP geometric series summation $\sum 2^{k} = \infty$ .

9.17 Key Takeaways

Off-policy learning decouples exploration (behavior policy $b$ ) from optimization (target policy $π$ ).
Importance sampling corrects distribution mismatch via ratio $ρ_{t : T - 1}$ ; environment transition probabilities cancel completely.
Weighted IS is far more stable than Ordinary IS because normalization bounds returns and eliminates infinite variance issues in practice.
Off-Policy MC Control uses weighted incremental updates and breaks backward scans on action mismatch.
Per-decision IS reduces variance by scaling each reward only by action ratios up to its arrival.
TD learning updates after every single step using bootstrapping $R_{t + 1} + γ V (S_{t + 1})$ .

9.18 Required Reading & References

Required Textbook Reading: Sutton, R. S., and Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Chapter 5 (Sections 5.5 to 5.7 required; Sections 5.8 to 5.9 optional).

Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
Precup, D., Sutton, R. S., & Singh, S. (2000). Eligibility traces for off-policy policy evaluation. Proceedings of ICML 2000.
Dudik, M., Langford, J., & Li, L. (2011). Doubly robust policy evaluation and learning. Proceedings of ICML 2011.
Chen, M., Beutel, A., Covington, P., Jain, S., Belletti, F., & Chi, E. (2019). Top-K off-policy correction for a REINFORCE recommender system. Proceedings of WSDM 2019.
Sutton, R. S., Mahmood, A. R., Precup, D., & van Hasselt, H. (2014). A new Q( $λ$ ) with interim forward view and Monte Carlo equivalence. Proceedings of ICML 2014.

DRL Lecture 9 notes · Off-Policy Monte Carlo Methods and Introduction to Temporal Difference Learning

Deep Reinforcement Learning· postgraduate· 2026-07-06

Sections Breakdown

19.1 The Role of Reinforcement Learning in Modern AI

Foundation of RL as trial-and-error learning, the agent-environment loop, iterative refinement in RAG, and LLM alignment with RLHF and DPO.

29.2 Agenda Overview

Roadmap: on-policy MC recap, off-policy MC with importance sampling, infinite variance proof, off-policy control, and introduction to TD learning.

39.3 Recap: On-Policy Monte Carlo Methods

Complete review of MC methods — policy evaluation, first-visit vs every-visit MC, MC control algorithm, symbol registry, and the exploration-exploitation tension.

49.4 Motivation for Off-Policy Learning

Decoupling exploration from optimization using separate behavior and target policies, safety constraints, learning from logs, and the coverage condition.

59.5 Foundations of Importance Sampling

General expectation transformation, trajectory probabilities, cancellation of transition dynamics, model-free ratio derivation, and a 3-decision numerical calculation.

69.6 Off-Policy Prediction: First-Visit vs. Every-Visit & Estimators

Visit set notation T_FV(s) vs T_EV(s), generic summation formulas for Ordinary IS and Weighted IS, and a complete numerical comparison.

79.7 Off-Policy Prediction Worked Examples

Long-trajectory weighting dominance example (States X, Y with 3 actions), short-trajectory calculation, and grid-world state evaluation.

89.8 Bias, Variance, and Infinite Variance in Off-Policy Estimation

Empirical Blackjack MSE plot analysis, Ordinary vs Weighted IS comparison table, and the formal mathematical proof of infinite variance in a 1-state MDP.

99.9 Incremental Implementation of Weighted Importance Sampling

Mathematical derivation of incremental weighted updates with cumulative weight C_n and a detailed numerical step-by-step update table.

109.10 The Off-Policy MC Control Algorithm

Deterministic target policy assumption, break condition rationale, full pseudocode, Line-World control trace, and Five-State Grid control trace.

119.11 Advanced Off-Policy Ideas: Discounting-Aware & Per-Decision IS

Discounting-aware IS for long horizon returns and per-decision IS for variance reduction.

129.12 Real-World Applications of Off-Policy Learning

Logged recommendation systems (Chen et al. 2019 WSDM) and logged bandit feedback in healthcare/advertising (Dudik et al. 2011 ICML).

139.13 Student Questions and Answers

In-depth clarifications on importance sampling intuition and target policy improvement from behavior policy experience.

149.14 Introduction to Temporal Difference (TD) Learning

TD(0) update rule, TD target, TD error, comparison table (DP vs MC vs TD), and why TD is foundational to modern RL.

159.15 Review Questions and Practice Problems

15 comprehensive exam-ready review questions covering all aspects of off-policy MC methods with step-by-step solutions.

169.16 Exam Guidance Summary

Key exam skills: manual rho computation, ordinary vs weighted IS formulas, off-policy algo trace, and understanding variable meanings.

179.17 Key Takeaways

Distilled takeaways spanning on-policy MC, off-policy MC, importance sampling, weighted IS, infinite variance, and TD preview.

189.18 Required Reading & References

Required reading from Sutton & Barto Chapter 5 and academic citations (Precup et al., Dudik et al., Chen et al., Sutton et al.).

Postgraduate students in Reinforcement Learning

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Use this section for rapid review before tests.

On-Policy Monte Carlo Methods

Must-know: On-policy MC evaluates a policy by averaging complete returns from sampled episodes. The same policy $π$ both generates experience and learns from it. First-visit MC is unbiased.

$V^{π} (s) = E_{π} [G_{t} ∣ S_{t} = s] \approx \frac{1}{N} i = 1 \sum N G_{i} (s)$

Top pitfall: Confusing on-policy and off-policy — the presence of importance weights $W$ and cumulative sum $C$ signals off-policy.

Self-check: Why must the behavior policy in on-policy MC be $ε$ -soft, and what would happen if it were purely greedy?

Connects to: Off-Policy MC, MC algorithm trace

Off-Policy Learning and Importance Sampling

Must-know: Off-policy learning separates behavior policy $b$ from target policy $π$ . The importance sampling ratio corrects for distribution mismatch while transition probabilities cancel out.

$ρ_{t : T - 1} = k = t \prod T - 1 \frac{π ( A _{k} ∣ S _{k} )}{b ( A _{k} ∣ S _{k} )}$

Top pitfall: Computing $ρ$ from the episode start instead of from the relevant step onward.

Self-check: If $π (a_{1} ∣ s_{0}) = 0.8, b (a_{1} ∣ s_{0}) = 0.5, π (a_{2} ∣ s_{1}) = 0.7, b (a_{2} ∣ s_{1}) = 0.4$ , compute $ρ$ for trajectory $(s_{0}, a_{1}, s_{1}, a_{2}, s_{0}, a_{1}, T)$ .

Connects to: Weighted IS, Coverage condition

Ordinary vs. Weighted Importance Sampling

Must-know: Weighted importance sampling is preferred in practice — denominator uses sum of weights not $N$ . Yields dramatically lower variance with negligible initial bias.

$V^{π} (s)_{weighted} = \frac{\sum ρ _{i} G _{i}}{\sum ρ _{i}} vs. V^{π} (s)_{ordinary} = \frac{\sum ρ _{i} G _{i}}{N}$

Top pitfall: Using ordinary IS formula when weighted IS is required, or using $N$ as denominator of weighted IS.

Self-check: Two episodes give $ρ_{1} = 4, G_{1} = 10$ and $ρ_{2} = 0.02, G_{2} = 1$ . Compute both ordinary and weighted IS estimates.

Connects to: Incremental average updates, Infinite Variance Proof

Proof of Infinite Variance in Ordinary IS

Must-know: Ordinary IS can have infinite variance even in simple 1-state MDPs because the second moment $E [(ρG)^{2}]$ contains a diverging geometric series $\sum_{k = 0}^{\infty} 2^{k} = \infty$ .

$E_{b} [(ρG)^{2}] = k = 0 \sum \infty 0. 5^{k + 1} (2^{k})^{2} = 0.5 k = 0 \sum \infty 2^{k} = \infty$

Top pitfall: Thinking infinite variance means the estimator is mathematically biased; ordinary IS is unbiased but practically unusable due to extreme variance.

Self-check: Why does weighted IS avoid infinite variance in the 1-state example?

Connects to: Ordinary IS, Weighted IS

Off-Policy MC Control Algorithm

Must-know: Processes episodes right-to-left, accumulating $G$ and $W$ . Updates $Q (s, a)$ via weighted incremental average. Breaks when action disagrees with deterministic target policy.

$Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + \frac{W}{C ( S _{t} , A _{t} )} (G - Q (S_{t}, A_{t})) with W \leftarrow W \times \frac{1}{b ( A _{t} ∣ S _{t} )}$

Top pitfall: Forgetting to add $W$ to $C$ before updating $Q$ , or updating $W$ after hitting the break condition.

Self-check: In Line-World control, why does an episode starting with action Left cause the inner loop to exit immediately?

Connects to: Weighted importance sampling, Deterministic target policy

Per-Decision & Discounting-Aware Importance Sampling

Must-know: Per-decision IS applies importance weights only up to each reward's step: $G ~_{t} = \sum γ^{k} ρ_{t : t + k} R_{t + k + 1}$ , eliminating unnecessary variance from later action ratios.

$G ~_{t} = k = 0 \sum T - t - 1 γ^{k} ρ_{t : t + k} R_{t + k + 1}$

Top pitfall: Multiplying early rewards by full trajectory ratios $ρ_{t : T - 1}$ when using per-decision IS.

Self-check: Why does per-decision IS reduce variance compared to standard trajectory-level IS?

Connects to: Variance reduction, Discounting-aware IS

Temporal Difference (TD) Learning

Must-know: TD updates after every single step using bootstrapped target $R_{t + 1} + γ V (S_{t + 1})$ . Combines MC's model-free learning with DP's bootstrapping.

$V (S_{t}) \leftarrow V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]$

Top pitfall: Confusing the TD target (one-step reward plus bootstrapped value) with the full MC return (complete episode return).

Self-check: In what situations would you prefer TD over MC, and vice versa?

Connects to: On-policy MC, DP bootstrapping, SARSA and Q-learning

Previous LectureLecture 08 · Monte Carlo Methods: On-Policy Prediction and Control

Next LectureLecture 10 · Temporal Difference Learning: TD(0), SARSA, and Q-Learning

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

9.1 The Role of Reinforcement Learning in Modern AI

9.1.1 RL as the Foundation for Iterative Refinement

9.2 Agenda Overview

9.3 Recap: On-Policy Monte Carlo Methods

9.3.1 What Are Monte Carlo Methods?

9.3.2 Policy Evaluation with MC

9.3.3 Symbol Registry — On-Policy MC Control

9.3.4 On-Policy First-Visit MC Control Algorithm

9.4 Motivation for Off-Policy Learning

9.4.1 The Two-Role Tension & Decoupling

9.4.2 Coverage Assumption

9.5 Foundations of Importance Sampling

9.5.1 General Expectation Transformation & Proof Idea

9.5.2 Trajectory Probability and Model Dynamics Cancellation

9.5.3 Symbol Registry — Importance Sampling

9.5.4 Numerical Worked Example: Trajectory Probability & Ratio

9.6 Off-Policy Prediction: First-Visit vs. Every-Visit & Estimators

9.6.1 Visit Set Notation: TFV​(s) vs. TEV​(s)

9.6.2 Ordinary vs. Weighted Importance-Sampling Estimators

9.6.3 Numerical Comparison: First-Visit vs. Every-Visit Returns

9.7 Off-Policy Prediction Worked Examples

9.7.1 Example 1: Long-Trajectory Weighting Can Dominate

9.7.2 Example 2: Short Trajectory Calculation

9.7.3 Worked Grid-World Example

9.8 Bias, Variance, and Infinite Variance in Off-Policy Estimation

9.8.1 Empirical MSE Analysis: Reading the Blackjack Plot

9.8.2 Summary Comparison Table

9.8.3 Formal Mathematical Proof of Infinite Variance

9.9 Incremental Implementation of Weighted Importance Sampling

9.9.1 Incremental Derivation

9.9.2 Numerical Step-by-Step Trace

9.10 The Off-Policy MC Control Algorithm

9.10.1 Deterministic Target Policy & Break Condition

9.10.2 Algorithm Pseudocode

9.10.3 Worked Walkthrough: Line World Control

9.10.4 Worked Walkthrough: Five-State Grid Control

9.11 Advanced Off-Policy Ideas

9.11.1 Discounting-Aware Importance Sampling

9.11.2 Per-Decision Importance Sampling

9.12 Real-World Applications of Off-Policy Learning

9.12.1 Logged Recommendation Systems

9.12.2 Logged Bandit Feedback in Healthcare & Advertising

9.13 Student Questions and Answers

9.14 Introduction to Temporal Difference (TD) Learning

9.15 Review Questions and Practice Problems

9.16 Exam Guidance Summary

9.17 Key Takeaways

9.18 Required Reading & References

DRL Lecture 9 notes · Off-Policy Monte Carlo Methods and Introduction to Temporal Difference Learning

Sections Breakdown

Exam Revision Notes

On-Policy Monte Carlo Methods

Off-Policy Learning and Importance Sampling

Ordinary vs. Weighted Importance Sampling

Proof of Infinite Variance in Ordinary IS

Off-Policy MC Control Algorithm

Per-Decision & Discounting-Aware Importance Sampling

Temporal Difference (TD) Learning

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

9.6.1 Visit Set Notation: $T_{F V} (s)$ vs. $T_{E V} (s)$