Deep Reinforcement Learning

Comprehensive Examination Revision and Advanced Policy Methods

Published: 2026-08-22

Level: postgraduate

Audience: Postgraduate students in Deep 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

Multi-Armed Bandits and Exploration — covered in Lecture 2
Markov Decision Processes and Bellman Equations — covered in Lecture 4
Dynamic Programming — Policy Evaluation and Policy Improvement — covered in Lecture 6
Monte Carlo Methods — On-Policy Prediction and Control — covered in Lecture 8
Off-Policy Monte Carlo and Importance Sampling — covered in Lecture 9
Temporal-Difference Learning — SARSA, Q-Learning and Expected SARSA — covered in Lecture 10
Maximization Bias and Double Q-Learning — covered in Lecture 11
Function Approximation and Semi-Gradient Methods — covered in Lectures 11–12
Deep Q-Networks — Experience Replay and Target Networks — covered in Lectures 12–13
Policy Gradient Methods and REINFORCE — covered in Lecture 14
Model-Based Planning and Monte Carlo Tree Search — covered in Lecture 15

16.1 Course Overview and Examination Scope

16.1.1 Lecture Notes as a Superset and What Is Examinable

Hook — why this matters before any equation: You will sit an open-book examination with every algorithm printed in front of you and still get the question wrong if you have not practiced what the symbols mean. The notes contain everything you might ever need — but the examination tests whether you can use what was actually taught.

The lecture notes for this course are a superset — a deliberately larger collection that contains every topic ever covered or intended to be covered in any offering of the course, including material prepared for a future re-alignment where early topics would be compressed and later advanced topics expanded. The watermarked combined document spans 191 pages. Not every page is examinable in the current offering.

The examinable scope follows what was actually delivered in class and in the slide decks, not the full extent of the notes. Where the notes include ambition material for future cohorts, that material is explicitly marked as not required for this examination. Where the notes compress a topic that was taught in detail in class, the slides and the textbook take priority over the notes. In short, the notes are a reference library; the lectures define the examination syllabus.

What "examinable" means in practice: A topic is examinable when it was presented in class with an algorithm or formula, explained line by line or in broad mechanism, and flagged for numerical practice. A topic is enrichment when it appears only in the notes as a pointer to papers or as a compressed survey. The two are intentionally different, and the examination follows the first.

The course as delivered is designed for 16 sessions. One session was contributed by a guest instructor and 15 by the main instructor, and the volume already exceeds a comfortable single-session review. An extra class originally on the calendar was cancelled because the course is on track; a replacement slot early next week is reserved on the calendar and will be used to discuss papers and future directions only if participation warrants it. That slot is enrichment, not remediation.

The examination is open-book. Every relevant algorithm and formula will be available in the notes during the examination. Rote memorization of parameter values or line numbers is not the skill being tested. The skill being tested is understanding what each term means and being able to use the algorithm to solve a problem. Even with the sheet open, confusion over a term such as the incremental weight accumulator will prevent a correct solution unless you have practiced the algorithm beforehand.

Scope — what the open-book format does and does not change: The open-book format removes the burden of memorizing pseudocode, but it raises the bar on comprehension. You must still know the meaning of every symbol, the direction of every loop, and the reason for every early exit. If a numerical problem omits a hyperparameter such as the step size $α$ or the discount factor $γ$ , do not silently assume a value — either ask for the missing information or declare the assumption explicitly on the answer sheet. Declared bookkeeping is part of the answer.

Visual intuition — think of the notes as a city map that shows every road ever planned, including roads not yet built. The delivered lectures trace the route you actually drove, street by street. For the examination you are tested on the route you drove, with the map open on your lap for reference. You still need to know which turns you took and why, because the map alone does not tell you where you went.

The notes were produced by concatenating existing sources into a single file. A watermarked version and a non-watermarked version circulated; the content is identical and any apparent discrepancy is a formatting artifact, not a difference in substance.

Exam note: Prioritize the slides and the textbook alongside the notes. If a topic is marked in this lecture as skippable or as post-examination enrichment, do not spend examination-preparation time on it. Practice the numerics that were flagged as requiring practice — especially the backward incremental weighting in off-policy Monte Carlo and the temporal-difference control loop — because the algorithm sheet will not save you if you have not traced those steps before.

16.1.2 Course Chronology and Conceptual Anchors

Understanding where each topic sits in the story makes the rest of the lecture easier to remember. The course unfolds as a deliberate relaxation of assumptions, starting from full knowledge and moving toward learning from raw experience.

Block	Sessions	Core idea	What it assumes
Foundations: what reinforcement learning is, stateless simplification	1–3	Agent, environment, reward, and the exploration problem without state	No state — each decision is independent
Markov decision processes and dynamic programming	4–6	State, transition, reward, and the Bellman optimality equations solved by iterative improvement	Full model of transition probabilities $p (s^{'}, r ∣ s, a)$ and complete state knowledge
Monte Carlo methods	Mid-term block	Learning $v_{π}$ and $q_{π}$ by averaging complete returns from sampled episodes	No model, but complete episodes and no bootstrapping
Off-policy Monte Carlo	Bridging mid-term to post-mid-term	Learning about a target policy $π$ from data generated by a different behaviour policy $b$ via importance sampling	Coverage: $b (a ∣ s) > 0$ whenever $π (a ∣ s) > 0$
Temporal-difference learning	Post-mid-term	Combining sampling with bootstrapping: update toward $R + γ V (S^{'})$	One-step lookahead plus a learned estimate
Function approximation and Deep Q-Networks	Following block	Replacing tables with parametrized functions $v^(s, w)$	Generalization across states, with stability concerns
Policy-gradient and model-based planning	Final blocks	Direct policy parametrization and decision-time search (MCTS, AlphaGo family)	Differentiable policies or a learned/known model

Midterm coverage ended at dynamic programming and on-policy Monte Carlo. The notes distributed at that stage went up to those topics. Off-policy Monte Carlo was partially covered before the midterm but completed after it — no midterm question was drawn from it, but it is included for the comprehensive examination. Everything after the midterm — temporal difference, function approximation, Deep Q-Networks, policy gradients, and the guest material on Monte Carlo Tree Search — is examinable at the level described in each section below. Advanced policy themes introduced in the final sessions — asynchronous methods, generalized advantage estimation, proximal policy optimization, and viewing language models as sequential policies — were presented as a high-level overview.

Two backbones to carry forward: Throughout the second half of the course two ideas keep reappearing. First, dynamic programming as a conceptual backbone — the idea of bootstrapping and iterative improvement shows up in every later family. Second, temporal difference as the practical backbone — understanding why temporal difference is a compromise between dynamic programming and Monte Carlo, and what temporal-difference target and temporal-difference error mean, pays off well beyond the examination because virtually every modern paper uses those terms.

Visual intuition — picture a triangle with dynamic programming at one corner (needs a full model, bootstraps), Monte Carlo at another corner (needs no model, no bootstrapping, waits for the end), and temporal difference in the middle, borrowing bootstrapping from the first and sampling from the second. Later topics — $n$ -step methods, function approximation, planning with a learned model — are different ways of sliding along the edges of that triangle or lifting it into higher-dimensional function spaces.

Common pitfall — treating chronology as trivia: Students sometimes memorize the list of topics without connecting the assumption each topic relaxes. If you can say for each transition "what assumption did we drop and what new difficulty did that create," you have understood the course structure. If you can only recite names, you have not.

16.1.3 How to Prepare from the Materials

Two complementary ways of approaching any algorithm in the notes were distinguished, and either succeeds provided the terms are genuinely understood.

Line-by-line understanding — read each statement, identify each symbol, and trace why it appears. This is the safest route for algorithms with a backward sweep or an early-exit condition, where the order of operations matters.

Mechanism understanding plus reference — grasp broadly how the algorithm achieves its correction (for example, how backward incremental weighting corrects for off-policy data), then use the algorithm sheet as a reference to solve a problem by mapping each symbol to its role. This is faster once the mechanism is solid, but it still requires that you can map every symbol.

Either approach succeeds only if the meaning of terms such as the weight accumulator $W$ , the cumulative denominator $C$ , the return $G$ , and the direction of the backward scan are correctly internalized.

A concrete preparation routine that works: Pick one representative algorithm — off-policy Monte Carlo control or one-step SARSA. Write the algorithm on a blank sheet from memory with every symbol defined. Generate a tiny three-step episode on paper with explicit rewards and policy probabilities. Run the algorithm backward by hand, computing each $W$ , $C$ , $G$ , and $Q$ update, and check the break condition. Compare your trace with the notes version and the slide version. If they differ in phrasing, settle on one and practice consistently with that version. The goal is not to memorize lines but to eliminate surprises when the sheet is open.

A second practical skill was highlighted: assumption-writing and bookkeeping. If a numerical problem omits a hyperparameter such as the step size $α$ , the discount factor $γ$ , or the exploration rate $ϵ$ , do not silently assume a value. Either ask for the missing information or declare the assumption explicitly before proceeding, and write every assumption on the answer sheet. Declared assumptions are part of a correct answer; hidden assumptions are a marking risk.

Finally, a note on consistency. The notes as a stitched document concatenate sources that may phrase or summarize the same algorithm differently. For numerical problems, it matters which exact statement you use — the one used in class to solve the worked example and the one summarized in the notes may differ in compression. When in doubt during examination practice, compare the slide version with the notes version for that algorithm, settle on one that is comfortable, and practice consistently with that version. Comfort with a chosen level of detail matters more than switching between variants.

Recap and bridge: This overview sorted the 191-page superset into a delivered syllabus, placed every upcoming topic on a single assumption-relaxation storyline with dynamic programming and temporal difference as persistent backbones, and distinguished two valid preparation styles. The next section begins the examinable technical material with the first post-midterm topic: off-policy Monte Carlo and the importance-sampling correction that makes learning from someone else's experience possible.

16.2 Off-Policy Monte Carlo Methods

16.2.1 What Off-Policy Learning Is and Why Importance Sampling Is Needed

Hook — a question that makes the difficulty visible: You have a log of a thousand episodes produced by an old, cautious warehouse robot that explores randomly 40% of the time. You have designed a new, much greedier policy you would like to deploy. Can you estimate how well the new policy would have performed without running it even once? Off-policy learning says yes — but only if you correct for the fact that you are averaging the wrong experience.

Off-policy learning separates the policy that generates data from the policy being learned about. The behaviour policy $b (a ∣ s)$ is the policy actually followed to produce episodes. The target policy $π (a ∣ s)$ is the policy whose value $v_{π} (s)$ or $q_{π} (s, a)$ we want to estimate or improve. In on-policy Monte Carlo control the two coincide; in off-policy Monte Carlo they are deliberately different.

Intuition and analogy — the movie critic: Imagine a critic who wants to predict how a particular audience (the target) would rate a film, but can only interview people who watched a different cut (the behaviour). If the two audiences differ in who they include, the critic must reweight each interview: an opinion from someone who would rarely be in the target audience counts less, an opinion from someone highly representative of the target counts more. The weight is the ratio of how likely that person-action is under the target versus the behaviour. Where the analogy breaks: In reinforcement learning the reweighting multiplies along a trajectory — each action choice contributes a factor — so the weight is a product, not a single opinion weight. A long trajectory can therefore become extremely light or extremely heavy.

Why off-policy matters. First, the exploration-exploitation dilemma: the behaviour policy can remain soft and exploratory to ensure every state-action pair is visited, while the target policy can be greedy or near-greedy and steadily move toward optimality. Second, data reuse: historical logs from an old recommender, a simulator, or a human demonstrator already exist and should be usable without fresh interaction. The price of this flexibility is that a return $G_{t}$ observed under $b$ has expectation $v_{b} (s)$ , not $v_{π} (s)$ . It is the wrong expectation and must be corrected.

Coverage — the assumption that makes correction possible: For off-policy prediction to be well-defined, the behaviour policy must give non-zero probability to every action the target might take. Formally, for every state $s$ and action $a$ : $b (a ∣ s) > 0 whenever π (a ∣ s) > 0$ Here $s$ is a state in the finite state set $S$ , $a$ is an action in $A (s)$ , $π (a ∣ s)$ is the target-policy probability of choosing $a$ in $s$ , and $b (a ∣ s)$ is the behaviour-policy probability. If $π$ can choose an action that $b$ never tries, no episode generated by $b$ can ever give evidence about that target action, and the correction ratio would require dividing by zero.

Visual intuition — picture two overlapping probability clouds over the same set of actions in a state. The behaviour cloud is broad and low (exploratory), the target cloud is peaked (greedy). The importance ratio at each action is the height of the target cloud divided by the height of the behaviour cloud at that point. Actions where the target peak towers above the behaviour cloud receive ratios larger than one; actions the target rarely takes receive ratios smaller than one. A trajectory that happens to follow the target peak throughout accumulates a large product and dominates the estimate.

Scope — when the correction applies and when it strains: The importance-sampling correction assumes episodic, finite-horizon tasks where returns $G_{t}$ are well-defined, the coverage assumption above holds, and we observe the behaviour-policy probabilities $b (A_{t} ∣ S_{t})$ for every taken action. It does not require knowledge of transition dynamics $p (s^{'}, r ∣ s, a)$ , because those cancel from the ratio (shown in the next subsection). It strains when trajectories are long (the product of many ratios can explode or vanish), when $π$ is near-deterministic while $b$ is diffuse (ratios become huge for the rare matching trajectory), or when rewards are unbounded. In those regimes variance dominates and weighted variants are preferred.

Keeping the scope in mind, the next habit to build is recognizing the two most frequent mistakes students make when they first apply the correction on paper.

Pitfalls to avoid:

Forgetting coverage. Treating an action with $b (a ∣ s) = 0$ as giving ratio zero is correct, but thinking it contributes "a small amount" is wrong — it contributes nothing, and earlier steps whose correction product includes that zero are truncated.
Mixing up ordinary and weighted averages. Dividing by the number of visits versus dividing by the sum of weights gives different estimates, different biases, and dramatically different variance. The examination will expect you to know which denominator you are using.
Reading the backward sweep forward. The accumulators $W$ and $C$ build backward from termination. Running them forward mixes up which suffix product belongs to which return.

In the broader field, off-policy Monte Carlo is the simplest instance of a pattern that recurs everywhere: in recommender systems a log from last year's ranker (behaviour) is reweighted to evaluate this year's candidate ranker (target); in healthcare, observational treatment decisions form the behaviour while a proposed protocol is the target. The tabular Monte Carlo instance taught here isolates the core statistical idea that those applied systems all build on.

Exam note: For this topic the essential examination material is the meaning of off-policy, the statement of the coverage assumption, the form of the per-step ratio $ρ_{t} = π (A_{t} ∣ S_{t}) / b (A_{t} ∣ S_{t})$ and its product along a trajectory, and numerical practice with that product and its incremental backward accumulation. Statistical-behaviour derivations about bias and variance are background for understanding, not a source of difficult computation. Application pointers to papers are motivation, not detailed question sources.

16.2.2 Importance Sampling — Mathematical Formulation

Single-step correction — the importance-sampling ratio: For a state $S_{t} = s$ and the action $A_{t} = a$ actually taken at time $t$ , the per-step importance-sampling ratio is $ρ_{t} = \frac{π ( A _{t} ∣ S _{t} )}{b ( A _{t} ∣ S _{t} )}$ where $π (A_{t} ∣ S_{t})$ is the target-policy probability of that action in that state, $b (A_{t} ∣ S_{t})$ is the behaviour-policy probability, and both are evaluated at the realized pair $(S_{t}, A_{t})$ . When $π$ would have chosen that action more often than $b$ did, $ρ_{t} > 1$ ; when $π$ would have chosen it less often, $ρ_{t} < 1$ . If $π (A_{t} ∣ S_{t}) = 0$ the ratio is zero, flagging that this trajectory suffix is inconsistent with the target.

To see why a product appears, write the probability of a trajectory segment. Conditioned on the starting state $S_{t} = s$ , the probability under policy $π$ of the suffix $A_{t}, S_{t + 1}, A_{t + 1}, \dots, 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})$

where $T$ is the termination time of the episode, $p (s^{'} ∣ s, a) = Pr {S_{k + 1} = s^{'} ∣ S_{k} = s, A_{k} = a}$ is the environment transition probability, and each factor $π (A_{k} ∣ S_{k}) p (S_{k + 1} ∣ S_{k}, A_{k})$ gives the probability of the action choice times the resulting transition. The same segment under behaviour policy $b$ has probability

$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})$

Dividing the two, every transition factor $p (S_{k + 1} ∣ S_{k}, A_{k})$ appears identically in numerator and denominator and cancels. The relative probability — the importance-sampling ratio for the segment — therefore depends only on policies, not on the unknown dynamics:

$ρ_{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} )} = k = t \prod T - 1 ρ_{k}$

where $T - 1$ is the last decision step before termination. This cancellation is why off-policy Monte Carlo can remain model-free: the agent never needs to know or estimate $p$ .

The correction property follows directly. Let $G_{t}$ be the discounted return from time $t$ , defined for episodic tasks as $G_{t} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{T - t - 1} R_{T}$ , where $R_{k + 1}$ is the reward on the transition $S_{k} \to S_{k + 1}$ and $γ \in [0, 1]$ is the discount factor (here $γ = 1$ is common for episodic Monte Carlo). Then weighting a $b$ -generated return by its segment ratio recovers the $π$ -expectation:

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

where $E_{b} [\cdot ∣ S_{t} = s]$ is the expectation over trajectories generated by $b$ starting from $s$ , and $v_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$ is the true state value under $π$ . In words: expand the expectation as a sum over all possible trajectory segments, each trajectory's behaviour probability $Pr_{b}$ times its ratio $Pr_{π} / Pr_{b}$ leaves $Pr_{π}$ , so the sum becomes the target-policy expectation.

Two estimators — ordinary and weighted: Fix a state $s$ and collect all time steps visiting $s$ across a batch of episodes. Write $T (s)$ for that set, $G_{t}$ for the return after $t$ , and $ρ_{t : T (t) - 1}$ for the ratio from $t$ to the termination time $T (t)$ of the episode containing $t$ . Then $V_{OIS} (s) = \frac{\sum _{t \in T (s)} ρ _{t : T (t) - 1} G _{t}}{∣ T ( s ) ∣}$ is the ordinary importance-sampling (OIS) estimator: a simple average of importance-weighted returns, where $∣ T (s) ∣$ is the number of visits to $s$ . It is unbiased for the first-visit variant (each first-visit weighted return has expectation $v_{π} (s)$ ) but can have enormous or infinite variance because a few huge ratios dominate the average.

$V_{WIS} (s) = \frac{\sum _{t \in T (s)} ρ _{t : T (t) - 1} G _{t}}{\sum _{t \in T (s)} ρ _{t : T (t) - 1}}$ is the weighted importance-sampling (WIS) estimator: a weighted average normalized by the sum of weights (defined as zero when the denominator is zero). It is biased in finite samples because the denominator is random, but the bias vanishes asymptotically and the variance is usually far smaller — bounded by the range of returns when returns are bounded — so WIS is strongly preferred in practice.

Visual intuition for the variance difference — plot mean-squared error against number of episodes on a log horizontal axis. The OIS curve (weight-unnormalized) starts high and fluctuates wildly: a single trajectory that happens to match $π$ receives a huge ratio and pulls the average far above or below the truth. The WIS curve is smoother and lower early on because the same huge ratio appears in both numerator and denominator and partially cancels, keeping the estimate within the range of observed returns.

A classic one-state infinite-variance illustration clarifies the product structure. One non-terminal state $s$ has actions left and right. Target $π$ always chooses left; behaviour $b$ chooses left or right with probability $0.5$ . The left action loops back to $s$ with probability $0.9$ (reward $0$ ) or terminates with reward $+ 1$ with probability $0.1$ ; right terminates immediately with reward $0$ . Under $π$ , every terminating trajectory has return $1$ and $v_{π} (s) = 1$ . For a trajectory with $n$ left-loops before termination the ratio is $ρ = (1/0.5)^{n} = 2^{n}$ . The second moment $E_{b} [(ρG)^{2}]$ becomes $0.1 \sum_{k = 0}^{\infty} 0. 9^{k} 2^{2 k + 1}$ , a geometric series with ratio $1.8 > 1$ that diverges to infinity. The estimator is unbiased but its variance is infinite — rare trajectories receive astronomically large weights.

Scope — what to prioritize for the examination: You should be able to write the per-step ratio, form the product along any short trajectory, and compute both OIS and WIS from given $ρ$ and $G$ values. You should understand in words why the WIS denominator is random and why that creates finite-sample bias that decays with data. The formal infinite-variance derivation and discounting-aware or per-decision refinements are background — they explain why long episodes are problematic and how advanced methods help, but they are below the focus for computation.

16.2.3 Off-Policy Monte Carlo Prediction and Control — Algorithm

This subsection uses the procedural spine: purpose, inputs and outputs, steps, trace, and cost. The material singled out in class as requiring careful study is the algorithm underlying Section 8 of the off-policy Monte Carlo notes — the incremental weighted-importance-sampling prediction and its extension to control.

The algorithm has a clear purpose that motivates every later detail.

Purpose — what the incremental algorithm solves: The batch WIS formula needs all episodes in memory to form sums over $T (s)$ . The incremental form processes episodes one at a time, sweeping backward, maintaining a running estimate that after each episode equals the batch WIS estimate so far. It is the practical bridge from the statistical formula to an episode-by-episode update loop that also underlies off-policy control.

With the purpose clear, the data the algorithm needs can be described precisely.

Inputs and outputs: Inputs are the target policy $π$ , the behaviour policy $b$ , a discount factor $γ \in [0, 1]$ , a state-action value table $Q (s, a)$ initialized arbitrarily, and a cumulative-weight table $C (s, a)$ initialized to zero. For control, the target policy is not fixed: it is defined as the greedy policy with respect to the current $Q$ , updated after each backward step. The output after many episodes is an estimate $Q \approx q_{π}$ (prediction) or $Q \approx q_{*}$ with $π (s) = ar g max_{a} Q (s, a)$ (control), learned from $b$ -generated episodes.

Symbols used below: $S_{t}, A_{t}, R_{t + 1}$ is the state, action, reward at step $t$ ; $T$ is the termination time; $G$ is the return built backward as $G \leftarrow γ G + R_{t + 1}$ ; $W$ is the cumulative importance weight from the suffix already processed; $C (s, a)$ is the sum of weights applied to $(s, a)$ so far.

With inputs defined, the backward scan that ties them together can be stated step by step.

Steps — the backward incremental loop: The algorithm generates one episode with $b$ and then scans it from the end to the beginning. At each step it accumulates the return, updates the weighted average for that state-action, improves the target policy greedily, and checks whether it can continue.

Initialize $Q (s, a)$ arbitrarily for all $s, a$ ; set $C (s, a) \leftarrow 0$ ; set the initial target $π (s) \leftarrow ar g max_{a} Q (s, a)$ with ties broken consistently.
For each episode: choose $b$ as any soft policy that covers the current greedy $π$ ; generate a complete episode $S_{0}, A_{0}, R_{1}, \dots, S_{T - 1}, A_{T - 1}, R_{T}$ using $b$ .
Set $G \leftarrow 0$ (return accumulator, built backward) and $W \leftarrow 1$ (suffix weight accumulator, starts as the empty product).
Loop for $t = T - 1, T - 2, \dots, 0$ (backward scan):

(a) $G \leftarrow γ G + R_{t + 1}$ — extend the return to include this step's reward.
(b) $C (S_{t}, A_{t}) \leftarrow C (S_{t}, A_{t}) + W$ — add the current suffix weight to the denominator for this pair.
(c) $Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + \frac{W}{C ( S _{t} , A _{t} )} [G - Q (S_{t}, A_{t})]$ — weighted incremental average: move the estimate a fraction $W / C$ toward the observed return $G$ .
(d) $π (S_{t}) \leftarrow ar g max_{a} Q (S_{t}, a)$ — improve the target policy greedily (control variant; in prediction $π$ stays fixed and this step is omitted).
(e) If $A_{t} \neq = π (S_{t})$ then break the inner loop — the deterministic target would never have taken this action, so $π (A_{t} ∣ S_{t}) = 0$ ; every earlier suffix ratio contains this zero factor and contributes nothing further.
(f) $W \leftarrow W \cdot \frac{1}{b ( A _{t} ∣ S _{t} )}$ — extend the weight backward: since $π$ is deterministic greedy, $π (A_{t} ∣ S_{t}) = 1$ for the actions that survived the break test, so the ratio simplifies to $1/ b (A_{t} ∣ S_{t})$ . In the prediction case with stochastic $π$ , the factor is $π (A_{t} ∣ S_{t}) / b (A_{t} ∣ S_{t})$ .

Why the break condition appears: Once a non-greedy action is encountered going backward, the importance ratio for every earlier time includes a factor $π (A_{t} ∣ S_{t}) = 0$ , making all earlier weights zero. There is no point updating earlier states in that episode for a deterministic target.

What the abstract loop does is clearest when traced over two concrete episodes.

Trace — two-episode line-world control: States $w, x, y, z$ with terminal exits. Action Exit at $w$ gives $- 100$ , at $z$ gives $+ 10$ ; moves between $x$ and $y$ give $0$ . Behaviour $b$ chooses $L, R$ each with $0.5$ in $x, y$ ; discount $γ = 0.9$ .

Episode 1 generated by $b$ : $x R, 0 y R, 0 z Exit, + 10 T$ .

Backward scan: At $z$ : $G = 10$ , $C (z, Exit) = 1$ , $Q (z, Exit) = 10$ . At $y$ : $G = 0 + 0.9 \cdot 10 = 9$ , $C (y, R) = 1$ , $Q (y, R) = 9$ , $π (y) = R$ , $W \leftarrow 1/0.5 = 2$ . At $x$ : $G = 0 + 0.9 \cdot 9 = 8.1$ , $C (x, R) = 2$ , $Q (x, R) = 8.1$ , $π (x) = R$ , $W \leftarrow 2/0.5 = 4$ . So after episode 1, $Q (x, R) = 8.1, Q (y, R) = 9$ .

Episode 2 generated by $b$ : $x L, 0 w Exit, - 100 T$ .

At $w$ : $G = - 100$ , $Q (w, Exit) = - 100$ . At $x$ : $G = 0 + 0.9 \cdot (- 100) = - 90$ , $C (x, L)$ becomes $1$ , $Q (x, L) = - 90$ . Now $Q (x, R) = 8.1 > Q (x, L) = - 90$ , so $π (x)$ remains $R$ . But the observed action at $x$ was $L \neq = π (x)$ , so the scan stops — no earlier update would be consistent with the greedy target. The target policy stays $π (x) = R, π (y) = R$ . Sense-check: The agent explored a poor left move; the off-policy update correctly learned that $L$ is bad without dragging the estimate for any still-earlier state down with it, because the break prevents contamination by target-inconsistent prefixes.

Complexity and cost — per episode the backward scan touches each step once: time $O (T)$ and memory $O (∣ S ∣∣ A ∣)$ for the tables. The practical limit is variance: when non-greedy actions are common, many episodes break early and only short suffixes contribute, so early states learn slowly. This "learning from tails" phenomenon is the main motivation for moving from Monte Carlo to temporal-difference methods that can learn from every transition.

When to use this versus alternatives: Use off-policy Monte Carlo control when you have episodic logs, need a greedy target, and can tolerate high variance in exchange for conceptual simplicity and model-freedom. Prefer on-policy Monte Carlo or temporal-difference methods when episodes are long, variance from product ratios is severe, or you need online step-by-step updates before termination. Per-decision and discounting-aware variants reduce variance without changing the idea; temporal-difference learning (next section) removes the need for full-episode weights entirely.

A domain connection that fixes the idea: in a logged recommender, $b$ is last quarter's production ranker that generated clicks, $π$ is the candidate ranker you want to evaluate, and each slate's ratio $\prod π (item ∣ context) / b (item ∣ context)$ reweights the observed click-through return. The tabular algorithm above is the textbook-scale version of that industrial counterfactual evaluation loop.

16.2.4 Worked Perspective on Importance Sampling Numerics

No single exhaustive numeric table was dictated in this session, but the preparation advice was explicit: work at least one small reweighting by hand until the product structure and the incremental backward perspective are automatic. Three compact exercises are provided below at increasing length.

Worked Example A — single three-step trajectory (the ratio product): A trajectory has states $s_{0}, s_{1}$ and actions $a_{1}, a_{2}$ : $s_{0} a_{1} s_{1} a_{2} s_{0} a_{1} T$ . Let $π (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$ . Then $ρ_{0 : 2} = \frac{0.8}{0.5} \cdot \frac{0.7}{0.4} \cdot \frac{0.8}{0.5} = 1.6 \times 1.75 \times 1.6 = 4.48$ If the observed return from $s_{0}$ is $G = 3$ , the ordinary importance-weighted return is $ρG = 13.44$ . Interpretation: $ρ > 1$ means this trajectory is more characteristic of the target than of the behaviour — a greedy-biased trajectory sampled by an exploratory behaviour — so its return is up-weighted.

Worked Example B — two returns, ordinary versus weighted: Two episodes starting from $X$ give $(G_{1} = 5.71096, ρ_{1} = 8.3333)$ and $(G_{2} = 4.59855, ρ_{2} = 0.4167)$ with $γ = 0.9$ (the long-trajectory example from the notes, six steps each). Then $V_{OIS} (X) = \frac{8.3333 \cdot 5.71096 + 0.4167 \cdot 4.59855}{2} = 24.7537$ $V_{WIS} (X) = \frac{8.3333 \cdot 5.71096 + 0.4167 \cdot 4.59855}{8.3333 + 0.4167} = 5.6580$ OIS is pulled far above both observed returns by the large weight on the first episode; WIS stays within the return range as a proper weighted average. Sense-check: Any WIS estimate with bounded returns must lie between the minimum and maximum observed returns — here between $4.59$ and $5.71$ — which $5.658$ does.

Worked Example C — incremental WIS update arriving weight by weight: Suppose weighted returns for a state arrive as $(W, G) = (2, 5), (1, 2), (3, 4)$ , processed incrementally with $V_{0} = 0, C_{0} = 0$ using $C \leftarrow C + W, V \leftarrow V + \frac{W}{C} (G - V)$ Step 1: $C = 2, V = 0 + \frac{2}{2} (5 - 0) = 5$ . Step 2: $C = 3, V = 5 + \frac{1}{3} (2 - 5) = 4$ . Step 3: $C = 6, V = 4 + \frac{3}{6} (4 - 4) = 4$ . Batch check: $(2 \cdot 5 + 1 \cdot 2 + 3 \cdot 4) / (2 + 1 + 3) = 24/6 = 4$ , matching the incremental result. Sense-check: The final batch weighted average must equal the incremental value after the last arrival — a useful examination verification.

Pitfalls in numerics:

Multiplying discounts into the ratio. The product $ρ$ involves only policy probabilities, never transition probabilities or $γ$ . Multiplying by powers of $γ$ or by $p (s^{'} ∣ s, a)$ is a common error.
Applying the full ratio to a prefix reward. Plain OIS applies $ρ_{t : T - 1}$ to the whole return $G_{t}$ . Attaching it only to the first reward underestimates the correction. (Per-decision variants deliberately refine this, but the base algorithm uses the full product — know which form the question asks for.)
Forgetting the break condition in control. Continuing the backward scan past a state where $A_{t} \neq = π (S_{t})$ adds updates that should have weight zero, corrupting $Q$ .

Recap and bridge: Off-policy Monte Carlo lets data from one policy speak about another by reweighting each trajectory with the product $\prod π / b$ ; the transition dynamics cancel, the expectation is corrected, but the product's variance can dominate. OIS divides by visit count and is unbiased but volatile; WIS divides by total weight, is asymptotically unbiased and far more stable. The incremental backward algorithm with accumulators $W$ and $C$ makes the batch estimate online and extends directly to control with a greedy target and an early-exit break. The next section replaces full-episode products with a local, low-variance alternative: temporal-difference learning, which bootstraps from the next estimate instead of waiting for the final return.

16.3 Temporal-Difference Learning

16.3.1 Temporal Difference as the Best of Both Worlds

Hook — the question that motivates everything in this section: If you already know your current estimate is partly wrong, should you wait until the journey ends to correct it, or correct it immediately using your next estimate — even though that next estimate is also imperfect? Temporal-difference learning answers: correct it immediately, and do it in a way that keeps the best of both alternatives.

Temporal-difference learning was framed in class as the method that takes the best of dynamic programming and the best of Monte Carlo. From dynamic programming it borrows bootstrapping — the idea of updating an estimate on the basis of another estimate rather than waiting for the final outcome. From Monte Carlo it borrows sampling and model-freedom — the ability to learn directly from raw experience without requiring a complete model of transition probabilities $p (s^{'}, r ∣ s, a)$ .

Intuition and analogy — the hill hiker and the driving home story: Picture a hiker in fog who wants to know the height of the hilltop. Dynamic programming is like having a perfect contour map: you can compute the height of any point from the heights of its neighbours, but you need the whole map in advance. Monte Carlo is like walking all the way to the top every time and then averaging the measured heights — no map needed, but each measurement requires the full walk. Temporal difference is like the hiker who walks one step, looks at the new estimated height under her boots plus the step she just climbed, and immediately adjusts the previous height estimate. She still walks (sampling), she still uses estimates of what lies ahead (bootstrapping), but she learns after every step instead of every expedition.

A concrete story used in the textbook makes the same point for prediction. You estimate that driving home will take 30 minutes. After five minutes you see rain and revise the remaining time to 35 minutes, so your total estimate becomes 40. After another 15 minutes you revise again. A Monte Carlo learner waits until you are home and then corrects the original 30 toward the true 43. A TD learner corrects the 30 toward 40 immediately after the rain observation, and later corrects the 40 toward the next estimate. Where the analogy breaks: In reinforcement learning the "remaining time" is not just observed — it is itself a learned value $v^(S_{t + 1}, w)$ that changes as learning proceeds, so the target moves while you chase it. That moving-target property is why step sizes and convergence conditions matter.

The conceptual comparison that was flagged as deceptively theoretical-looking but genuinely important is best seen as a table.

Dimension	Dynamic Programming	Monte Carlo	Temporal Difference (one-step)
Needs a model $p (s^{'}, r ∣ s, a)$	Yes — needs full distribution	No — learns from sampled episodes	No — learns from sampled transitions
Bootstraps (updates an estimate from another estimate)	Yes — $V (S_{t}) \leftarrow E [R + γ V (S_{t + 1})]$	No — $V (S_{t}) \leftarrow G_{t}$ waits for final return	Yes — $V (S_{t}) \leftarrow R_{t + 1} + γ V (S_{t + 1})$
When it can learn	After a full sweep over states	Only at episode end	After every single transition
Bias / variance tendency	Low variance, but model bias if model is wrong	Unbiased, high variance (depends on full return)	Biased (target depends on current estimate), lower variance than Monte Carlo
Typical use	Planning with known model	Episodic prediction and control without model	Online prediction and control, continuing tasks, long episodes

When to pick which: Use dynamic programming when you have a trustworthy model and need exact sweeps. Use Monte Carlo when you have episodic data and want unbiased estimates without bootstrapping. Use temporal difference when you need online, incremental, model-free learning — especially for long or continuing tasks where waiting for termination is impractical.

Why the "best of both" claim is not just a slogan: Monte Carlo target $G_{t} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{T - t - 1} R_{T}$ is an unbiased sample of $v_{π} (S_{t})$ but has high variance because it sums many random rewards. Dynamic programming target $E [R_{t + 1} + γ v_{π} (S_{t + 1}) ∣ S_{t}]$ has lower variance but requires the model expectation. Temporal difference replaces the unknown true value $v_{π} (S_{t + 1})$ with the current estimate $V (S_{t + 1})$ and replaces the model expectation with a single sample transition $(S_{t}, R_{t + 1}, S_{t + 1})$ . The result is a model-free, single-step, bootstrapped target that trades a small bias for a large reduction in variance and wait time. Multi-step TD generalizes this trade-off over horizons $n = 1, 2, \dots$ before falling back to a learned estimate.

Visual intuition — imagine a spectrum drawn horizontally from "full model, full bootstrapping" on the left (dynamic programming) to "no model, no bootstrapping" on the right (Monte Carlo). Mark one-step TD just right of centre: it samples like Monte Carlo but bootstraps after one step like dynamic programming. Further to the right lie $n$ -step TD methods that sample $n$ rewards before bootstrapping; at $n = T - t$ they reach Monte Carlo. The diagram shows that all three families are points on one continuum, not separate islands. The professor's visual with exhaustive search at one extreme and TD at the most compact alternative conveys the same width-versus-depth trade-off: TD achieves the best blend.

Scope — when the one-step TD idea applies: The one-step TD prediction update described here assumes a Markov decision process with states $S_{t} \in S$ , rewards $R_{t + 1} \in R$ , discount $γ \in [0, 1]$ , and a fixed policy $π$ being evaluated. It applies to both episodic and continuing tasks. It does not require a model, but it does require that the value estimate $V$ be stored for every visited state (tabular case) or parametrized smoothly (function approximation, later section). It breaks down as a reliable estimator if the step size $α$ is too large or if the bootstrapped estimate $V (S_{t + 1})$ is extremely inaccurate early in learning — the same moving-target issue noted above.

With the scope clear, the practical habits that prevent mistakes become important.

Pitfalls to avoid:

Treating TD as "just an approximation to Monte Carlo." It is not an approximation that will converge to the same finite-sample answer. Under batch updating, TD converges to the certainty-equivalence estimate (the value that would be correct if the maximum-likelihood model built from the data were the true environment), while Monte Carlo converges to the minimum mean-squared-error estimate on the training returns. They are answers to different questions.
Confusing bootstrapping with cheating. Learning a guess from a guess sounds circular, but the TD target $R_{t + 1} + γ V (S_{t + 1})$ contains fresh information — the real reward $R_{t + 1}$ and the real next state $S_{t + 1}$ — that the old estimate $V (S_{t})$ did not have. That is what makes the update informative.

In the broader field, one-step TD is the atomic operation inside virtually every modern reinforcement learning paper — from Q-learning to actor-critic to the value head of AlphaGo. Understanding the vocabulary "TD target" and "TD error" introduced here is therefore not just examinable; it is the shared language for reading any contemporary algorithm.

Recap and bridge: Temporal difference sits at the intersection of dynamic programming's bootstrapping and Monte Carlo's sampling, giving model-free, online, low-variance updates at the cost of a transient bias. The next subsection formalizes the two terms that carry that idea — the TD target and the TD error — and extends them to the $n$ -step case that will later connect this section to eligibility traces.

16.3.2 Mathematical Formulation — Targets, Errors and Updates

Starting from the Bellman identity makes the TD construction transparent.

The Bellman starting point: For a fixed policy $π$ , the true state value is the mean discounted return $v_{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$ where $G_{t} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{T - t - 1} R_{T}$ is the return, $R_{k + 1}$ the reward on transitioning $S_{k} \to S_{k + 1}$ , $γ \in [0, 1]$ the discount factor, and $T$ the termination time. By splitting off the first reward, $v_{π} (s) = E_{π} [R_{t + 1} + γ G_{t + 1} ∣ S_{t} = s] = E_{π} [R_{t + 1} + γ v_{π} (S_{t + 1}) ∣ S_{t} = s]$ Here $S_{t}$ is the state at time $t$ , $S_{t + 1}$ the next state, $R_{t + 1}$ the immediate reward, and $E_{π} [\cdot ∣ S_{t} = s]$ the expectation over the policy and the environment dynamics starting from $s$ . The Monte Carlo target estimates the first line by sampling $G_{t}$ ; the dynamic programming target uses the second line with a model expectation; the TD target samples the second line.

With the Bellman identity in hand, the TD target and error follow directly.

One-step TD target and TD error (tabular prediction): Let $V (S)$ denote the current tabular estimate of $v_{π} (S)$ , with $V (terminal) = 0$ . On observing the transition $S_{t} R_{t + 1} S_{t + 1}$ , define

the one-step TD target (also called the one-step return $G_{t : t + 1}$ ):

$G_{t}^{(1)} = R_{t + 1} + γ V (S_{t + 1})$

the one-step TD error (the quantity universally called $δ_{t}$ ):

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

Every symbol: $R_{t + 1} \in R$ is the immediate reward; $γ \in [0, 1]$ is the scalar discount factor; $V (S_{t + 1})$ is the current estimated value of the next state (defined as $0$ if $S_{t + 1}$ is terminal); $V (S_{t})$ is the current estimated value of the current state; $δ_{t} \in R$ is a signed scalar that is positive when the transition turned out better than predicted and negative when it turned out worse. When function approximation is used, $V (S)$ becomes $v^(S, w)$ parametrized by weight vector $w$ , but the form of target and error is identical.

The tabular one-step TD prediction update is then $V (S_{t}) \leftarrow V (S_{t}) + α δ_{t} = V (S_{t}) + α [R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})]$ where $α \in (0, 1]$ is the step-size parameter. This is TD(0), the simplest TD method.

The relationship between Monte Carlo error and TD errors clarifies why TD is a decomposition of the same information. Assume for a moment that $V$ does not change during the episode (as in batch Monte Carlo). Then by expanding $G_{t} - V (S_{t})$ with the identity $G_{t} = R_{t + 1} + γ G_{t + 1}$ :

$G_{t} - V (S_{t}) = R_{t + 1} + γ G_{t + 1} - V (S_{t}) + γ V (S_{t + 1}) - γ V (S_{t + 1}) = δ_{t} + γ (G_{t + 1} - V (S_{t + 1})) = δ_{t} + γ δ_{t + 1} + γ^{2} δ_{t + 2} + \dots + γ^{T - t - 1} δ_{T - 1}$

so that

$G_{t} - V (S_{t}) = k = t \sum T - 1 γ^{k - t} δ_{k}$

where each $δ_{k} = R_{k + 1} + γ V (S_{k + 1}) - V (S_{k})$ is the TD error at step $k$ , and $V (S_{T}) = 0$ for the terminal state. In words: the Monte Carlo error (how far the full sampled return is from the current estimate) equals the discounted sum of one-step TD errors along the trajectory. When $V$ is updated online, the identity holds only approximately, with an additional correction for the changing $V$ ; the approximation is good when $α$ is small. This decomposition is the algebraic reason $n$ -step methods can interpolate between TD(0) and Monte Carlo.

Multi-step targets generalize the same idea over $n$ real rewards before bootstrapping. For $n \geq 1$ and $0 \leq t < T - n$ ,

$G_{t}^{(n)} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{n - 1} R_{t + n} + γ^{n} V (S_{t + n})$

with the convention $G_{t}^{(n)} = G_{t}$ when $t + n \geq T$ (the window reaches termination and no bootstrap is needed). Here $R_{t + k}$ is the reward $k$ steps after $t$ , $S_{t + n}$ the state $n$ steps ahead, and $V (S_{t + n})$ the current estimate there. The $n$ -step TD error is $G_{t}^{(n)} - V (S_{t})$ , and the $n$ -step TD update is

$V (S_{t}) \leftarrow V (S_{t}) + α [G_{t}^{(n)} - V (S_{t})]$

The choice $n = 1$ recovers TD(0); as $n \to \infty$ (or $n \geq T - t$ ) it recovers Monte Carlo. The backup diagram for $n$ -step TD is a chain of $n$ sampled states, rewards and bootstrapped value — the visual bridge between the one-step TD diagram (one sampled successor) and the Monte Carlo diagram (chain to termination).

For action values, the same construction applies with $Q (S, A)$ in place of $V (S)$ . With function approximation, $V (S)$ becomes $v^(S, w)$ and the gradient-based form $w \leftarrow w + α δ_{t} \nabla_{w} v^(S_{t}, w)$ appears; the semi-gradient subtlety — that the target's dependence on $w$ through $V (S_{t + 1})$ is ignored when differentiating — belongs to the function-approximation section and is not needed for the tabular derivations here.

Scope — what the formulas assume: The identities above assume the Markov property (the future depends on the present state, not the full history), a well-defined discount $γ$ , and tabular storage where each $V (S)$ can be updated independently. They hold exactly for the batch viewpoint where $V$ is frozen during the expansion; online, they describe the direction of the update rather than an exact equality. Convergence of TD(0) to $v_{π}$ with probability 1 requires the usual stochastic-approximation step-size conditions ( $\sum α_{t} = \infty$ , $\sum α_{t}^{2} < \infty$ ) and that every state is visited infinitely often — covered formally in later analysis.

Exam note: Be able to write down the one-step TD target $R_{t + 1} + γ V (S_{t + 1})$ , the TD error $δ_{t} = R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})$ , and the multi-step target $G_{t}^{(n)}$ from memory, with every symbol defined. Expect to identify which $n$ a given update uses from its form, and to explain why TD(0) bootstraps while Monte Carlo does not. The derivation $G_{t} - V (S_{t}) = \sum γ^{k - t} δ_{k}$ is the bridge to the next chapter and is worth being able to reproduce.

16.3.3 Worked Examples — Grid World, Random Walks and the Control Loop

This subsection follows the procedural spine: purpose, inputs and outputs, steps, trace, and cost.

Purpose — why worked examples are the core here: Prediction formulas are compact, but control is where students stumble. The grid-world running example and the random-walk extra problems exist to make the abstract loop — choose an action from $Q$ , observe a transition, form a target, update one $Q$ entry, and thereby change the policy — concrete and traceable cell by cell.

With that purpose in mind, the data that flow through one control step can be listed explicitly.

Inputs and outputs of one tabular control step: Inputs are a small grid world where each cell is a state $s$ , the set of movement actions $A (s)$ (typically up, down, left, right), a reward function $R (s, a, s^{'})$ (for example $- 1$ per step, $+ 10$ for reaching a goal, $- 10$ for an undesirable terminal), a discount $γ$ , a step size $α$ , an exploration parameter $ϵ \in [0, 1]$ , and the current action-value table $Q (s, a)$ for all state-action pairs with $Q (terminal, \cdot) = 0$ . Output is the single updated entry $Q (S, A)$ and, implicitly, the new $ϵ$ -greedy policy at state $S$ derived from the updated $Q$ .

Symbols: $Q (s, a) \in R$ is the estimated mean return starting from $s$ , taking $a$ , then following the current policy; $ϵ$ is the probability of exploring a non-greedy action; $α$ scales the incremental correction.

Once inputs and outputs are clear, the loop that uses them can be stated step by step.

Steps — the representative control loop as narrated in class:

In state $S$ , choose action $A$ using the policy derived from the current $Q$ . For $ϵ$ -greedy: with probability $1 - ϵ$ pick $A^{*} = ar g max_{a} Q (S, a)$ (break ties arbitrarily but consistently); with probability $ϵ$ pick uniformly among the non-greedy actions. Consulting all $Q (S, \cdot)$ at that state is the entire policy.
Execute $A$ , observe reward $R$ and next state $S^{'}$ .
Form the algorithm-specific target:

SARSA: $R + γ Q (S^{'}, A^{'})$ where $A^{'}$ is the action actually taken in $S^{'}$ under the same $ϵ$ -greedy policy.
Q-learning: $R + γ max_{a} Q (S^{'}, a)$ .
Mean SARSA: $R + γ \sum_{a} π (a ∣ S^{'}) Q (S^{'}, a)$ where $π$ is the current policy.

Compute $δ = target - Q (S, A)$ and update $Q (S, A) \leftarrow Q (S, A) + α δ$ .

Because $Q (S, A)$ changed, the implied policy at $S$ automatically changes. Iterating this loop improves both $Q$ and the policy it implies. No separate "policy update" statement is needed beyond the $Q$ update — improving $Q$ is improving the policy.

The phrase emphasized in class — "when I update the $Q$ -value, I am updating the policy as well" — captures the tight coupling that surprises students who expect an explicit policy table.

Visual intuition — picture the grid with each cell containing a small table of four $Q$ -values (one per action). An arrow in the cell points toward the greedy action (the largest $Q$ ). One update changes a single number in one cell's table, which may flip the arrow in that cell. Over many episodes the arrows gradually swing toward the goal, carving a policy path through the grid. $ϵ$ -greedy exploration occasionally forces a non-arrow action, which is how new cells get visited.

Worked trace — one step of the grid-world control loop with numbers: Consider a $3 \times 3$ grid where position $(1, 1)$ is the start, $(3, 3)$ is a goal with reward $+ 10$ on entry, every other move gives reward $- 1$ , $γ = 0.9$ , $α = 0.5$ , $ϵ = 0.1$ . Suppose the current $Q$ -values at the critical states are: $Q (S = (2, 2), up) = 1.0, Q (S, down) = 0.2, Q (S, left) = 0.5, Q (S, right) = 1.8$ and at the successor state $S^{'} = (2, 3)$ : $Q (S^{'}, up) = 2.0, Q (S^{'}, down) = 0.8, Q (S^{'}, left) = 1.5, Q (S^{'}, right) = - 0.5$

SARSA trace: Policy at $S$ is $ϵ$ -greedy; the greedy action is right ( $1.8$ ). Suppose exploration does not happen and $A = right$ is chosen. Executing right yields $R = - 1$ and $S^{'} = (2, 3)$ . Now choose $A^{'}$ at $S^{'}$ $ϵ$ -greedily — suppose the greedy action up ( $2.0$ ) is chosen. SARSA target $= R + γ Q (S^{'}, A^{'}) = - 1 + 0.9 \times 2.0 = 0.8$ . Error $δ = 0.8 - Q (S, A) = 0.8 - 1.8 = - 1.0$ . Update $Q (S, right) \leftarrow 1.8 + 0.5 (- 1.0) = 1.3$ . After the update, the $Q$ -values at $S$ become $1.0, 0.2, 0.5, 1.3$ and the greedy arrow at $S$ now points to right still, but less strongly — the policy shifted because its underlying numbers did.

Q-learning on the same transition: Target $= R + γ max_{a} Q (S^{'}, a) = - 1 + 0.9 \times 2.0 = 0.8$ as well (here the actually taken $A^{'}$ happened to be the maximizing action). If instead $A^{'}$ had been a non-greedy action, SARSA's target would have used that non-greedy $Q$ while Q-learning would still use the max — the source of their different behaviour under persistent $ϵ$ -greedy exploration, detailed in the next subsection.

Sense-check: Any update must move $Q (S, A)$ toward the target. Here $Q (S, right)$ was $1.8$ and the target estimate was $0.8$ , so the value correctly moves downward. If a trace moves a $Q$ away from its target, the sign of $δ$ was applied incorrectly.

The random-walk extra-practice problems are the prediction-side counterpart. The textbook five-state walk $A$ – $B$ – $C$ – $D$ – $E$ with start at $C$ , reward $+ 1$ on terminating right and $0$ elsewhere, and undiscounted $γ = 1$ , has true values $v_{π} (A) = 1/6, v_{π} (B) = 2/6, v_{π} (C) = 3/6, v_{π} (D) = 4/6, v_{π} (E) = 5/6$ for the equiprobable random policy. Initializing $V (s) = 0.5$ for all $s$ and running TD(0) with $α = 0.1$ , the estimates after 100 episodes closely approach the true values and converge faster in root mean-squared error than constant- $α$ Monte Carlo. Under batch updating, Monte Carlo converges to the sample-average returns (minimum squared error on the training set) while TD converges to the certainty-equivalence estimate — unbiased for the maximum-likelihood model of the Markov chain — which often predicts future data better.

Pitfalls in the control loop:

Storing a separate policy table unnecessarily. In tabular TD control the policy is the argmax of $Q$ . Maintaining an independent policy array that you forget to update after changing $Q$ creates an inconsistency that no longer matches what the algorithm does.
Forgetting the terminal condition. $Q (S_{t + 1}, \cdot)$ or $V (S_{t + 1})$ is defined as $0$ when $S_{t + 1}$ is terminal. Leaving the old value in place adds a phantom bootstrap.
Mixing up which $Q$ the examination expects. The notes sometimes summarize a lengthy algorithm for space. For numerics, compare the slide version with the notes version and commit to the one used in the class worked example — they are conceptually identical but may differ in where $ϵ$ -greedy action selection appears in the listing.

16.3.4 Three Tabular Control Algorithms — SARSA, Q-Learning and Expected SARSA

Each of the three algorithms should be recognizable on sight from its update target. The table below contrasts them on the dimensions that matter for understanding and for the examination.

Dimension	SARSA (on-policy)	Q-learning (off-policy)	Expected SARSA
Full name / mnemonic	State–Action–Reward–State–Action $(S, A, R, S^{'}, A^{'})$	—	Expectation over next actions under $π$
Update equation	$Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1}) - Q (S_{t}, A_{t})]$	$Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ a max Q (S_{t + 1}, a) - Q (S_{t}, A_{t})]$	$Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ a \sum π (a ∣ S_{t + 1}) Q (S_{t + 1}, a) - Q (S_{t}, A_{t})]$
Which next action does the target use?	The action $A_{t + 1}$ actually taken under the behaviour policy $π$	The greedy action $ar g max_{a} Q (S_{t + 1}, a)$ regardless of what was taken	The expected value over all next actions weighted by $π (a ∣ S_{t + 1})$
On- versus off-policy (why)	On-policy: evaluates and improves the same $ϵ$ -greedy policy it follows, because the target contains the sampled $A_{t + 1}$	Off-policy: learns values for the greedy policy while behaving $ϵ$ -greedily, because the max decouples behaviour from target	Can be either: on-policy when $π$ is the behaviour, off-policy when $π$ is a different target (then it generalizes Q-learning)
Variance of target	Higher — depends on the random $A_{t + 1}$	Lower target variance from max, but introduces maximization bias	Lowest variance — averages over the randomness of $A_{t + 1}$
Behaviour under persistent $ϵ$ -greedy exploration	Learns the value of the exploratory policy; tends to find safer paths (accounts for the fact that exploration will happen)	Learns the value of the greedy policy; can find the optimal path in value but may still stumble during online execution because it ignores exploration risk	Retains SARSA's safety advantage with less variance; often outperforms both in cliff-walking experiments
Classic illustration	Windy gridworld; safer cliff path	Optimal cliff-edge path in value; poorer online return while $ϵ > 0$	Best interim and asymptotic performance on cliff walking at larger $α$

When to pick which: Use SARSA when online safety under the actual exploratory behaviour matters — robotics with constraints, or any task where a random exploratory action can be costly. Use Q-learning (and its deep extension) when the goal is the optimal greedy value regardless of current exploration. Use Expected SARSA when you want SARSA-like safety with reduced variance, and can afford the small extra cost of summing over actions.

Formal definitions with symbols: In every equation below, $S_{t} \in S$ is the state, $A_{t} \in A (S_{t})$ the action, $R_{t + 1} \in R$ the reward, $S_{t + 1}$ the next state, $Q (s, a) \in R$ the current action-value estimate with $Q (terminal, \cdot) = 0$ , $α \in (0, 1]$ the step size, $γ \in [0, 1]$ the discount, and $π (a ∣ s)$ the policy probability. For $ϵ$ -greedy, $π (a ∣ s) = 1 - ϵ + ϵ /∣ A (s) ∣$ for the greedy $a^{*} = ar g max_{a} Q (s, a)$ and $ϵ /∣ A (s) ∣$ otherwise.

SARSA target: $R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1})$ where $A_{t + 1} \sim π (\cdot ∣ S_{t + 1})$ . The quintuple $(S_{t}, A_{t}, R_{t + 1}, S_{t + 1}, A_{t + 1})$ names the algorithm.
Q-learning target: $R_{t + 1} + γ max_{a} Q (S_{t + 1}, a)$ . The max makes the update off-policy: the target is greedy even when behaviour is $ϵ$ -greedy.
Expected SARSA target: $R_{t + 1} + γ \sum_{a} π (a ∣ S_{t + 1}) Q (S_{t + 1}, a) = R_{t + 1} + γ E_{π} [Q (S_{t + 1}, \cdot) ∣ S_{t + 1}]$ . When $π$ is greedy this equals the Q-learning target; in general it is the expectation SARSA moves toward in mean.

Visual intuition — the backup diagrams tell the story at a glance. SARSA's diagram is a chain $S_{t}, A_{t}, R_{t + 1}, S_{t + 1}, A_{t + 1}$ — a sample action node follows the sample state. Q-learning's diagram fans out from $S_{t + 1}$ to all possible action nodes with an arc across them indicating the max — the target looks at the best branch regardless of which was taken. Expected SARSA's diagram is the same fan-out but weighted by $π$ — an average over branches rather than a max.

Worked comparison — same episode, different targets: States $A$ and $B$ are non-terminal, then terminal. From $A$ only action go leads to $B$ with reward $0$ . From $B$ two actions end the episode: safe gives $+ 1$ , risky gives $- 1$ . Discount $γ = 1$ , step size $α = 0.5$ . Current estimates: $Q (A, go) = 0.5$ , $Q (B, safe) = 0.8$ , $Q (B, risky) = 0.2$ . Observed episode (due to $ϵ$ -greedy exploration): $(A, go, 0, B, risky)$ , $(B, risky, - 1, terminal)$ .

SARSA: Update $Q (A, go)$ uses the taken next action risky: target $= 0 + Q (B, risky) = 0.2$ . New $Q (A, go) = 0.5 + 0.5 (0.2 - 0.5) = 0.35$ . Update $Q (B, risky)$ : target $= - 1$ , new $Q (B, risky) = 0.2 + 0.5 (- 1 - 0.2) = - 0.40$ . Interpretation: because exploration forced risky, SARSA pulls the value of go downward to reflect what actually happens under the behaviour.

Q-learning: Update $Q (A, go)$ uses the greedy next action at $B$ : target $= 0 + max {0.8, 0.2} = 0.8$ . New $Q (A, go) = 0.5 + 0.5 (0.8 - 0.5) = 0.65$ . Update $Q (B, risky)$ is the same $- 0.40$ . Interpretation: Q-learning ignores the exploratory risky in the target and backs up the optimistic greedy continuation.

Expected SARSA (with $ϵ = 0.1$ , two actions): $π (safe ∣ B) = 0.95$ , $π (risky ∣ B) = 0.05$ if safe is greedy. Target for $Q (A, go)$ $= 0 + 0.95 \times 0.8 + 0.05 \times 0.2 = 0.77$ . New $Q (A, go) = 0.5 + 0.5 (0.77 - 0.5) = 0.635$ — between SARSA and Q-learning, with less variance than SARSA. Sense-check: Any Expected SARSA target must lie between the SARSA target (worst single sample) and the Q-learning target (best) when the same $Q (B, \cdot)$ are used — here $0.2 < 0.77 < 0.8$ , which holds.

Pitfalls distinguishing the three:

Calling Q-learning "on-policy because it uses $ϵ$ -greedy for action selection." Action selection is behaviour; the target's use of max is what makes it off-policy. Behaviour can be $ϵ$ -greedy in all three algorithms — the difference is only in the target.
*Forgetting that Expected SARSA with a greedy $π$ is Q-learning.* When $π$ puts probability 1 on $ar g max_{a} Q (S_{t + 1}, a)$ , the expectation collapses to the max. This is why the text says Expected SARSA subsumes Q-learning.
Using the wrong sum in Expected SARSA. The expectation is over next actions $a$ at $S_{t + 1}$ weighted by $π (a ∣ S_{t + 1})$ , not over current actions. Summing over $A_{t}$ is a common transcription error.

16.3.5 Maximization Bias and Double Q-Learning

Hook — the statistical trap hidden inside the max: Suppose every action at a state is truly worthless — true value zero — but your estimates are noisy, some above zero, some below. If you take the maximum of those noisy estimates, will you get zero? No. You will get something positive, because the noise that happens to push an action upward is the noise that gets selected. Q-learning does exactly this on every update, and the bias accumulates.

Maximization bias — why the max is systematically optimistic: Consider a single state $s$ where many actions $a$ have true value $q (s, a) = 0$ but estimated values $Q (s, a)$ are uncertain, distributed around zero — some above, some below. The true maximum is $max_{a} q (s, a) = 0$ . The estimated maximum $max_{a} Q (s, a)$ is the largest of those noisy samples, which is almost surely positive. In general, $E [max_{a} Q (s, a)] \geq max_{a} E [Q (s, a)]$ , with equality only when the maximizer is known with certainty. Because Q-learning's target contains $max_{a} Q (S_{t + 1}, a) - Q (S_{t}, A_{t})$ , this positive bias propagates: sampling noise makes the maximizing action look better than it truly is, Q-learning reinforces that optimism, and the agent can confidently prefer actions that are not in fact optimal — especially early in learning when estimates are noisiest. This is not a rare corner case; it is the reason Q-learning can be overoptimistic in stochastic environments.

A clean demonstration is the $A$ – $B$ MDP used in the textbook. State $A$ has two actions: right goes directly to terminal with reward $0$ ; left goes to state $B$ with reward $0$ , from which many actions all terminate with reward drawn from $N (- 0.1, 1)$ — mean $- 0.1$ , variance $1$ . Any trajectory starting with left therefore has expected return $- 0.1$ , so left is always the wrong choice at $A$ . Yet Q-learning with $ϵ$ -greedy ( $ϵ = 0.1$ , $α = 0.1$ , $γ = 1$ ) initially chooses left far more often than the 5\% minimum exploration rate, and even at asymptote takes left about $5%$ more often than optimal. The cause is maximization bias at $B$ : among the many noisy actions, one will by chance have a large positive sample that the max selects.

Double Q-learning removes the bias by decoupling selection from evaluation. Two action-value functions $Q_{1}$ and $Q_{2}$ are maintained, each an independent estimate of $q$ . On each transition a coin is flipped: with probability $0.5$ update $Q_{1}$ using $Q_{2}$ to evaluate the action that $Q_{1}$ selected, and otherwise the reverse.

Double Q-learning — algorithm: Initialize $Q_{1} (s, a), Q_{2} (s, a)$ arbitrarily with $Q_{1, 2} (terminal, \cdot) = 0$ . Behaviour is $ϵ$ -greedy with respect to $Q_{1} + Q_{2}$ (average or sum). On each step $S A, R S^{'}$ :

With probability $0.5$ :

$Q_{1} (S, A) \leftarrow Q_{1} (S, A) + α [R + γ Q_{2} (S^{'}, ar g a max Q_{1} (S^{'}, a)) - Q_{1} (S, A)]$

Otherwise:

$Q_{2} (S, A) \leftarrow Q_{2} (S, A) + α [R + γ Q_{1} (S^{'}, ar g a max Q_{2} (S^{'}, a)) - Q_{2} (S, A)]$ Every symbol: $Q_{1}, Q_{2}$ are the two independent estimators; $ar g max_{a} Q_{1} (S^{'}, a)$ is the action $Q_{1}$ considers best at $S^{'}$ (selection), $Q_{2} (S^{'}, \cdot)$ provides its value (evaluation), and vice versa. Here $R$ is $R_{t + 1}$ , $S$ is $S_{t}$ , $S^{'}$ is $S_{t + 1}$ , $A$ is $A_{t}$ , $α$ the step size, $γ$ the discount. Only one table is updated per step, so memory doubles but computation per step does not.

Because the action is selected using one noisy estimate and evaluated using an independent noisy estimate, the upward selection bias in the first is not reinforced by the second — the evaluation is unbiased in expectation for the selected action. Swapping roles keeps the two tables symmetric.

On the same $A$ – $B$ MDP, Double Q-learning is essentially unaffected by maximization bias: the fraction of left actions from $A$ stays near the exploration floor, matching the optimal policy's preference for right. Analogous double versions exist for SARSA and Expected SARSA.

Scope — when Double Q-learning matters: The bias is most harmful when the action set at a state is large, rewards are stochastic, and early estimates are noisy — all conditions where the max has many candidates to be optimistic about. In near-deterministic, low-noise tasks the bias is small and single Q-learning works well. Double Q-learning does not change the on/off-policy character; it is a bias-reduction refinement that can be combined with any of the three algorithms above.

A domain connection: in financial trading, auction bidding, or any recommender where many actions have similar true values but noisy realized rewards, a vanilla Q-learner will systematically overvalue the apparent best action and may deploy it with misplaced confidence. Double estimators are used precisely to keep that optimism in check.

Exam note: Be able to explain in words why the max causes a systematic positive bias (same samples used to select and to evaluate) and how Double Q-learning fixes it by using one estimator to select and the other to evaluate. The $A$ – $B$ MDP with Gaussian rewards at $B$ is the canonical illustration. You should also be able to write the Double Q-learning update with the selection and evaluation roles correctly assigned.

16.3.6 Student Questions and Answers on Temporal Difference

Q: How do I know what policy to use when the algorithm says "choose action $A$ from state $S$ using the policy derived from $Q$ "? A: Look at the current $Q$ -values for exactly that state $S$ . For each action $a$ available in $S$ there is a number $Q (S, a)$ . The greedy action is the $a$ with the largest $Q (S, a)$ ; with $ϵ$ -greedy that greedy action is taken most of the time and a non-greedy action is explored with probability $ϵ$ . Concretely, if $∣ A (S) ∣$ is the number of actions and $a^{*} = ar g max_{a} Q (S, a)$ , then $π (a^{*} ∣ S) = 1 - ϵ + ϵ /∣ A (S) ∣$ and $π (a ∣ S) = ϵ /∣ A (S) ∣$ for every other $a$ . Knowing the $Q$ -values and knowing $ϵ$ is sufficient to determine the full action-selection distribution — no additional policy object needs to be stored separately.

The next question shifts from how to select an action to what happens to the policy when values change.

Q: When I update $Q$ , am I also updating the policy or is there a separate policy-update step? A: The update to $Q (S, A)$ is itself a policy update. Because the policy at $S$ is defined as the maximizer (or $ϵ$ -soft maximizer) of $Q (S, \cdot)$ , any change to $Q (S, A)$ immediately changes which action the derived policy prefers at $S$ , or with what probability. There is no separate "now update the policy" line in the SARSA or Q-learning pseudocode beyond the greedy improvement implied by the new $Q$ . Iteratively improving $Q$ entry by entry is how the policy improves — this tight coupling is why the class emphasized "when I update the $Q$ -value, I am updating the policy as well."

A final practical question concerns which printed algorithm to trust when sources differ in length.

Q: The algorithm block in the notes for SARSA or Q-learning looks shorter than the one in the slides. Which one should I use for numerics? A: The notes sometimes summarize a lengthy algorithm for space — for example collapsing the $ϵ$ -greedy selection or the terminal-state handling into fewer lines — because a fully expanded listing would be long. For solving problems, what matters is that the algorithm you actually apply matches the one used to produce the class worked example. Compare the notes version and the slides version for that algorithm, decide on one, and stay consistent when you solve examination-style numerics. The three targets — SARSA's sampled $Q (S^{'}, A^{'})$ , Q-learning's $max_{a} Q (S^{'}, a)$ , and Expected SARSA's $\sum_{a} π (a ∣ S^{'}) Q (S^{'}, a)$ — must be exactly as practiced, because the arithmetic depends on which target you use.

Recap and bridge: This section built the TD target $R_{t + 1} + γ V (S_{t + 1})$ and error $δ_{t}$ , showed how the control loop turns a single $Q (S, A)$ update into a policy improvement, distinguished the three tabular control algorithms by their targets, and explained why the max in Q-learning creates a systematic overestimation that Double Q-learning removes by separating selection from evaluation. With tabular TD in hand, the next section asks what happens when the state space is too large for a table and the value function must be approximated — the step from tables to parametrized functions that leads toward deep methods.

16.4 On-Policy Prediction with Function Approximation

16.4.1 Why Function Approximation and the Textbook Summary Image

Hook — what if your table has more rows than atoms in the universe? Backgammon has about $1 0^{20}$ states, Go about $1 0^{170}$ , and a robot camera sees a new $84 \times 84 \times 4$ image every frame. A table that stores one number per state cannot even be allocated, let alone filled. How do you learn a value function when you can never visit most states?

Function approximation answers by replacing a separate table entry for every state with a single parametrized function that generalizes across states. Instead of $v^(s)$ with one independent parameter per $s$ , you maintain $v^(s, w)$ where $w \in R^{d}$ with $d ≪ ∣ S ∣$ is a shared weight vector and $x (s) \in R^{d}$ is a feature representation of $s$ . Updating $w$ on one state changes the estimated value of many other states that share features — that is the entire point and the entire risk.

Intuition and analogy — painting a landscape with a small palette: Think of true values $v_{π} (s)$ as a detailed landscape with a height at every location. Tabular learning is like setting the height of each location independently with a separate peg — exact but impossible when there are billions of locations. Function approximation is like painting the landscape with a limited set of brush strokes (the features) blended by adjustable weights. One brush stroke affects a region, not a single point, so you can paint the whole landscape quickly, but you can never match every bump exactly. The question becomes: which regions should match best? That weighting is the state distribution $μ (s)$ introduced below. Where the analogy breaks: A painter can add more colors freely; an approximator with fixed $d$ has a permanent capacity limit, and the interaction of bootstrapping, off-policy data, and approximation can even cause divergence — a painting never diverges no matter how you mix.

The textbook image reproduced in both the slides and the notes makes the same point from the search perspective. Picture a two-dimensional trade-off diagram.

Visual intuition — imagine a square whose horizontal axis is breadth (how many actions you sample at a frontier) and vertical axis is depth (how far you follow a trajectory before evaluating). The bottom-right corner is exhaustive search — the full tree expansion familiar from classical AI search where every branch is enumerated to terminal depth. The top-left corner is one-step temporal-difference learning — the most compact alternative that samples one action, observes one reward, and bootstraps immediately. The two interior quadrants prioritize breadth-first sampling versus depth-first rollout. Temporal-difference achieves the best blend: it samples like Monte Carlo but bootstraps like dynamic programming, sitting closest to the ideal of low computation per update and rapid propagation of information. The professor highlights this image because it connects the classical search intuition from the earlier AI course to the compact backup used throughout reinforcement learning.

Scope — when the on-policy prediction formulation applies: The objective and algorithms in this section assume on-policy data — states $S_{t}$ are encountered by following the same policy $π$ whose value $v_{π}$ is being estimated, and the state-weighting $μ (s)$ is the on-policy distribution (stationary distribution for continuing tasks, normalized visitation frequency for episodic tasks). The approximator $v^(s, w)$ must be differentiable in $w$ . State features $x (s)$ are assumed given. The theory in this section does not guarantee convergence for off-policy bootstrapping with approximation — that failure mode belongs to the next chapter's divergence examples.

That scope sets up the practical mistakes that follow — misreading the image or misjudging feature capacity can cost more than a missed derivation.

Pitfalls to avoid:

Assuming "more features always helps." With linear methods, too many overlapping features can make the $A$ matrix in the TD fixed-point analysis ill-conditioned; with nonlinear networks, too much capacity invites overfitting to recent experience and poor generalization to unseen states.
Forgetting that the image is a conceptual map, not a performance ranking. Exhaustive search is not "worse" in principle — it is exact when feasible. Temporal-difference is not "better" universally — it is the most data-efficient trade-off when the model is unknown or the state space is huge.

Recap and bridge: Function approximation is forced by large state spaces and works by sharing parameters across states via features. The summary image places every method on a breadth-versus-depth spectrum, with temporal-difference at the most compact, best-blended point. The next subsection makes that sharing concrete — first in the linear form used for all class numerics, then as a stand-in for deep networks.

16.4.2 Approximation Architecture — Linear and Non-Linear Forms

Linear value approximation — the workhorse of every class numeric: For a state $s$ with feature vector $x (s) \in R^{d}$ and weight vector $w \in R^{d}$ , $v^(s, w) = w^{⊤} x (s) = i = 1 \sum d w_{i} x_{i} (s) .$ Here $x (s) = (x_{1} (s), \dots, x_{d} (s))^{⊤}$ is the feature vector (each $x_{i} (s) \in R$ is one feature's response at $s$ ), $w = (w_{1}, \dots, w_{d})^{⊤}$ is the weight vector learned by the algorithm, and $v^(s, w) \in R$ is the scalar approximate value. A constant bias term is included by adding a feature $x_{0} (s) \equiv 1$ so that $w_{0}$ acts as an intercept. The gradient that will drive learning is exceptionally simple in the linear case: $\nabla_{w} v^(s, w) = x (s) .$ That is, each weight's influence is exactly its feature's activation.

Why does the course use this form almost exclusively in numerics even though the field has moved to deep networks? The professor's answer is direct: linearity is a pedagogical stand-in. Everywhere the notes write $w^{⊤} x (s)$ you may substitute a neural network $v^(s, w) = NN_{w} (x (s))$ that maps the same feature vector through one or more hidden layers with nonlinear activations to a scalar output. The deep case, the shallow nonlinear case, and the linear case share the same prediction objective and the same gradient-descent template; only the mapping $v^(s, w)$ and its gradient $\nabla_{w} v^(s, w)$ change.

In the linear case the function class is a $d$ -dimensional hyperplane over feature space, which makes convergence analysis tractable and lets a single numeric be worked with pen and paper. In the nonlinear case the function class is far richer — a one-hidden-layer sigmoid network can approximate any continuous function on a compact region, and a deep convolutional network can learn hierarchical features end-to-end — but the same weight-update line $w \leftarrow w + α (U - v^) \nabla_{w} v^$ applies, now with $\nabla_{w} v^$ computed by backpropagation rather than read off as $x (s)$ .

Visual intuition — picture feature space as a gallery of detectors: one detector fires for "left side of room," another for "near the goal," another for "high velocity." A state lights up a pattern of detectors; the value is the weighted vote of the lit detectors. Tile coding makes those detectors square tiles; radial basis functions make them soft Gaussian bumps; a deep network learns what detectors to build in its hidden layers.

Scope — linearity as a teaching device, not a restriction: The linear exposition is not a claim that linear models are sufficient in practice. It is the clearest vehicle for teaching the objective, the semi-gradient distinction, and the feature-construction ideas. When an examination problem says "assume $v^(s, w) = w^{⊤} x (s)$ ", it is specifying the arithmetic to use, not restricting the concept to that form. If a problem instead says "a neural network approximator," the same conceptual steps apply with $\nabla_{w} v^(s, w)$ in place of $x (s)$ .

Exam note: Know the linear form by heart and know that its gradient is the feature vector. Then rehearse the sentence: "wherever the notes write $w^{⊤} x (s)$ , a neural network may be substituted without changing the conceptual structure." That single sentence closes the gap between the examination arithmetic and the deployed deep systems.

16.4.3 Prediction Objective — Mean Squared Value Error — and Gradient Descent

Hook — what should "good" mean when you cannot be good everywhere? With a table you can eventually match every true value exactly. With approximation you have far fewer weights than states ( $d ≪ ∣ S ∣$ ), so improving the estimate at one state inevitably worsens it at another. You must declare which states matter most before you can say what learning should minimize.

The declaration is a state distribution $μ (s) \geq 0$ with $\sum_{s} μ (s) = 1$ that weights how much the squared error at each state counts.

Mean Squared Value Error (MSVE) — the prediction objective: Let $v_{π} (s) \in R$ be the true value of state $s$ under policy $π$ (the expected discounted return from $s$ ), $v^(s, w)$ the approximate value with weights $w \in R^{d}$ , and $μ (s)$ the state-weighting distribution. Then $VE (w) = s \in S \sum μ (s) (v_{π} (s) - v^(s, w))^{2} = E_{S \sim μ} [(v_{π} (S) - v^(S, w))^{2}] .$ Here $s$ ranges over states, $v_{π} (s)$ is fixed (unknown to the learner), $v^(s, w)$ varies with $w$ , and $E_{S \sim μ}$ averages squared error according to how often each state matters. The root MSVE $VE (w)$ is often plotted as a more interpretable scale. Under on-policy training, $μ (s)$ is the on-policy distribution: the stationary distribution under $π$ for continuing tasks, or the normalized expected visitation frequency for episodic tasks. In practice the expectation is sampled — on each visit to a state $S_{t}$ you incur squared error $(v_{π} (S_{t}) - v^(S_{t}, w))^{2}$ weighted implicitly by how often you visit $S_{t}$ .

A sampled stochastic form often written in notes is $J (w) = \frac{1}{2} E [(G_{t} - v^(S_{t}, w))^{2}],$ where $G_{t}$ is the return sampled from $S_{t}$ as an unbiased replacement for $v_{π} (S_{t})$ , and the factor $\frac{1}{2}$ is a convenience that cancels the $2$ from differentiation. Different texts omit or include the $\frac{1}{2}$ ; the concept — squared error averaged over the on-policy visitation — is what matters.

With an objective defined, the optimizer is gradient descent, and in reinforcement learning specifically stochastic gradient descent (SGD). The reason is not just computational convenience but the nature of the data: experience arrives as a stream of states, targets are nonstationary (they depend on the current weights when bootstrapping), and waiting to collect a full batch before updating would waste data and react slowly to a changing policy.

Stochastic-gradient and semi-gradient updates: Let $U_{t} \in R$ be an update target for the visited state $S_{t}$ — for example the Monte Carlo return $U_{t} = G_{t}$ or the one-step TD target $U_{t} = R_{t + 1} + γ v^(S_{t + 1}, w_{t})$ . With step size $α > 0$ , the general SGD prediction update is $w_{t + 1} = w_{t} + α [U_{t} - v^(S_{t}, w_{t})] \nabla_{w} v^(S_{t}, w_{t}) .$ Here $w_{t} \in R^{d}$ is the weight vector before the update, $U_{t} - v^(S_{t}, w_{t})$ is a scalar error (how far the target is from the current estimate), $\nabla_{w} v^(S_{t}, w_{t}) \in R^{d}$ points in the direction that would most increase the estimate at $S_{t}$ , and $α$ scales the step. In the linear case this becomes the especially simple $w_{t + 1} = w_{t} + α [U_{t} - v^(S_{t}, w_{t})] x (S_{t}) .$

True gradient versus semi-gradient: When $U_{t} = G_{t}$ (Monte Carlo), $U_{t}$ does not depend on $w_{t}$ — it is a sample return — so the update is a true stochastic gradient of the MSVE. When $U_{t} = R_{t + 1} + γ v^(S_{t + 1}, w_{t})$ (one-step temporal difference), $U_{t}$ does depend on $w_{t}$ through $v^(S_{t + 1}, w_{t})$ , but the standard derivation ignores that dependence and treats the target as if it were fixed when differentiating. Because only part of the gradient is included, it is called a semi-gradient method. Concretely, the true gradient of $\frac{1}{2} (R_{t + 1} + γ v^(S_{t + 1}, w) - v^(S_{t}, w))^{2}$ would contain a term $γ \nabla_{w} v^(S_{t + 1}, w)$ ; semi-gradient TD(0) drops that term and keeps only $- \nabla_{w} v^(S_{t}, w)$ . The resulting temporal-difference error $δ_{t} = R_{t + 1} + γ v^(S_{t + 1}, w_{t}) - v^(S_{t}, w_{t})$ is therefore the error that drives the semi-gradient update $w_{t + 1} = w_{t} + α δ_{t} \nabla_{w} v^(S_{t}, w_{t})$ .

Two pairings of optimizer and estimator were flagged as "certainly know" material: Monte Carlo gradient-based prediction (true gradient, unbiased target, higher variance, must wait to episode end) and semi-gradient TD(0) (biased target due to bootstrapping, lower variance, online after every step). Structurally they look identical — both are $w + α \cdot error \cdot gradient$ — but the error they use is the entire distinction. Under linear function approximation and on-policy sampling, gradient Monte Carlo converges to the global minimum of the MSVE, while semi-gradient TD(0) converges to a nearby fixed point whose MSVE is within a bounded expansion of the optimum — a subtlety captured formally by the bound $VE (w_{TD}) \leq \frac{1}{1 - γ} min_{w} VE (w)$ in the continuing case.

Visual intuition — imagine descending a bowl (the MSVE surface) by taking steps in the direction that most reduces error at the current state. True-gradient Monte Carlo steps point toward the bowl's bottom. Semi-gradient TD steps point toward a slightly shifted aim — toward where the bowl would be if the bootstrap target were nailed down — so they converge quickly but not quite to the same point.

Assumptions and scope: SGD convergence assumes $α$ small or decreasing according to stochastic-approximation conditions and that states are sampled according to $μ$ . Semi-gradient TD guarantees hold for the on-policy distribution with linear approximation; switching to an off-policy distribution or to nonlinear approximation without additional machinery can cause divergence. The expectation in the MSVE is not over a fixed dataset — it shifts as the policy or the weights change, which is why full-batch gradient descent is poorly suited and SGD's incremental sampling is preferred.

That distinction also creates the most frequent beginner mistakes — getting the names and roles of the error terms wrong.

Pitfalls to avoid:

Calling semi-gradient TD "gradient descent." It is not — it ignores the target's dependence on $w$ . That omission is why it can be combined with bootstrapping while true gradient methods cannot without additional corrections.
Confusing the two roles of $γ$ . In the episodic return $G_{t}$ and the TD target, $γ \in [0, 1]$ discounts future rewards. In the SGD step it has no relation to $α$ ; they are separate scalars that happen to multiply in the update.
Forgetting that $μ$ defines "good." Under weighted MSVE, an approximator that is excellent on frequently visited states and poor on rare states is considered better than one with the reverse property — the objective bakes in the visitation frequency.

Worked example — one SGD step with linear approximation: Consider two states $s_{1}, s_{2}$ with features $x (s_{1}) = [1, 0]^{⊤}$ , $x (s_{2}) = [0, 1]^{⊤}$ and current weights $w_{t} = [0.3, 0.5]^{⊤}$ , so $v^(s_{1}, w_{t}) = 0.3$ , $v^(s_{2}, w_{t}) = 0.5$ . Let $α = 0.1$ , $γ = 0.9$ .

Monte Carlo step: Visit $s_{1}$ , observe return $G_{t} = 1.0$ . Error $= 1.0 - 0.3 = 0.7$ . Update $w_{t + 1} = [0.3, 0.5]^{⊤} + 0.1 \times 0.7 \times [1, 0]^{⊤} = [0.37, 0.5]^{⊤}$ . Only the first component moves because only the first feature was active.

Semi-gradient TD(0) step: Visit $s_{1}$ , observe transition $s_{1} \to s_{2}$ with $R_{t + 1} = 0$ . TD target $= 0 + 0.9 \times 0.5 = 0.45$ . TD error $δ_{t} = 0.45 - 0.3 = 0.15$ . Update $w_{t + 1} = [0.3, 0.5]^{⊤} + 0.1 \times 0.15 \times [1, 0]^{⊤} = [0.315, 0.5]^{⊤}$ . The bootstrap target was smaller than the Monte Carlo return, so the weight moves less. Sense-check: In both cases the weight for the active feature moves toward the target — positive error increases the weight, negative error would decrease it — and inactive features do not move.

Recap and bridge: The prediction objective is MSVE weighted by the on-policy distribution; SGD is the optimizer suited to streaming, nonstationary reinforcement-learning data; the same SGD template yields true-gradient Monte Carlo and semi-gradient TD depending on the target, and that target choice is the key conceptual distinction. With the objective and optimizer in hand, the remaining design choice is how to build the features $x (s)$ that the approximator consumes.

16.4.4 Feature Construction — Coarse Coding, Tile Coding and Radial Basis Functions

Feature construction is how raw states — positions, velocities, pixels — are mapped to the $x (s)$ vectors that the linear approximator blends. Three classical families illustrate the spectrum from binary to smooth representations.

Coarse coding groups states into overlapping receptive fields — for example intervals on a line or circles in a plane — and represents a state by the set of fields covering it. Each field is a binary feature (1 if the state lies inside, 0 otherwise). Generalization is controlled by overlap width: wide fields make nearby states share many active features and generalize broadly; narrow fields share few and discriminate finely. The textbook's illustration of overlapping circles of three sizes shows that different overlap widths change the shape of generalization but, with enough fields, the asymptotic accuracy can still be fine-grained — breadth of generalization and fineness of approximation are partly separable when coverage is dense.

Tile coding is the computationally efficient form of coarse coding for modern digital computers. Each tiling is a partition of the state space into non-overlapping tiles (often squares or rectangles in two dimensions). A state activates exactly one tile per tiling. Multiple tilings, each offset by a fraction of a tile width, together give coarse coding: a state activates one feature per tiling, so total active features equals number of tilings (for example four tilings produce four active features out of perhaps $4 \times 4 \times 4 = 64$ ). Because every state activates the same number of features, the step size can be set intuitively — for example $α = 1/ (number of tilings)$ gives one-step convergence on a single example. Tile coding gains efficiency from binary features ( $w^{⊤} x (s)$ is just the sum of weights of active tiles) and from a hashing trick that collapses large tilings into compact memory. Irregular tilings, stripe tilings, and multi-resolution tilings let the designer inject prior knowledge about which dimensions should generalize together.

Radial basis functions (RBFs) generalize coarse coding to continuous-valued features. Rather than 0 or 1, each feature responds with a graded activation that decays with distance to a centre $c_{i}$ : $x_{i} (s) = exp (- \frac{∥ s - c _{i} ∥ ^{2}}{2 σ _{i}^{2}}),$ where $c_{i}$ is the centre of the $i$ -th RBF, $σ_{i}$ controls its width, and $∥ \cdot ∥$ is a distance metric chosen for the task. Gaussian RBFs produce smooth, differentiable approximate value functions, whereas tile coding produces piecewise-constant ones. Learning can also adjust $c_{i}$ and $σ_{i}$ , which moves the approximator into the nonlinear regime.

Visual intuition — coarse coding is like overlapping spotlights on a stage: where spotlights overlap the light is strongest; tile coding is like stacking several transparent grids offset by half a square — the exact combination of squares covering a point encodes its position; RBFs are like heat sources — each source warms its neighborhood smoothly, strongest at its centre, fading with distance.

Scope — what the notes versus the textbook cover: Class time on feature construction was deliberately kept to what is needed for the examination — the classical families above at the level illustrated in the slides. The notes contain a more expanded survey that includes deep-learning-based feature extraction (for example convolutional layers that learn $x (s)$ from pixels). For examination preparation, follow the level of detail established in class and prioritize the textbook and slides over the notes for this block. The reason is not that the notes are wrong but that they intentionally compress classical methods and expand deep-learning feature extraction to serve both the current offering and a planned future emphasis where early material would be compressed. For post-course study, the notes' expanded deep-learning survey is the recommended next reading.

With scope clear, the two most common mistakes are easy to name — treating features as neutral and confusing one tiling with coarse coding.

Pitfalls to avoid:

Treating feature design as neutral. The choice of tilings or RBF centres injects strong inductive bias. Poorly chosen features can make even a perfectly optimized linear approximator incapable of representing the true value function — no amount of SGD tuning can fix a representational limitation.
Forgetting that tile-coding features are binary and conjunctive. A single tiling is just state aggregation (one active feature). Coarse coding only appears when multiple offset tilings are used together.

In the broader field, feature construction is the bridge between raw sensor data and value prediction. Every deployed system that values states — from a warehouse robot estimating time-to-goal from lidar features to a game agent estimating win probability from board features — makes a feature-construction choice before any weight is learned. Deep networks automate part of this choice by learning features end-to-end, but the classical families remain the clearest way to reason about generalization.

Recap and bridge: Coarse coding gives intuition, tile coding gives efficiency, and RBFs give smoothness — all three map raw states to $x (s)$ vectors that linear weights blend. With architecture, objective, optimizer, and features established, the on-policy prediction loop with approximation is complete, and the section closes with the question students most often ask about the linear form itself.

16.4.5 Student Questions and Answers on Approximation

Q: If everything in the exercises is linear $w^{⊤} x (s)$ , does that mean approximation only works for linear models? A: No — linearity is a pedagogical stand-in, not a restriction. Everywhere the notes write $w^{⊤} x (s)$ you may substitute a neural network that maps $x (s)$ to a scalar value, for example a one-hidden-layer network $v^(s, w) = u^{⊤} σ (W x (s) + b)$ or a deep convolutional stack for pixel inputs. The approximation property that matters — that different states share parameters and therefore generalize — holds for linear and nonlinear parametrizations alike, and the same MSVE objective and SGD template apply with $\nabla_{w} v^(s, w)$ in place of $x (s)$ . The linear case is used in class because it makes the arithmetic tractable and the generalization mechanism visible; the notes deliberately retain it as the clearest teaching vehicle, with the understanding that a network can replace the linear form wherever it appears.

The underlying doubt is natural: when every worked calculation multiplies a weight vector by a feature vector, it looks as if the theory depends on that multiplication. It does not. The theory depends on differentiability and on sharing parameters across states — both properties hold for deep networks, whose expressive power strictly contains the linear class.

Recap and bridge: This section established why large state spaces force approximation, how linear approximation and its deep-network substitution share the same MSVE objective and SGD machinery distinguished by true versus semi-gradient errors, and how feature construction controls generalization. The next section applies the same function-approximation machinery to control — replacing tabular $Q (s, a)$ with a deep network that approximates optimal action values from high-dimensional inputs.

16.5 Deep Q-Networks

16.5.1 How Deep Learning Helps Q-Learning

Hook — what changes when the board becomes a photograph? Tabular Q-learning stores one number for every $(s, a)$ pair and updates it from one transition. An Atari frame is $210 \times 160 \times 3 = 100, 800$ numbers changing 60 times per second. No table can list those states, and two successive frames differ by a handful of pixels — updating one table entry teaches almost nothing about the next frame. How does the same temporal-difference control loop survive when the state is an image?

The answer is to keep the control loop and replace the table with a learned function that generalizes across images.

Deep Q-Network — definition and scope: For a discrete action set $A = {1, \dots, K}$ and a state representation $s$ (for example a stack of four $84 \times 84$ grayscale frames), a Deep Q-Network parametrizes the action-value function as $Q (s, a; θ) \approx Q^{*} (s, a),$ where $θ \in R^{d}$ collects all network weights. The network takes $s$ as input and outputs a vector $Q (s, \cdot; θ) \in R^{K}$ with one entry per action. The optimal value $Q^{*} (s, a) = max_{π} E [R_{t} ∣ s, a, π]$ is the maximum expected discounted return $E [r_{t + 1} + γ r_{t + 2} + \dots ∣ s, a]$ with discount $γ \in [0, 1]$ . The DQN architecture that realizes this mapping in the 2015 Nature paper is a convolutional stack: input $84 \times 84 \times 4$ , first hidden layer 32 filters $8 \times 8$ stride 4 with rectifier, second layer 64 filters $4 \times 4$ stride 2, third layer 64 filters $3 \times 3$ stride 1, followed by a fully connected layer of 512 rectifier units, then a linear output layer with one unit per action. Earlier 2013 variants used two convolutional layers and 256 hidden units; every element of the 2013 design is contained in the 2015 design, so studying the 2015 version subsumes the 2013 version.

Every symbol: $s$ is the (possibly history-based) state, $a$ a discrete action, $θ$ the vector of network weights, $Q (s, a; θ) \in R$ the predicted action value, $Q^{*} (s, a)$ the optimal value, $K = ∣ A ∣$ the number of actions, $γ$ the discount, and the loss below averages over a behaviour distribution $ρ (s, a)$ over states and actions encountered during training.

With that mapping, the temporal-difference machinery carries over with one architectural change — a single forward pass now produces all $K$ values at once, whereas a history-action network that concatenates $(s, a)$ as input would need $K$ forward passes.

Bellman target, loss, and gradient for DQN: The optimal action-value function satisfies the Bellman optimality equation $Q^{*} (s, a) = E_{s^{'} \sim E} [r + γ a^{'} \in A max Q^{*} (s^{'}, a^{'}) s, a],$ where $E$ denotes the environment dynamics that generates next state $s^{'}$ and reward $r$ from $(s, a)$ . DQN turns this identity into an iterative regression. At iteration $i$ with frozen target weights $θ_{i - 1}$ , define the target $y_{i} = E_{s^{'} \sim E} [r + γ a^{'} max Q (s^{'}, a^{'}; θ_{i - 1}) s, a],$ and the loss $L_{i} (θ_{i}) = E_{s, a \sim ρ (\cdot), s^{'} \sim E} [(y_{i} - Q (s, a; θ_{i}))^{2}] .$ Differentiating gives the gradient used for stochastic updates, $\nabla_{θ_{i}} L_{i} (θ_{i}) = E_{s, a \sim ρ; s^{'} \sim E} [(r + γ a^{'} max Q (s^{'}, a^{'}; θ_{i - 1}) - Q (s, a; θ_{i})) \nabla_{θ_{i}} Q (s, a; θ_{i})] .$ In the practical minibatch form, the outer expectations are replaced by samples $(s, a, r, s^{'})$ and a single gradient step is taken. The 2015 DQN stabilizes this further with two engineering choices: an experience replay buffer that supplies $s, a \sim ρ$ from many past policies, and a target network $Q^$ with parameters $θ^{-}$ that are copied from $θ$ only every $C$ steps, so that $y$ uses $θ^{-}$ rather than $θ_{i - 1}$ and does not chase a target that moves on every gradient step.

Visual intuition — picture the tabular backup as updating one isolated cell in a giant spreadsheet. The DQN backup is pulling a rope attached to many cells at once: the network's shared weights mean that moving $Q (s, a; θ)$ toward $r + γ max_{a^{'}} Q (s^{'}, a^{'}; θ^{-})$ for a single sampled $(s, a)$ nudges the values of visually similar states in the same direction. The convolutional filters are what define "visually similar" — they learn to detect paddles, balls, and enemies directly from reward, rather than relying on hand-crafted colour channels or background subtraction used in pre-DQN Atari work.

Class time devoted more than one full lecture to this question precisely because the idea is simple but the reason it works is not. All architecture details, discount values, network sizes, and training schedules are provided open-book; the assessment tests whether you can explain the role of each component, not whether you can recite its number.

Scope — what "DQN" means for this examination: Study the 2015 Nature/Atari DQN with experience replay and a periodically updated target network. The 2013 NIPS workshop version is subsumed by it and need not be studied separately. Double DQN is the one-line change that selects the maximizing action with the online network and evaluates it with the target network — know that it addresses the overestimation caused by the $max$ in the target. No paper year, layer count, or hyperparameter needs to be memorized.

The scope above implies concrete mistakes that follow — mischaracterizing DQN as on-policy or misjudging its architecture.

Pitfalls to avoid:

Calling DQN on-policy because its behaviour is $ϵ$ -greedy. The learning target uses $max_{a^{'}} Q (s^{'}, a^{'}; θ^{-})$ regardless of which action was actually taken next, so the value being learned is for the greedy policy even while data are gathered $ϵ$ -greedily — that decoupling is what makes DQN off-policy and what licenses replay.
Assuming a separate forward pass per action. With the $Q (s, \cdot; θ)$ architecture, one forward pass returns all action values. The older history-action architecture that inputs $(s, a)$ jointly is not the DQN evaluated here.

In the broader field, this single change — $Q (s, a)$ as a deep convolutional mapping from pixels — bridged high-dimensional vision and sequential decision making for the first time at scale, demonstrating one network, one algorithm, and one hyperparameter set succeeding across 49 Atari games from raw pixels and score alone. That demonstration re-ignited the combination of deep learning and reinforcement learning after earlier divergence concerns with nonlinear approximators.

Recap and bridge: Deep Q-Networks keep the Q-learning temporal-difference target but replace the table with $Q (s, a; θ)$ that outputs all action values from one state in a single forward pass, trained against a periodically frozen target via squared-error regression. The component that makes that regression stable and data-efficient is experience replay, which is the deepest examinable point and the focus of the next subsection.

16.5.2 Experience Replay — Purpose Beyond the Three Bullet Points

Hook — why would you ever throw away a hard-won transition after using it once? In tabular Monte Carlo you must — the return after that state will be different next time you visit it. With a deep network each gradient step is tiny, and a single transition can still teach the network after the first pass. Insisting on learning on-policy discards that opportunity and forces the optimizer to learn from a correlated, shifting stream.

Three textbook phrases — reuse, decorrelation, distribution smoothing — name the purposes, but the examination asks you to reason beyond the phrases.

Experience replay — mechanism: Each environment step produces a transition $e_{t} = (s_{t}, a_{t}, r_{t}, s_{t + 1})$ , where $s_{t}$ is the state, $a_{t}$ the action taken, $r_{t}$ the reward, and $s_{t + 1}$ the next state, with a flag for terminal $s_{t + 1}$ . A replay buffer $D = {e_{1}, \dots, e_{N}}$ stores the last $N$ transitions pooled over many episodes, typically $N = 1 0^{6}$ frames in the Atari experiments, and overwrites the oldest when full. Training draws minibatches of size 32 uniformly at random, $(s, a, r, s^{'}) \sim U (D)$ , and for each element computes $y = {r r + γ max_{a^{'}} Q (s^{'}, a^{'}; θ^{-}) if s^{'} terminal otherwise$ and a gradient step on $(y - Q (s, a; θ))^{2}$ . Because samples come from many past policies, the update is off-policy by necessity — the current $θ$ differs from the $θ$ that generated most of the buffer.

Every symbol: $D$ is the buffer, $N$ its capacity, $θ$ the online weights, $θ^{-}$ the target weights frozen between copies, $γ$ the discount, and $U (D)$ the uniform distribution over stored transitions.

Reuse, decorrelation, and smoothing each repair a distinct weakness of the naive online stream.

Reuse means a transition survives beyond its creation step and contributes to many gradient updates. With function approximation the gradient only conveys reliable direction in a small neighbourhood of the current $θ$ ; a transition whose target error is large may need many small steps to be fully exploited. Reusing it amortizes the cost of gathering it — important when data are generated by slow environment interaction rather than by cheap dataset iteration. The uniform minibatch of 32 from a million-entry buffer typically contains experience from dozens of episodes and many stages of learning.

Decorrelation means random sampling breaks the strong temporal correlation of consecutive frames. Successive Atari frames differ by a few pixels; consecutive transitions $(s_{t}, a_{t}, r_{t}, s_{t + 1})$ and $(s_{t + 1}, a_{t + 1}, r_{t + 1}, s_{t + 2})$ share almost the same image and produce almost the same gradient. Training on them in order feeds the optimizer a sequence of nearly identical directions, violating the independent-samples assumption behind stochastic gradient descent and inflating variance. Shuffling through $D$ restores an approximately independent and identically distributed stream and therefore reduces the variance of updates. Without it, a modern optimizer can oscillate or diverge even on simple games.

Distribution smoothing means averaging over the buffer smooths the non-stationary, non-uniform distribution of states that a single episode or a single policy phase induces. Early in training the buffer is filled with poor play; later it contains expert play; at any fixed time a single episode visits only a narrow slice of the state space. Sampling from $D$ mixes those phases and slices, producing a more stationary and better-covering training distribution that averages over many previous behaviours. That averaging prevents the feedback loop where the current policy's preference for "move left" biases the training distribution toward the left side of the screen, which then reinforces moving left even when the policy would otherwise change.

The class exhortation is to be able to argue these effects for a new scenario: replay helps most when data are precious, frames are visually correlated, and the state distribution shifts as the policy improves — all true for Atari. It would help less if transitions were already independent random draws from a fixed distribution and data were free.

Visual intuition — imagine the online trajectory as a narrow, winding river that cuts one groove through state space. Each gradient step digs that groove deeper. Replay is a reservoir that collects water from many rivers cut at different times; drawing buckets uniformly from the reservoir irrigates the whole plain rather than deepening a single trench.

Scope — assumptions and limits: Replay assumes discrete actions where $max_{a^{'}} Q (s^{'}, a^{'})$ is computed by enumeration; it is not directly applicable to continuous actions without a different maximization method. The buffer does not differentiate important transitions — uniform sampling gives equal importance to all stored experience, and finite capacity means older transitions are eventually overwritten. A more sophisticated variant prioritizes transitions with larger temporal-difference error, but uniform replay is the examinable base.

Given that scope, three misconceptions tend to follow — reciting phrases without mechanism, expecting replay to cure all instability, and forgetting it forces off-policy learning.

Pitfalls to avoid:

Reciting the three phrases without the mechanism. "Reuse, decorrelation, smoothing" earns little without being able to name the stored tuple $(s, a, r, s^{'})$ , the buffer size and minibatch size, and why consecutive samples violate the independent-samples assumption.
Treating replay as a cure for all instability. Replay smooths the behaviour distribution but does not by itself remove correlation between $Q$ and its target $r + γ max Q$ ; that second correlation is what the frozen target network addresses. The learning curves in the DQN Nature paper show divergence when replay or the target network is removed.
Forgetting that replay forces off-policy learning. Because the buffer contains data from past policies, the learned $Q$ must be for the greedy policy defined by the current $Q$ , not for the behaviour distribution — which is why the target uses $max$ rather than the action actually taken next.

In production, replay is the template for every value-based agent that learns from high-dimensional observations — from game agents that bank millions of frames to robotics stacks that bank real-world transitions because robot time is expensive and correlated.

Exam note: Be ready to explain, for any scenario, which of the three purposes would or would not help and what would go wrong without replay — mere recitation of the three bullet points is not the standard. That reasoning is also how you should read the learning-curve figure that plots average score (noisy) versus average predicted $Q$ (smoother) over training epochs.

16.5.3 Worked Example — Scope and Limits

Worked forward computation — putting numbers into the DQN expressions: Consider a tiny DQN that flattens a single $2$ -pixel state $s = [0.5, 0.8]^{⊤}$ and uses a one-hidden-layer network with two hidden rectifier units and two discrete actions. Let weights be $W_{1} \in R^{2 \times 2} = [[0.4, - 0.2], [0.1, 0.3]]$ , bias $b_{1} = [0, 0.1]^{⊤}$ , and output weights $W_{2} \in R^{2 \times 2} = [[0.5, 0.2], [- 0.1, 0.6]]$ , $b_{2} = [0.1, - 0.1]^{⊤}$ . The forward pass is:

Hidden pre-activation: $h_{pre} = W_{1}^{⊤} s + b_{1} = [0.4 \times 0.5 + 0.1 \times 0.8, - 0.2 \times 0.5 + 0.3 \times 0.8]^{⊤} + [0, 0.1]^{⊤} = [0.28, 0.24]^{⊤}$ . Rectifier $h = max (0, h_{pre}) = [0.28, 0.24]^{⊤}$ .

Outputs: $Q (s, \cdot; θ) = W_{2}^{⊤} h + b_{2} = [0.5 \times 0.28 - 0.1 \times 0.24 + 0.1, 0.2 \times 0.28 + 0.6 \times 0.24 - 0.1]^{⊤} = [0.216, 0.100]^{⊤}$ . So $Q (s, a_{1}; θ) = 0.216$ , $Q (s, a_{2}; θ) = 0.100$ ; the greedy action is $a_{1}$ .

Now sample a transition $(s, a_{1}, r = 1, s^{'})$ where for $s^{'}$ the target network predicts $Q (s^{'}, \cdot; θ^{-}) = [0.30, 0.50]^{⊤}$ . With $γ = 0.99$ , the DQN target for this non-terminal transition is $y = r + γ max_{a^{'}} Q (s^{'}, a^{'}; θ^{-}) = 1 + 0.99 \times 0.50 = 1.495$ . If the target network is the same as the online network in this tiny example (no lag), the squared error for the taken action is $(y - Q (s, a_{1}; θ))^{2} = (1.495 - 0.216)^{2} = 1.636$ , and the gradient step moves $θ$ to reduce that gap via $\nabla_{θ} Q$ . With experience replay this same transition would be sampled again in later minibatches, contributing to many such steps.

Sense-check: The target $1.495$ exceeds either $Q (s, a; θ)$ because it adds the immediate reward plus discounted optimistic next value; the loss is positive and larger when the network underestimates the return, which is the typical early-training case.

The pedagogical role of the textbook's own DQN numeric was qualified in class: it puts numbers into the expressions above and carries one forward computation to a result, but it does not by itself convey deep insight beyond confirming that the expressions can be evaluated mechanically. Once the concepts — what $Q (s, a; θ)$ represents, why $max_{a^{'}} Q (s^{'}, a^{'}; θ^{-})$ is the target, why a frozen $θ^{-}$ stabilizes it, and why sampling from $D$ is required — are understood, the arithmetic follows without surprise. That is why the examination rewards conceptual reasoning over numeric substitution here.

Scope — what not to spend time on: For Deep Q-Networks, material from Section 10 onward in the DQN notes — extended surveys of individual games as solved by DQN — can be ignored for examination preparation. Those sections are examples for curiosity, not examinable content. Section 13 of the DQN notes is labelled as an ambition for the next offering; it was not delivered in class, is not part of this assessment, and should be assumed out of scope. The discussion of bias in DQN in that later section is therefore also out of scope.

Recap and bridge: How deep learning helps Q-learning is the mapping $s \mapsto Q (s, \cdot; θ)$ that scales temporal-difference control to images; why experience replay matters is the triple effect of reuse, decorrelation, and distribution smoothing that makes stochastic gradient descent on that mapping stable; how the numeric works is a forward pass producing all $K$ values, a target $r + γ max Q (s^{'}, a^{'}; θ^{-})$ , and a squared-error step sampled from replay. With value-based deep control established, the next section switches families to directly parametrizing and improving a stochastic policy for continuous control.

16.6 Policy Gradient Methods and the Lane-Keeping Control Problem

16.6.1 Policy Gradient Theorem — Statement, Intuition and What to Skip

Hook — what if you stopped learning values and learned the driving itself? Value-based methods learn how good each lane position is and then derive steering from those values. Policy-gradient methods skip the middleman: they directly adjust the steering distribution so that good steers become more probable and bad steers become less probable, guided by the return those steers actually produced.

That direct parametrization is the shift in viewpoint. Two networks were shown side by side in class to make it tangible.

Intuition and analogy — the coach who only moves the mean: Imagine a coach who controls a dart thrower whose throws scatter around an aim point with a fixed spread. The coach cannot change the scatter, only the aim. After each throw the coach sees where the dart landed and whether it scored. If a throw slightly left of aim still scored well because the target was left, the coach nudges the aim a little left — "keep more of that direction." Over many throws the aim drifts toward the region that scores. Policy-gradient learning is that coach: the aim is $μ (s)$ , the scatter is $σ$ , and the score is the return $G$ . Where the analogy breaks: In dart throwing the score depends only on where the dart lands; in reinforcement learning the score depends on the whole future trajectory, so the credit for a good outcome must be assigned to every action in the episode, not just the last throw — hence the $γ^{t} G_{t}$ weighting that discounts later steps when viewed from the start.

With that picture, the theorem that makes the update principled can be stated cleanly.

Policy gradient theorem — examinable statement (proof not required): Let $π (a ∣ s; θ)$ be a stochastic policy differentiable in $θ \in R^{d}$ , let $J (θ) = E_{τ \sim π_{θ}} [R (τ)]$ be the expected discounted return over trajectories $τ$ , and let $d^{π} (s)$ be the state distribution and $Q^{π} (s, a)$ the action-value under $π$ . Then $\nabla_{θ} J (θ) = E_{S \sim d^{π}, A \sim π (\cdot ∣ S; θ)} [Q^{π} (S, A) \nabla_{θ} lo g π (A ∣ S; θ)] .$ Here $θ$ is the policy parameter vector, $π (a ∣ s; θ) \in [0, 1]$ the probability (or density) of action $a$ in state $s$ , $lo g π (a ∣ s; θ)$ its logarithmic logarithm, $\nabla_{θ} lo g π (a ∣ s; θ) \in R^{d}$ the score-function gradient, and $Q^{π} (s, a) = E [G_{t} ∣ S_{t} = s, A_{t} = a]$ the expected return from that state-action. In the REINFORCE instantiation the expectation over $Q^{π}$ is replaced by a single sampled return $G_{t}$ from the episode, giving the sampled gradient $G_{t} \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ)$ .

A useful equivalent form collects the time steps: $\nabla_{θ} J (θ) = E_{τ \sim π_{θ}} [t = 0 \sum T - 1 G_{t} \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ)] = E_{τ \sim π_{θ}} [t = 0 \sum T - 1 γ^{t} G_{t} \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ)] (discounted) .$ The textbook and the slides differ only in whether the per-step discount $γ^{t}$ is written explicitly outside the sum or absorbed into $G_{t}$ ; both are the same estimator.

Visual intuition — picture two adjacent training loops. The value network loop predicts $V (s)$ , compares to a target $R + γ V (s^{'})$ , computes squared error, and backpropagates mean-squared error. The policy network loop samples an action $a \sim π (\cdot ∣ s; θ)$ , observes the downstream return $G$ , and nudges $θ$ in the direction $\nabla_{θ} lo g π (a ∣ s; θ)$ scaled by $G$ . One loop minimizes prediction error; the other follows the gradient of expected return. That is why class asked "which network should use the policy-gradient theorem and which should use gradient descent on mean-squared error" — the value head uses the second, the policy head uses the first.

Scope — when the theorem applies and what was flagged to skip: The theorem assumes a Markov decision process with states $S_{t} \in S$ , actions $A_{t} \in A$ , rewards $R_{t + 1} \in R$ , discount $γ \in [0, 1]$ , a stochastic policy $π (a ∣ s; θ)$ that is differentiable in $θ$ , and the ability to sample trajectories under $π$ (on-policy). It holds for both discrete and continuous actions and for episodic and continuing tasks with appropriate $J$ . The statement and the ability to use it to derive REINFORCE, baseline, and actor-critic updates are examinable. The proof of the theorem does not appear in the notes and is explicitly not examinable. For post-examination study the book Grokking Deep Reinforcement Learning was recommended because its proof is accessible, but that pointer is not part of the examinable material.

That scope distinction causes two recurring mistakes — mixing the two losses and studying the proof for credit that does not exist.

Pitfalls to avoid:

Confusing the value-network loss with the policy objective. Minimizing $(G - V (s))^{2}$ learns a value; maximizing $J (θ)$ via $\nabla_{θ} lo g π$ learns a policy. Swapping their gradients is a common transcription error — the policy update never contains a squared error, and the value update never contains $lo g π$ .
Treating the proof as required. Spending examination time reconstructing the proof trades points for no credit. Know the implication — that sampling an action and weighting $\nabla_{θ} lo g π$ by return yields an unbiased gradient estimate — and move on to using it.

Recap and bridge: Policy-gradient methods follow $\nabla_{θ} J (θ)$ via the score function $\nabla_{θ} lo g π$ weighted by return or advantage, rather than deriving a policy from values. The theorem statement above is the contract; the next subsection turns it into the concrete REINFORCE algorithm and derives the log-derivative trick that makes it computable. Exam note: Be able to write the theorem, name every symbol, and explain that sampling $a \sim π$ and scaling $\nabla_{θ} lo g π (a ∣ s; θ)$ by $G$ estimates the true gradient.

16.6.2 REINFORCE — Algorithm and Update in Words and Mathematics

Purpose — the Monte Carlo policy gradient: REINFORCE generates an episode under the current policy, computes the return $G_{t}$ from each visited state, and moves $θ$ in the direction that would make the actions actually taken more likely in proportion to how good their consequences $G_{t}$ turned out to be. It is Monte Carlo because each $G_{t}$ is the full sampled return, not a bootstrapped estimate.

With that purpose clear, the concrete mathematics that realizes it can be stated without ambiguity.

REINFORCE update — mathematics: With differentiable policy $π (a ∣ s; θ)$ , step size $α > 0$ , discount $γ \in [0, 1]$ , and an episode $S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, \dots, S_{T - 1}, A_{T - 1}, R_{T}, S_{T},$ where $S_{t}$ is the state at time $t$ , $A_{t}$ the action, $R_{t + 1}$ the immediate reward, and $T$ the termination time, the textbook REINFORCE processes the episode as

for each time step $t = 0, \dots, T - 1$ : $G_{t} = k = t + 1 \sum T γ^{k - t - 1} R_{k}, θ \leftarrow θ + α γ^{t} G_{t} \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ) .$ Here $G_{t} \in R$ is the discounted return from step $t$ , $α$ the scalar step size, $γ^{t}$ the additional discount that progressively down-weights later steps when viewed from the start of the episode, and $\nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ) \in R^{d}$ the score-function gradient for the realized state-action. The professor's verbal parsing — "alpha gamma power $t$ " for $α γ^{t}$ , "one is $G$ that is return," and "the other one is the gradient part" — maps directly to the three multiplied factors. In some textbook presentations $γ^{t}$ is absorbed into the definition of $G_{t}$ ; the arithmetic is identical.

The gradient factor is not a postulate — it follows from a short, examinable derivation known as the log-derivative trick.

Log-derivative trick — complete derivation (no skipped algebra): Let $p (x; θ)$ be a probability mass or density differentiable in $θ$ and let $f (x) \in R$ be any scalar function not depending on $θ$ . Then $\nabla_{θ} E_{x \sim p (\cdot; θ)} [f (x)] = \nabla_{θ} \int f (x) p (x; θ) d x = \int f (x) \nabla_{θ} p (x; θ) d x = \int f (x) p (x; θ) \frac{\nabla _{θ} p ( x ; θ )}{p ( x ; θ )} d x = \int f (x) p (x; θ) \nabla_{θ} lo g p (x; θ) d x = E_{x \sim p (\cdot; θ)} [f (x) \nabla_{θ} lo g p (x; θ)] (definition of expectation) (move gradient inside integral) (multiply and divide by p) (log-derivative identity) (re-assemble as expectation) .$ The identity $\nabla_{θ} lo g p (x; θ) = \nabla_{θ} p (x; θ) / p (x; θ)$ is the log-derivative trick. Applying it with $x = τ$ a full trajectory, $p (x; θ) = p (τ; θ)$ the trajectory probability, and $f (x) = R (τ)$ the total return gives $\nabla_{θ} J (θ) = \nabla_{θ} E_{τ \sim p (\cdot; θ)} [R (τ)] = E_{τ} [R (τ) \nabla_{θ} lo g p (τ; θ)] .$ Writing $p (τ; θ) = \prod_{t = 0}^{T - 1} π (A_{t} ∣ S_{t}; θ) p (S_{t + 1}, R_{t + 1} ∣ S_{t}, A_{t})$ and taking logs, all environment dynamics terms have zero $θ$ -gradient and drop, leaving $\nabla_{θ} lo g p (τ; θ) = \sum_{t = 0}^{T - 1} \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ)$ . Distributing $R (τ)$ and using causality (return before $t$ is unaffected by action at $t$ ) replaces $R (τ)$ by $G_{t}$ term by term, yielding the REINFORCE estimator $\sum_{t} G_{t} \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ)$ and its discounted form $\sum_{t} γ^{t} G_{t} \nabla_{θ} lo g π$ . This is why sampling one episode and summing $G_{t} \nabla_{θ} lo g π$ estimates the true gradient.

Visual intuition — imagine $J (θ)$ as a hilly surface over $θ$ . You cannot evaluate the whole surface, but at your current $θ$ you can sample a trajectory, compute $G_{t} \nabla_{θ} lo g π$ at each step, and that vector points on average uphill. Repeating the sample-and-step moves the policy toward higher expected return.

Scope — assumptions and what $γ^{t}$ does: REINFORCE assumes stochastic, differentiable $π (a ∣ s; θ)$ and on-policy sampling — the trajectory must be generated by the same $π (\cdot ∣ \cdot; θ)$ that is being updated. The factor $γ^{t}$ is not an extra hyperparameter; it is the textbook's per-step discounting that reduces the influence of later updates when viewed from time zero. If a problem statement gives $γ = 1$ , it disappears. Common hyperparameter values cited in class are $α = 0.01$ or $0.1$ and $γ = 1$ for the simplest one-step episode; a specific examination problem will state its values.

Two errors follow directly from that scope — misplacing the extra discount and trying to differentiate the environment's reward.

Pitfalls to avoid:

Dropping $γ^{t}$ or applying it to $G_{t}$ twice. $G_{t}$ already contains $γ^{k - t - 1}$ inside the sum. The outer $γ^{t}$ is the additional weighting from the start of the episode, not a correction to $G_{t}$ itself.
Trying to differentiate $R (τ)$ directly. Rewards come from the environment and are not differentiable in $θ$ ; the log-derivative trick is how $θ$ influences return — through the action distribution, not through the reward function.

Recap and bridge: REINFORCE is Monte Carlo policy gradient with update $θ \leftarrow θ + α γ^{t} G_{t} \nabla_{θ} lo g π$ ; the log-derivative trick derives that gradient from $\nabla_{θ} E [R (τ)]$ without differentiating rewards. Once $\nabla_{θ} lo g π$ is known, the rest is mechanical — so the hard part, if the examination changes $π$ , is computing that logarithmic derivative, which is exactly what the Continuous-action derivation in the next two subsections practices.

16.6.3 The Lane-Keeping Assistance Problem — Full Specification

Hook — the car that must stay in the middle between the gutters: An assistance system steers a car that is somewhere in its lane. If the car is already in the centre it should stay there; if it has drifted left it should steer right, and vice versa. The reward is simple — plus one when the car ends up in the centre, zero otherwise — but the steering command is continuous, so the policy cannot be a discrete choice. This is the running example that makes every policy-gradient variant concrete with the same states, features, and episode.

States, features, and actions: The lane is discretized to three positions $S = {left, centre, right} = {S_{0}, S_{1}, S_{2}} .$ Each state is encoded by a one-hot feature vector $x (s) \in {0, 1}^{3}$ : $x (left) = 100, x (centre) = 010, x (right) = 001 .$ Here $x (s)$ is the feature extraction of state $s$ , written in the lecture as " $X$ of $S$ ." The mapping is explicit: " $X$ of $S_{0}$ is left represented as $100$ , centre is $010$ , right is $001$ ."

The steering action is a continuous real number $A = [- 1, + 1],$ where $- 1$ is full left, $+ 1$ is full right, and intermediate values are proportional (for example $- 0.77$ is almost fully left, $+ 0.79$ almost fully right). The policy must therefore output a distribution over this interval from which a steering value is sampled.

The reward structure is $R = {+ 1 0 if the transition lands the car in centre, if it lands in left or right .$ In words: "you get plus one if the car is in the centre, you get zero if the car is in left or right." The objective is to stay in centre.

Gaussian policy parametrization for continuous actions: Because the action is continuous, a softmax over finitely many actions is not applicable. Instead the network outputs the parameters of a Gaussian $N (μ (s), σ^{2})$ from which the steering command is sampled.

Conceptually two heads share the same input features $x (s)$ : $μ (s; θ_{μ}) = θ_{μ}^{⊤} x (s) (mean steering), σ (s; θ_{σ}) (standard deviation) .$ Here $θ_{μ} \in R^{3}$ is the mean-network parameter vector, $θ_{σ}$ parametrizes the standard deviation, and the lecture's shallow-network assumption "assume the network is a very simple, very shallow network doing only theta transpose $X$ of $S$ " makes the linear form $θ_{μ}^{⊤} x (s)$ the operative model. In the simplified numerical example only the mean network is learned; the standard-deviation network is fixed to $σ (s) \equiv 0.2 for all s,$ so the policy is a narrow Gaussian centred at $μ (s)$ with variance $σ^{2} = 0.04$ . The learner updates only $θ_{μ}$ ; the lecture frames this as "you are only learning mean and you are not learning sigma; sigma is assumed." Initial parameters are $θ_{μ}^{(0)} = - 0.5 0 0.5,$ with hyperparameters step size $α$ (cited as $0.01$ in the worked episode and $0.1$ in variant illustrations — the problem statement gives the value to use) and discount $γ \in [0, 1]$ (taken as $1$ in the simplest episode). The advice given is: if $α$ or $γ$ are missing from a problem statement, ask or declare the assumed value explicitly.

Visual intuition — draw a road from above with three lanes: left, centre, right. Above each lane position plot a narrow bell curve: centred at $- 0.5$ over left (leaning left), at $0$ over centre (straight), at $+ 0.5$ over right (leaning right). Sampling a steering command means dropping a dot under the bell for the current lane — most dots fall near the centre of that bell. Learning slides each bell's centre so that dots increasingly land where the $+ 1$ reward lives.

Scope — when this specification applies: The one-hot encoding and $σ = 0.2$ constant are the examinable simplification for lane keeping. The general case would learn both $μ$ and $σ$ as functions of state with richer features (for example lane offset and heading angle). The discrete-action alternative — discretizing steering into bins and using a softmax policy — is a different parametrization not required for numerics here; it was noted as straightforward for anyone familiar with discrete softmax but not covered technically.

That fixed-variance choice is exactly what students most often misread — confusing the mean with the sample and trying to learn $σ$ when it is frozen.

Pitfalls to avoid:

Treating $μ (s)$ as the action. The mean is where the distribution is centred; the action $a$ is a single sample from $N (μ (s), 0.04)$ . Confusing the two makes the gradient $(a - μ) / σ^{2}$ collapse to zero.
Forgetting that $σ = 0.2$ is fixed here. Its gradient is not computed and its value does not update. A problem that instead says "learn $σ$ " would require an additional derivative.

Recap and bridge: Lane keeping is three states with one-hot features, continuous steering in $[- 1, + 1]$ , reward $+ 1$ for centre and $0$ elsewhere, and a Gaussian policy $N (θ_{μ}^{⊤} x (s), 0.04)$ with initial $θ_{μ} = [- 0.5, 0, 0.5]^{⊤}$ and fixed $σ = 0.2$ . The next subsection evaluates what that initial $θ_{μ}$ actually means for each lane position.

16.6.4 Means for Each State Under the Initial Parameters

With the one-hot encoding, computing $μ (s) = θ_{μ}^{⊤} x (s)$ is a table lookup — it selects one coordinate of $θ_{μ}$ .

Worked computation — all three states: Let $θ_{μ}^{(0)} = [- 0.5, 0, 0.5]^{⊤}$ .

Left: $x (left) = [1, 0, 0]^{⊤}$ ,

$μ (left) = (- 0.5) (1) + 0 (0) + 0.5 (0) = - 0.5.$ The policy's centre is significantly left — negative is left.

Centre: $x (centre) = [0, 1, 0]^{⊤}$ ,

$μ (centre) = (- 0.5) (0) + 0 (1) + 0.5 (0) = 0.$ The policy's centre is straight ahead.

Right: $x (right) = [0, 0, 1]^{⊤}$ ,

$μ (right) = (- 0.5) (0) + 0 (0) + 0.5 (1) = + 0.5.$ The policy's centre is significantly right.

These three numbers are the starting distribution centres before any learning. Intuition: being in the left lane already biases steering left, being on the right biases it right, and being centred biases it straight — the initial parametrization encodes a naive corrective tendency that learning will refine. Sense-check: Each mean equals exactly one entry of $θ_{μ}$ because one-hot features pick out one weight; if the encoding were not one-hot, $μ (s)$ would be a blend of weights.

Scope and pitfall: This lookup property depends on the one-hot choice. With richer features (for example two-dimensional features including lane offset and heading), $μ (s)$ would interpolate between weights rather than selecting one. For examination numerics, keep the one-hot rule: $μ (S_{0}) = - 0.5$ , $μ (S_{1}) = 0$ , $μ (S_{2}) = + 0.5$ under the initial $θ_{μ}$ .

Recap and bridge: Initial means are $- 0.5$ for left, $0$ for centre, $+ 0.5$ for right — each is one coordinate of $θ_{μ}$ . Those means parametrize the Gaussian whose log-density and derivative are needed for the update, which is the next derivation.

16.6.5 Policy Density, Log-Policy and Its Gradient for the Gaussian

The quantity that enters REINFORCE is not the density $π$ but its logarithm and the logarithm's gradient — the highlighted derivative that multiplies $G$ . The derivation is three short steps with no skipped algebra.

Step 1 — Gaussian density: With $μ (s; θ_{μ}) = θ_{μ}^{⊤} x (s)$ and fixed $σ = 0.2$ , the policy density for steering command $a \in [- 1, 1]$ is $π (a ∣ s; θ_{μ}) = \frac{1}{2 π σ} exp (- \frac{( a - μ ( s ; θ _{μ} ) ) ^{2}}{2 σ ^{2}}) .$ Here $a$ is the realized steering value, $μ (s; θ_{μ}) \in R$ the state-dependent mean, $σ = 0.2$ the fixed standard deviation, and $θ_{μ} \in R^{3}$ the parameter vector. The lecture's phrase "the probability of an action given a state is this, because we assumed if I know mu and sigma I go to the normal distribution expression to plug these values" is this line.

Step 2 — log-policy: Taking the natural logarithm, $lo g π (a ∣ s; θ_{μ}) = - lo g (2 π σ) - \frac{( a - μ ( s ; θ _{μ} ) ) ^{2}}{2 σ ^{2}} .$ Here the first term $- lo g (2 π σ)$ is a constant in $θ_{μ}$ (since $σ$ is fixed) and the second term carries the $θ_{μ}$ -dependence through $μ$ . The lecture isolates this as "first you take the pi, apply the log."

Step 3 — gradient with respect to $θ_{μ}$ : Differentiate, using $μ (s; θ_{μ}) = θ_{μ}^{⊤} x (s)$ so $\nabla_{θ_{μ}} μ (s; θ_{μ}) = x (s)$ : $\nabla_{θ_{μ}} lo g π (a ∣ s; θ_{μ}) = - \frac{1}{2 σ ^{2}} \nabla_{θ_{μ}} [(a - μ (s; θ_{μ}))^{2}] = - \frac{1}{2 σ ^{2}} \cdot 2 (a - μ (s; θ_{μ})) \cdot (- \nabla_{θ_{μ}} μ (s; θ_{μ})) = \frac{a - μ ( s ; θ _{μ} )}{σ ^{2}} x (s) . (constant term drops) (chain rule)$ So the boxed result that "is going to come in this great important" place — the factor that multiplies $α γ^{t} G_{t}$ in the REINFORCE update — is $\nabla_{θ_{μ}} lo g π (a ∣ s; θ_{μ}) = \frac{a - μ ( s ; θ _{μ} )}{σ ^{2}} x (s) .$ With $σ = 0.2$ , $σ^{2} = 0.04$ ; with one-hot $x (s)$ , the gradient has only one nonzero coordinate. This is the Gaussian "score" — it points in the feature direction, with magnitude proportional to how far the sampled action was from the current mean, scaled by precision $1/ σ^{2}$ .

Visual intuition — the bell curve is steep near its centre. If you sampled $a$ to the right of the mean ( $a - μ > 0$ ), the gradient points toward increasing the weight for that state's feature, which will slide the bell rightward. Sampling left of the mean pushes it left. The narrower the bell (smaller $σ$ ), the same distance $a - μ$ produces a larger push because $1/ σ^{2}$ is larger — a confident narrow policy updates more sharply from each sample.

Scope — what changes if the policy form changes: The three-step pattern — write $π$ , take $lo g π$ , differentiate with respect to $θ$ — is universal. If the examination gives a different $π$ (for example a Bernoulli or a different continuous density), apply the same two operations; the resulting derivative replaces $(a - μ) / σ^{2} \cdot x (s)$ in the update, and every other piece ( $G_{t}$ , $α γ^{t}$ , addition to $θ$ ) remains identical. That replacement is the only non-mechanical part of the REINFORCE computation.

Those two steps are mechanical, but two transcription slips routinely break them — dropping the feature factor and misplacing the variance.

Pitfalls to avoid:

Forgetting the chain rule through $μ$ . The gradient is with respect to $θ_{μ}$ , not $μ$ . The factor $x (s)$ comes from $\nabla_{θ_{μ}} μ (s; θ_{μ}) = x (s)$ ; omitting it collapses a vector gradient to a scalar.
Mixing up $σ$ and $σ^{2}$ . The density has $σ$ in the normalization $1/ (2 π σ)$ and $σ^{2}$ in the exponent denominator $2 σ^{2}$ . After logging and differentiating, only $σ^{2}$ remains in the gradient denominator. Writing $σ$ instead of $σ^{2}$ is a factor-of-five error when $σ = 0.2$ .

Recap and bridge: The Gaussian log-policy is $- lo g (2 π σ) - (a - μ)^{2} / (2 σ^{2})$ and its gradient is $(a - μ) / σ^{2} \cdot x (s)$ — that vector is the boxed quantity that scales the REINFORCE step. With all pieces defined, the next subsection puts numbers into that gradient for a one-step episode.

16.6.6 Worked Example — REINFORCE on a One-Step Episode

Worked example — the simplest possible episode carried end to end: The episode is a single transition that ends immediately, so every return and discount collapses to one number.

Setup: Current state $S_{0} = left$ with $x (S_{0}) = [1, 0, 0]^{⊤}$ . Current mean $μ (left) = - 0.5$ from the previous subsection. Fixed $σ = 0.2$ so $σ^{2} = 0.04$ . Sampled action $A_{0} = - 0.3$ (slightly left of straight; negative is left). Reward $R_{1} = + 1$ because the action lands the car in centre. Next state $S_{1} = centre$ ; episode terminates.

Return: With $γ = 1$ and only one reward, $G_{0} = R_{1} = + 1.$ The lecture's phrasing "since there is only one episode you know your $G$ is plus $1$ , correct? There is only one thing to sum" is this line.

Log-policy gradient at this transition: Using $a = - 0.3$ , $μ = - 0.5$ , $σ^{2} = 0.04$ , $\frac{a - μ}{σ ^{2}} = \frac{- 0.3 - ( - 0.5 )}{0.04} = \frac{0.2}{0.04} = 5.$ Multiplying by the feature vector, $\nabla_{θ_{μ}} lo g π (A_{0} ∣ S_{0}; θ_{μ}) = 5 \cdot 100 = 500 .$ With the stated $σ = 0.2$ the active coordinate is $5$ . (A value of $500$ would correspond to $σ = 0.02$ , i.e. $σ^{2} = 0.0004$ ; the problem as specified uses $σ = 0.2$ .)

Parameter update: With step size $α = 0.01$ and $γ^{0} = 1$ for the first step, $θ_{μ}^{new} = θ_{μ}^{old} + α G_{0} \nabla_{θ_{μ}} lo g π (A_{0} ∣ S_{0}; θ_{μ}) .$ Substituting $θ_{μ}^{old} = [- 0.5, 0, 0.5]^{⊤}$ , $α = 0.01$ , $G_{0} = 1$ , gradient $[5, 0, 0]^{⊤}$ , $θ_{μ}^{new} = - 0.5 0 0.5 + 0.01 \cdot 1 \cdot 500 = - 0.45 0 0.5 .$ Only the left-state coordinate moves, from $- 0.5$ to $- 0.45$ ; the centre and right coordinates are unchanged because their feature entries are zero for this transition. The lecture's stated result "the answer comes to minus $0.45$ " matches this arithmetic.

Interpretation: The current mean says "turn significantly left" ( $- 0.5$ ); the good outcome ( $+ 1$ for reaching centre) was achieved with a slightly less left action ( $- 0.3$ ), so the update relaxes the left bias toward $- 0.45$ — "don't keep that much effort left, slightly relax, come to centre." Accumulated over many episodes this small shift centres the steering policy.

Extension to longer episodes: For a three-step episode the same five-step mini-algorithm from the textbook applies: form $G_{t}$ for each $t$ , compute $(a_{t} - μ (S_{t})) / σ^{2} \cdot x (S_{t})$ , multiply by $α γ^{t} G_{t}$ , and add to $θ$ . Later steps are discounted by $γ^{t}$ when viewed from the start. Sense-check: Every update moves $θ$ toward the sampled action when $G_{t} > 0$ and away when $G_{t} < 0$ ; here $G_{0} = + 1$ and $a_{0} = - 0.3$ is to the right of $μ = - 0.5$ , so the mean correctly shifts right (less negative).

The full written update the professor walked through — "new theta is old theta plus alpha gamma power $t$ times $G$ times the gradient" — is exactly the displayed equation used above.

Scope — hyperparameters to watch: The value $α = 0.01$ here is the one used in the spoken walk-through for this episode; other lanes or problems may specify $α = 0.1$ . The episode length, $γ$ , and $σ$ will be stated. If any is missing, declare the assumption before computing.

Pitfalls to avoid:

Applying the gradient to all three coordinates. Only the state actually visited $(left)$ contributes; the gradient entries for centre and right are zero because those feature entries are zero. Updating all three is the most common arithmetic error.
Using reward $R_{1}$ instead of return $G_{0}$ when the episode is longer. For a one-step episode they coincide, but for a multi-step episode $G_{t}$ sums discounted future rewards, not just the immediate $R_{t + 1}$ .

Exam note: If the form of $π$ is changed, the only non-mechanical part is recomputing $lo g π$ and $\nabla_{θ} lo g π$ ; forming $G$ , scaling by $α γ^{t}$ , and adding to $θ$ remains identical. Master the Gaussian derivative above and the rest of any lane-keeping numeric is bookkeeping.

16.6.7 REINFORCE with Baseline — What Changes

REINFORCE with baseline keeps every piece of REINFORCE scaffolding except the scalar that multiplies the gradient. The change is one subtraction.

Baseline update — the single-term substitution: Let $v^(s) \in R$ , written in the lecture as " $V$ cap of $s$ ," be an estimated state value (a baseline) that may be learned separately or given. The per-step update becomes $θ \leftarrow θ + α γ^{t} (G_{t} - v^(S_{t})) \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ) .$ Here $G_{t}$ is the usual sampled return from step $t$ , $v^(S_{t})$ the baseline value for the visited state, and $G_{t} - v^(S_{t})$ the advantage-flavoured scalar that replaces bare $G_{t}$ . Every other factor — $α γ^{t}$ and $\nabla_{θ} lo g π$ — is unchanged from the REINFORCE calculation. The lecture's guidance "you have in place $G$ minus the value of $S_{t}$ ; everything is same except that minus $V$ cap" is this line.

Why it helps: Subtracting a state-dependent constant does not bias the expected gradient (because $E_{A \sim π} [\nabla_{θ} lo g π (A ∣ s; θ)] = 0$ , so $E [v^(s) \nabla_{θ} lo g π] = 0$ ), but it reduces variance — the gradient estimate fluctuates less because the baseline recentres the return around its typical value for that state. The theory behind that variance reduction was covered analytically before the numerics; for the examination numeric the operational change is the subtraction.

Worked continuation of the same one-step episode with a baseline: Keep $S_{0} = left$ , $A_{0} = - 0.3$ , $R_{1} = + 1$ , $G_{0} = 1$ , gradient $[5, 0, 0]^{⊤}$ , $α = 0.01$ . Suppose the given baseline values are $v^(left) = 0.4$ , $v^(centre) = 0.6$ , $v^(right) = 0.4$ (illustrative values of the kind the notes state for each lane position).

Baseline-corrected scalar: $G_{0} - v^(left) = 1 - 0.4 = 0.6.$ Update: $θ_{μ}^{new} = - 0.5 0 0.5 + 0.01 \cdot 0.6 \cdot 500 = - 0.47 0 0.5 .$ The mean still shifts right but by less ( $+ 0.03$ instead of $+ 0.05$ ) because part of the return was already expected by the baseline. If instead $v^(left) = 1.2$ (return worse than expected), the scalar would be negative and the mean would shift away from the sampled action. Sense-check: Baseline does not change the gradient direction — only its magnitude and potentially its sign via $G_{t} - v^(S_{t})$ .

Pitfalls to avoid:

Subtracting $v^(S_{t + 1})$ instead of $v^(S_{t})$ . The baseline is for the current state's value, not the next state's. The actor-critic variant in the next subsection is the one that uses both.
Learning the baseline from the same $G_{t}$ without a separate update. The baseline $v^(s)$ is typically trained to minimize $(G_{t} - v^(S_{t}))^{2}$ via its own gradient step; plugging $G_{t}$ into both the policy and the baseline without that separation conflates two objectives.

Recap and bridge: REINFORCE with baseline replaces the scalar $G_{t}$ by $G_{t} - v^(S_{t})$ and is otherwise identical to REINFORCE — one extra lookup and subtraction before the multiplication. The next variant goes one step further and replaces the Monte Carlo quantity entirely.

16.6.8 Actor-Critic (One-Step) — Replacing $G$ with the TD Error

The actor-critic variant replaces the sampled return with a bootstrapped one-step temporal-difference error that needs no wait to episode end.

One-step actor-critic — the second substitution: In place of $G_{t}$ or $G_{t} - v^(S_{t})$ , the one-step actor-critic uses the TD error $δ_{t} = R_{t + 1} + γ v^(S_{t + 1}) - v^(S_{t}),$ called "advantage" and "one-step TD error" interchangeably in this context. The policy update becomes $θ \leftarrow θ + α δ_{t} \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ) .$ Here $R_{t + 1}$ is the immediate reward, $v^(S_{t + 1})$ the estimated value of the next state, $v^(S_{t})$ the estimated value of the current state, $γ$ the discount, and $\nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ)$ the same score-function gradient as before (for the Gaussian, $(a - μ) / σ^{2} \cdot x (s)$ ). The lecture's phrasing "in place of $G$ you are actually using delta" is this substitution; the gradient factor is unchanged, only the scalar weighting it changes from a full return to a one-step bootstrapped error. A separate critic update trains $v^$ toward the TD target, typically $v^(S_{t}) \leftarrow v^(S_{t}) + β δ_{t}$ with its own step size $β$ .

The three lane-keeping numerics in the notes share the same episode and feature representation so that the variants can be compared by inspecting one scalar.

Worked continuation — same one-step lane keeping episode as actor-critic: Keep $S_{0} = left$ , $A_{0} = - 0.3$ , $R_{1} = + 1$ , $γ = 1$ , gradient $[5, 0, 0]^{⊤}$ , $α = 0.01$ . Let the given estimates be $v^(left) = 0.5$ and $v^(centre) = 0.4$ (the lecture cites "point four something" for centre).

TD error: $δ_{0} = R_{1} + γ v^(centre) - v^(left) = 1 + 1 \times 0.4 - 0.5 = 0.9.$ Policy update: $θ_{μ}^{new} = - 0.5 0 0.5 + 0.01 \cdot 0.9 \cdot 500 = - 0.455 0 0.5 .$ If instead $v^(left) = 1.6$ (overestimate), then $δ_{0} = 1 + 0.4 - 1.6 = - 0.2$ and the update would be $θ_{μ}^{new} = [- 0.51, 0, 0.5]^{⊤}$ , pushing the mean away from the sampled action because the transition turned out worse than the critic expected. Sense-check: When bootstrapping is accurate, $δ_{t}$ is centred and lower-variance than $G_{t}$ ; when the critic is wrong, the bias in $v^$ biases the policy step — the cost of not waiting for the full return.

Side-by-side, the only difference across the three lane-keeping numerics is the scalar:

Variant	Scalar weighting $\nabla_{θ} lo g π$	Needs full episode?	Bias / variance
REINFORCE	$G_{t}$	Yes — wait to $T$	Unbiased, high variance
REINFORCE with baseline	$G_{t} - v^(S_{t})$	Yes — still needs $G_{t}$	Unbiased, lower variance
One-step actor-critic	$δ_{t} = R_{t + 1} + γ v^(S_{t + 1}) - v^(S_{t})$	No — one transition	Biased (depends on $v^$ ), lowest variance, online

When to pick which: Use REINFORCE when you need unbiased Monte Carlo and can afford episode-length waits. Add a baseline whenever a value estimate is available — it is a free variance reduction. Use actor-critic when episodes are long or continuing and you need updates after every step; that is the control loop that scales to driving, robotics, and language-model fine-tuning.

Scope — what the notes label not required: The discretization-with-softmax alternative (Section 11 of the policy-gradient notes, "if steering is discretized, a softmax alternative") and the optional session from Section 13 onward are explicitly not required for examination preparation; they were not covered technically. They are straightforward for anyone familiar with discrete-action softmax but should not consume examination-preparation time.

Pitfalls to avoid:

Replacing $G_{t}$ with $R_{t + 1}$ alone. The actor-critic scalar is the TD error $R_{t + 1} + γ v^(S_{t + 1}) - v^(S_{t})$ , not the raw reward. The $v^(S_{t + 1})$ bootstrap and the $- v^(S_{t})$ baseline are both essential.
Updating $θ$ with $δ_{t}$ but forgetting the critic update. The critic $v^$ must be updated toward $R_{t + 1} + γ v^(S_{t + 1})$ ; otherwise the same biased $v^$ persists and the policy converges to the wrong point.

Recap and bridge: The three lane-keeping numerics share the same episode, features, and $\nabla_{θ} lo g π = (a - μ) / σ^{2} \cdot x (s)$ ; they differ only in the scalar — $G$ , $G - v^(S)$ , or $δ = R + γ v^(S^{'}) - v^(S)$ . Understanding one numeric and applying the single-term substitution for each of the other two is the recommended preparation path. The section closes with the two questions students most often ask when a continuous-action Gaussian is used.

16.6.9 Student Questions and Answers on Policy Gradients

Q: I missed how the continuous action is actually selected if the network only outputs a mean. A: The mean $μ (s) = θ_{μ}^{⊤} x (s)$ together with the fixed standard deviation $σ = 0.2$ defines a full Gaussian $N (μ (s), σ^{2})$ . Action selection samples a single number from that Gaussian and uses it as the steering command — for example with $μ (left) = - 0.45$ after the update, the policy draws $a \sim N (- 0.45, 0.04)$ and steers by that $a$ . Learning the mean shifts the centre of the sampling distribution; sampling from the updated Gaussian automatically produces actions closer to the rewarded region more often. The spread $σ$ stays constant here, so exploration does not collapse but also does not adapt — that is the simplification that keeps the numeric to one parameter vector.

A practical follow-up often arises: what if the policy were not Gaussian at all?

Q: What if the examination gives me a different policy form than the Gaussian? A: Apply the same two operations, no new machinery: take the natural logarithm of the given $π (a ∣ s; θ)$ and differentiate the result with respect to $θ$ . That derivative replaces the boxed Gaussian term $(a - μ) / σ^{2} \cdot x (s)$ in the update. Every other piece — forming $G_{t}$ (or $G_{t} - v^(S_{t})$ or $δ_{t}$ ), scaling by $α γ^{t}$ , updating $θ$ — remains identical. For example, if the problem instead gave a discrete softmax $π (a ∣ s; θ) = exp (θ_{a}^{⊤} x (s)) / \sum_{b} exp (θ_{b}^{⊤} x (s))$ , then $lo g π$ and $\nabla_{θ} lo g π$ would be the softmax log-derivative (indicator minus probability times feature), and that vector would multiply $G_{t}$ exactly as the Gaussian gradient did. If the calculus is solid, the remainder is mechanical.

Recap and bridge: Continuous actions under a Gaussian are sampled from $N (μ (s), σ^{2})$ and learned by moving $μ (s)$ ; any alternative policy is handled by the same log-and-differentiate step, with only the gradient factor changing. With policy-gradient numerics — REINFORCE, baseline, and actor-critic — established on the lane-keeping problem, the next section turns to model-based planning where a learned model guides search before acting.

16.7 Model-Based Planning — MCTS, AlphaGo, MuZero and Planet

16.7.1 Why Model-Based Learning and Decision-Time Planning

Hook — thinking before you move: Picture a Go board where your opponent has just played. You have almost two minutes before you must reply. You could blurt out the first move that looks plausible, or you could spend those two minutes mentally trying moves, following their consequences with the rules of Go in your head, and only then commit. That deliberate use of time to search with a model is exactly what this block is about.

Model-free methods learn a policy $π (a ∣ s)$ or a value $v (s)$ that maps the current state directly to an action, with no explicit look-ahead at decision time. Model-based methods learn or are given a model of the environment and then plan with it — they simulate what would happen if actions were taken, evaluate those futures, and choose after the search.

Model and what planning means: Let $S$ be the state set, $A$ the action set, and let a model be a function $m : S \times A \to Δ (S \times R)$ that predicts the next state $S_{t + 1}$ and immediate reward $R_{t + 1}$ from $(S_{t}, A_{t})$ , i.e. $m (s, a) \approx p (s^{'}, r ∣ s, a)$ . Planning is any computation that uses $m$ to improve a policy or value before acting in the real environment. Background planning improves the policy offline from simulated experience; decision-time planning runs search from the current state $S_{t}$ at the moment a move is required.

The classic analogy used in class makes the operational difference concrete.

Intuition and analogy — two examinations: In a closed-book examination you must answer from memory alone — that is the model-free policy: state goes in, action comes out. In an open-book examination you arrive well prepared, and when a hard scenario question appears you flip through your notes, refresh the mental model, test perspectives against each other, and only then write. The ability to enter well prepared, then search the notes before committing, is decision-time planning. The Go clock gives the same story in game terms: after the opponent moves you have up to two minutes not to recall a memorized line but to systematically explore using the rules of the game as the model. Where the analogy breaks: Notes can be re-read at leisure, but a game clock is finite and the branching factor is enormous. Brute-force search of every continuation is impossible — planning must be selective, sampling promising lines more deeply than unpromising ones, which is precisely what Monte Carlo Tree Search does.

Not every problem benefits equally from decision-time planning. The slide that enumerates when it helps can be read as three conditions: the state space or branching factor is too large to have an optimal policy tabulated for every state; the decision is not required in a few milliseconds, so thinking time can be invested; and a model of the environment is available or can be learned accurately enough to simulate. When those hold, evaluating many possible actions by looking ahead and gathering evidence before choosing systematically outperforms committing to the first output of a reactive policy.

Visual intuition — imagine two pipelines side by side. On the left, a single arrow from state $S_{t}$ through a network to an action $A_{t}$ ; the network has done all its work during training and contributes nothing at decision time. On the right, the state $S_{t}$ is the root of a growing tree; each edge is a simulated action using the model, each child is a predicted next state, and a search algorithm expands that tree for as many iterations as the clock allows, scores the branches, and finally returns the most promising root action. The left pipeline is fast but blind to this specific position's subtleties; the right pipeline pays time to get evidence about this position.

Scope — what is examinable here and what is not: Examinable are the motivation for model-based learning and the precise meaning of decision-time planning versus a reactive policy. Examinable at the level used in the guest session is the search algorithm itself — its four stages and the rule that drives its selection. Deep recall of every engineering choice, network architecture, or training hyperparameter in each historical paper is explicitly not required. Section 15 of the notes lists ambitious future topics beyond the 16-session scope; only apprenticeship learning (DAgger) will be covered in depth there — see 16.7.4.

That scope is where students most often mis-allocate time — either memorising paper pseudocode or ignoring the planning concept entirely.

Pitfalls to avoid:

Conflating planning with learning the model. Planning assumes a model already exists (given as rules or learned). Learning the model and using it to plan are two distinct steps; this block tests the second — how search produces a decision — not the derivation of model-learning losses.
Treating decision-time planning as background replay. Background planning updates a global value or policy from simulated experience for later use. Decision-time planning is local to the current state $S_{t}$ and its value is specific to the move now required, even though the statistics it builds may be discarded afterwards.

Comparison at a glance:

Dimension	Background planning (e.g. Dyna)	Decision-time planning (MCTS)
When	Between real actions, offline	At decision time, from $S_{t}$
Root	Many simulated starts	Single current state $S_{t}$
Output	Improved global $v$ or $π$ for future states	Best $A_{t}$ for this state
Cost	Amortised over many states	Paid per move, bounded by clock

Recap and bridge: Model-based learning uses a model $p (s^{'}, r ∣ s, a)$ to simulate futures. Decision-time planning invests thinking time from the current state $S_{t}$ to evaluate actions before committing — the open-book examination, the Go two-minute clock. When branching is huge but time exists, selective search beats a blind reactive choice. The next subsection makes that selective search procedural: the four stages that define Monte Carlo Tree Search and the confidence-bound rule that steers it.

16.7.2 Monte Carlo Tree Search — The Four Stages and the UCT Formula

Hook — how do you search a tree you cannot finish? Go has about 250 legal moves per position and games last ~150 moves; exhaustive search is astronomically larger than chess. Monte Carlo Tree Search (MCTS) answers by growing the tree selectively: it keeps statistics at every edge, always extends the most promising but least explored branches first, and backs up the results of fast random play-outs to refine those statistics. Time, not depth, determines when to stop.

MCTS interleaves four stages on every iteration, starting from the root that represents the current real state $S_{t}$ . The guest session devoted significant time to these stages and the ability to trace them is the examinable core.

The four stages — procedural definition:

1. Selection. Starting at the root, repeatedly descend by choosing the child that maximizes the UCT score (defined below) until a leaf node — a node with at least one untried action — or a terminal game position is reached. Selection is the tree policy; it balances exploiting high-valued children against exploring rarely visited ones.
2. Expansion. Create one or more child nodes for an untried action from the selected node and attach them to the tree. The newly added node represents the predicted state after that action under the model.
3. Simulation (rollout). From the newly expanded node, play out to a terminal state (or a fixed truncation depth) using a fast rollout policy — often uniform random or a lightweight learned policy — collecting the outcome $G$ (win/loss or scored return). The rollout need not be strong; it must be fast enough to be repeated thousands of times within the clock.
4. Backup (backpropagation). Propagate $G$ back up the path visited in this iteration. For each ancestor node $s$ and edge $(s, a)$ on the path, increment visit counts $N (s)$ and $N (s, a)$ by one and update the edge's mean value $X ˉ (s, a)$ toward the observed result, e.g. $X ˉ (s, a) \leftarrow X ˉ (s, a) + (G - X ˉ (s, a)) / N (s, a)$ .

The score that drives selection is UCT — the Upper Confidence bound applied to Trees — the tree analogue of the classic UCB bandit rule. The instructor's comment that "the expression does not really differ from your classic UCB, you just take this UCT expression and you look at your good old UCB expression; they are not much different, you are doing primarily the same thing" reconstructs to:

$UCT (s, a) = X ˉ (s, a) + c \frac{lo g N ( s )}{N ( s , a )} .$

Here $X ˉ (s, a) \in R$ is the empirical mean value of action $a$ from state $s$ averaged over rollouts through $(s, a)$ so far, $N (s) \in N$ is the visit count of parent state $s$ , $N (s, a) \in N$ is the visit count of the child edge $(s, a)$ (with $N (s, a) \geq 1$ for the formula to be defined; untried actions are given $+ \infty$ priority), and $c > 0$ is the exploration constant that trades exploitation of currently good-looking moves (large $X ˉ$ ) against exploration of less-visited moves (large second term). $c$ larger favours broader search; $c$ smaller favours deeper exploitation of the current best line. UCT applies the UCB principle at every internal node of the tree, so confidence bounds are composed down the path.

Visual intuition — draw the root with two children. Each incident edge is labelled with a pair $(X ˉ, N (s, a))$ and each node with $N (s)$ . Selection follows the bold edge whose UCT is larger; expansion adds a new leaf dangling from that edge; simulation shoots a dashed line from the new leaf straight to a terminal outcome; backup colours the entire visited path and ticks every count. After many iterations the tree is broad near the root where many alternatives have been tried, and deep along the few lines whose UCT remained highest — exactly selective growth.

Worked example — two-iteration trace with real numbers: Consider root $s_{0}$ with two legal actions $a_{1}, a_{2}$ and exploration constant $c = 1.4$ (the common $2$ choice). Visits and means are maintained as $(N, X ˉ)$ . Untried actions have UCT $= + \infty$ and are taken before any visited action.

Initial state before any iteration: $N (s_{0}) = 0$ , no children expanded.

Iteration 1 — Selection finds $s_{0}$ has untried actions, so it picks one, say $a_{1}$ , without using UCT. Expansion creates node $s_{1}$ for $(s_{0}, a_{1})$ . Simulation from $s_{1}$ with the rollout policy returns $G = 1$ (win for the player to move). Backup updates the visited path: $N (s_{0}) = 1, N (s_{0}, a_{1}) = 1, X ˉ (s_{0}, a_{1}) = 1.00, N (s_{0}, a_{2}) = 0.$ Root statistics now record one win down the $a_{1}$ branch and nothing yet for $a_{2}$ .

Iteration 2 — Selection at $s_{0}$ . Child $a_{2}$ is still untried, so its UCT is infinite and it is selected regardless of $X ˉ (s_{0}, a_{1})$ . No UCT arithmetic is needed to see this — starvation of an unvisited edge dominates. Expansion creates $s_{2}$ for $(s_{0}, a_{2})$ . Simulation from $s_{2}$ returns $G = 0$ (loss). Backup: $N (s_{0}) = 2, N (s_{0}, a_{1}) = 1, X ˉ (s_{0}, a_{1}) = 1.00, N (s_{0}, a_{2}) = 1, X ˉ (s_{0}, a_{2}) = 0.00.$

What the next selection would do (illustrative iteration 3): Now both children have been visited, so UCT governs. With $N (s_{0}) = 2$ , $UCT (s_{0}, a_{1}) = 1.00 + 1.4 \frac{lo g 2}{1} = 1.00 + 1.4 0.6931 = 1.00 + 1.4 (0.8326) = 1.00 + 1.166 = 2.166,$ $UCT (s_{0}, a_{2}) = 0.00 + 1.4 \frac{lo g 2}{1} = 1.166.$ So iteration 3 would select $a_{1}$ again, expand a child beneath $s_{1}$ , simulate, and back up, deepening the more promising branch while the exploration bonus for $a_{2}$ will grow slowly as $lo g N (s_{0})$ increases. Sense-check: After iteration 2 the means are 1.00 and 0.00 — the algorithm has seen one win and one loss. UCT correctly keeps both lines in contention because visit counts are still tiny; as counts grow the $lo g N (s) / N (s, a)$ term shrinks for heavily visited edges, forcing the tree to eventually return to less-explored branches.

Why the two numerics flagged in class matter: the guest instructor's live trace shows how the narration maps to the four verbs — "I am selecting, now expanding, now simulating, now backing up" — while the compact notes numerical provides a self-contained table of UCT calculations and backup arithmetic that can be reproduced on paper. Preparatory advice is to be able to do what the box above does: given a small tree with visit counts and means, compute UCT for competing children, pick the maximizer, expand the untried edge, assume a rollout outcome, and back up counts and means along the visited path.

Relationship to the bandit UCB: at each node MCTS faces a bandit problem whose arms are the legal moves from that state. UCT is literally UCB1 re-applied at every node, which is why the formula looks identical except for the state-conditioning $(s, a)$ .

Concept	UCB (bandit)	UCT (tree)
Arm	Action $a$	Edge $(s, a)$ conditioned on node $s$
Mean	$X ˉ (a)$	$X ˉ (s, a)$ for that node's subtree
Count	$N$ total pulls, $N (a)$ per arm	$N (s)$ node visits, $N (s, a)$ edge visits
Scope	One decision	Every internal node, composed along the path

Assumptions and scope: MCTS assumes a generative model that can sample next states and outcomes quickly enough for thousands of simulations within the clock, a finite action set at each node so that children can be enumerated, and the ability to define a rollout policy and a terminal evaluation. It does not require a perfect value function in advance — the tree and rollout outcomes are the evaluation. For the examination, being able to state the four stages in order, write UCT with all symbols defined, and trace one or two iterations with numbers is sufficient; convergence proofs and alternative selection rules beyond UCT are out of scope.

Two slips break otherwise correct traces:

Pitfalls to avoid:

Forgetting $lo g N (s)$ in the numerator or swapping it with $N (s, a)$ . The confidence width grows with $lo g N (s)$ (parent visits) and shrinks with $N (s, a)$ (child visits). Writing $N (s) / N (s, a)$ or $lo g N (s, a)$ changes the exploration rate dramatically.
Treating a rollout as an evaluation of the parent instead of the new leaf. Simulation starts from the newly expanded node, not from the root or the selected node before expansion. Backing up to the wrong path assigns credit to branches that were never traversed.

Recap and bridge: MCTS repeats selection by $UCT (s, a) = X ˉ (s, a) + c lo g N (s) / N (s, a)$ , expansion of an untried action, fast simulation to a terminal outcome, and backup of visit counts and mean values. UCT is UCB on a tree. Tracing two or three iterations with arithmetic — computing UCT, expanding the winning edge, simulating a 1 or 0, and incrementing counts — is the mechanical skill to practice. The next subsection shows how four landmark game-playing systems all use that same loop, differing only in what model they search with.

16.7.3 AlphaGo, AlphaZero, MuZero and Planet — What to Know and What Not to Memorize

Hook — four systems, one search backbone: From 2016 to 2019 a single research thread produced a sequence where each system did more with less — less hand-craft, less privileged access to the real environment, more learned structure — yet played stronger. What never changed was the backbone: Monte Carlo Tree Search at decision time. What changed was the model that MCTS searched over.

The notes title enumerates MCTS, AlphaGo, AlphaZero, MuZero and Planet as a lineage. Read chronologically they show decision-time planning carried progressively further by learning better models.

At-a-glance lineage — milestones and what improved:

System	Year	Model MCTS searches	Training signal	Key advance over predecessor	Strength signal
AlphaGo (Fan / Lee)	2016	Given rules + supervised policy/value nets + rollout policy	Human expert games + self-play RL + value regression	First superhuman Go with MCTS guided by deep nets	Defeated European champion Fan Hui 5–0, Lee Sedol 4–1
AlphaGo Zero	2017	Given rules + single net (policy + value)	Pure self-play from scratch, no human games	Removed human data; one network trained entirely by self-play	Defeated AlphaGo Lee version 100–0
AlphaZero	2017–18	Given rules (general game) + single net	Pure self-play	Generalised the Zero method beyond Go to chess and shogi with identical architecture and minimal game-specific knowledge	Superhuman in three games with one algorithm
MuZero	2019	Learned latent dynamics model (no given rules)	Self-play + latent model learning (reward, value, policy)	Plans in a learned abstract state, not the real rules; needs only reward and action interface	Matches AlphaZero on Go/chess/shogi and exceeds on Atari without seeing the simulator
Planet (and Dreamer lineage)	2018+	Learned latent world model for continuous control	Model-based RL in latent space	Demonstrates the same idea — learn dynamics, then plan with search — outside board games, in visual control	Sample-efficient control from pixels via latent planning

Across the entire lineage the pattern is invariant: MCTS is the decision-time planner; the networks supply the prior policy that biases selection, the value that truncates and evaluates leaves, and (from MuZero on) the dynamics that replace the given simulator.

In more detail, AlphaGo combined MCTS with two deep convolutional networks produced by supervised learning on human games and reinforcement learning from self-play: a policy network to propose moves and a value network to evaluate positions, plus a fast rollout policy for simulations. AlphaGo Zero collapsed those into a single network and removed the human phase — the only input was the board and the rules. AlphaZero showed that collapse was not Go-specific. MuZero removed the last crutch: instead of the true transition model, it learned a latent dynamics function that predicts rewards, values and policies in an abstract state, and MCTS searches entirely inside that learned latent space. Planet applies the same principle — learn a latent world model from pixels and plan inside it — to continuous visual control, showing that the idea extends beyond perfect-information board games.

Visual intuition — imagine the planner's tree gradually detaching from the real board. In AlphaGo the edges of the tree are legal Go moves and nodes are real board positions. In MuZero the tree's nodes are abstract latent states that the model learned to make search work, and edges are actions whose consequences are predicted rather than simulated by the true rules; the real environment is only consulted for the root state and the rewards that train the latent model. Planet does the same but the leaves are video frames compressed to latent vectors.

What to know versus what not to memorize:

Know and be able to write a few sentences on each: what the system did (its milestone), what the technical improvement over its predecessor was, and how MCTS is used inside it (as the decision-time search guided by learned policy/value and, where applicable, a learned model). A compact lineage table like the one above plus one sentence per system is the right granularity.

Do not memorize: algorithm pseudocode, network depths, layer counts, training hours, or specific parameter values from any paper. Slides contain slightly more detail than the notes; either source at that high level suffices. No numerical of the Alpha family was flagged for mechanical practice comparable to the lane-keeping numerics — conceptual lineage is the preparation goal.

That expectation mirrors the open-book analogy from 16.7.1: even for a high-level description, having refreshed the notes pages that summarize each paper's contribution before writing makes the answer precise.

Pitfalls to avoid:

Saying MCTS disappeared in later systems. It did not — later systems strengthened MCTS by pairing it with a stronger learned model, not by replacing it. "MCTS is the planner; the model is what improved" is a safe summary sentence.
Listing milestones without the improvement direction. An answer that names four systems but cannot say what AlphaZero removed relative to AlphaGo, or what MuZero learns that AlphaZero was given, reads as memorised names rather than understood progression.

Recap and bridge: AlphaGo (human data + MCTS), AlphaGo Zero (zero human data + single net + MCTS), AlphaZero (general game + same method), MuZero (learned latent model + MCTS in latent space), Planet (latent world model for visual control) — one search backbone, progressively more learned. Know milestone, improvement, and MCTS role; skip pseudocode and parameters. The final subsection maps what from this rich landscape the course will pursue further and what it will deliberately defer.

16.7.4 Roadmap Items Deferred — Section 15 and Imitation Learning

Hook — a course cannot cover everything it names: The combined notes span 191 pages and were designed as a superset for multiple offerings. Section 15 lists a set of frontier topics that is explicitly too ambitious for 16 taught sessions at the depth used elsewhere. Naming the deferred items is part of keeping the examinable scope honest.

Section 15 enumerates, among others, imitation learning and the DAgger (Dataset Aggregation) algorithm, inverse reinforcement learning (also called reward modeling), multi-agent reinforcement learning, and safety in reinforcement learning. The stated plan is that a future re-alignment of the course would compress some early material to create room to cover more of these topics in depth.

What will be covered versus deferred:

Topic in Section 15	Coverage in this offering	What to understand
Imitation learning / DAgger	~1 hour in depth	What imitation learning is, why it matters when expert demonstrations exist, how DAgger (Dataset Aggregation) iteratively collects states under the learner's policy but labels them with the expert to fix distribution shift, and what class of problems it addresses
Inverse RL / reward modeling	Introductory only	That the reward function itself can be learned from preferences or demonstrations; the idea that appears directly in preference-optimization methods for language models
Multi-agent RL	Introductory only	That multiple learners interact, so the environment is non-stationary from any single agent's perspective; models joint or adversarial dynamics
Safety in RL	Introductory only	That constraints and guarantees are needed before deploying learned policies in the physical world

Imitation learning is included because it connects directly to planning: when a high-quality policy or human expert is available, the cheapest way to get good sequential behaviour can be to imitate rather than discover from scratch via reward search, provided distribution shift is handled (the problem DAgger addresses). The other three topics will be introduced only to the level of "what the topic is, what class of applications it models, and where it connects to material already seen." Concretely, inverse reinforcement learning as reward modeling appears in direct-preference-optimization style algorithms; multi-agent RL as the extension where multiple learners co-adapt; safety as the family of constraints needed for real-world deployment.

Scope — examination level for deferred topics: Imitation learning and DAgger may be examined for understanding of what imitation is, why it matters, how DAgger works, and what problem class it addresses. Inverse RL / reward modeling, multi-agent RL, and safety will be presented at an introductory what-it-is level, not as a source of numerical or proof-style examination material. No deep paper recall is required for any deferred topic.

Recap and bridge: Section 15 is a roadmap, not all of it examinable: DAgger will be treated in an hour in depth; inverse RL, multi-agent, and safety will be introduced as landscape. Together with the MCTS lineage, this completes the model-based planning thread — from why to plan at decision time, through the four-stage algorithm and its confidence-bound rule, through the Alpha-family that shows the idea scaling, to what comes next. The following section stays with policy methods but turns to how advantages and trust regions make that learning stable and sample-efficient.

16.8 Advanced Policy Methods — Asynchronous Methods, Generalized Advantage Estimation and Proximal Policy Optimization

16.8.1 Asynchronous Advantage Actor-Critic (A3C) and Synchronous Advantage Actor-Critic (A2C)

Hook — why train one agent when you can train ten at once? A single actor-critic collecting one trajectory at a time learns slowly and sees highly correlated data — frame after frame of the same game. If ten copies of the same agent play ten copies of the game in parallel, each seeing a different part of the state space, and all contribute to one shared brain, the brain learns faster and more stably. That shared-brain, many-workers design is what this block organizes.

Both A3C and its synchronous variant A2C start from the single-instance actor-critic: an actor with policy parameters $θ$ that outputs $π_{θ} (a ∣ s)$ and a critic with parameters $w$ that outputs $v^_{w} (s)$ . The goal in both parallel variants is to learn the parameters of the shared master network — the global $θ$ and global $w$ — while workers do the data collection.

Master, workers, and the five-step cycle: Let $θ \in R^{d_{θ}}$ be the global actor parameters and $w \in R^{d_{w}}$ the global critic parameters held in the master network. Let there be $K$ workers (the lecture uses $K = 10$ as the running example) each with a local copy $θ^{'}$ and $w^{'}$ . Each worker repeats:

Copy. Synchronize local parameters from the master: $θ^{'} \leftarrow θ$ , $w^{'} \leftarrow w$ .
Roll out. Interact with the environment for a trajectory of length $n$ (or until termination) using the local policy $π_{θ^{'}}$ , producing $(S_{t}, A_{t}, R_{t + 1}, S_{t + 1})_{t}$ .
Compute. Form parameter updates from that rollout — typically $n$ -step advantage actor updates and value-regression critic updates. If the trajectory is long, multiple $n$ -step windows are taken inside the same rollout; for example a 100-step rollout with $n = 10$ yields 10 incremental advantage computations.
Accumulate. Aggregate the resulting incremental deltas locally (a worker sums its roughly 5–10 gradient contributions before communicating).
Apply. Push the accumulated update to the master parameters $θ, w$ .

Here $n$ is the $n$ -step horizon, $R_{t + 1}$ the immediate reward, $γ \in [0, 1]$ the discount, and the advantage $A^_{t}$ (defined in 16.8.2) weights the actor gradient $A^_{t} \nabla_{θ^{'}} lo g π_{θ^{'}} (A_{t} ∣ S_{t})$ . The cycle is the same for A3C and A2C; what differs is the synchronization of step 5.

Intuition and analogy — submitting notebooks without a roll call: Picture 30 students sent to solve a task at their own desks. In the asynchronous room, each student works at their own pace and walks up to hand in their notebook the moment they finish — whoever finishes first submits first, regardless of roll number or start order, and the shared grade sheet is updated immediately on each arrival. In the synchronous room, everyone works for a fixed interval, then all notebooks are collected together into one stack and the grade sheet is updated once from the whole stack. The first room is A3C; the second is A2C. The asynchronous room tolerates staleness for speed, the synchronous room pays coordination for a cleaner, batched gradient. Where the analogy breaks: Students do independent work, but workers share parameters that drift while a worker is still collecting data — so an asynchronous worker's gradient may have been computed under a policy slightly older than the master it updates, which is why locking and staleness were active research considerations before the synchronous variant became standard.

The distinction is therefore not in what is computed but in how step 5 is applied.

In A3C the application is asynchronous and lock-free: each worker pushes its accumulated update to the master as soon as it finishes, without waiting for other workers and without a global barrier. Updates interleave in arrival order — the order in which workers happen to complete, which depends on varying trajectory lengths and computation times. The master evolves incrementally after every worker's push.

In A2C the collection is synchronized: multiple environments still run in parallel and each collects a planned number of steps under the same current policy, but their data are assembled into a single batch. One joint gradient is computed from the batch and one synchronized update is applied to the master. Concretely the operational difference is independent rollouts with unlocked pushes versus synchronized rollouts with a batched update.

Visual intuition — draw one central book labelled Master $θ, w$ with $K$ spokes to worker desktops. Each worker's spoke is a loop: copy down from the centre, orbit the environment for a few steps, sum gradients locally, then arrow back to the centre. In the A3C diagram those back-arrows arrive at random times, interleaved; in the A2C diagram they all land together, are summed in the middle of the diagram into one thick arrow, and a single update is applied.

Dimension	A3C (asynchronous)	A2C (synchronous)
Step-5 synchronization	Unlocked, per-worker push on completion	Barrier, batched joint update
Arrival order	First-come, first-applied (notebook analogy)	Synchronized collection, single batch
Gradient staleness	Mild staleness possible (local policy slightly behind master)	No staleness within the batch
Implementation today	Historically influential, less common now	Modern default; aligns with batched GPU computation
When preferred	Many CPU workers, minimal coordination overhead	Batched accelerators, cleaner optimization semantics

Assumptions and scope: Both methods assume on-policy data — each worker's rollout is generated by the policy whose gradient it computes (or, in the asynchronous case, by a very recent copy). They assume a parametrized stochastic policy $π_{θ} (a ∣ s)$ differentiable in $θ$ and a learned state-value critic $v^_{w} (s)$ . The five-step cycle is examinable at the operational level — be able to list the five steps and explain the asynchronous-versus-synchronized difference. Specific distributed-system details, lock implementations, or throughput numbers are not examinable. The notes identify A2C as the variant that aligns with more recent engineering; the asynchronous-versus-synchronized contrast is the takeaway.

The usual transcription error is to describe the difference as "A3C has no master" or "A2C has no workers" — both have the same master and workers; only the timing of step 5 changes.

Pitfalls to avoid:

Saying A3C has no shared network. It does — the master $θ, w$ is the point of A3C. Asynchrony is about when pushes happen, not about whether a shared target exists.
Forgetting the accumulate step. Each worker does not push after every single transition; it aggregates several $n$ -step deltas (for example 10 windows inside a 100-step rollout) and pushes the sum. Describing the cycle as copy-rollout-push skips the accumulation that makes the update stable.

Recap and bridge: A3C and A2C share one master $θ, w$ and $K$ workers that each copy, roll out, compute $n$ -step advantages, accumulate, and apply — they differ only in whether step 5 is unlocked per-worker (A3C, notebooks arrive as finished) or synchronized into one batch (A2C, stack collected together). That batched collection is what modern implementations use. The quality of what workers compute depends on the advantage estimator they use, which is the subject of the next subsection.

16.8.2 Advantage Estimation — From One-Step and $n$ -Step to Generalized Advantage Estimation

Hook — judging an action fairly: Suppose a chess engine evaluates your position as winning and you play a move that keeps it winning but slightly less so — was that move good or bad? The raw return says "still winning" (positive), but relative to how good the position already was, the move lost value. The advantage $A (s, a) = Q (s, a) - V (s)$ captures exactly that relative judgment: how much better the action was than the state's average. Actor-critic methods weight the policy gradient by this relative signal, not by the absolute return, which is why its estimation matters so much.

Advantage — definition: For a policy $π$ , let $Q^{π} (s, a) = E_{π} [G_{t} ∣ S_{t} = s, A_{t} = a]$ be the action value and $V^{π} (s) = E_{π} [G_{t} ∣ S_{t} = s]$ the state value, where $G_{t} = \sum_{k = 0}^{\infty} γ^{k} R_{t + k + 1}$ is the discounted return with discount $γ \in [0, 1]$ . The advantage is $A^{π} (s, a) = Q^{π} (s, a) - V^{π} (s) .$ Here $A^{π} (s, a) \in R$ measures how much better action $a$ is than the policy's average behaviour in $s$ ; its expectation under $π$ is zero, $E_{a \sim π} [A^{π} (s, a)] = 0$ . In practice $Q^{π}$ and $V^{π}$ are estimated by a learned critic $v^_{w} (s) \approx V^{π} (s)$ and rollout rewards, so $A^$ denotes an estimator.

Rather than learning $Q^{π}$ and $V^{π}$ separately, modern actor-critic learns only $v^_{w} (s)$ and combines it with sampled rewards to estimate $Q^{π}$ .

One-step and $n$ -step advantage — mathematics: Let $v^(s) = v^_{w} (s)$ be the current critic, $γ \in [0, 1]$ the discount, and $R_{t + 1}$ the immediate reward. The one-step TD error advantage is $δ_{t} = R_{t + 1} + γ v^(S_{t + 1}) - v^(S_{t}) .$ The $n$ -step advantage generalizes over $n$ real rewards before bootstrapping: $A^_{t}^{(n)} = [k = 0 \sum n - 1 γ^{k} R_{t + k + 1} + γ^{n} v^(S_{t + n})] - v^(S_{t}) .$ Here $n \geq 1$ is the horizon, $A^_{t}^{(n)} \in R$ the $n$ -step estimator, and $γ^{n} v^(S_{t + n})$ the bootstrapped tail. Special cases: $n = 1$ recovers $A^_{t}^{(1)} = δ_{t}$ ; as $n$ reaches the episode end the bracket becomes the full Monte Carlo return $G_{t}$ and $A^_{t}^{(\infty)} = G_{t} - v^(S_{t})$ .

Why two extremes are not enough: The Monte Carlo advantage $G_{t} - v^(S_{t})$ is unbiased for the true advantage but varies widely from episode to episode because $G_{t}$ sums many random rewards — high variance, low bias. The one-step advantage $δ_{t}$ depends heavily on the possibly biased critic $v^$ and is myopic — low variance but higher bias. The $n$ -step family trades these properties discretely via $n$ ; Generalized Advantage Estimation blends them continuously.

The continuous blend is what GAE formalizes — an exponential weighting of the whole $δ$ -sequence rather than a hard horizon cut.

Generalized Advantage Estimation — the $λ$ -weighted blend: Let $δ_{t + l} = R_{t + l + 1} + γ v^(S_{t + l + 1}) - v^(S_{t + l})$ be the one-step TD error at time $t + l$ with discount $γ$ as above, and let $λ \in [0, 1]$ be the GAE weighting parameter. Then $A^_{t}^{GAE} = l = 0 \sum \infty (γ λ)^{l} δ_{t + l} .$ Here $A^_{t}^{GAE} \in R$ is the GAE Advantage at time $t$ , each $δ_{t + l} \in R$ is a one-step TD error, $γ$ discounts for time, and $λ$ controls the exponential down-weighting of distant TD errors. When $λ = 0$ only $l = 0$ survives and $A^_{t}^{GAE} = δ_{t}$ (high bias, low variance). When $λ = 1$ the telescoping sum recovers the Monte Carlo advantage $G_{t} - v^(S_{t})$ (low bias, high variance). Intermediate $λ$ smoothly interpolates — "every subsequent step is discounted down and down to give lesser and lesser importance" by an extra factor $γ λ$ per step.

Derivation intuition in one line: expanding the definition of $A^_{t}^{(n)}$ shows $A^_{t}^{(n)} = \sum_{l = 0}^{n - 1} γ^{l} δ_{t + l}$ ; GAE is the exponentially weighted average $\sum_{n} w_{n} A^_{t}^{(n)}$ with $w_{n} \propto λ^{n - 1}$ , which collapses to the compact $\sum_{l} (γ λ)^{l} δ_{t + l}$ form.

Visual intuition — picture a timeline from $t$ to the right, each position $t + l$ holding a block $δ_{t + l}$ . The $n$ -step estimator with $n = 3$ stacks the first three blocks with weights $1, γ, γ^{2}$ . GAE stacks all blocks but dims each successive block by an extra factor $λ$ — the contribution fades exponentially. Small $λ$ keeps only the first few bright blocks (short-horizon, critic-heavy); large $λ$ keeps many dim blocks out to the horizon (long-horizon, reward-heavy).

Worked example — GAE by hand with short numbers: Take discount $γ = 0.99$ and GAE parameter $λ = 0.95$ , so $γ λ = 0.9405$ . Suppose a short trajectory with learned values and rewards:

$v^(S_{t}) = 10.0, v^(S_{t + 1}) = 11.0, v^(S_{t + 2}) = 9.0, v^(S_{t + 3}) = 9.5, R_{t + 1} = 1.0, R_{t + 2} = 0.0, R_{t + 3} = 1.0.$

Step 1 — one-step TD errors: $δ_{t} = 1.0 + 0.99 (11.0) - 10.0 = 1.0 + 10.89 - 10.0 = 1.89,$ $δ_{t + 1} = 0.0 + 0.99 (9.0) - 11.0 = 8.91 - 11.0 = - 2.09,$ $δ_{t + 2} = 1.0 + 0.99 (9.5) - 9.0 = 1.0 + 9.405 - 9.0 = 1.405.$

Step 2 — GAE as exponentially weighted sum (truncate after $l = 2$ for illustration): $A^_{t}^{GAE} \approx δ_{t} + (γ λ) δ_{t + 1} + (γ λ)^{2} δ_{t + 2} = 1.89 + 0.9405 (- 2.09) + (0.9405)^{2} (1.405) .$ Since $0.940 5^{2} = 0.8845$ , $A^_{t}^{GAE} \approx 1.89 - 1.9656 + 0.8845 (1.405) = 1.89 - 1.9656 + 1.2428 = 1.167.$

For comparison:

One-step advantage $A^_{t}^{(1)} = δ_{t} = 1.89$ .
Two-step advantage $A^_{t}^{(2)} = δ_{t} + γ δ_{t + 1} = 1.89 + 0.99 (- 2.09) = 1.89 - 2.069 = - 0.179$ .
Monte Carlo advantage (three steps here) $A^_{t}^{(3)} = δ_{t} + γ δ_{t + 1} + γ^{2} δ_{t + 2} = 1.89 - 2.069 + 0.9801 (1.405) = 1.198$ .

GAE with $λ = 0.95$ gives $1.167$ , close to the Monte Carlo $1.198$ but with variance reduced because distant rewards are softly down-weighted rather than fully included. If $λ = 0$ the answer would be $1.89$ ; if $λ = 1$ it would be the Monte Carlo $1.198$ (with exact $γ$ ). Sense-check: $δ_{t + 1}$ is strongly negative because the value dropped from 11.0 to 9.0 unexpectedly; GAE with intermediate $λ$ dilutes that surprise relative to the pure one-step, but not as harshly as truncating at $n = 1$ .

Bias–variance trade-off at a glance:

Estimator	Uses	Bias	Variance	$λ$ / $n$ regime
One-step $δ_{t}$	$v^$ heavily	Higher (depends on critic)	Lower	$n = 1$ , $λ = 0$
$n$ -step $A^^{(n)}$	$n$ rewards + $v^$ tail	Decreases with $n$	Increases with $n$	Hard cutoff at $n$
GAE $A^^{GAE}$	Exponentially weighted $δ$ 's	Decreases with $λ$	Increases with $λ$	Soft blend, $0 \leq λ \leq 1$
Monte Carlo $G_{t} - v^(S_{t})$	Full return	Lowest (unbiased for $V^{π}$ )	Highest (episodic variation)	$n \to \infty$ , $λ = 1$

Assumptions and scope: GAE assumes a learned state-value critic $v^_{w} (s)$ , discount $γ \in [0, 1]$ , and the ability to compute $δ_{t}$ along a trajectory. The finite-horizon implementation truncates the infinite sum at the end of the trajectory and bootstraps with $v^(S_{t + n})$ or zero at termination. The idea — $n$ -step and GAE as bias-variance controls, what $λ$ does, and which extreme each $λ$ recovers — is examinable. Detailed numeric sensitivity to $λ$ is not the focus of examination computation. GAE was flagged as required at this high level because it appears pervasively in contemporary papers, including PPO.

Two confusions break GAE answers:

Pitfalls to avoid:

Writing GAE as $(γ λ)^{l} G_{t + l}$ or omitting $δ$ . GAE sums TD errors $δ_{t + l}$ , not raw rewards or returns. Summing rewards directly is the $n$ -step return, not GAE.
Treating $λ$ as the discount. $γ$ discounts future reward for the objective; $λ$ discounts how far into the future the advantage looks for variance control. They multiply as $γ λ$ but play distinct roles — $γ$ is part of the problem, $λ$ is an estimator design choice.

Recap and bridge: The advantage $Q^{π} - V^{π}$ judges actions relative to the state's average. Its $n$ -step estimator $\sum_{k = 0}^{n - 1} γ^{k} R_{t + k + 1} + γ^{n} v^(S_{t + n}) - v^(S_{t})$ and its exponentially smoothed form $A^_{t}^{GAE} = \sum_{l = 0}^{\infty} (γ λ)^{l} δ_{t + l}$ trade bias against variance — $λ = 0$ is one-step biased but stable, $λ = 1$ is Monte Carlo unbiased but noisy. That blended advantage is the signal PPO will reuse and clip — the next subsection's subject.

16.8.3 Proximal Policy Optimization (PPO) — Motivation, Ratio, and Clipped Objective

Hook — data are precious, but reusing them is dangerous: In on-policy learning the usual cycle is collect a rollout with $π$ , use it for one gradient step, discard it, collect again with the new $π$ . When a rollout contains a rare success, discarding it after a single use is wasteful. PPO asks: can we squeeze several mini-batch updates out of the same rollout before discarding it, without letting the policy drift so far that the old data misleads it? The clipping mechanism is the guardrail that makes that reuse safe.

The on-policy cycle without reuse is: $π_{old}$ generates an episode, the episode is used once to update $π$ , the old episode is thrown away, $π$ generates fresh data, repeat. The motivating observation for PPO is that this is sample-inefficient when good experience is rare; the desire is to "reuse the rollout again and again for controlled mini-batch updates; once you have reused your rollouts enough number of times you discard and collect again." The risk of naive reuse is that $π_{θ}$ may move far from the $π_{θ_{old}}$ that actually produced the data, so gradients computed from old state-action frequencies become misleading and can cause a large, destabilizing jump — the "huge change of mind" that should not dominate the loss.

The drift is what must be measured before it can be bounded.

Probability ratio — the drift measure: Let $π_{θ_{old}} (a ∣ s)$ be the old policy that generated the rollout and $π_{θ} (a ∣ s)$ the current policy being updated, with $θ$ the actor parameters and $θ_{old}$ the snapshot at data-collection time. For the state-action $(S_{t}, A_{t})$ in the rollout, define $r_{t} (θ) = \frac{π _{θ} ( A _{t} ∣ S _{t} )}{π _{θ_{old}} ( A _{t} ∣ S _{t} )} .$ Here $r_{t} (θ) \in (0, \infty)$ is the likelihood ratio, $π_{θ_{old}} (A_{t} ∣ S_{t}) \in (0, 1]$ the probability the old policy assigned to the action actually taken, and $π_{θ} (A_{t} ∣ S_{t}) \in (0, 1]$ the probability the current policy assigns to that same action. Interpretation: $r_{t} (θ) = 1$ means today and yesterday agree on this action; $r_{t} (θ) > 1$ means the current policy emphasizes this action more than the old policy did; $r_{t} (θ) < 1$ means it de-emphasizes it. Naively maximizing $r_{t} (θ) A^_{t}$ would let large deviations of $r_{t}$ drive large updates.

Once drift can be measured, it can be bounded — the clipped objective is that bound.

Clipped objective — the guardrail: Let $A^_{t} \in R$ be the advantage estimate for $(S_{t}, A_{t})$ (typically the GAE value from 16.8.2) and let $ϵ \in (0, 1)$ , usually $0.1$ – $0.2$ , be the clipping parameter. Define the clipped ratio $clip (r_{t} (θ), 1 - ϵ, 1 + ϵ) = max (1 - ϵ, min (r_{t} (θ), 1 + ϵ)),$ which constrains the effective ratio to the interval $[1 - ϵ, 1 + ϵ]$ . The PPO clipped objective is $L^{CLIP} (θ) = E_{t} [min (r_{t} (θ) A^_{t}, clip (r_{t} (θ), 1 - ϵ, 1 + ϵ) A^_{t})] .$ Here the expectation $E_{t}$ is over time steps in the rollout batch, $A^_{t}$ weights whether the action should be made more or less likely, and the $min$ implements a pessimistic bound: when the unclipped term would improve the objective more than the clipped term allows, the clipped term is taken, removing the incentive for $r_{t}$ to leave the neighbourhood $[1 - ϵ, 1 + ϵ]$ . When $r_{t}$ is inside the interval, both terms inside the $min$ are equal and clipping has no effect.

Clipping intuition is easiest with the numbers quoted in class. Take $ϵ = 0.2$ so the allowed interval is $[0.8, 1.2]$ . The box below works three regimes with that interval.

Worked clipping arithmetic — three cases with $ϵ = 0.2$ :

Case 1 — modest increase, stays inside: Yesterday $π_{θ_{old}} (a ∣ s) = 0.80$ , today $π_{θ} (a ∣ s) = 0.90$ . $r = \frac{0.90}{0.80} = 1.125.$ Since $0.8 \leq 1.125 \leq 1.2$ , $clip (r, 0.8, 1.2) = 1.125$ . Clipping does nothing; both terms in the $min$ are $1.125 A^_{t}$ . A $12.5%$ increase is tolerated.

Case 2 — large increase, hits the ceiling: Yesterday $0.50$ , today $0.90$ . $r = \frac{0.90}{0.50} = 1.8.$ Since $1.8 > 1.2$ , $clip (r, 0.8, 1.2) = 1.2$ . If advantage is positive, say $A^_{t} = + 1.0$ , $r A^_{t} = 1.8, clip (r) A^_{t} = 1.2, min (1.8, 1.2) = 1.2.$ The objective is capped at $1.2 A^_{t}$ ; the extra $0.6 A^_{t}$ from pushing $r$ to $1.8$ is ignored. The "huge change of mind" from 0.5 to 0.9 is not allowed to dominate.

Case 3 — large decrease, hits the floor: Yesterday $0.50$ , today $0.10$ . $r = \frac{0.10}{0.50} = 0.20.$ Since $0.20 < 0.8$ , $clip (r, 0.8, 1.2) = 0.8$ . If advantage is negative, say $A^_{t} = - 1.0$ , $r A^_{t} = - 0.20, clip (r) A^_{t} = - 0.80, min (- 0.20, - 0.80) = - 0.80.$ Here $min$ again picks the more pessimistic (more negative) value, preventing the large drop from being exploited. Sense-check: Clipping is not symmetric in its effect — it always takes the worse of the clipped and unclipped terms, which is why $L^{CLIP}$ is a lower bound on the unclipped surrogate. When $A^_{t} > 0$ , clipping caps how much $r > 1$ can help; when $A^_{t} < 0$ , clipping caps how much $r < 1$ can help — in both cases it removes the incentive to move $r$ far outside $[1 - ϵ, 1 + ϵ]$ .

The training cycle that this objective supports was described procedurally: collect a fresh rollout (a sequence of interactions), compute advantages $A^_{t}$ for that rollout (typically via GAE), then reuse the same rollout for several controlled mini-batch epochs — for example 4 epochs of mini-batches — optimising $L^{CLIP}$ each time, and only then discard the rollout and collect again with the now-updated policy. The earlier performance measure $J (θ) = E [G_{t}]$ from tabular policy gradients expressed the same "want to improve" intention; PPO translates it into this clipped surrogate, with the sign convention flipped to a loss to be minimized or an objective to be maximized via gradient steps on $L^{CLIP}$ .

Visual intuition — imagine a leash of length $ϵ$ between today's policy and yesterday's policy for each state-action. The ratio $r_{t} (θ)$ is how far the dog has pulled; inside $[1 - ϵ, 1 + ϵ]$ the leash is slack and the dog moves freely; at the boundary the leash goes taut and further pulling in that direction does not move the owner — the gradient from that term is clipped. Positive advantage pulls toward larger $r$ , negative toward smaller $r$ , but neither pull matters beyond the leash length.

How reuse differs	Naive reuse of on-policy data	PPO clipped reuse
Objective	$E [r_{t} (θ) A^_{t}]$ unbounded in $r$	$E [min (r A^, clip (r, 1 \pm ϵ) A^)]$ bounded
Large $r$ when $A^_{t} > 0$	Encouraged without limit	Capped at $(1 + ϵ) A^_{t}$
Small $r$ when $A^_{t} < 0$	Encouraged without limit	Capped at $(1 - ϵ) A^_{t}$
Effect of $ϵ$	No guardrail	Trust region of radius $ϵ$ around $r = 1$

Assumptions and scope: PPO assumes on-policy rollouts (data from $π_{θ_{old}}$ ), a differentiable policy $π_{θ}$ , and an advantage estimator $A^_{t}$ . The ratio $r_{t} (θ)$ and clipping interval $[1 - ϵ, 1 + ϵ]$ with $ϵ$ typically $0.1$ – $0.2$ are the core mechanics. The idea — why PPO wants to reuse data, what $r_{t} (θ) = 1$ , $> 1$ , $< 1$ mean, what clipping does, and the rollout → advantages → mini-batch reuse → discard cycle — is examinable at the conceptual level introduced. The lecture explicitly says detailed PPO numerics are not required for the examination; the simplified worked illustration in the notes is recommended as a clearer entry point than the original papers when studying in free time.

A frequent misreading is to treat PPO as fully off-policy because it reuses old data.

Pitfalls to avoid:

Calling PPO off-policy. The data are generated by $π_{θ_{old}}$ but reused only within the proximal neighbourhood $[1 - ϵ, 1 + ϵ]$ and only for a few epochs before being discarded. True off-policy methods learn indefinitely from arbitrary behaviour policies; PPO is better described as controlled reuse of on-policy rollouts.
Applying clipping to the advantage instead of the ratio. Clipping acts on $r_{t} (θ)$ , not on $A^_{t}$ . Writing $clip (A^_{t}, \cdot)$ or $A^_{t} \pm ϵ$ misplaces the guardrail; the quantity bounded is how far the policy's probability for the taken action may move.

Recap and bridge: PPO reuses a fresh rollout for several mini-batch epochs before discarding it, but guards that reuse with $r_{t} (θ) = π_{θ} / π_{θ_{old}}$ clipped to $[1 - ϵ, 1 + ϵ]$ via $L^{CLIP} = E [min (r A^, clip (r, 1 \pm ϵ) A^)]$ . Inside the interval $r$ matters normally; outside, the $min$ removes the incentive to push $r$ further — a huge change of mind from yesterday to today cannot dominate the loss. With the A3C/A2C cycle, GAE blending, and PPO clipping in place, the remaining questions are the two students most often ask about off-policy reuse and what "middle ground" really means.

16.8.4 Student Questions and Answers on Advanced Policy Methods

Q: If PPO reuses old data for multiple updates, does that not make it off-policy? A: The data are indeed generated by an older policy $π_{θ_{old}}$ while updates are applied to the current $π_{θ}$ , so there is a mismatch. PPO acknowledges that mismatch through the ratio $r_{t} (θ) = π_{θ} (A_{t} ∣ S_{t}) / π_{θ_{old}} (A_{t} ∣ S_{t})$ and the clipping constraint $clip (r_{t}, 1 - ϵ, 1 + ϵ)$ . Reuse is allowed only within the proximal neighbourhood $∣ r_{t} - 1∣ \leq ϵ$ and only for a small, fixed number of epochs (for example 3–4) before the rollout is discarded and fresh on-policy data are collected with the new $π_{θ}$ . That controlled, short-horizon reuse distinguishes PPO from fully off-policy methods that would learn indefinitely from a fixed replay buffer under an arbitrary behaviour policy. The right description is reuse of on-policy rollouts with a trust-region guardrail, not off-policy learning.

Why GAE is repeatedly called the middle ground was the second point students asked to hear again.

Q: Why is GAE described as a middle ground, and what does $λ$ actually control? A: Because it blends many one-step TD errors $δ_{t + l}$ rather than committing to a single horizon $n$ . With $λ$ near $0$ the blend is dominated by the first few $δ$ 's — it inherits their low variance but also the bias of the critic $v^$ , behaving like the myopic one-step advantage. With $λ$ near $1$ the blend reaches far into the future and recovers the Monte Carlo advantage $G_{t} - v^(S_{t})$ — nearly unbiased but with the high variance of full returns. Intermediate $λ$ trades the two: each successive $δ_{t + l}$ is multiplied by another factor $γ λ$ , so its contribution is progressively down-weighted. Formally $A^_{t}^{GAE} = \sum_{l = 0}^{\infty} (γ λ)^{l} δ_{t + l}$ , with $γ$ the problem discount and $λ$ the estimator design knob. That soft, exponential weighting — versus the hard cutoff of a fixed $n$ -step — is why GAE is called a soft choice.

Exam-facing synthesis for this section:

Question that appears on the paper	What a good answer shows
Contrast A3C and A2C operationally	Five-step cycle (copy, roll out, compute, accumulate, apply) and whether step 5 is asynchronous unlocked or synchronized batched; A2C is the modern batched variant
Write an advantage estimator	One-step $δ_{t}$ , $n$ -step $A^_{t}^{(n)} = \sum_{k = 0}^{n - 1} γ^{k} R_{t + k + 1} + γ^{n} v^(S_{t + n}) - v^(S_{t})$ , and GAE $\sum_{l} (γ λ)^{l} δ_{t + l}$ with $λ \in [0, 1]$ and bias-variance interpretation
Explain PPO at idea level	Data are precious but on-policy data would be discarded after one use; PPO reuses a rollout for several mini-batch epochs, guarding drift via $r_{t} (θ) = π_{θ} / π_{θ_{old}}$ clipped to $[1 - ϵ, 1 + ϵ]$ and the pessimistic objective $L^{CLIP} = E [min (r A^, clip (r, 1 \pm ϵ) A^)]$

Recap and bridge: A3C versus A2C is asynchronous unlocked pushes versus synchronized batched pushes of the same five-step worker cycle; GAE is the exponential blend $\sum_{l} (γ λ)^{l} δ_{t + l}$ that soft-trades bias for variance between the myopic $δ_{t}$ and the noisy $G_{t} - v^$ ; PPO makes reuse safe by measuring drift as $r_{t} (θ) = π_{θ} / π_{θ_{old}}$ and clipping it to $[1 - ϵ, 1 + ϵ]$ inside a pessimistic $L^{CLIP}$ . No detailed PPO numerics are required for the examination — the ratio, the interval, the $min$ , and the rollout-advantages-minibatch-reuse-discard cycle are the ideas to carry forward. Together with the decision-time planning of 16.7, these policy methods complete the transition from single-trajectory actor-critic to the large-scale, stable training that underpins contemporary applications — including, as the next section shows, viewing a language model itself as a sequential policy.

16.9 Language Models Viewed as Sequential Policies

This closing perspective reframes a familiar system — a language model — in the vocabulary built across the lecture. What looked like next-word prediction becomes a policy, a trajectory, and an optimization problem identical in form to lane keeping and game playing.

16.9.1 A Language Model as a Sequential Policy

Hook — the language model as an agent that acts by writing: A chatbot does not answer in one shot. It chooses a word, sees the sentence so far, chooses the next word, sees the updated sentence, and continues until it decides to stop. Each word is an action that changes what the model sees next. That incremental, state-dependent choice is exactly what a sequential policy does.

The intuition is conversation as trajectory. A conversation starts with an initial context — the user's prompt and system instruction. The model emits a first token, the context grows by that token, the model emits a second token conditioned on the longer context, and so on. The full response is not scored word by word in isolation; the final quality — helpfulness, correctness, tone — is judged after the sequence is complete. In reinforcement-learning language, the sequence of contexts and tokens is a trajectory and the final judgement is a return that credits every token choice.

Language model distribution: Let prompt $x$ be the initial context (for example "write a program that sorts a list"), let vocabulary $V$ be the finite token set, and let $y = (y_{1}, y_{2}, \dots, y_{T})$ with each $y_{t} \in V$ be the generated response. Let $θ$ be the model parameters. The model defines a conditional distribution over full responses $p_{θ} (y ∣ x) \in [0, 1], y \sum p_{θ} (y ∣ x) = 1,$ where $T$ may vary across responses and termination is signalled by a special end-of-sequence token $EOS \in V$ or a length limit.

This joint distribution is not parametrized directly over exponentially many sequences. It is factorized autoregressively.

Chain-rule factorization — 16.9.formula.1: By the chain rule of probability applied to the token sequence, $p_{θ} (y ∣ x) = t = 1 \prod T p_{θ} (y_{t} ∣ x, y_{1}, \dots, y_{t - 1}) = t = 1 \prod T p_{θ} (y_{t} ∣ x, y_{< t}),$ where $y_{< t}$ denotes $(y_{1}, \dots, y_{t - 1})$ with $y_{< 1}$ empty, each factor $p_{θ} (y_{t} ∣ x, y_{< t}) \in [0, 1]$ is the next-token distribution given the prompt and all earlier tokens, and $\sum_{v \in V} p_{θ} (v ∣ x, y_{< t}) = 1$ for every prefix. Taking logarithms gives the sum used in training, $lo g p_{θ} (y ∣ x) = t = 1 \sum T lo g p_{θ} (y_{t} ∣ x, y_{< t}) .$ Each factor is produced by the same network $θ$ conditioned on a growing context, so generating a response is sampling a trajectory one factor at a time.

In reinforcement-learning terms each factor is already a policy. Writing $s_{t} = (x, y_{< t})$ for the context before step $t$ and $a_{t} = y_{t}$ for the token chosen at that step, $π_{θ} (a_{t} ∣ s_{t}) = p_{θ} (y_{t} ∣ x, y_{< t}),$ so the factorization reads $p_{θ} (y ∣ x) = \prod_{t = 1}^{T} π_{θ} (a_{t} ∣ s_{t})$ . The probability of a full response is the product of policy decisions along its trajectory — identical in form to the trajectory probability $\prod_{t} π_{θ} (A_{t} ∣ S_{t})$ that appears in REINFORCE.

Visual intuition — draw a horizontal timeline of $T$ steps. At step $t$ a box holds the current state $s_{t} = (x, y_{< t})$ — the prompt plus the prefix built so far, for example "write a program" $\to$ "write a program: def". An arrow labelled $π_{θ} (\cdot ∣ s_{t})$ fans out to the vocabulary, one token $a_{t} = y_{t}$ is sampled and appended, producing $s_{t + 1}$ . Repeating the loop builds the full sequence. Below the timeline the product $\prod_{t} π_{θ} (a_{t} ∣ s_{t})$ accumulates to $p_{θ} (y ∣ x)$ . A terminal EOS token caps the trajectory; before EOS the process is open, after EOS the episode ends.

Illustration — a three-token response with the factorization visible: Take prompt $x =$ "complete: Hello". Suppose the model generates $y = (Hello, world,!)$ in three steps: $p_{θ} (y ∣ x) = p_{θ} (Hello ∣ x) \times p_{θ} (world ∣ x, Hello) \times p_{θ} (! ∣ x, Hello world) .$ If the three factors are $0.8$ , $0.6$ , and $0.9$ , then $p_{θ} (y ∣ x) = 0.432$ and $lo g p_{θ} (y ∣ x) = lo g 0.8 + lo g 0.6 + lo g 0.9$ . Changing $θ$ to increase any factor increases the joint probability of the responses that contain it — exactly how a policy update shifts probability toward rewarded trajectories.

What is not being claimed: This view does not change how the language model is architecturally implemented. The same transformer that was trained to predict the next token is reinterpreted as a policy; no new network is introduced by the reinterpretation. The benefit is vocabulary: optimization ideas from earlier sections — REINFORCE's $G_{t} \nabla lo g π$ , baselines, actor-critic TD errors, GAE, and PPO's clipped reuse — can be applied to language-model fine-tuning by substituting $(s_{t}, a_{t}, π_{θ})$ with the elements above.

16.9.2 Mapping Reinforcement-Learning Elements to Language-Model Elements

Complete mapping: The correspondence is one-to-one between the MDP vocabulary of Sections 16.2–16.8 and the language-model vocabulary:

MDP element	Symbol	Language-model element	Concrete instance
State	$s_{t} = (x, y_{< t})$	Prompt plus all tokens generated so far	Instruction "write a program" concatenated with the code emitted up to the current position
Action	$a_{t} = y_{t} \in V$	Next token chosen from the vocabulary	Choosing "def" from among keywords and subword tokens
Policy	$π_{θ} (a_{t} ∣ s_{t}) = p_{θ} (y_{t} ∣ x, y_{< t})$	Next-token distribution the model outputs at step $t$	Softmax over $V$ conditioned on the growing context
Transition	$s_{t + 1} = (s_{t}, a_{t})$	Deterministic concatenation	Appending the sampled token to the context
Episode / trajectory	$τ = (s_{1}, a_{1}, \dots, s_{T}, a_{T}, s_{T + 1})$	One completed response	User asks for a letter, model generates token by token until $EOS$ or length limit
Reward	$R (τ)$ or $r_{t}$	Quality of the response	Human thumbs-up, pairwise preference, or score from a reward model; typically sparse and given at the end
Reward model	$r^_{ϕ} (x, y)$	Learned evaluator of response quality	Model trained on human comparisons that maps $(x, y)$ to a scalar score used as the optimization signal

Here $x$ is the prompt, $V$ the vocabulary, $EOS$ the end-of-sequence token, and $ϕ$ the reward-model parameters (distinct from policy parameters $θ$ ). The transition is deterministic — choosing $a_{t}$ fully determines $s_{t + 1}$ — so all stochasticity is in the policy.

This mapping clarifies where the reward comes from. In classical control the environment returns a numeric reward; in language, quality is a human judgement. In practice the judgement is distilled into a reward model $r^_{ϕ} (x, y)$ trained from multiple signals — ratings, comparisons, or pairwise preferences — that evaluates how useful or appropriate a response was. The lecture's phrasing that quality "can be inferred from multiple places" and that "what you actually do is to learn a model, a reward model, which will evaluate various parameters and tell you how good this response was" refers to this object. Once $r^_{ϕ}$ is available, it supplies the scalar reward for policy optimization.

Real-world — RLHF and DPO as policy optimization on this MDP: Reinforcement learning with human feedback (RLHF) collects human comparisons between responses, trains a reward model $r^_{ϕ} (x, y)$ to predict the preferred response, and then fine-tunes $π_{θ}$ to maximize $r^_{ϕ}$ with a policy-gradient method — often PPO — regularized to stay close to the original model. Direct preference optimization (DPO) reaches a similar end by optimizing the policy directly from preferences without an explicit scalar reward model. Both frame the same problem: state is prompt plus prefix, action is next token, policy is the next-token distribution, and trajectory quality is preference. This is why the A3C/A2C, GAE, and PPO machinery of Section 16.8 reappears in contemporary language-model training.

The view is unifying rather than expansive: it does not add a new algorithm to memorize but shows that the states, actions, policies, episodes, and rewards defined for grid worlds, lane keeping, and game planning already organize language-model fine-tuning.

Recap: A language model defines $p_{θ} (y ∣ x) = \prod_{t = 1}^{T} p_{θ} (y_{t} ∣ x, y_{< t})$ where each factor is a policy $π_{θ} (a_{t} ∣ s_{t})$ over next tokens, state is prompt plus prefix $s_{t} = (x, y_{< t})$ , action is the next token, transition is concatenation, an episode is a completed response ending at $EOS$ or length limit, and reward is response quality typically supplied by a learned reward model $r^_{ϕ}$ . That identification lets the policy-gradient, advantage-estimation, and PPO ideas of earlier sections transfer to RLHF and DPO for language models.

Exam Guidance Summary

This appendix consolidates every explicit scope and study instruction issued during the session. It does not add new material; it organizes what is examinable, what is background only, and how to use the open-book format. Keep the algorithm sheets flagged for quick reference and treat this page as the checklist for revision.

How to use this summary: The lecture notes are a 191-page superset spanning all ambitions for the course across offerings. Only topics actually delivered in class and at the depth delivered in class are examinable at this offering; ambition material earmarked for future re-alignment is not. The slides and the textbook are authoritative companions to the notes — where the notes compress what was taught in detail, follow the slides and textbook. The examination is open-book; no parameter values, paper years, or line-by-line algorithm text need to be memorized, but the ability to interpret and apply the material is essential.

Scope by topic — what to prioritize

General scope. Notes are a 191-page superset; examinable scope follows delivered content only. Slides and textbook are the authoritative companions where notes are compressed.

Foundations (classes 1–6) and dynamic programming. As previously covered for the midterm, these remain background that every later topic builds upon. No change in scope; treat as assumed knowledge for all later numerics.

Off-policy Monte Carlo. Examinable: definition of off-policy learning, the importance-sampling ratio $ρ$ and its product form, and its numerical use (basic sections and the numerical), and the off-policy Monte Carlo prediction and control algorithm of the notes' Section 8. For understanding and post-course enrichment only: statistical-behaviour derivations and the application survey. Practice the backward incremental sweep involving $W$ and $C$ .

Temporal-difference learning. Examinable: what temporal difference is, how it takes the best of dynamic programming and Monte Carlo, the meaning of temporal-difference target and temporal-difference error (one-step $δ_{t} = R_{t + 1} + γ v^(S_{t + 1}) - v^(S_{t})$ and its multi-step generalization), the grid-world running example, the control loop (initial $Q$ , $ϵ$ -greedy policy derived from $Q$ , update that simultaneously improves $Q$ and policy), and the three algorithms SARSA, Q-learning and Expected SARSA — including which parts of their update targets differ. Maximization bias and how double Q-learning addresses it are important to understand irrespective of a guarantee that a question will appear on them. Recommended practice: random-walk extra problems. For numerical precision, commit to one exact algorithm statement (notes versus slides) and use it consistently.

On-policy prediction with approximation. Examinable: mean squared value error as the objective, stochastic gradient descent as the optimizer and when to use it, the semi-gradient distinction, and the two pairings (Monte Carlo versus temporal difference with approximation). The textbook summary image (exhaustive search versus temporal difference, width versus depth trade-off) is examinable. Feature construction (coarse coding, tile coding, radial basis functions) is examinable at the class-taught level; the notes' expanded deep-learning feature-extraction survey is lower priority for this examination and higher priority for post-course reading. For this block, prioritize the textbook and slides over the notes.

Deep Q-Networks. One-plus class of coverage; the 2015 version plus the incremental Double DQN idea are sufficient — the 2013 version need not be studied separately because its content is contained in the 2015 version. Experience replay is the deepest examinable point: be able to explain reuse, decorrelation and distribution smoothing beyond the one-line definitions, and to argue why replay helps or would not help in a new scenario. Not examinable: sections from Section 10 onward in the DQN notes and the games-solved-by-DQN surveys. Entirely out of scope: Section 13 of the DQN notes — marked as ambition for the next offering — including bias in DQN there.

Policy-gradient methods. Examinable: the policy-gradient theorem statement and its implication (gradient involves $\nabla_{θ} lo g π$ ) — the proof is explicitly not examinable (post-examination pointer: Grokking Deep Reinforcement Learning for an accessible proof). Examinable at the conceptual level and through the lane-keeping numerics: REINFORCE, REINFORCE with baseline, and actor-critic with one-hot states, $μ = θ^{⊤} x (s)$ , $σ = 0.2$ constant, $θ_{μ}^{(0)} = [- 0.5, 0, 0.5]^{⊤}$ , $α$ and $γ$ given, and $G$ versus $G - v^$ versus $δ$ weighting the same $\nabla lo g π$ . The Gaussian log-policy derivation and the substitution $\nabla lo g π = (a - μ) / σ^{2} \cdot x (s)$ are expected; changing $π$ 's form changes only that derivative, the rest remaining mechanical. Not required: Section 11 of the policy-gradient notes (softmax alternative for discretized steering) and the optional Section 13 onward. The shared intermediate notes on lane keeping are provided for practice and verification but are not themselves examination material.

MCTS / AlphaGo / AlphaZero / MuZero / Planet — guest session. Examinable: motivation for model-based learning, meaning of decision-time planning, and MCTS at the four-stage level (selection, expansion, simulation, backup) with the UCT rule understood as UCB on a tree, including the ability to trace a couple of iterations through the two numerics flagged (guest's class example and the small notes numerical). For AlphaGo, AlphaZero, MuZero and Planet, examinable at a high level: what each work accomplished, its key technical improvement, and how it uses MCTS. Explicitly not expected: specific pseudocode and parameter values from those papers.

Advanced policy themes — A3C/A2C, GAE, PPO, and language models as policies. Examinable at the operational level: the A3C/A2C five-step worker cycle and the asynchronous-versus-synchronized distinction. Examinable at the trade-off level: generalized advantage estimation — $n$ -step versus one-step versus GAE as a $λ$ -weighted sum of TD errors $A^_{t}^{GAE} = \sum_{l} (γ λ)^{l} δ_{t + l}$ , with the bias–variance interpretation. Examinable at the idea level: PPO's cycle — collect a fresh rollout, compute advantages, reuse the same rollout for controlled mini-batch updates before discarding, the ratio $r_{t} (θ) = π_{θ} / π_{θ_{old}}$ and the meaning of $r > 1$ / $r < 1$ / $r = 1$ , and clipping to $[1 - ϵ, 1 + ϵ]$ to prevent large changes of mind from dominating the loss; detailed PPO numerics were explicitly marked as not required (use the simplified notes illustration when free as an easier entry point than the research papers). Viewing a language model as a sequential policy — state as prompt plus generated prefix, action as next token, policy as next-token distribution, episode as a completed response ending with EOS or length limit, and reward via a reward model — was introduced as a unifying application perspective; it consolidates rather than extends the assessed material and is examinable at the mapping level above. From Section 15: the promised imitation-learning session (DAgger, about one hour) is the only topic that will be covered in depth; inverse reinforcement learning and reward modeling (as used in DPO), multi-agent reinforcement learning, and safety in reinforcement learning will be introduced only at a what-it-is and what-it-models level.

Practical conduct

Open-book discipline: Have the algorithm sheets cleanly flagged for quick reference. Write all assumptions explicitly. Show work in tables where applicable; a tabular layout is easier to grade than scattered prose. If any hyperparameter or definition is missing from a problem statement, ask or declare an explicit assumption rather than guessing silently.

Recap — revision priority in one scan: Foundations are assumed background. Off-policy Monte Carlo, temporal difference (including SARSA, Q-learning, Expected SARSA, and double Q-learning), function approximation, DQN with replay, policy gradients through lane-keeping numerics, MCTS with UCT, and the A3C/A2C–GAE–PPO chain plus the language-model-as-policy mapping are examinable at the depths named above. Statistical derivations, application surveys, and ambition sections are enrichment unless explicitly listed. The proof of the policy-gradient theorem and detailed PPO numerics are not required; the theorem statement, REINFORCE mechanics, and PPO's ratio-clipping idea are.

Key Industry Applications

This appendix maps each major method from the lecture to a named industry domain that uses the same structure. It does not introduce new examination material; it shows where the ideas reappear in production systems.

How to read this appendix: Each entry names a domain, the lecture concept it instantiates, and the concrete transfer. The same state–action–policy–episode–reward vocabulary organizes all of them — from tree search to language-model alignment.

Planning and search — game playing and logistics optimization. The exhaustive-search versus temporal-difference spectrum is not merely a pedagogical diagram — the same trade-off appears in production planning where full tree expansion is infeasible and sampling-based planning (MCTS-style) or learned value heuristics are used instead. The width–versus–depth choice the textbook image makes visible governs how logistics, scheduling, and game-playing systems allocate computation.

Value prediction with generalization — recommendation and large-scale state evaluation. Function approximation with $w^{⊤} x (s)$ as a linear precursor to deep-network approximation underpins every modern value-prediction system that generalizes across states. The substitution of a deep network wherever the notes write the linear form is how deployed reinforcement-learning systems scale from textbook grid worlds to high-dimensional inputs such as user–item contexts in recommendation and content ranking.

Deep reinforcement learning from high-dimensional observations — game AI and visual control. Deep Q-Networks as scaled Q-learning with function approximation, together with experience replay for decorrelation and sample efficiency, are the template behind game-playing agents that operate directly on high-dimensional observations — the notes' games-solved-by-DQN surveys point to that class of application, which extends to visual navigation and simulated control where observations are images rather than compact states.

Continuous control — robotics and lane-keeping assistance. The stochastic policy $π (a ∣ s; θ)$ parametrized as a Gaussian $N (μ (s), σ^{2})$ with $μ (s) = θ_{μ}^{⊤} x (s)$ is the standard continuous-control parametrization in industrial control problems; the lane-keeping assistance problem is a representative instantiation — keeping a vehicle centred in a lane with continuous steering in $[- 1, + 1]$ and a $+ 1$ reward for centre — of the same class that includes robotic manipulation, autonomous driving, and industrial process control.

Decision-time planning — the Alpha family of game-playing systems. Decision-time planning via Monte Carlo Tree Search, with the UCT rule balancing exploration and exploitation in the tree, is the search backbone behind the Alpha family — AlphaGo, AlphaZero, MuZero and Planet — each of which applies MCTS over a learned model with progressively less reliance on hand-crafted knowledge and progressively more on learned dynamics. The pattern transfers wherever a simulator or learned world model is available for lookahead.

Distributed training — large-scale reinforcement learning infrastructure. Parallel actor-critic architectures — A3C with asynchronous unlocked updates and A2C with synchronized batched rollouts — are the design pattern for distributed reinforcement-learning training, where many workers explore independently and contribute to a shared master policy. The same coordinator–worker structure underpins data-centre-scale training for games, robotics fleets, and language-model fine-tuning.

Stable large-scale policy optimization — RLHF and DPO pipelines. Generalized advantage estimation as a bias–variance-controlled blend of TD-error signals and proximal policy optimization as a clipped, reuse-aware on-policy updater are the current default combination for training large-scale policies, including the reinforcement-learning-with-human-feedback (RLHF) and direct-preference-optimization (DPO) pipelines that fine-tune language models. PPO's ratio $r_{t} (θ)$ and interval $[1 - ϵ, 1 + ϵ]$ are what make reuse of on-policy rollouts safe at that scale.

Language models as sequential decision-makers — conversational AI and code generation. Viewing a language model as a sequential policy $p_{θ} (y ∣ x) = \prod_{t} p_{θ} (y_{t} ∣ x, y_{< t})$ with state as prompt plus prefix, action as next token, episode as a completed response, and reward supplied by a learned reward model is how modern RLHF and DPO systems frame language-model alignment — the same MDP vocabulary that organizes grid-world control now organizes the training of conversational and code-generation models.

Data efficiency — sample-efficient learning in any sequential-data system. Experience replay's three purposes — reuse, decorrelation and distribution smoothing — generalize to any data-driven system where sequential correlations would otherwise bias learning and where carefully curated historical data improve efficiency, from offline reinforcement learning on logged interactions to continual learning from production traces.

Recap: Grid worlds illustrate tabular control; approximation and deep Q-networks scale that control to high-dimensional domains such as recommendations and game AI; Gaussian policies instantiate continuous control in robotics and driving; MCTS with UCT powers the Alpha family; A3C/A2C, GAE, and PPO supply the distributed, variance-controlled, reuse-safe training behind today's RLHF and DPO language-model pipelines; and the language-model-as-policy view unifies all of them under one vocabulary of states, actions, policies, episodes, and reward models.

DRL Lecture 16 notes · Comprehensive Examination Revision and Advanced Policy Methods

Deep Reinforcement Learning· postgraduate· 2026-08-22

Sections Breakdown

1Course Overview and Examination Scope

The 191-page notes are a superset; the examinable syllabus follows delivered lectures and slides, with an open-book examination that tests comprehension of every algorithm term rather than memoriza...

2Off-Policy Monte Carlo Methods

Off-policy Monte Carlo reweights episodes from a behaviour policy b to estimate values for a different target policy pi via the product importance-sampling ratio; ordinary and weighted estimators a...

3Temporal-Difference Learning

One-step TD combines dynamic-programming bootstrapping with Monte Carlo sampling via the target R+gamma V(S') and error delta; SARSA, Q-learning and Expected SARSA differ by their targets, and Doub...

4On-Policy Prediction with Function Approximation

Function approximation replaces a per-state table with a shared parametrized function vhat(s,w) trained to minimize MSVE under the on-policy distribution via SGD; the same template yields true-grad...

5Deep Q-Networks

DQN replaces tabular Q(s,a) with a convolutional network Q(s,a;theta) trained off-policy against the Bellman target r+gamma max Q(s',a';theta-) via squared-error regression, stabilized and made dat...

6Policy Gradient Methods and the Lane-Keeping Control Problem

Policy gradients follow nabla log pi(a|s;theta) weighted by return via the log-derivative trick; REINFORCE, its baseline variant (G - Vhat), and one-step actor-critic (delta = R+gamma Vhat(s')-Vhat...

7Model-Based Planning — MCTS, AlphaGo, MuZero and Planet

Decision-time planning uses a model to search from the current state before acting; MCTS makes this practical via iterative selection by UCT, expansion, fast rollout simulation, and backup, and the...

8Advanced Policy Methods — Asynchronous Methods, Generalized Advantage Estimation and Proximal Policy Optimization

Parallel actor-critic (A3C async vs A2C sync) scales the same five-step worker cycle; n-step and GAE advantage estimators trade bias for variance via horizon n or exponential weighting by lambda; P...

9Language Models Viewed as Sequential Policies

Reframes a language model as an autoregressive sequential policy via the chain rule p(y|x)=prod p(y_t|x,y_{\lt t}>); each factor is pi(a_t|s_t) with state s_t=(x,y_{\lt t}>), action next token, deterministic...

10Exam Guidance Summary

Appendix consolidating all examinable scope: 191-page notes are a superset — only delivered content is examinable; off-policy MC, TD/SARSA/Q-learning/Expected SARSA/double Q, function approximation...

11Key Industry Applications

Appendix mapping each method to a named domain: planning/search to logistics optimization, approximation to recommendation, DQN+replay to game AI/visual control, Gaussian policy to robotics and lan...

Postgraduate students in Deep Reinforcement Learning

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Course Overview and Examination Scope

Must-know: Notes are a superset — examinable scope follows delivered lectures and slides, not the full 191 pages; open-book means every algorithm is available but you must know what each symbol and step means and declare any assumed hyperparameters.

$See notes for formulas$

⚠️ Top pitfall: Treating the notes superset as the syllabus, or assuming hidden hyperparameters without declaring them on the answer sheet.

Self-check: What are the two valid preparation styles for any algorithm, and why does comfort with a chosen level matter more than memorizing line numbers?

Connects to: 16.2, 16.3, 16.4

Off-Policy Monte Carlo Methods

Must-know: Coverage requires b(a|s)>0 whenever pi(a|s)>0; per-step ratio rho_t=pi/b product along trajectory corrects the expectation because dynamics cancel; WIS divides by sum of weights, is biased finite-sample but low variance.

$ρ_{t : T - 1} = k = t \prod T - 1 \frac{π ( A _{k} ∣ S _{k} )}{b ( A _{k} ∣ S _{k} )}, 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}}$

⚠️ Top pitfall: Multiplying discount gamma or transition p into rho; dividing by visit count when the question asks for WIS; forgetting the break when At != pi(St) in control.

Self-check: Given pi(L|X)=0.8 and b(L|X)=0.5 for one step, what is rho_t, and does it up-weight or down-weight that transition?

Connects to: 16.3, 16.6, 16.8

Temporal-Difference Learning

Must-know: TD target is R+gamma V(S') and TD error is that minus V(S); SARSA uses sampled Q(S',A'), Q-learning uses max_a Q(S',a) (off-policy), Expected SARSA uses sum_a pi(a|S')Q(S',a); Double Q-learning decouples max selection from evaluation to remove positive bias.

$δ_{t} = R_{t + 1} + γ V (S_{t + 1}) - V (S_{t}), Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + α [R_{t + 1} + γ a max Q (S_{t + 1}, a) - Q (S_{t}, A_{t})]$

⚠️ Top pitfall: Calling Q-learning on-policy because its behaviour is epsilon-greedy; maintaining a separate policy table instead of deriving it from Q; forgetting Q(terminal)=0 bootstrap.

Self-check: Does updating Q(S,A) also update the policy at S, and why does Expected SARSA with a greedy pi collapse to Q-learning?

Connects to: 16.2, 16.4, 16.5

On-Policy Prediction with Function Approximation

Must-know: MSVE = E_{S~mu}[(v_pi(S)-vhat(S,w))^2] is the objective; linear vhat=w^T x(s) has gradient x(s); Monte Carlo update uses error G_t - vhat (true gradient) while TD(0) uses delta = R+gamma vhat(S')-vhat(S) as semi-gradient ignoring target dependence on w; linearity is a pedagogical stand-in for a neural network.

$v^(s, w) = w^{⊤} x (s), VE (w) = E_{S \sim μ} [(v_{π} (S) - v^(S, w))^{2}], w_{t + 1} = w_{t} + α [U_{t} - v^(S_{t}, w_{t})] \nabla_{w} v^(S_{t}, w_{t})$

⚠️ Top pitfall: Calling semi-gradient TD true gradient descent; forgetting that d << |S| forces trade-offs weighted by mu(s); assuming more features always helps.

Self-check: Why is the TD(0) update called semi-gradient and what target does it ignore when differentiating?

Connects to: 16.3, 16.5

Deep Q-Networks

Must-know: 2015 DQN subsumes 2013; Q(s,a;theta) outputs all K action values from one state in a single forward pass and is trained against y=r+gamma max Q(s',a';theta-); experience replay's three purposes are reuse, decorrelation, and distribution smoothing and must be argued beyond the three phrases.

$y = r + γ a^{'} max Q (s^{'}, a^{'}; θ^{-}), L_{i} (θ_{i}) = E_{s, a \sim ρ, s^{'} \sim E} [(y_{i} - Q (s, a; θ_{i}))^{2}], e_{t} = (s_{t}, a_{t}, r_{t}, s_{t + 1}) \in D$

⚠️ Top pitfall: Calling DQN on-policy because behaviour is epsilon-greedy; reciting reuse/decorrelation/smoothing without naming the tuple, buffer size, and violation of the i.i.d. assumption.

Self-check: Why must DQN be off-policy and why does uniform sampling from a million-entry buffer reduce variance?

Connects to: 16.3, 16.4, 16.6

Policy Gradient Methods and the Lane-Keeping Control Problem

Must-know: Policy gradient theorem gives nabla J = E[Q pi nabla log pi]; REINFORCE is theta <- theta + alpha gamma^t G_t nabla log pi with log-derivative trick; Gaussian log pi gradient is (a-mu)/sigma^2 x(s); baseline uses G-Vhat and actor-critic uses delta=R+gamma Vhat(s')-Vhat(s); lane-keeping has three one-hot states, sigma=0.2, theta0=[-0.5,0,0.5], worked left-state update to -0.45.

$θ \leftarrow θ + α γ^{t} G_{t} \nabla_{θ} lo g π (A_{t} ∣ S_{t}; θ), π (a ∣ s) = \frac{1}{2 π σ} e^{- (a - μ)^{2} /2 σ^{2}}, \nabla_{θ_{μ}} lo g π = \frac{a - μ}{σ ^{2}} x (s), δ_{t} = R_{t + 1} + γ v^(S_{t + 1}) - v^(S_{t})$

⚠️ Top pitfall: Treating mu(s) as the action instead of a sample from N(mu,sigma^2); updating all theta coordinates instead of only the visited state's one-hot coordinate; writing sigma instead of sigma^2 in the gradient denominator.

Self-check: Derive the Gaussian nabla log pi from pi -> log pi -> gradient and compute the left-state REINFORCE update for a=-0.3, sigma=0.2, G=1, alpha=0.01.

Connects to: 16.4, 16.5, 16.8

Model-Based Planning — MCTS, AlphaGo, MuZero and Planet

Must-know: Model-based vs model-free and decision-time vs background planning; MCTS four stages in order (selection, expansion, simulation/rollout, backup); UCT as UCB on a tree with exploration constant c; ability to trace 2 iterations computing UCT, expanding, simulating, and backing up counts/means; Alpha-family lineage at high level — milestone, improvement over predecessor, and how MCTS is used; DAgger in depth vs inverse RL / multi-agent / safety at intro level.

$UCT (s, a) = X ˉ (s, a) + c \frac{lo g N ( s )}{N ( s , a )}$

⚠️ Top pitfall: Swapping log N(s) with N(s) or N(s,a) in the UCT numerator; starting simulation from the root instead of the newly expanded leaf; conflating planning (using a model to search) with learning the model.

Self-check: Given root N(s0)=2, children (N=1,Xbar=1.0) and (N=1,Xbar=0.0), c=1.4, compute both UCT values and state which child selection picks; then expand the untried edge, assume rollout G=1, and write the updated N and Xbar along the visited path.

Connects to: 16.5, 16.6, 16.8

Advanced Policy Methods — Asynchronous Methods, Generalized Advantage Estimation and Proximal Policy Optimization

Must-know: A3C/A2C five-step worker cycle and async unlocked vs sync batched step-5 difference; n-step advantage and GAE A^GAE=sum (gamma lambda)^l delta_{t+l} with lambda in [0,1] bias-variance trade; PPO motivation (precious data, reuse), ratio r=pi/pi_old meaning r=1/>1/<1, clipping to [1-eps,1+eps] (eps 0.1-0.2), L_CLIP=E[min(rA, clip(r,1+-eps)A)], and rollout-advantages-minibatch reuse-discard cycle. No detailed PPO numerics required.

$A^_{t}^{GAE} = l = 0 \sum \infty (γ λ)^{l} δ_{t + l}, δ_{t} = R_{t + 1} + γ v^(S_{t + 1}) - v^(S_{t}), r_{t} (θ) = \frac{π _{θ} ( A _{t} ∣ S _{t} )}{π _{θ_{old}} ( A _{t} ∣ S _{t} )}, L^{CLIP} (θ) = E_{t} [min (r_{t} A^_{t}, clip (r_{t}, 1 - ϵ, 1 + ϵ) A^_{t})]$

⚠️ Top pitfall: Saying A3C has no master network; writing GAE over raw rewards instead of delta; clipping the advantage instead of the ratio r; calling PPO fully off-policy rather than controlled reuse of on-policy rollouts.

Self-check: List the 5 worker steps and say which step differs between A3C and A2C; write GAE and state what lambda=0 and lambda=1 recover; given pi_old=0.5, pi=0.9, eps=0.2 compute r and clip(r,0.8,1.2) and say which term min() picks when A>0.

Connects to: 16.6, 16.7, 16.9

Language Models Viewed as Sequential Policies

Must-know: Chain rule factorization p(y|x)=prod p(y_t|x,y_{\lt t}}) and log sum; RL mapping: s_t=(x,y_{\lt t}}), a_t=y_t, pi=p(y_t|x,y_{\lt t}}), episode ends at EOS/length, reward via learned reward model hat{r}_phi.

$p_{θ} (y ∣ x) = t = 1 \prod T p_{θ} (y_{t} ∣ x, y_{< t})$

⚠️ Top pitfall: Treating p(y|x) as a single joint table instead of product of policy factors; confusing state (prompt+prefix) with prompt alone; expecting per-token reward instead of sparse end-of-episode preference.

Self-check: Write p(y|x) as product over t, map each symbol to s_t/a_t/pi, and name where RLHF and DPO use the same MDP elements.

Connects to: 16.6

Exam Guidance Summary

Must-know: Notes are a superset; only delivered depth is examinable; slides/textbook authoritative where notes are compressed; open-book — no memorization of values or verbatim algorithms, but ability to interpret and compute is essential.

$Examinable scope follows delivered lectures and slides$

⚠️ Top pitfall: Revising ambition sections (e.g. DQN Section 13, games surveys, Section 11 softmax alternative) or memorizing paper pseudocode/parameters explicitly marked not expected.

Self-check: List each block's examinable boundary and one item explicitly marked out-of-scope for this offering.

Connects to: 16.2, 16.3, 16.4, 16.5, 16.6, 16.7, 16.8, 16.9

Key Industry Applications

Must-know: Each method's deployed counterpart: exhaustive-vs-TD trade-off, approximation generalization, DQN replay, Gaussian continuous control, MCTS+UCT, distributed actor-critic, GAE+PPO for RLHF/DPO, and LM as sequential policy.

$p_{θ} (y ∣ x) = t \prod p_{θ} (y_{t} ∣ x, y_{< t})$

⚠️ Top pitfall: Treating industry entries as new material to memorize rather than the same MDP vocabulary — state, action, policy, episode, reward — instantiated in a different domain.

Self-check: Name the domain for each method and state which MDP element it instantiates.

Connects to: 16.4, 16.5, 16.6, 16.7, 16.8, 16.9

Previous LectureLecture 15 · Model-Based Learning and Monte Carlo Tree Search

Next LectureLecture 01 · Software Development Lifecycle, Waterfall, and Agile

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

16.1 Course Overview and Examination Scope

16.1.1 Lecture Notes as a Superset and What Is Examinable

16.1.2 Course Chronology and Conceptual Anchors

16.1.3 How to Prepare from the Materials

16.2 Off-Policy Monte Carlo Methods

16.2.1 What Off-Policy Learning Is and Why Importance Sampling Is Needed

16.2.2 Importance Sampling — Mathematical Formulation

16.2.3 Off-Policy Monte Carlo Prediction and Control — Algorithm

16.2.4 Worked Perspective on Importance Sampling Numerics

16.3 Temporal-Difference Learning

16.3.1 Temporal Difference as the Best of Both Worlds

16.3.2 Mathematical Formulation — Targets, Errors and Updates

16.3.3 Worked Examples — Grid World, Random Walks and the Control Loop

16.3.4 Three Tabular Control Algorithms — SARSA, Q-Learning and Expected SARSA

16.3.5 Maximization Bias and Double Q-Learning

16.3.6 Student Questions and Answers on Temporal Difference

16.4 On-Policy Prediction with Function Approximation

16.4.1 Why Function Approximation and the Textbook Summary Image

16.4.2 Approximation Architecture — Linear and Non-Linear Forms

16.4.3 Prediction Objective — Mean Squared Value Error — and Gradient Descent

16.4.4 Feature Construction — Coarse Coding, Tile Coding and Radial Basis Functions

16.4.5 Student Questions and Answers on Approximation

16.5 Deep Q-Networks

16.5.1 How Deep Learning Helps Q-Learning

16.5.2 Experience Replay — Purpose Beyond the Three Bullet Points

16.5.3 Worked Example — Scope and Limits

16.6 Policy Gradient Methods and the Lane-Keeping Control Problem

16.6.1 Policy Gradient Theorem — Statement, Intuition and What to Skip

16.6.2 REINFORCE — Algorithm and Update in Words and Mathematics

16.6.3 The Lane-Keeping Assistance Problem — Full Specification

16.6.4 Means for Each State Under the Initial Parameters

16.6.5 Policy Density, Log-Policy and Its Gradient for the Gaussian

16.6.6 Worked Example — REINFORCE on a One-Step Episode

16.6.7 REINFORCE with Baseline — What Changes

16.6.8 Actor-Critic (One-Step) — Replacing G with the TD Error

16.6.9 Student Questions and Answers on Policy Gradients

16.7 Model-Based Planning — MCTS, AlphaGo, MuZero and Planet

16.7.1 Why Model-Based Learning and Decision-Time Planning

16.7.2 Monte Carlo Tree Search — The Four Stages and the UCT Formula

16.7.3 AlphaGo, AlphaZero, MuZero and Planet — What to Know and What Not to Memorize

16.7.4 Roadmap Items Deferred — Section 15 and Imitation Learning

16.8 Advanced Policy Methods — Asynchronous Methods, Generalized Advantage Estimation and Proximal Policy Optimization

16.8.1 Asynchronous Advantage Actor-Critic (A3C) and Synchronous Advantage Actor-Critic (A2C)

16.8.2 Advantage Estimation — From One-Step and n-Step to Generalized Advantage Estimation

16.8.3 Proximal Policy Optimization (PPO) — Motivation, Ratio, and Clipped Objective

16.8.4 Student Questions and Answers on Advanced Policy Methods

16.9 Language Models Viewed as Sequential Policies

16.9.1 A Language Model as a Sequential Policy

16.9.2 Mapping Reinforcement-Learning Elements to Language-Model Elements

Exam Guidance Summary

Scope by topic — what to prioritize

Practical conduct

Key Industry Applications

DRL Lecture 16 notes · Comprehensive Examination Revision and Advanced Policy Methods

Sections Breakdown

Exam Revision Notes

Course Overview and Examination Scope

Off-Policy Monte Carlo Methods

Temporal-Difference Learning

On-Policy Prediction with Function Approximation

Deep Q-Networks

Policy Gradient Methods and the Lane-Keeping Control Problem

Model-Based Planning — MCTS, AlphaGo, MuZero and Planet

Advanced Policy Methods — Asynchronous Methods, Generalized Advantage Estimation and Proximal Policy Optimization

Language Models Viewed as Sequential Policies

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

16.6.8 Actor-Critic (One-Step) — Replacing $G$ with the TD Error

16.8.2 Advantage Estimation — From One-Step and $n$ -Step to Generalized Advantage Estimation