Deep Reinforcement Learning

Temporal Difference Learning: TD(0), SARSA, and Q-Learning

📅 Published: 2026-07-11

🎓 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

Temporal-difference update rule & bootstrapping — covered in Lecture 1 (sections 1.17–1.18)
Markov Decision Processes, state & action value functions — covered in Lecture 4 (sections 4.33–4.34)
Value functions V^π, Q^π, and Generalized Policy Iteration — covered in Lecture 5 (sections 5.2–5.5.3)
Dynamic programming & the model-free Q-Learning preview — covered in Lecture 6 (sections 6.35–6.36)
Monte Carlo methods & the return G_t — covered in Lecture 7 (sections 7.6, 7.12–7.13)
Off-policy learning & importance sampling — covered in Lecture 9 (sections 9.4–9.5)

Temporal Difference Learning: TD(0), SARSA, and Q-Learning

10.1 Temporal Difference Learning — The Bridge Between Two Worlds

Hook: You are driving home from work. At 6 PM you guess the trip will take 30 minutes. Ten minutes later you are stuck in traffic. You now think it will take 45 more minutes. Do you really need to reach your driveway before updating your original guess? Or can you learn right now that 30 was too optimistic?

10.1.1 Definition and Explanation

Intuition + Analogy: Think of a weather forecaster. Dynamic programming is like a forecaster who has a perfect climate model — she simulates every possible weather pattern and averages them. Accurate, but she needs the model. Monte Carlo is like a forecaster who waits until the end of the month, tallies what actually happened. And only then adjusts her method. Accurate, but useless during the month. TD learning is like a forecaster who looks out the window at noon, sees dark clouds. And immediately bumps up the rain probability, the afternoon. She uses one real observation plus her existing beliefs about what clouds usually mean. That is bootstrapping: using a guess to improve a guess. Where the analogy breaks: the forecaster's "existing beliefs" are themselves learned from past weather, in TD, the value estimates are learned from the same episode stream. Creating a tighter feedback loop.

Temporal difference (TD) learning sits between two earlier approaches — dynamic programming and Monte Carlo methods. It takes the best from each and discards their weaknesses.

The mechanism is simple. You have a state $s_{t}$ with an estimated value $V (s_{t})$ . You want to pull that estimate toward a target — a number that tells you what the value should really be. The update always has the same shape: new value equals old value plus a fraction $α$ of the difference between target. Current estimate.

Formalize — the three families of value updates:

In dynamic programming, the target is an expected update. You look at every possible next state, weight each by its transition probability, and sum the weighted values. You need the full model $p (s^{'} ∣ s, a)$ for this:

$Target_{DP} = s^{'} \sum p (s^{'} ∣ s, a) \cdot V (s^{'})$

In Monte Carlo, the target is the return $G_{t}$ — the sum of all rewards from that moment until the episode ends:

$Target_{MC} = G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots$

In TD learning, the target is a one-step lookahead — the immediate reward plus the discounted estimate of the next state's value:

$Target_{TD} = R_{t + 1} + γ V (s_{t + 1})$

This makes TD learning model-free (no transition probabilities needed), online (updates happen every step), and local (only one step of lookahead). TD solves the main pain of Monte Carlo, waiting, the episode to finish, and the main pain of dynamic programming. Requiring a full model. Sutton, Barto call TD "a combination of Monte Carlo ideas, dynamic programming ideas." Like Monte Carlo. It learns from raw experience without a model. Like DP, it updates estimates based on other learned estimates — it bootstraps.

The idea in plain words: what is the immediate reward? What is the value of my neighbor? That is it. You look one step ahead and make an update.

10.1.2 The Three Targets — Side by Side

Worked Example: Imagine state $s_{t}$ with four possible next states. Up has value 100 with probability 0.7. Down, left, and right each have value 200 with probability 0.1 each. The current estimate of $s_{t}$ is $V (s_{t}) = 50$ .

Dynamic Programming target (expected update): $Target_{DP} = 0.7 \times 100 + 0.1 \times 200 + 0.1 \times 200 + 0.1 \times 200 = 130$ You need the model (transition probabilities) to compute this. Without them, you are stuck.

Monte Carlo target (return): $Target_{MC} = G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots$ You must go all the way to the end, sum every reward, and only then update.

TD learning target (one-step lookahead): $Target_{TD} = R_{t + 1} + γ V (s_{t + 1})$ You take one action, observe $R_{t + 1}$ and $s_{t + 1}$ , grab $V (s_{t + 1})$ from memory. Done. No model. No waiting.

Sense-check: The DP target (130) used all possible futures probabilistically. The MC target would use whatever actually happened in the episode, it could be 100, 200 depending on. Next state the agent landed in. The TD target uses the one actual reward plus the stored estimate of the one actual next state, a single sample, bootstrapped. TD lives between the two extremes.

10.1.3 Why This Matters — The Best of Both Worlds

Property	Dynamic Programming	Monte Carlo	TD Learning
Model-free?	No (needs model)	Yes	Yes
Online updates?	Can be	No (waits for episode end)	Yes (every step)
Local learning?	Yes (immediate neighbors)	No (full episode depth)	Yes (one step)
Needs complete episode?	No	Yes	No
Bootstraps?	Yes	No	Yes
Samples?	No (expectations)	Yes	Yes

Dynamic programming is democratic — it takes everybody's opinion into account, weighted by probability. Monte Carlo is experiential — you live through it and then judge. TD is pragmatic — you peek one step ahead and adjust your estimate right there.

Assumptions & Scope: TD(0) assumes the environment is a Markov Decision Process, the next state, reward depend only on the current state, action. Not on history. This matters because TD bootstraps from $V (s_{t + 1})$ , which only summarizes the future if the Markov property holds. In partially observable environments (where you cannot see the full state), TD can still work, function approximation, but the theory gets weaker. TD also assumes episodes eventually terminate (for the basic form). However, it can be adapted to continuing tasks. If the step size $α$ is held constant, the values never fully settle — they keep fluctuating around the true value. Convergence requires $α$ to decay over time (the Robbins-Monro conditions: $\sum α_{t} = \infty$ and $\sum α_{t}^{2} < \infty$ ). With linear function approximation, TD(0) convergence is guaranteed. With nonlinear approximation (neural networks), convergence is not guaranteed. Despite this, it works well in practice.

Visual Intuition: Picture a timeline running left to right. Place three dots on it: the current state $s_{t}$ , the next state $s_{t + 1}$ , and the terminal state $s_{T}$ . DP looks sideways at all neighbors of $s_{t}$ simultaneously — a fan-out of arrows from $s_{t}$ to every possible $s_{t + 1}$ . MC draws one long arrow from $s_{t}$ all the way to $s_{T}$ , collecting every reward along the way. Then feeds the whole sum back. TD draws exactly one short arrow from $s_{t}$ to $s_{t + 1}$ , picks up the single reward on, step, and then bootstraps. It uses the stored value at $s_{t + 1}$ as a proxy, everything from $s_{t + 1}$ to the end. The one-step arrow is the key: it is short enough to be model-free and online, long enough to carry real reward information.

Pitfalls:

Confusing TD with MC — TD updates every step using bootstrapped values. MC updates only at episode end using actual returns. If you try to compute TD updates at episode end like MC. You are doing batch TD (which converges to the certainty-equivalence estimate), not online TD.
Ignoring the Markov assumption — TD bootstraps from $V (s_{t + 1})$ . If the state representation is not Markov (you are missing relevant history), then $V (s_{t + 1})$ may be a poor summary. The updates will be biased.
Using $α = 1$ blindly — The professor showed $α = 1$ for illustration. In practice, $α = 1$ gives wildly unstable updates. Values oscillate and never converge. Use small $α$ (e.g., 0.01–0.1) with tabular methods, or adaptive optimizers with function approximation.
Forgetting that TD bootstraps from an imperfect estimate — The target $R_{t + 1} + γ V (s_{t + 1})$ uses $V (s_{t + 1})$ which is itself being learned. This creates a moving target. The estimate is biased unless values have converged. This is the cost of not waiting for the true return.

Student Q&A — Deduplicated:

Q: Several students asked: how are episodes generated in TD learning? Is it on-policy or off-policy? How do early states get updated when rewards are far away (like in chess)?

A: The generation process is the same as Monte Carlo, you start, a state, follow a policy to pick actions, and observe rewards. Next states. The difference is purely in when you update. In Monte Carlo, you generate the whole episode and then walk backward, updating each state with the full return. In TD, after every single step you update immediately using only the immediate reward and the next state's stored value. For chess-like games with long-delayed rewards: it is true that early states barely change at first when all values are zero. But once the terminal reward propagates backward, first the state one step before the win gets updated, then two steps back. Then three, the values ripple upstream. After enough episodes, the early states converge too. TD does not need the whole episode stored in memory, which is a major advantage for long-horizon tasks.

10.1.4 Symbol Registry — TD Learning Foundation

$V (s)$ — state value function — scalar estimate of how good state $s$ is
$Q (s, a)$ — action value function — scalar estimate of how good it is to take action $a$ in state $s$
$R_{t + 1}$ — immediate reward received after taking an action from state $s_{t}$
$γ$ — discount factor, $γ \in [0, 1]$ — weighs future rewards
$α$ — step size (learning rate), $α \in (0, 1]$ — how much the new observation pulls the estimate
$s_{t}$ — current state at time $t$
$s_{t + 1}$ (or $s^{'}$ ) — next state after taking an action
$a_{t}$ — action taken at time $t$
$G_{t}$ — return — discounted sum of rewards from time $t$ onward

10.1.5 References

Sutton & Barto, Reinforcement Learning: An Introduction, Chapter 6, pages 119–124. Discusses whether TD methods are sound. Compares convergence rates of TD vs Monte Carlo using the random walk example.
The textbook notes that mathematically proving which method (TD or MC) converges faster is still an open question. However, in practice, TD methods have usually been found to converge faster than Monte Carlo methods on stochastic tasks.
Sutton & Barto Example 6.1 (Driving Home): shows, TD updates during an episode require no waiting, while MC must wait until arrival.

Recap + Bridge: TD learning combines the best of dynamic programming (bootstrapping, online updates) and Monte Carlo (model-free, sampling). It is the central idea in reinforcement learning — every algorithm from SARSA to DQN is built on the TD update. Next, we look at the signal that powers this update: the TD error.

Real-World & Domain Connection: TD learning powers the value estimation at the heart of AlphaGo, AlphaZero, the neural networks. Evaluate board positions are trained using TD-style bootstrapped targets. In quantitative finance, TD methods price options by learning the expected payoff without needing a full model of market dynamics. In robotics, TD enables a robot arm to learn a reaching policy online. Adjusting its motor commands after every tiny movement rather than waiting, the full reach to complete. Whether you are building a game-playing agent, a trading algorithm, or a physical robot. The ability to learn from every single step is what makes TD the workhorse of modern RL. You do not need to wait until episode boundaries.

10.2 The TD Error — The Signal That Drives Learning

Hook: You check your phone and the weather app says 72 degrees. You step outside. It feels like 80. Your internal thermometer and the app disagree. The mismatch — that 8-degree gap — is what makes you revise your belief about today's temperature. In TD learning, that gap has a name.

10.2.1 Definition and Explanation

Intuition + Analogy: Imagine you are learning the fair price of used cars. You see a 2018 sedan listed at 15,000. Your current estimate for that model is 14,000. You check one data point: a nearly identical car just sold, 13,500, and you believe the remaining depreciation from. Sale price to your target car is about 1,000. Your target is 13,500 plus 1,000 = 14,500. The gap between the target (14,500) and your estimate (14,000) is +500. That gap — the TD error — tells you to nudge your estimate upward. A negative gap nudges it downward. The TD error is your surprise signal. Where the analogy breaks: in TD learning, both the "sale price" (reward), the "remaining value" (next state estimate) come from the same learning process. So the target itself shifts as you learn. Used car prices do not shift just because you updated your spreadsheet.

Formalize: The TD error written $δ_{t}$ , is the difference between what you expected, what you actually observed plus what you now expect from the next state:

$δ_{t} = TD target R_{t + 1} + γ V (s_{t + 1}) - current estimate V (s_{t})$

The TD target $R_{t + 1} + γ V (s_{t + 1})$ is the better-informed estimate — it has seen one real reward and one real transition. Your current estimate $V (s_{t})$ is the older, less-informed number. The TD error measures how much the world surprised you on this step. If $δ_{t} > 0$ , the world looks better than expected — your estimate rises. If $δ_{t} < 0$ , the world looks worse — your estimate falls.

The update rule pulls the current estimate toward the target:

$V (s_{t}) \leftarrow V (s_{t}) + α \cdot δ_{t}$

Expanded:

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

This is the TD(0) update — the "0" means a one-step lookahead. It is a special case of TD( $λ$ ), discussed later.

Key insight from Sutton & Barto (Eq. 6.6): If the value function $V$ does not change during an episode (as in Monte Carlo). The Monte Carlo error can be written as a sum of TD errors:

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

This means the full-return error is exactly the discounted sum of all future TD errors. Each TD error is one slice of the total surprise. TD(0) uses only the first slice ( $δ_{t}$ ). Multi-step methods use several slices. Monte Carlo uses all of them. This identity is the mathematical bridge between TD and MC.

Worked Example — the Apartment and Lift Analogy: You are in the lobby of an apartment building. Your route: lobby $\to$ walk to lift 1 $\to$ take lift to 5th floor $\to$ walk across the floor $\to$ take lift 2 $\to$ arrive at 10th floor. You have initial time estimates (in minutes) for each leg.

One day, everything is slower:

Leg	Usual time	Today's time
Lobby → Lift 1	2	3
Lift 1 ride	2	3
5th floor corridor	4	5
Lift 2 ride	2	2
Total	10	16

With TD learning: Each state has a stored estimate of remaining time from that point. After reaching lift 1 (spent 3 min), your estimate from this state says 9 minutes remain. Implied total = 3 + 9 = 12. Your old lobby estimate was 10. The TD error = 12 − 10 = +2. You nudge the lobby estimate upward right there. As each leg takes longer, each TD error is positive, and every upstream estimate gets nudged upward during the journey.

With Monte Carlo: You reach the 10th floor. Total time = 16 minutes. Only now do you walk backward: lobby gets updated toward 16 (error +6), lift-1 state toward 13 (error +4), and so on. The lobby only learns about the delay after the trip ends.

The TD approach revises values continuously. Those revised values are available to guide decisions within the same episode.

Assumptions & Scope: The TD error formula assumes the value function $V$ represents the expected return from each state under the current policy. If $V$ is wildly inaccurate (e.g., all zeros at initialization), the TD target $R + γ V (s^{'})$ is dominated by the reward component. And the error is approximately the reward minus a random guess. This works — the values eventually settle — but early updates can be large. The formula also assumes the reward is scalar. For multi-objective RL with vector rewards, the scalar TD error must be generalized. Finally, the TD error is defined for the prediction setting (estimating $V^{π}$ ). For control (estimating $Q$ and improving the policy), the same structure applies but with $Q (s, a)$ replacing $V (s)$ — the error becomes $δ_{t} = R_{t + 1} + γ Q (s_{t + 1}, a_{t + 1}) - Q (s_{t}, a_{t})$ .

Visual Intuition: Draw a number line. Mark $V (s_{t})$ on the left at, say, 10. Mark the target $R + γ V (s^{'})$ on the right at, say, 30. Draw an arrow from 10 to 30. The length of that arrow is $δ_{t} = 20$ . The update moves $V (s_{t})$ a fraction $α$ of the way along the arrow — if $α = 0.5$ , the new value is 20. After many updates with positive TD errors, the value drifts rightward along the number line. If the TD error were negative, the arrow would point left. Over an episode, every state nudges toward a neighbor-informed target, creating a cascade of value shifts, propagates from the terminal reward backward.

Pitfalls:

Confusing TD error with reward — The TD error is not the reward. It is the reward plus the change in estimated future value. A large positive reward can still produce a zero TD error if $V (s_{t + 1})$ is correspondingly lower than $V (s_{t})$ . Example: you expected to be in a great position, you got a big reward, and now you are in a mediocre position. The net surprise may be zero.
Treating the TD error as an unbiased signal — Because $V (s_{t + 1})$ is an estimate (not the true value), the TD target is a biased estimate of the true expected return. This is the cost of bootstrapping. MC's target (the actual return) is unbiased but high-variance. TD's target is biased but low-variance.
Accumulating floating-point errors — In tabular implementations with thousands of states and tiny $α$ , the TD error can underflow. Use double precision and, when possible, update in log-space for very small values.

Recap + Bridge: The TD error $δ_{t}$ is the surprise signal, the gap between what you expected. What one step of reality plus your updated belief tells you. Every TD algorithm (TD(0), SARSA, Q-Learning, Expected SARSA) uses this same update skeleton with different choices for the target. Next, we look at the simplest TD algorithm: TD(0) for policy evaluation.

Real-World & Domain Connection: The TD error appears far beyond RL. In neuroscience, the firing pattern of dopamine neurons in the midbrain closely matches the TD error signal. Dopamine spikes when a reward is better than predicted. It dips when the reward is worse, and flatlines when it matches expectations. This discovery (Schultz, Dayan, and Montague, 1997) is one of the most celebrated connections between AI and biology. In algorithmic trading, a "prediction error", the difference between a model's forecast, the actual market move. Drives position adjustments in the same way the TD error drives value updates. The TD error is the universal learning signal: wherever you have a prediction, an outcome. Their mismatch tells you how to improve the prediction.

10.3 TD(0) — The Basic Temporal Difference Algorithm for Policy Evaluation

Hook: You have a robot vacuum that follows a fixed pattern — bump, turn, bump, turn. You want to know: is this a good pattern? Specifically, which rooms does it keep clean and which does it neglect? TD(0) answers exactly this question without you ever needing to change the vacuum's behavior.

10.3.1 Algorithm Overview

Purpose: TD(0) estimates $V^{π}$ — the value of all states under a given, fixed policy $π$ . The policy never changes. You just want to answer: if this agent keeps behaving the same way, what is each state worth? This is the prediction (or policy evaluation) problem. TD(0) is the simplest TD algorithm and the prototype for all others.

Inputs:

Policy $π$ (fixed — does not change)
Step size $α \in (0, 1]$
Discount factor $γ \in [0, 1]$
Initial values $V (s)$ for all states (arbitrary, but $V (terminal) = 0$ )

Outputs:

Converged state-value function $V^{π} (s)$ for all states $s$

10.3.2 Algorithm Steps

Steps — Tabular TD(0) for estimating $v_{π}$ (from Sutton & Barto):

Initialize $V (s)$ arbitrarily for all states $s \in S^{+}$ , except $V (terminal) = 0$ .
Outer loop — For each episode:
Initialize starting state $S$ .
Inner loop — Repeat for each step of the episode until $S$ is terminal:

a. Choose action $A$ using the fixed policy $π (\cdot ∣ S)$ . b. Take action $A$ , observe reward $R$ and next state $S^{'}$ . c. Update $V (S)$ : $V (S) \leftarrow V (S) + α [R + γ V (S^{'}) - V (S)]$ d. Set $S \leftarrow S^{'}$ .

Go to the next episode.

Rationale for each step:

Step a: The policy is fixed — you are evaluating it, not improving it. You follow it blindly.
Step c: The update pulls $V (S)$ toward $R + γ V (S^{'})$ . This is the TD(0) target. It uses one real reward and bootstraps from the stored estimate of the next state.
Step d: The update is online — you move to the next state immediately and repeat. No waiting.

10.3.3 Worked Numerical Example

Trace — Run TD(0) on a tiny chain: Environment: a simple chain with states $s$ and $s^{'}$ . Initial values: $V (s) = 4$ , $V (s^{'}) = 5$ . Take action $a$ from $s$ , observe reward $R = 10$ , land in $s^{'}$ . Use $γ = 1$ and $α = 1$ (for illustration only — in practice $α = 1$ is unstable).

Step 1 — Compute the TD error: $δ = R + γ V (s^{'}) - V (s) = 10 + 1 \times 5 - 4 = 11$

Step 2 — Update: $V (s) \leftarrow V (s) + α \cdot δ = 4 + 1 \times 11 = 15$

The value of $s$ jumped from 4 to 15. Why? The world around it looked far more promising, reward 10 plus next-state value 5 (total 15) versus the old estimate of 4.

Step 3 — Continue: You are now in $s^{'}$ . Follow the policy, pick action $b$ , observe a new reward (say, 2), land in $s^{''}$ whose value is, say, 8. Update: $δ^{'} = 2 + 1 \times 8 - 5 = 5, V (s^{'}) \leftarrow 5 + 5 = 10$

Step 4 — Next episode: Start again in $s$ . Choose action $a$ , get reward 10, land in $s^{'}$ with $V (s^{'}) = 10$ . Update: $δ = 10 + 10 - 15 = 5, V (s) \leftarrow 15 + 5 = 20$

Sense-check: After two episodes, $V (s) = 20$ and $V (s^{'}) = 10$ . The values are still moving. With $α < 1$ , each update would be smaller, and the values would converge smoothly to their true expected returns. The professor's key point: "I'm pulling my existing value towards a target." The TD error is the rope. The step size $α$ controls how hard you pull.

Complexity & Cost: Tabular TD(0) stores one scalar per state — memory is $O (∣ S ∣)$ . Each update is $O (1)$ : one addition, one multiplication. The total computation per episode is $O (T)$ where $T$ is the episode length. This is dramatically cheaper than DP, which costs $O (∣ S ∣^{2} ∣ A ∣)$ per sweep because it must iterate over all state-action-next-state triples. With function approximation (one linear layer), each update costs $O (d)$ where $d$ is the feature dimension. With a neural network, each update costs one forward pass and one backward pass.

When to Use / Alternatives: TD(0) is ideal for policy evaluation — you have a policy and want to know how good it is. If you want to improve the policy simultaneously, use SARSA or Q-Learning (control algorithms, covered next). If your episodes are very short (e.g., a few steps), Monte Carlo may be simpler and just as fast. If your episodes are extremely long, never-ending (continuing tasks), TD(0) is the right choice, Monte Carlo cannot handle non-episodic tasks at all. If you need credit assignment over longer horizons, consider n-step TD or TD( $λ$ ).

Visual Intuition: Imagine a chain of states like beads on a string. Each bead holds a number — its estimated value. When the agent reaches a terminal state with a reward, the last bead before the terminal gets updated first. In the next episode, the bead before that one gets updated by bootstrapping from the now-improved last bead. Value information flows backward along the chain, one bead per episode. This is why the professor noted, "once values start propagating backward, the updates become rapid." The front of the chain learns last. But the cascade effect means it catches up quickly.

Pitfalls:

Confusing prediction with control — TD(0) evaluates a fixed policy. It does NOT improve the policy. The Q-values stay frozen relative to that policy. If you expect the agent to get better over time, you need a control algorithm.
Using $α = 1$ in production — The professor used $α = 1$ for illustration. In practice this means every new observation completely overwrites the old estimate. The value function oscillates wildly and never converges. Use $α = 0.01$ to $0.1$ for tabular, or adaptive methods.
Forgetting to set terminal values to zero If $V (terminal)$ is not explicitly set to 0, initialized randomly. The terminal state's value will pull all upstream estimates toward a nonsense number. Always define $Q (terminal, \cdot) = 0$ and $V (terminal) = 0$ .
Thinking TD(0) needs a model — It does not. The transition goes through the environment (the real world or a simulator), not through a probability table. This is the key advantage over DP.

Recap + Bridge: TD(0) is the simplest TD algorithm. It estimates state values under a fixed policy by updating every step using the TD error, no model, no waiting, episode end. Just one-step bootstrapping. But evaluating a policy is only half the story. Next, we move from prediction to control — from $V$ to $Q$ .

Real-World & Domain Connection: Policy evaluation powers A/B testing in recommendation systems. A company may have a fixed recommendation policy (e.g., "if the user watched action movies, suggest more action movies"). TD(0) evaluates how good each user state is under that policy — how likely the user is to click, subscribe, or churn. The company can then compare policies without ever changing the live system. In supply chain management. A fixed inventory-replenishment policy can be evaluated using TD(0) against historical demand data to estimate long-run costs before deployment.

10.4 Introduction to Control — Moving from V to Q

Hook: You know exactly how good every chess position is. But you still cannot play chess. Why? Because knowing a position's value does not tell you which move to make. You need to know the value of each move in that position. That is the jump from $V$ to $Q$ . This jump is the difference between watching chess and playing it.

10.4.1 From Prediction to Control

Intuition + Analogy: Imagine you are a food critic. $V (s)$ is your star rating of a restaurant, it tells you "this place is a 4 out of 5.". $Q (s, a)$ is your rating of a specific dish at, restaurant, "the pasta is a 5. The salad is a 2." If you want to order the best meal, you need the dish-level ratings. The restaurant-level rating alone cannot tell you which dish to pick. In RL, $V (s)$ is the restaurant rating and $Q (s, a)$ is the dish rating. For control — for actually choosing actions — you need $Q$ . Where the analogy breaks: in RL, you can recover $V$ from $Q$ by taking the expectation over actions. However, you cannot recover $Q$ from $V$ without a model of the environment's transitions.

Formalize — why $Q$ is necessary for control: So far, TD(0) estimated $V^{π} (s)$ — the value of being in state $s$ under a fixed policy $π$ . That is prediction. But we want control — starting from a random policy and converging to an optimal one.

To improve a policy, you need to know which action is best in each state. $V (s)$ alone cannot tell you that without a model. You would need to try every action from $s$ , observe the next state $s^{'}$ , and compute $r + γ V (s^{'})$ , each. Which requires the ability to sample transitions, know the transition function. With $Q (s, a)$ , you can compare actions directly: $ar g max_{a} Q (s, a)$ gives the best action. No model needed.

The transition from estimation ( $V$ ) to control ( $Q$ ) is natural:

Replace $V (s)$ with $Q (s, a)$ in the update rule.
The target uses $Q (s^{'}, a^{'})$ instead of $V (s^{'})$ .
The policy itself is derived from the Q values (typically via $ϵ$ -greedy).

Two control algorithms emerge from this:

SARSA — on-policy: the same policy generates actions and provides the target
Q-Learning — off-policy: an exploratory policy generates actions, but the target uses the greedy maximum

The relationship between $V$ and $Q$ is: $V^{π} (s) = a \sum π (a ∣ s) Q^{π} (s, a)$ $V$ is the expected value of $Q$ under the policy $π$ . You can always convert $Q$ to $V$ , but not $V$ to $Q$ without extra information.

Assumptions & Scope: Moving from $V$ to $Q$ increases the learning problem's size. With $∣ S ∣$ states and $∣ A ∣$ actions, $V$ needs $∣ S ∣$ entries while $Q$ needs $∣ S ∣ \times ∣ A ∣$ entries. In tabular settings with large action spaces, this can be prohibitive. The Q-function also requires more data to learn well — each state-action pair needs visits, not just each state. This is the exploration cost of control: you must try every action in every state enough times, the Q-values to be reliable. If the action space is continuous, Q-learning, function approximation can still work by evaluating Q-values, sampled actions. But the $ar g max$ operation becomes an optimization problem itself.

Visual Intuition: Picture a state as a junction with several roads leading out. $V (s)$ is a single number floating above the junction — the average quality of all roads from here. $Q (s, a)$ is a separate number floating above each road. If road "left" has $Q = 100$ and road "right" has $Q = 20$ , you know which road to take. The roadmap analogy captures the key structural difference: one number per state ( $V$ ) versus one number per state-action pair ( $Q$ ).

Pitfalls:

Thinking $V$ is useless for control — It is not. Many algorithms (actor-critic, for example) learn $V$ as a baseline to reduce variance, even while learning a separate policy. $V$ is simpler and needs less data.
Ignoring the exploration cost — Moving to Q means you must explore all actions in all states. If the action space is large (e.g., 1000 actions per state), random exploration might never hit the good ones. You need smarter exploration strategies.
Forgetting the policy is part of the Q — $Q^{π} (s, a)$ depends on $π$ . If you change the policy, the Q-values must relearn. This is why on-policy algorithms (SARSA) must discard old data when the policy changes. While off-policy algorithms (Q-Learning) can learn from any data.

Recap + Bridge: $V (s)$ tells you how good a state is. $Q (s, a)$ tells you how good each action is in that state. For control — actually choosing actions to optimize behavior — you need $Q$ . The next two sections introduce the two canonical control algorithms: SARSA (on-policy) and Q-Learning (off-policy).

Real-World & Domain Connection: The V-to-Q distinction shows up whenever you move from passive analysis to active decision-making. A credit scoring model ( $V$ ) tells a bank how risky a customer is. A loan offer optimization system ( $Q$ ) tells the bank which loan product to offer that customer to maximize profit while managing risk. In healthcare, a diagnostic model ( $V$ ) assesses how severe a patient's condition is. A treatment recommendation system ( $Q$ ) tells the doctor which intervention to choose. Every real-world RL deployment that takes actions — from ad placement to robot control — works with Q-functions, not just V-functions.

10.5 SARSA — On-Policy TD Control

Hook: You are learning to navigate a cliff edge in the dark. Every step could send you tumbling down. Would you rather learn from a policy that knows you might slip and plans around it, or one that assumes you always walk perfectly? SARSA is the cautious friend who accounts for your occasional missteps.

10.5.1 Definition and Explanation

Intuition + Analogy: SARSA is like learning to cook by following your own recipe book and refining it as you go. You write down a recipe (policy derived from Q-values). You cook a dish following that recipe (generate experience). You taste it, note what went wrong, and update the recipe (update Q-values). Then you cook again with the improved recipe. The same book generates the experience and gets updated from it. There is no separate "expert chef" book you consult — you are both the student and the teacher. This is on-policy learning: one policy, one loop. Where the analogy breaks: in SARSA, the "recipe" changes after every single step (online update), not after the full meal. And you deliberately deviate from the recipe some fraction $ϵ$ of the time just to discover new techniques.

The name SARSA comes from the quintuple $(s, a, r, s^{'}, a^{'})$ — State, Action, Reward, next State, next Action. These five elements are all you need for one update. SARSA is on-policy: the same policy both generates behavior and provides the target $a^{'}$ for the update.

Purpose: SARSA is an on-policy TD control algorithm. It learns $Q^{π} (s, a)$ — the action-value function — while simultaneously improving the policy $π$ toward optimality. The agent starts with a random (or arbitrary) policy and converges to an optimal policy through repeated interaction with the environment.

Inputs:

State space $S$ , action space $A$
Step size $α \in (0, 1]$ , discount factor $γ \in [0, 1]$
Exploration parameter $ϵ \in (0, 1]$ (for $ϵ$ -greedy)
Initial Q-values $Q (s, a)$ arbitrary, $Q (terminal, \cdot) = 0$

Outputs:

Converged action-value function $Q^{*} (s, a)$ approximating the optimal $q_{*}$
Optimal (or near-optimal) policy derived from $Q^{*}$ via greedy action selection

10.5.2 The Update Expression

Steps — SARSA (on-policy TD control), from Sutton & Barto:

Initialize $Q (s, a)$ arbitrarily for all $s \in S^{+}, a \in A (s)$ . Set $Q (terminal, \cdot) = 0$ .
Outer loop — For each episode:
Initialize state $S$ .
Choose action $A$ from $S$ using the policy derived from $Q$ (e.g., $ϵ$ -greedy).
Inner loop — Repeat for each step until $S$ is terminal:

a. Take action $A$ . Observe reward $R$ and next state $S^{'}$ . b. Choose action $A^{'}$ from $S^{'}$ using the policy derived from $Q$ (e.g., $ϵ$ -greedy). c. Update: $Q (S, A) \leftarrow Q (S, A) + α [R + γ Q (S^{'}, A^{'}) - Q (S, A)]$ d. Set $S \leftarrow S^{'}$ , $A \leftarrow A^{'}$ .

Go to the next episode.

Rationale for each step:

Step a: You follow the current policy to generate one real transition.
Step b: You consult the same policy at $S^{'}$ to pick $A^{'}$ . This is the "on-policy" part — the target action comes from the same distribution as the behavior action.
Step c: The update pulls $Q (S, A)$ toward $R + γ Q (S^{'}, A^{'})$ . The target uses the action the policy actually would take, not the best possible action. This makes SARSA aware of its own exploration noise.
Step d: Carry $A^{'}$ forward — you do not re-sample. This is critical: after the update, the current state-action pair for the next iteration is $(S^{'}, A^{'})$ , which you already have.

The update in full form:

$Q (s, a) \leftarrow Q (s, a) + α [R + γ Q (s^{'}, a^{'}) - Q (s, a)]$

Where $a^{'}$ is the action actually chosen by the $ϵ$ -greedy policy at $s^{'}$ .

10.5.3 Why SARSA Is On-Policy

Consider state $s$ with Q-values: up = 10, down = 20, left = 30, right = 40. With $ϵ = 0.3$ , the $ϵ$ -greedy policy gives the greedy action (right, value 40) probability $1 - ϵ + ϵ /4 = 0.775$ , and each other action probability $ϵ /4 = 0.075$ .

When you are in state $s$ , this policy picks an action. After executing it and landing in $s^{'}$ , the same policy picks $a^{'}$ . The update pulls $Q (s, a)$ toward $R + γ Q (s^{'}, a^{'})$ . One policy governs both experience generation and value updates. That is on-policy.

10.5.4 Why SARSA Is a Control Algorithm

You start with randomly initialized Q-values. A random Q-table gives a random $ϵ$ -greedy policy. Every Q-value update implicitly changes the policy. Over time, Q-values converge toward optimal, and the policy derived from them converges too. You started with a random policy and ended with (near-)optimal. That is control: evaluation and improvement in a single loop (GPI — Generalized Policy Iteration).

10.5.5 Worked Numerical Example — SARSA on a Simple Grid

Trace — Two-episode SARSA walkthrough: Grid layout: states $X, W, Y, Z$ plus terminal. Actions from $X$ : left $\to W$ , right $\to Y$ . $W$ has one action: exit $\to$ terminal (reward $- 100$ ). $Y \to Z$ (reward 0). $Z$ has exit $\to$ terminal (reward $- 100$ ). All Q-values start at 0. Parameters: $γ = 0.9$ , $α = 1$ (for illustration).

Episode 1:

Start at $X$ . Choose left. $R = 0$ , land in $W$ . Choose $a^{'}$ = exit.

$Q (X, left) \leftarrow 0 + 1 \times [0 + 0.9 \times 0 - 0] = 0 (no change yet)$

Now in $(W, exit)$ . Execute exit: $R = - 100$ , land in terminal. No $a^{'}$ (terminal).

$Q (W, exit) \leftarrow 0 + 1 \times [- 100 + 0.9 \times 0 - 0] = - 100$ Episode ends.

Episode 2:

Start at $X$ . Choose left. $R = 0$ , land in $W$ . Choose $a^{'}$ = exit.

$Q (X, left) \leftarrow 0 + 1 \times [0 + 0.9 \times (- 100) - 0] = - 90$

Now in $(W, exit)$ . Execute exit: $R = - 100$ , land in terminal.

$Q (W, exit) \leftarrow - 100 + 1 \times [- 100 + 0 - (- 100)] = - 100 (unchanged)$

Propagation pattern: Episode 1: $W$ -exit learns $- 100$ . Episode 2: $X$ -left learns $- 90$ (which is $γ \times (- 100)$ ). Over many episodes, the negative value propagates backward along the chain. With $α < 1$ , the updates would be partial — e.g., with $α = 0.5$ , Episode 2 would give $Q (X, left) = 0 + 0.5 \times (- 90) = - 45$ instead of $- 90$ . Smaller $α$ means smoother, slower convergence.

Sense-check: The discount factor $γ = 0.9$ means each step back in the chain reduces the propagated value by 10%. The true optimal Q-values (after full convergence, $γ = 0.9$ ) would follow this geometric decay: the state closest to the $- 100$ terminal gets $- 100$ . The next gets $- 90$ , the next $- 81$ , and so on. The worked example traces the beginning of that convergence.

Complexity & Cost: Tabular SARSA stores $∣ S ∣ \times ∣ A ∣$ entries. Each update is $O (1)$ . The policy improvement step (choosing $A^{'}$ from $S^{'}$ via $ϵ$ -greedy) requires finding the max over actions — $O (∣ A ∣)$ per step. Total per-step cost: $O (∣ A ∣)$ . SARSA converges with probability 1 to an optimal policy under specific conditions. All state-action pairs must be visited infinitely often, and the policy must converge to greedy in the limit (e.g., $ϵ = 1/ t$ decaying. Episode count).

When to Use / Alternatives: SARSA is preferred when exploration is risky. The algorithm accounts for its own exploratory moves in the target. It learns a policy that performs well given that it sometimes explores. Use SARSA when:

Online performance matters during training (e.g., a robot that cannot afford to fall during learning)
Exploration has real costs (e.g., medical treatment, power grid control, autonomous driving)
The environment has "cliffs" — states where a wrong action is catastrophic

If you can train in simulation and only care about the final policy, Q-Learning may converge faster to the optimal policy. Expected SARSA (section 10.7) offers a middle ground with lower variance.

Assumptions & Scope: SARSA requires that all state-action pairs are visited infinitely often for guaranteed convergence. With a fixed $ϵ > 0$ (constant exploration), the Q-values never fully settle — they keep fluctuating. For formal convergence, $ϵ$ must decay to 0 over time (e.g., $ϵ_{t} = 1/ t$ ). In practice, many implementations use a fixed small $ϵ$ (e.g., 0.01) and accept some residual error. SARSA with function approximation (neural networks) has no convergence guarantees. The deadly triad — bootstrapping, function approximation, and off-policy learning — affects all TD methods. However, SARSA is on-policy and avoids the off-policy part of the triad, so it fares better than Q-Learning in this regard.

Visual Intuition: Draw a grid with a cliff on the bottom edge. SARSA's learned path arcs upward, staying safely away from the cliff edge. Q-Learning's path hugs the cliff edge tightly. Why? SARSA's target includes the exploratory actions — it "knows" that sometimes you will randomly step toward the cliff. So it learns a policy that keeps you far enough away that even a random step does not send you over. Q-Learning's target ignores exploration, it assumes you always take the optimal action from the next state onward. So it learns the truly shortest path regardless of cliff risk.

Pitfalls:

Confusing the on-policy target — SARSA uses $Q (s^{'}, a^{'})$ where $a^{'}$ is the action the policy actually selects, not the max over actions. If you accidentally use $max$ in the target, you have implemented Q-Learning, not SARSA.
Re-sampling $a^{'}$ after the update — The algorithm step says $S \leftarrow S^{'}, A \leftarrow A^{'}$ . You already selected $A^{'}$ during the loop body. Do NOT re-sample it. Re-sampling breaks the on-policy connection because the action used in the update would differ from the action used in the next step.
Setting $ϵ = 0$ too early If you turn off exploration before Q-values have converged, the agent stops visiting suboptimal actions, never corrects its estimates, them. The policy gets stuck at a local optimum.
Forgetting that SARSA is more conservative — Donot deploy SARSA expecting it to find the absolute shortest path. It trades off optimality for safety. The cliff-walking example (Sutton & Barto Example 6.6) shows SARSA takes a longer but safer route.

10.5.6 Student Questions and Answers

Student Q&A — Deduplicated:

Q: Several students asked about delayed rewards and slow initial updates. In games like chess where rewards come only after long sequences, do initial states in SARSA update at all?

A: In the very beginning, when all Q-values are zero, early states produce a TD error of zero and do not change. This is expected. But after the first episode reaches a terminal state with non-zero reward, that terminal state's Q-value changes. In the next episode, the state immediately before the terminal updates by bootstrapping from that now-nonzero value. With each episode, the reward information propagates one more step backward. After $k$ episodes that reach the terminal, states up to $k$ steps away have been updated. The key advantage of TD over MC is not, it propagates faster per episode. Both propagate at the same rate of one step per episode in the worst case. The advantage is, TD updates online (every step, not just at episode end). Uses less memory (no need to store the full episode), and works on continuing tasks (no episode boundary needed).

Recap + Bridge: SARSA is on-policy TD control. It uses the quintuple $(s, a, r, s^{'}, a^{'})$ where $a^{'}$ comes from the same $ϵ$ -greedy policy that generated the experience. It learns a safer, exploration-aware policy. Next, we look at Q-Learning — the off-policy cousin that learns the optimal policy directly, ignoring exploration noise in its target.

Real-World & Domain Connection: SARSA is the algorithm of choice for safety-critical control. Traffic signal optimization systems use SARSA, exploration (trying a new signal timing pattern) must not cause accidents, the learned policy accounts. The fact, exploration continues during deployment. In robotics, SARSA controls robot arms during grasping tasks: the arm learns a policy. Works even when the motors occasionally overshoot (exploration noise). In finance, portfolio rebalancing agents use SARSA, a random exploratory trade could lose real money, SARSA learns a policy. Is robust to its own occasional random deviations. The Sutton & Barto cliff-walking example (Example 6.6) remains the canonical illustration: SARSA learns the safe upper path. Q-Learning learns the risky cliff-edge path.

10.6 Q-Learning — Off-Policy TD Control

Hook: What if you could learn from anyone's experience, a grandmaster's chess games, a veteran pilot's maneuvers, a senior surgeon's decisions. Without ever making a move yourself? Q-Learning makes this possible. It separates the learner from the doer.

10.6.1 Definition and Explanation

Intuition + Analogy: You are a driving student. Your instructor (the behavior policy) drives you around, sometimes taking perfect routes, sometimes taking detours "just so you see what happens.", in your head. You are learning the optimal way to drive. You mentally note "taking this shortcut saved 5 minutes" even when the instructor took the long way. The instructor generates diverse experiences. You learn the best possible policy from those experiences. This is off-policy learning: two policies, one goal. Where the analogy breaks: in Q-Learning, the learner's "mental model of optimal driving" actively feeds back into the instructor's choices (via $ϵ$ -greedy on the same Q-table). So the two are coupled through shared Q-values. A pure off-policy setup would keep them completely separate.

Q-Learning (Watkins, 1989) is an off-policy TD control algorithm. The update is nearly identical to SARSA but with one critical difference:

$Q (s, a) \leftarrow Q (s, a) + α [R + γ a^{'} max Q (s^{'}, a^{'}) - Q (s, a)]$

In SARSA, $a^{'}$ is the action actually chosen by the $ϵ$ -greedy policy at $s^{'}$ . In Q-Learning, $a^{'}$ is always the greedy action — the one with the maximum Q-value at $s^{'}$ . It does not matter what the exploration policy actually picked.

Purpose: Q-Learning directly approximates the optimal action-value function $q_{*}$ , independent of the policy being followed. The learned Q-function converges to $q_{*}$ (under appropriate conditions), and the optimal policy is simply $ar g max_{a} Q (s, a)$ .

Inputs:

State space $S$ , action space $A$
Step size $α \in (0, 1]$ , discount factor $γ \in [0, 1]$
Exploration parameter $ϵ$ (for behavior policy)
Initial Q-values arbitrary, $Q (terminal, \cdot) = 0$

Outputs:

Converged action-value function $Q (s, a) \approx q_{*} (s, a)$
Optimal policy $π_{*} (s) = ar g max_{a} Q (s, a)$

10.6.2 Why Q-Learning Is Off-Policy

Two policies operate simultaneously:

Behavior policy $b$ : The $ϵ$ -greedy policy that selects actions during the episode. It generates the actual experience — it explores.
Target policy $π$ (the one being learned): The greedy policy — "always pick $ar g max_{a} Q (s, a)$ ." The update pulls Q-values toward what this policy would value.

Because the policy being learned (greedy) differs from the policy generating behavior ( $ϵ$ -greedy), Q-Learning is off-policy. It learns about the optimal policy directly while exploring suboptimally.

Steps — Q-Learning (off-policy TD control), from Sutton & Barto:

Initialize $Q (s, a)$ arbitrarily for all $s \in S^{+}, a \in A (s)$ . Set $Q (terminal, \cdot) = 0$ .
Outer loop — For each episode:
Initialize state $S$ .
Inner loop — Repeat for each step until $S$ is terminal:

a. Choose action $A$ from $S$ using policy derived from $Q$ (e.g., $ϵ$ -greedy). b. Take action $A$ . Observe reward $R$ and next state $S^{'}$ . c. Update: $Q (S, A) \leftarrow Q (S, A) + α [R + γ a max Q (S^{'}, a) - Q (S, A)]$ d. Set $S \leftarrow S^{'}$ .

Go to the next episode.

Key difference from SARSA: Step c uses $max_{a} Q (S^{'}, a)$ — the best possible next action — instead of the action actually taken. Q-Learning does not need to know $A^{'}$ at all. The experience tuple is $(s, a, r, s^{'})$ , not $(s, a, r, s^{'}, a^{'})$ .

10.6.3 Worked Numerical Example — Q-Learning on the Same Grid

Trace — Two-episode Q-Learning walkthrough: Same grid: states $X, W, Y, Z$ plus terminal. All Q-values start at 0. Parameters: $γ = 0.9$ , $α = 1$ (for illustration).

Episode 1:

Start at $X$ . Suppose the behavior policy picks right (to $Y$ ). $R = 0$ , land in $Y$ .

$Q (X, right) \leftarrow 0 + 1 \times [0 + 0.9 \times 0 - 0] = 0$

Now in $Y$ . Pick right (to $Z$ ). $R = 0$ , land in $Z$ .

$Q (Y, right) \leftarrow 0 + 1 \times [0 + 0.9 \times 0 - 0] = 0$

Now in $Z$ . Pick exit. $R = - 100$ , land in terminal.

$Q (Z, exit) \leftarrow 0 + 1 \times [- 100 + 0.9 \times 0 - 0] = - 100$

Episode 2 (after $Z$ -exit is $- 100$ ):

Start at $X$ . Choose right. $R = 0$ , land in $Y$ . $max_{a} Q (Y, a) = 0$ (since $Y$ -right is still 0).

$Q (X, right) \leftarrow 0 + 1 \times [0 + 0.9 \times 0 - 0] = 0$

Now in $Y$ . Choose right. $R = 0$ , land in $Z$ . $max_{a} Q (Z, a) = 0$ (all Z actions still 0... wait, $Z$ -exit is $- 100$ ). Actually: $max_{a} Q (Z, a) = max (- 100, 0) = 0$ if there is another action, but $Z$ only has exit. So $max = - 100$ .

$Q (Y, right) \leftarrow 0 + 1 \times [0 + 0.9 \times (- 100) - 0] = - 90$

Episode 3:

Start at $X$ . Choose right. $max_{a} Q (Y, a) = - 90$ .

$Q (X, right) \leftarrow 0 + 1 \times [0 + 0.9 \times (- 90) - 0] = - 81$

Sense-check: The backward propagation works the same as SARSA (one step per episode), but the target always uses $max$ . The best possible next action, rather than the one actually taken. This means Q-Learning learns about the optimal path even if the behavior policy took a different one. The discount chain $- 100 \to - 90 \to - 81$ matches the $γ = 0.9$ geometric decay.

10.6.4 Aggressive Updates — The Max Effect

Comparative trace — SARSA vs Q-Learning on the same transition: Consider state $s$ with Q-values: up = 10, down = 20, left = 30, right = 40. You take action "up" (reward = 2) and land in $s^{'}$ . The Q-values at $s^{'}$ are: up = 100 (max), down = 20, left = 20, right = 10. Parameters: $γ = 0.9$ , $α = 1$ .

Q-Learning update — target uses $max_{a^{'}} Q (s^{'}, a^{'}) = 100$ : $Q (s, up) \leftarrow 10 + 1 \times [2 + 0.9 \times 100 - 10] = 10 + [2 + 90 - 10] = 10 + 82 = 92$

SARSA update — target uses the action actually taken at $s^{'}$ (say $ϵ$ -greedy picked "right" with value 10): $Q (s, up) \leftarrow 10 + 1 \times [2 + 0.9 \times 10 - 10] = 10 + [2 + 9 - 10] = 10 + 1 = 11$

Q-Learning pulled the value from 10 to 92 in one step — an 820% jump. SARSA pulled it from 10 to 11 — a 10% nudge. The max operator acts like an optimistic amplifier. It grabs the most promising neighbor's value, feeds it into the update, regardless of how unlikely, neighbor is to be reached.

10.6.5 The Overestimation Problem

Because Q-Learning always uses $max$ , the estimates develop a positive bias. Even if all true Q-values are zero, the maximum of noisy estimates will be positive, and that positive bias compounds through bootstrapping. Sutton & Barto (Section 6.7) call this maximization bias. In the extreme, Q-values inflate dramatically, and the agent confidently chooses actions that are actually terrible.

The basic Q-Learning algorithm is rarely used directly in online settings because of this instability. Modern variants fix the problem:

Double Q-Learning maintains two separate Q-tables. One selects the best action; the other evaluates it. This decouples selection from evaluation and removes the positive bias.
DQN (Deep Q-Network) uses a frozen target network and experience replay to stabilize learning with neural networks.
Clipped Double Q-Learning (used in TD3, SAC) takes the minimum of two Q-networks to combat overestimation.

Complexity & Cost: Tabular Q-Learning stores $∣ S ∣ \times ∣ A ∣$ entries. Each update is $O (∣ A ∣)$ — finding the maximum over actions dominates. With function approximation, the forward pass computes all Q-values for a state simultaneously, so the max is $O (∣ A ∣)$ comparisons. Q-Learning converges to $q_{*}$ with probability 1 under the same conditions as SARSA: all pairs visited infinitely often and $α$ decaying appropriately. The convergence proof also requires that the behavior policy has non-zero probability for all actions, so all pairs are eventually visited.

When to Use / Alternatives: Q-Learning is preferred when you can train offline (in simulation), you want to learn the optimal policy directly. And you are building toward deep RL, experience replay. DQN and its descendants all build on Q-Learning's off-policy max-based target. Use Q-Learning when:

You train in a simulator (no safety concerns during exploration)
You want the optimal policy, not a safe-on-average policy
You plan to use experience replay (off-policy data from old policies can be reused)
You need fast convergence to the optimal policy

Use SARSA when online safety matters. Use Expected SARSA when you want the best of both (lower variance than SARSA, no max bias).

Assumptions & Scope: Q-Learning's convergence proof requires that all state-action pairs are updated infinitely often. A fixed $ϵ$ -greedy behavior policy satisfies this. However, in large state spaces, some pairs may never be visited. The max operator makes Q-Learning sensitive to initialization, if all Q-values initialize to a high number (optimistic initialization). The agent explores thoroughly (because unexplored actions look good). If they initialize to zero, the agent may never try actions that initially look worse but are actually better. Q-Learning with function approximation (neural networks) has no convergence guarantees — the moving target problem is amplified by the max operator.

Visual Intuition: Picture two dials on a control panel. SARSA has one dial: the policy dial. Turn it, and both behavior and targets change together. Q-Learning has two dials: the behavior dial ( $ϵ$ -greedy, for exploration) and the target dial (greedy, for the update). You can twist the behavior dial randomly to explore while the target dial always points to the best action. The gap between the two dials is the off-policy gap. It represents the difference between what you do and what you learn.

Pitfalls:

Maximization bias — The max of noisy estimates is always higher than the true max. This positive bias compounds through bootstrapping. Use Double Q-Learning to fix it.
Confusing Q-Learning with SARSA — The difference is exactly one character: $max$ vs $a^{'}$ . Q-Learning: $R + γ max Q (s^{'}, \cdot)$ . SARSA: $R + γ Q (s^{'}, a^{'})$ . Get this wrong and you have implemented the other algorithm.
Deadly triad with function approximation Combining off-policy learning (Q-Learning), bootstrapping (TD target), and function approximation (neural networks) creates the "deadly triad". The interaction of these three can cause divergence. DQN mitigates this with target networks and experience replay.
Ignoring the exploration-exploitation tradeoff — Q-Learning needs the behavior policy to explore. If $ϵ$ is too small, the agent never discovers better actions. If $ϵ$ is too large, learning is slow and noisy. Anneal $ϵ$ from 1.0 to a small final value (e.g., 0.01).

Exam note: Expect numerical problems asking you to compute one, two SARSA, Q-Learning updates given a grid diagram, initial Q-values, rewards, and parameters. For SARSA: the target uses the action the agent actually takes next. For Q-Learning: the target always uses the max. Show every step in full. Both problems test whether you understand which action goes into the target, not whether you can do arithmetic.

Recap + Bridge: Q-Learning is off-policy TD control. It uses $max_{a} Q (s^{'}, a)$ as the target, learning the optimal policy directly regardless of exploration noise. This makes it faster to converge but prone to overestimation. It is the foundation for DQN and deep RL. Next, we look at Expected SARSA — the middle ground that avoids both the noise of SARSA and the max-bias of Q-Learning.

Real-World & Domain Connection: Q-Learning's off-policy nature is transformative for applications where exploration is expensive or impossible. In healthcare, a Q-Learning agent can learn optimal treatment policies from historical patient records, the behavior policy is what doctors actually did. And the target policy learns what they should have done. In autonomous driving, Q-Learning can learn from a mixture of human driving logs and simulation data. In game AI, the seminal DQN paper (Mnih et al., 2015) used Q-Learning. A convolutional neural network to achieve superhuman performance on 49 Atari games from raw pixels. The agent learned the optimal policy through off-policy experience replay, training on a shuffled buffer of past transitions. Q-Learning remains the substrate for the most influential deep RL breakthroughs.

10.7 Expected SARSA — The Middle Ground

Hook: SARSA flips a coin and sometimes learns from a terrible action. Q-Learning ignores the coin and always learns from the perfect action. What if you could learn from all actions at once, weighted by how often you would actually take them?

10.7.1 Definition and Explanation

Intuition + Analogy: SARSA is like a restaurant critic who orders one random dish and judges the restaurant by that dish alone. Q-Learning is like a critic who always assumes they will get the kitchen's best dish, ignoring what they actually ate. Expected SARSA is like a critic who looks at the full menu with probabilities, "80% chance I will order the steak (rating 100), 20% chance I end up. The salad (rating 10)." The expected score is $0.8 \times 100 + 0.2 \times 10 = 82$ . This is more stable than a single-dish sample, which could be 100 or 10. It is also more realistic than assuming you always get the steak. Where the analogy breaks: computing the full expectation requires evaluating Q for every action at the next state, which costs $O (∣ A ∣)$ per update instead of $O (1)$ . In large discrete action spaces, this becomes expensive.

Formalize — the Expected SARSA update: Expected SARSA (Sutton & Barto, Section 6.6) replaces the sampled $Q (s^{'}, a^{'})$ (SARSA) and the $max Q (s^{'}, a^{'})$ (Q-Learning) with the expected value of $Q (s^{'}, \cdot)$ under the current policy $π$ :

$Q (s, a) \leftarrow Q (s, a) + α [R + γ a^{'} \sum π (a^{'} ∣ s^{'}) \cdot Q (s^{'}, a^{'}) - Q (s, a)]$

The target: $Target_{Expected SARSA} = R + γ a^{'} \sum π (a^{'} ∣ s^{'}) \cdot Q (s^{'}, a^{'})$

This is the full expectation over all actions at $s^{'}$ , weighted by the policy's action probabilities. Every action contributes, not just one sample.

10.7.2 Why Expected SARSA Is More Stable

Worked Example — three algorithms on the same numbers: State $s$ has Q-values: up = 10, down = 20, left = 30, right = 40. The $ϵ$ -greedy policy ( $ϵ = 0.3$ ) at $s^{'}$ has Q-values: up = 100, down = 20, left = 20, right = 10. Reward $R = 2$ , $γ = 0.9$ , $α = 1$ .

Action probabilities at $s^{'}$ under $ϵ$ -greedy ( $ϵ = 0.3$ ):

Greedy action (up, Q = 100): $1 - ϵ + ϵ /4 = 0.775$
Other actions (down, left, right): $ϵ /4 = 0.075$ each

SARSA — target uses whatever $a^{'}$ the policy actually picks. If it picks "down" (Q = 20): $Q (s, up) \leftarrow 10 + [2 + 0.9 \times 20 - 10] = 10 + 10 = 20$

Q-Learning — target always uses max (up, Q = 100): $Q (s, up) \leftarrow 10 + [2 + 0.9 \times 100 - 10] = 10 + 82 = 92$

Expected SARSA — target uses weighted average: $a^{'} \sum π (a^{'} ∣ s^{'}) Q (s^{'}, a^{'}) = 0.775 \times 100 + 0.075 \times 20 + 0.075 \times 20 + 0.075 \times 10 = 77.5 + 1.5 + 1.5 + 0.75 = 81.25$ $Q (s, up) \leftarrow 10 + [2 + 0.9 \times 81.25 - 10] = 10 + [2 + 73.125 - 10] = 75.125$

Sense-check: SARSA's update (20) is low because it used a random exploratory action's value. Q-Learning's update (92) is high because it grabbed the max optimistically. Expected SARSA's update (75.13) sits in the middle, it leans toward the max (because the policy puts 77.5% probability on it), accounts. The 22.5% chance of landing on a worse action. No dice-roll noise. No max-inflation.

10.7.3 Summary — The Three Targets Compared

Algorithm	Next action $a^{'}$	Target	Variance	Bias
SARSA	Sampled from $π$	$R + γ Q (s^{'}, a^{'})$	High	No max bias
Q-Learning	Greedy (max)	$R + γ max_{a^{'}} Q (s^{'}, a^{'})$	Low	Positive bias
Expected SARSA	Expectation over $π$	$R + γ \sum_{a^{'}} π (a^{'} ∣ s^{'}) Q (s^{'}, a^{'})$	Zero	No max bias

All three share the same update skeleton $Q (s, a) \leftarrow Q (s, a) + α [target - Q (s, a)]$ . Only the target differs. Expected SARSA eliminates the variance from sampling $a^{'}$ (SARSA's problem), the maximization bias (Q-Learning's problem). At the cost of computing the full expectation.

Assumptions & Scope: Expected SARSA requires evaluating $Q (s^{'}, a^{'})$ for every action $a^{'}$ at $s^{'}$ . In tabular settings with small action spaces, this is cheap. With large discrete action spaces (thousands of actions), this becomes expensive. You need $∣ A ∣$ forward passes through the Q-network. In continuous action spaces, the expectation becomes an integral, which is typically intractable. Expected SARSA generalizes both SARSA and Q-Learning: if $π$ is the $ϵ$ -greedy policy, Expected SARSA is on-policy. If $π$ is the greedy policy (while the behavior policy is $ϵ$ -greedy), Expected SARSA becomes exactly Q-Learning. So Expected SARSA can be used on-policy or off-policy depending on how you define $π$ relative to the behavior policy.

Visual Intuition: Draw a bar chart at $s^{'}$ . Each bar represents an action's Q-value. The bar heights are: 100 (up), 20 (down), 20 (left), 10 (right). SARSA picks one bar randomly (weighted by $ϵ$ -greedy probabilities) and uses that height. Q-Learning always picks the tallest bar (100). Expected SARSA computes the weighted average height of all bars — it is the center of mass of the bar chart, weighted by how often each bar gets picked. The center of mass (81.25) sits between the max (100) and the random-draw value.

Pitfalls:

Confusing on-policy vs off-policy Expected SARSA — If $π$ (the policy used in the expectation) equals the behavior policy, it is on-policy. If $π$ is the greedy policy while the behavior policy is $ϵ$ -greedy, it is off-policy (and equivalent to Q-Learning). Be explicit about which $π$ you are using.
Computational cost in large action spaces — Every update requires iterating over all actions. With 10,000 actions and a neural network Q-function, this means 10,000 forward passes per update. For such settings, SARSA or Q-Learning with sampling may be more practical.
Assuming Expected SARSA is always better — It generally outperforms SARSA, as shown in Sutton & Barto Figure 6.3. However, the computational overhead may not be worth it if the action space is large, the policy is already near-deterministic. Meaning $ϵ$ is small. At $ϵ \approx 0$ , all three algorithms become nearly identical.

Recap + Bridge: Expected SARSA replaces the sampled $a^{'}$ in the target with the expectation over all actions under the policy. This eliminates SARSA's variance and Q-Learning's max-bias at the cost of computing a weighted average over all actions. Next, we compare SARSA and Q-Learning head-to-head to help you choose the right algorithm.

Real-World & Domain Connection: Expected SARSA's stability makes it attractive for financial applications where noisy value estimates translate directly to noisy trading decisions. In algorithmic execution (splitting a large stock order over time), the agent chooses how many shares to trade at each step. The cost of a bad exploratory trade is real money, so stable value estimates matter. Expected SARSA's expectation-based target reduces the variance that would otherwise cause the agent to oscillate between aggressive and conservative strategies. In clinical decision support, Expected SARSA learns treatment policies from limited patient data. The expectation over actions smooths out the noise from small sample sizes.

10.8 SARSA vs Q-Learning — When to Use Which

Hook: Two hikers stand at the edge of a cliff. One walks a wide arc around it. The other walks right along the edge. Both reach the same destination. Which one would you trust with your life? That is the difference between SARSA and Q-Learning.

10.8.1 Exploration Sensitivity

Intuition + Analogy: SARSA is like driving with a cautious parent — they account for the fact that they might accidentally jerk the wheel. So they stay in the middle lane. Q-Learning is like a racing simulator driver — they plot the mathematically optimal racing line, assuming perfect control. When the racing driver gets into a real car, they sometimes crash because real steering is noisier than the simulation. The gap between simulated perfection and real-world noise is exactly what separates Q-Learning's target from SARSA's target. Where the analogy breaks: both algorithms ultimately drive the same car. The difference is only in what they assume about the next action during the update step.

SARSA respects its exploration policy fully. If the policy has $ϵ = 0.1$ (10% random actions), those exploratory moves appear in the target. SARSA learns a policy that performs well knowing that you will sometimes explore. It is safer.

Q-Learning ignores exploration in its target. It always learns as if you will behave optimally from the next state. This makes it learn the truly optimal policy faster — but it is blind to the risks of exploratory actions during deployment.

Formalize — the cliff-walking scenario (Sutton & Barto, Example 6.6):

The gridworld has a start state $S$ , a goal state $G$ , and a cliff along the bottom edge. Falling off the cliff gives $- 100$ reward and teleports you back to start. All other steps give $- 1$ .

With $ϵ = 0.1$ (10% random actions):

Q-Learning learns the optimal path — straight along the cliff edge. This is the shortest path to the goal. But 10% of the time, a random action from a cliff-edge state sends the agent off the cliff. The online performance during learning is terrible.
SARSA learns a longer path — an arc staying safely above the cliff. This takes more steps, but even with 10% random actions, the agent rarely falls because it stays far from the edge.

After training (once $ϵ \to 0$ and both algorithms become greedy), both would take the optimal cliff-edge path. But during training, SARSA's performance is far better because it accounts for its own exploration noise.

10.8.2 Use Cases and Comparative Summary

Comprehensive Comparison — SARSA vs Q-Learning across key dimensions:

Dimension	SARSA (On-Policy)	Q-Learning (Off-Policy)
Update Target	$R_{t + 1} + γ Q (S_{t + 1}, A_{t + 1})$ (Uses the next action actually selected)	$R_{t + 1} + γ max_{a} Q (S_{t + 1}, a)$ (Uses the greedy next action)
On/Off Policy Rationale	Evaluates and improves the same behavior policy $π$ . Target contains $A_{t + 1} \sim π$ , tying learning directly to exploratory actions.	Learns values for greedy target policy while behaving under exploratory policy $b$ . Target assumes greedy continuation.
Behavior under $ϵ$ -greedy	Learns safer, conservative values/policies when exploratory actions can be harmful.	Learns aggressive/optimistic values; looks optimal in values but suffers poorer online performance if $ϵ > 0$ .
Practical Applications	Online control with persistent exploration where safety matters: robotics navigation, adaptive traffic control, safe routing.	Value-based control where learning optimal $q_{*}$ is desired from exploratory data: tabular control, DQN with experience replay.
Limitations / Cautions	If $ϵ$ is not reduced, policy remains conservative and converges slower to the optimal greedy policy.	Off-policy bootstrapping with function approximation can be unstable (deadly triad); needs sufficient exploration coverage.

Assumptions & Scope: The SARSA-vs-Q-Learning tradeoff is most pronounced when $ϵ$ is non-negligible. As $ϵ \to 0$ , both algorithms converge to the same optimal policy. The difference matters during the learning phase, not at asymptote. If you can train entirely in simulation with a decaying $ϵ$ that approaches zero, the practical difference shrinks. The choice also depends on whether you can reuse data: SARSA requires fresh on-policy data for every update. Q-Learning can learn from off-policy data (including data collected by old policies or other agents).

Visual Intuition: Picture the cliff gridworld. The cliff runs along the bottom. The start is bottom-left, the goal is bottom-right. Q-Learning's path: a straight horizontal line one row above the cliff — mathematically optimal, 12 steps. SARSA's path: an arc going up two rows before descending — 17 steps, but safe. Now imagine the agent randomly stepping down on any given move. From Q-Learning's cliff-edge path, a random "down" action = instant $- 100$ cliff fall. From SARSA's upper path, a random "down" = one row closer but still above the cliff. This diagram captures the entire philosophy: SARSA pays a step-cost premium for insurance against exploration noise.

Pitfalls:

Always picking Q-Learning "because it is faster" — Faster convergence to the optimal policy does not help if the agent dies during training. For real-world deployment where training happens online, SARSA's safety margin is critical.
Always picking SARSA "because it is safer" — If you train purely in simulation and only deploy the final greedy policy, the training-phase safety is irrelevant. Q-Learning will find the truly optimal policy faster.
Ignoring Expected SARSA Expected SARSA often dominates both algorithms on the cliff-walking task (Sutton & Barto Figure 6.3). Can set $α = 1$ without degradation in deterministic environments. It is worth considering as the default choice when the action space is small enough.
Forgetting that the gap closes as $ϵ \to 0$ — If you anneal exploration to near-zero, SARSA and Q-Learning produce nearly identical policies. The choice matters most during the high-exploration phase.

10.8.3 Worked Comparison — Same Episode, Different Targets

Worked Example: Single Episode Trajectory under SARSA vs Q-Learning

Consider a tiny environment with nonterminal states $A$ and $B$ , followed by a terminal state. Discount factor $γ = 1.0$ , step size $α = 0.5$ .

Environment Dynamics & Current Estimates:

From state $A$ , only one action is available: $go$ , leading to $B$ with reward $R = 0$ . ( $A go, 0 B$ )
From state $B$ , two actions end the episode: $safe$ gives reward $+ 1$ ; $risky$ gives reward $- 1$ .
Prior Q-value estimates: $Q (A, go) = 0.5$ , $Q (B, safe) = 0.8$ , $Q (B, risky) = 0.2$ .

Observed Trajectory (due to exploratory action selection):

$(A, go, 0, B, risky), (B, risky, - 1, terminal)$

1. SARSA Solution (On-Policy Backup):

Update 1 for $Q (A, go)$ : Uses the next action actually taken at $B$ ( $risky$ , value $0.2$ ):

$Target_{SARSA} = R + γ Q (B, risky) = 0 + 1.0 \times 0.2 = 0.2$

$Q (A, go) \leftarrow 0.5 + 0.5 \times (0.2 - 0.5) = 0.5 - 0.15 = 0.35$

Update 2 for $Q (B, risky)$ : Next state is terminal ( $Q (terminal, \cdot) = 0$ ):

$Target = R = - 1.0 ⟹ Q (B, risky) \leftarrow 0.2 + 0.5 \times (- 1.0 - 0.2) = 0.2 - 0.60 = - 0.40$

Quantity	Old Estimate	Update Target	New Estimate
$Q (A, go)$	0.50	0.20	0.35
$Q (B, risky)$	0.20	-1.00	-0.40

Interpretation: Because exploration selected $risky$ at state $B$ , SARSA pulls the value of $Q (A, go)$ downward from $0.50$ to $0.35$ to reflect what actually happens under the exploratory behavior policy.

2. Q-Learning Solution (Off-Policy Backup):

Update 1 for $Q (A, go)$ : Uses the greedy next action at $B$ ( $max_{a} Q (B, a) = max (0.8, 0.2) = 0.8$ ):

$Target_{Q-Learning} = R + γ a max Q (B, a) = 0 + 1.0 \times 0.8 = 0.8$

$Q (A, go) \leftarrow 0.5 + 0.5 \times (0.8 - 0.5) = 0.5 + 0.15 = 0.65$

Update 2 for $Q (B, risky)$ : Next state is terminal:

$Target = R = - 1.0 ⟹ Q (B, risky) \leftarrow 0.2 + 0.5 \times (- 1.0 - 0.2) = - 0.40$

Quantity	Old Estimate	Update Target	New Estimate
$Q (A, go)$	0.50	0.80	0.65
$Q (B, risky)$	0.20	-1.00	-0.40

Interpretation: Q-Learning completely ignores the exploratory choice of $risky$ in the target calculation for $Q (A, go)$ and backs up the optimal greedy continuation ( $safe$ , value $0.8$ ), pushing $Q (A, go)$ upward from $0.50$ to $0.65$ .

Key Takeaway — Same Experience, Different Learning Signals: SARSA learns the value of the behavior policy (including exploration risks), whereas Q-learning learns toward the greedy/optimal policy values directly. This is why SARSA is typically safer under persistent $ϵ$ -greedy exploration, while Q-learning learns the optimal path but can suffer poorer online performance during training if $ϵ$ remains non-zero.

Exam note: Given a scenario (traffic control, nuclear plant, game AI, robot in simulation), you should identify whether SARSA, Q-Learning is more appropriate. Justify your answer. The justification should mention exploration sensitivity, safety, online vs offline training, and whether the policy must perform well during learning.

Recap + Bridge: SARSA is safer because it accounts for exploration noise in its target. Q-Learning is faster because it learns the optimal policy directly, ignoring exploration noise. Choose SARSA when safety matters during learning. Choose Q-Learning when you can train offline and care about the final policy. Next, we look at TD( $λ$ ) — a spectrum that generalizes both one-step TD and Monte Carlo.

Real-World & Domain Connection: In 2016, a team deploying RL for data center cooling chose SARSA over Q-Learning. The reason: during training, the agent controlled real server-room temperatures. An exploratory action that turned off cooling to a rack could destroy hardware. SARSA's conservative target, which accounts, the fact, exploration sometimes picks bad actions, kept temperatures within safe bounds even during the exploration phase. For game-playing (Atari, Go, chess), all major breakthroughs (DQN, AlphaGo, AlphaZero) use Q-Learning variants trained in simulation. Where the cost of losing a game during training is zero.

10.9 TD( $λ$ ) — The Credit Assignment Spectrum

Hook: You go on a 30-day diet. On day 30, you step on the scale and you are down 5 kg. Who gets the credit? The salad you ate yesterday? The run you did last week? The decision to quit soda three weeks ago? TD(0) credits only yesterday's salad. Monte Carlo splits credit equally across all 30 days. The truth is somewhere in between.

10.9.1 The Credit Assignment Problem

Intuition + Analogy — The Team Analogy (Professor's): Imagine you are the most junior person on a team that produces a great result. In a TD(0) team, only the person who executed the final action gets the credit, the junior person gets nothing. Weeks of preparation. In a Monte Carlo team, every single member from the CEO to the intern gets equal credit, even if they barely contributed. Neither is fair. You want credit to decay with distance: the people closer to the outcome get more, people further back get less. That is exactly what $λ$ controls. Where the analogy breaks: in a real team, credit is often assigned top-down (leaders get more), not bottom-up. TD( $λ$ ) assigns credit based on temporal distance from the reward, not hierarchical position.

Consider a sequence of state-action pairs leading to a reward of +100 somewhere along the way:

$(s, a), (s^{'}, a^{'}), (s^{''}, a^{''}), (s^{'''}, a^{'''}), \dots$

TD(0): credit goes only to the immediately preceding state-action pair $(s^{''}, a^{''})$ .
Monte Carlo: credit spreads equally over the entire sequence.
The credit assignment problem: how far back should credit propagate?

Formalize — TD( $λ$ ) spectrum: TD( $λ$ ) interpolates between these extremes with $λ \in [0, 1]$ :

$λ = 0$ : TD(0) — credit to immediate predecessor only
$λ = 1$ : Monte Carlo — credit equally over the whole episode
$0 < λ < 1$ : Credit decays exponentially with distance — $λ^{k}$ where $k$ is steps back from the reward

Worked Example — Credit decay with $λ = 0.8$ and TD error $δ = 2$ :

Steps before the outcome	Credit received	Computation
Immediate (0 steps back)	2.000	$δ \times λ^{0}$
1 step back	1.600	$δ \times λ^{1}$
2 steps back	1.280	$δ \times λ^{2}$
3 steps back	1.024	$δ \times λ^{3}$
4 steps back	0.819	$δ \times λ^{4}$
10 steps back	0.215	$δ \times λ^{10}$
20 steps back	0.023	$δ \times λ^{20}$

Sense-check: After about $1/ (1 - λ) = 5$ steps, the credit drops to roughly 33% of the original. After about $2/ (1 - λ) = 10$ steps, it drops below 11%. The effective horizon of credit is roughly $1/ (1 - λ)$ steps. At $λ = 0.9$ , the horizon is about 10 steps. At $λ = 0.99$ , about 100 steps. Small changes in $λ$ near 1 dramatically increase the credit horizon.

10.9.2 The Executive Analogy (Professor's)

A top-level executive makes a decision that leads to an outcome. The executive takes full responsibility (full TD error $δ$ ). The person reporting to the executive takes partial responsibility ( $λ \cdot δ$ ). Their direct report takes still less ( $λ^{2} \cdot δ$ ). This continues down the chain until, at some level, the credit effectively stops, the "bug stops", the person far enough back. The parameter $λ$ controls how quickly responsibility fades along the reporting chain.

Note on the standard formulation: The professor presented TD( $λ$ ) as credit assignment decaying with $λ^{k}$ across steps. Sutton & Barto (Chapter 12) formalize this through eligibility traces — a backward-view mechanism where each state maintains an eligibility trace that accumulates when visited and decays with $γ λ$ each step. The forward view (presented here) and backward view (eligibility traces) are equivalent. The forward view is simpler to understand conceptually; the backward view is more efficient to implement.

Assumptions & Scope: TD( $λ$ ), $λ > 0$ requires storing eligibility traces, each state (or state-action pair). Which increases memory from $O (∣ S ∣)$ to $O (∣ S ∣)$ in tabular form (just one extra scalar per state). The computational cost per step increases from constant to still-constant (updating all traces). The key assumption is, the Markov property holds, if states are not Markov. Distributing credit backward along actual trajectories (higher $λ$ ) can be better than bootstrapping from one-step estimates (lower $λ$ ). In practice, intermediate $λ$ values (0.3–0.7) often perform best because they balance the bias of bootstrapping against the variance of Monte Carlo.

Visual Intuition: Draw a horizontal timeline with a reward event (a star) at the right end. Above the timeline, draw a curve that starts at height 1 (full credit) at the reward event and decays exponentially leftward. The area under the curve is the total credit distributed. At $λ = 0$ , the curve is a spike at exactly the reward event — zero width, zero area elsewhere. At $λ = 1$ , the curve is a flat line at height 1 all the way to the start — equal credit everywhere. At $λ = 0.8$ , the curve decays smoothly: it is at 1.0 at the reward, 0.8 one step left, 0.64 two steps left. And so on. The balance between spike and flat line is what makes intermediate $λ$ values practically useful.

Pitfalls:

Thinking $λ = 1$ is always best because it uses "all the data" — Monte Carlo ( $λ = 1$ ) has the lowest bias but the highest variance. In stochastic environments, the high variance can slow learning dramatically. Intermediate $λ$ often gives better sample efficiency.
Thinking $λ = 0$ is always fastest — TD(0) has the lowest variance but the highest bias (it bootstraps from imperfect estimates). In environments with long reward delays, TD(0) propagates information one step per episode, which can be catastrophically slow.
Confusing TD( $λ$ ) with $n$ -step TD — Both bridge the TD-MC gap, but differently. TD( $λ$ ) decays credit across all past states simultaneously using eligibility traces. $n$ -step TD uses exactly $n$ real rewards and then bootstraps. They are related (the $n$ -step return is one component of the $λ$ -return), but implemented differently.
Ignoring computational cost of $λ > 0$ — Every step, eligibility traces for all states must be decayed. In large state spaces with function approximation, this is expensive. In practice, approximations like truncated $λ$ -returns or $n$ -step methods are often used instead.

Recap + Bridge: TD( $λ$ ) provides a spectrum from one-step TD ( $λ = 0$ ) to full Monte Carlo ( $λ = 1$ ). The parameter $λ$ controls how far back credit propagates by decaying the TD error geometrically. All algorithms covered so far (TD(0), SARSA, Q-Learning, Expected SARSA) are $λ = 0$ methods. Next, we look at $n$ -step TD — another way to bridge the gap, this time by using $n$ real rewards before bootstrapping.

Real-World & Domain Connection: TD( $λ$ ), eligibility traces is the backbone of the original TD-Gammon program (Tesauro, 1992–1995). Which learned to play backgammon at a superhuman level using only self-play, TD( $λ$ ). The long credit horizons in backgammon (a move early in the game affects the final outcome) benefited from intermediate $λ$ values around. 0.7. In modern deep RL, TD( $λ$ ) variants like the $λ$ -return are used in R2D2 (Recurrent Replay Distributed DQN), other agents. Long-term credit assignment matters. In finance, TD( $λ$ ) helps assign P&L (profit, loss) attribution in trading, which of the past decisions contributed most to today's gain, loss.

10.10 $n$ -Step TD Prediction — Beyond One Step

Hook: TD(0) looks one step ahead. Monte Carlo looks all the way to the end. What if the sweet spot is exactly three steps? Two is too few — you miss context. Ten is too many — you wait too long. $n$ -step TD lets you choose exactly how many real rewards to collect before bootstrapping.

10.10.1 Definition

Intuition + Analogy: You are estimating how long a road trip will take. TD(0) drives one mile, checks the speedometer, and extrapolates. Monte Carlo drives the entire trip and only then revises the estimate. $n$ -step TD drives 50 miles, notes the actual time for those 50 miles, and then extrapolates from the remaining distance. The 50-mile sample gives you real data (not just a guess). But you do not need to finish the whole trip to update your prediction. Where the analogy breaks: in the analogy, the "remaining distance" is known. In RL, the value of the state $n$ steps ahead is itself an estimate, so the bootstrapped part still has error.

The $n$ -step TD target replaces the one-step bootstrap with $n$ real rewards plus the estimated value $n$ steps ahead:

Formalize — $n$ -step return (Sutton & Barto, Eq. 7.1):

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

The update: $V_{t + n} (S_{t}) \leftarrow V_{t + n - 1} (S_{t}) + α [G_{t : t + n} - V_{t + n - 1} (S_{t})]$

Note the timing: the update for state $S_{t}$ happens at time $t + n$ (after $n$ real steps). No updates occur during the first $n - 1$ steps of each episode. The subscript $V_{t + n - 1}$ means we use the value function as it was at time $t + n - 1$ to bootstrap.

Error reduction property (Sutton & Barto, Eq. 7.3): The expected $n$ -step return is a better estimate of $v_{π}$ than the current $V$ is. In a worst-state sense: $s max E_{π} [G_{t : t + n} ∣ S_{t} = s] - v_{π} (s) \leq γ^{n} s max V (s) - v_{π} (s)$ This means every extra real reward reduces the worst-case error by a factor of $γ$ . At $γ = 0.9$ , a 3-step return reduces the error bound to $0. 9^{3} = 0.729$ of the one-step error. At 10 steps, it is $0. 9^{10} \approx 0.35$ . The theoretical improvement is guaranteed. This is why intermediate $n$ often works better than $n = 1$ or $n = \infty$ in practice.

10.10.2 Comparison of Targets

Step count $n$	Target	Bias	Variance	Update delay
$n = 1$	$R_{t + 1} + γ V (S_{t + 1})$	High (bootstrapped)	Low	1 step
$n = 2$	$R_{t + 1} + γ R_{t + 2} + γ^{2} V (S_{t + 2})$	Medium	Medium	2 steps
$n = 5$	$R_{t + 1} + \dots + γ^{4} R_{t + 5} + γ^{5} V (S_{t + 5})$	Low	Med-High	5 steps
$n = \infty$	$R_{t + 1} + γ R_{t + 2} + \dots$ (full return)	Zero (unbiased)	High	Episode end

Trace — 3-step TD on a random walk: Consider the 5-state random walk from Sutton & Barto (Example 6.2): states A–B–C–D–E. With terminal states at both ends (left = 0 reward, right = +1 reward). All $V (s)$ initialized to 0.5.

One episode: C → D → E → terminal (right, reward +1).

1-step TD: Only $V (E)$ is updated toward 1. $V (D)$ and $V (C)$ unchanged. Slow propagation.
2-step TD: $V (D)$ updates toward $0 + γ \times 1 = 0.9$ (using $R_{E} = 0$ , $V (terminal) = 0$ ? No — using $R_{D} + γ R_{E} + γ^{2} V (terminal) = 0 + 0.9 \cdot 0 + 0.81 \cdot 0 = 0$ — wait, let me recalculate.) Actually: 2-step from D: $G_{D : D + 2} = R_{D} + γ R_{E} + γ^{2} V (T)$ . $R_{D} = 0$ , $R_{E} = 0$ , $V (T) = 0$ . So $G = 0$ . Hmm. Let me reconsider.

Actually, from C: 3-step return = $R_{C} + γ R_{D} + γ^{2} R_{E} + γ^{3} V (T) = 0 + 0.9 \times 0 + 0.81 \times 0 + 0.729 \times 0 = 0$ . This does not work because all intermediate rewards are zero and the terminal reward goes into $V (T)$ which is 0.

Let me think again. In the random walk from Sutton & Barto:

Episode: C(0), D(0), E(0), right-terminal(+1)
The rewards ARE zero for all intermediate states. The reward of +1 occurs when transitioning FROM E to the terminal.
So $R_{E}$ (reward when leaving E) = +1.

So:

1-step from E: $G_{E : E + 1} = R_{E} + γ V (T) = 1 + 0.9 \times 0 = 1$ . Update $V (E)$ toward 1.
2-step from D: $G_{D : D + 2} = R_{D} + γ R_{E} + γ^{2} V (T) = 0 + 0.9 \times 1 + 0.81 \times 0 = 0.9$ . Update $V (D)$ toward 0.9.
3-step from C: $G_{C : C + 3} = R_{C} + γ R_{D} + γ^{2} R_{E} + γ^{3} V (T) = 0 + 0.9 \times 0 + 0.81 \times 1 + 0.729 \times 0 = 0.81$ . Update $V (C)$ toward 0.81.

In a single episode, 3-step TD propagates the reward three steps back immediately, while 1-step TD only updates the last state.

Sense-check: The true values for this random walk are $V (A) = 1/6, V (B) = 2/6, V (C) = 3/6, V (D) = 4/6, V (E) = 5/6$ . After one episode going right from C, 3-step TD brings $V (C), V (D), V (E)$ closer to their true values in one shot. While 1-step TD only nudges $V (E)$ . This is the speedup. But the 3-step update happens at step 3, while 1-step updates happen at steps 1, 2, and 3. So 1-step gets three updates, 3-step gets one. The tradeoff is real: more steps per update vs more updates per episode.

Assumptions & Scope: $n$ -step TD requires storing the last $n$ states and rewards — $O (n)$ memory. Updates are delayed by $n$ steps, which may be unacceptable in time-critical applications (e.g., high-frequency trading). For episodic tasks, if the episode length $T < n$ , the $n$ -step return reduces to the full Monte Carlo return (no bootstrapping). The optimal $n$ depends on the environment. Larger $n$ works better when rewards are delayed and the value function is inaccurate, meaning bootstrap error is high. Smaller $n$ works better when rewards are frequent and the value function is already good, since variance reduction matters more. Sutton & Barto (Figure 7.2) show that intermediate $n$ values (4–32) outperform both extremes on the 19-state random walk.

Pitfalls:

Ignoring the update delay — $n$ -step TD does not update at all during the first $n - 1$ steps of an episode. For short episodes ( $T \approx n$ ), you lose most of your update opportunities. For long episodes, the delay is negligible.
Choosing $n$ arbitrarily — $n = 1$ and $n = \infty$ are rarely optimal. The best $n$ depends on the reward delay structure and the stochasticity of the environment. Test a range.
Confusing $n$ -step TD with TD( $λ$ ) — $n$ -step uses exactly $n$ real rewards and then bootstraps once. TD( $λ$ ) uses eligibility traces to decay credit across all past states simultaneously. They are related (the $λ$ -return is a weighted sum of all $n$ -step returns), but the implementation and memory costs differ.

Recap + Bridge: $n$ -step TD bridges TD(0) and Monte Carlo by using $n$ real rewards before bootstrapping. Larger $n$ reduces bias but increases variance and update delay. Intermediate $n$ values often perform best. Next, we take a deeper look at on-policy vs off-policy — the philosophical divide that cuts across all TD algorithms.

Real-World & Domain Connection: $n$ -step methods are used in practice when the environment has a natural "checkpoint" granularity. In robot locomotion, a step is a millisecond motor command, but the meaningful unit is a full stride. Using $n$ -step returns, $n$ matches one stride length provides better credit assignment than one-step TD, being cheaper than full-episode Monte Carlo. In dialogue systems, a conversation turn is a natural unit. $n$ -step returns spanning one full exchange (user utterance + system response) capture the reward signal more meaningfully than single-word-level TD.

10.11 On-Policy vs Off-Policy — A Deeper Discussion

Hook: You can learn to drive in two ways. Option A: you drive the car yourself, make mistakes, learn from them, and improve. Option B: you sit in the passenger seat, an expert chauffeur drives, you observe every turn, every brake, every near-miss. And you learn the optimal driving strategy from their experience without ever touching the wheel. Option A is on-policy. Option B is off-policy.

10.11.1 Behavior Policy and Target Policy

Intuition + Analogy — The Driving School (Professor's): Different instructors (behavior policies) give you different driving experiences. One instructor takes highways. Another takes back roads. A third drives aggressively. You, the student (target policy), learn to drive from all of them. The instructors do not change — their role is to provide diverse training scenarios. This is off-policy learning in one sentence. Where the analogy breaks: in the strict algorithm, the instructor (behavior policy $b$ ) is never updated. A real driving instructor might also improve with experience, but in the algorithm, $b$ is frozen. Any evolution of $b$ happens outside the algorithm loop.

In off-policy learning, two distinct policies operate:

Behavior policy $b$ : Generates experience — the actions actually executed in the environment. This can come from expert data, safety rules, exploratory heuristics, or any source.
Target policy $π$ : The policy being learned — the one whose values are updated and improved.

In on-policy methods, $b = π$ — one policy handles everything in a closed loop.

Formalize — why off-policy matters (and when it does not): Decoupling experience generation from learning gives three superpowers:

Learn from others' experience. A doctor's decades of clinical decisions (behavior policy) generate a dataset of state-action-reward tuples. The target policy learns optimal treatment from this data without ever interacting with a patient during training.

Safety constraints. In a nuclear plant, the behavior policy encodes "never open this valve." The target policy learns optimal control within the safe envelope. It never explores the forbidden action, it never generates experience.

Reuse data. Past experiences from any source can be pooled. The target policy learns from all of it.

The cost: off-policy learning is harder. When the behavior and target policies differ, the data distribution is skewed. Monte Carlo off-policy methods need importance sampling — reweighting each trajectory by $\prod_{t} \frac{π ( a _{t} ∣ s _{t} )}{b ( a _{t} ∣ s _{t} )}$ — which can have enormous variance. TD methods like Q-Learning avoid this, they only use one-step transitions. Reducing the importance sampling to a single ratio (or eliminating it entirely when the target is greedy, as in Q-Learning's max).

The on-policy/off-policy checklist:

On-policy: One policy $π$ . Sample from $π$ , learn from $π$ , update $π$ , repeat. Example: SARSA.
Off-policy: Two policies. $b$ generates experience. $π$ is updated. Example: Q-Learning.

10.11.2 Algorithm Walkthrough (High-Level)

At each step:

Behavior policy $b$ generates an action.
Execute the action. Observe reward and next state.
Update target policy $π$ using the experience.
$b$ is never updated — it is a given, provided at the start.

Student Q&A — Deduplicated:

Q: Several students asked: where does the behavior policy come from? Can it evolve? If we start with a policy, use it to generate experience, update it, and reuse it — is that on-policy?

A — Three-part answer from the professor:

Where does $b$ come from? It is a given input, defined by the domain designer before learning. It can be constructed from supervised learning on expert data, safety rules, best practices, or a separate RL training process. In the algorithm, $b$ is only used to generate experience — it is never updated.

Can $b$ evolve? The behavior policy can change over time to provide different challenges, but this evolution happens outside the algorithm. Inside the algorithm, $b$ is treated as fixed during each interaction.

Is a self-updating policy on-policy? Yes. In on-policy methods, you start with some policy (it can be random or come from prior learning). You use it to generate experience, update it, and use the updated version for the next batch. The initialization need not be arbitrary — it can come from past learning and still be on-policy. These are engineering decisions around the algorithm, not inside it.

Q: Confirmation, in the nuclear plant example, the safety rules go into the behavior policy $b$ . And the target policy never explores unsafe actions?

A: Exactly. The behavior policy encodes all "never do this" rules. The target policy learns optimal behavior within the safe envelope without ever exploring the forbidden actions. In on-policy learning, the agent would have to explore the unsafe action at least occasionally to know it is bad. Which is unacceptable in safety-critical settings.

10.11.3 Terminology Note

Terminology:"Teacher policy" and "learner policy" are casual analogies used for intuition. The formal terms are behavior policy and target policy. Do not use the informal terms in exams or formal writing — they are not standard.

Assumptions & Scope: Off-policy learning assumes the behavior policy has coverage — $b (a ∣ s) > 0$ whenever $π (a ∣ s) > 0$ . The behavior policy must have non-zero probability for every action the target policy might take. If $b$ never visits a state-action pair that $π$ would choose, that pair's value can never be learned. With importance sampling (needed, off-policy Monte Carlo), if $b$ assigns very low probability to an action, $π$ assigns high probability. The importance weight becomes very large, inflating variance. TD methods avoid this by using one-step updates where the importance weight involves only a single ratio. When the target is greedy (Q-Learning), the max operator eliminates the need for importance sampling entirely.

Visual Intuition: Draw two circles overlapping partially. Label the left circle "Behavior Policy $b$ " — the actions actually taken. Label the right circle "Target Policy $π$ " — the actions being learned. In on-policy learning, the two circles are exactly the same — one circle. In off-policy learning, the circles overlap (coverage assumption) but are not identical. The gap between them is the distribution shift — the difference between what you do and what you learn. Importance sampling bridges this gap by reweighting data from the left circle to reflect the right circle's distribution.

Pitfalls:

Confusing "off-policy" with "offline" — Off-policy means the behavior and target policies differ. Offline (batch) RL means learning from a fixed dataset without further interaction. These are orthogonal concepts. You can have online on-policy, online off-policy, offline on-policy, and offline off-policy.
Forgetting the coverage assumption — If $b (a ∣ s) = 0$ for some action, off-policy methods cannot learn about that action. The behavior policy must explore everything the target policy might want to use.
Using importance sampling carelessly with long trajectories — The product of importance ratios over a long episode can explode or vanish. TD methods are preferred for off-policy learning because they only need one-step ratios.
Calling $ϵ$ -greedy Q-Learning "on-policy" because it uses the same Q-table — The Q-table is shared, but the policies differ: the behavior policy is $ϵ$ -greedy; the target policy is greedy. The algorithm is off-policy.

Exam note: Be able to explain why SARSA is on-policy (same policy generates experience, provides the target $a^{'}$ ). Why Q-Learning is off-policy (behavior policy is $ϵ$ -greedy, target is greedy max). Given a scenario, identify whether an on-policy, off-policy approach is more suitable, justify, reference to safety, data reuse, or expert data.

Recap + Bridge: On-policy methods use one policy for everything — simple but restrictive. Off-policy methods separate experience generation from learning — powerful but harder. SARSA is on-policy. Q-Learning is off-policy. This distinction is one of the most important conceptual divides in RL. Next, we clarify the three value-related symbols that students most often confuse: $V$ , $Q$ , and $G$ .

Real-World & Domain Connection: Off-policy learning powers the recommender systems at companies like Netflix and YouTube. The behavior policy is the current production recommendation algorithm (which must keep users engaged). The target policy is the improved algorithm being trained offline on logged user interaction data. The production system never takes random exploratory actions — it always serves its best guess. But the target policy learns from the inherent diversity in user responses to different recommendations. This offline off-policy setup is standard in industry because randomly recommending bad content to users (exploration) costs engagement and revenue.

10.12 Understanding V, Q, and G — What to Update When

Hook: Three letters. Three concepts. Students mix them up constantly. Here is the one-line version: $V$ is a property of a place. $Q$ is a property of a choice in that place. $G$ is the actual outcome of a specific journey — not stored, just computed.

Intuition + Analogy (Professor's): $V (s)$ says "this person is generally in a bad situation" — it is a holistic judgment. $Q (s, a)$ says "this person is good at this specific thing but bad at that specific thing" — it breaks down capability by action. $G_{t}$ is the recounting of exactly what happened, "you tried this, this, and this. And here is what you got." $Q$ associates actions, outcomes. That is what you need for control. Where the analogy breaks: $G_{t}$ is not just a story — it is a discounted sum. Late rewards count less than early ones, which has no equivalent in a simple retelling of events.

10.12.1 The Three Value Objects — Definitions and Distinctions

Formalize — $V$ , $Q$ , and $G$ precisely defined:

$V (s)$ — the state-value function: $V^{π} (s) = E_{π} [k = 0 \sum \infty γ^{k} R_{t + k + 1} S_{t} = s]$

What it is: the expected cumulative discounted reward from state $s$ , assuming you follow policy $π$ .
Stored in memory: yes — a table or function approximator.
Used for: prediction (evaluating a fixed policy).
Updated by: TD(0), Monte Carlo, Dynamic Programming.
Think: "How good is this position, on average?"

$Q (s, a)$ — the action-value function: $Q^{π} (s, a) = E_{π} [k = 0 \sum \infty γ^{k} R_{t + k + 1} S_{t} = s, A_{t} = a]$

What it is: the expected cumulative discounted reward from taking action $a$ in state $s$ , then following $π$ .
Stored in memory: yes — a table or function approximator.
Used for: control (choosing the best action).
Updated by: SARSA, Q-Learning, Expected SARSA.
Think: "How good is this specific move?"

$G_{t}$ — the return: $G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots$

What it is: the actual cumulative discounted reward experienced from time $t$ to episode end.
Stored in memory: no — it is computed from the episode trajectory and discarded.
Used for: the target in Monte Carlo methods (and as a component of $n$ -step targets).
Think: "What actually happened this time?"

Relationship between them: $V^{π} (s) = a \sum π (a ∣ s) \cdot Q^{π} (s, a) (V is the expectation of Q under π)$ $G_{t} is a single sample of the quantity whose expectation is v_{π} (S_{t}) or q_{π} (S_{t}, A_{t})$

In plain language: $V$ is the average of $Q$ over the policy's actions. $G$ is one random draw from the distribution whose mean is $V$ (or $Q$ ).

Assumptions & Scope: $V$ and $Q$ are defined with respect to a specific policy $π$ . Change the policy, and the values change. This is why on-policy algorithms must discard old data when the policy updates, the old data was generated under a different $π$ . Its $Q^{π}$ values are no longer valid. $G$ , being a sample from the environment under a specific trajectory, does not depend on $π$ in the same way. It is simply what happened. But its expectation does depend on $π$ .

Visual Intuition: Picture a game tree. $V (s)$ is a single number floating above each node — the average outcome from that position. $Q (s, a)$ is a number on each edge leaving the node — the average outcome from taking that specific action. $G_{t}$ is a highlighted path from the root to a leaf with the actual rewards written along the edges. $V$ and $Q$ are summaries (averages over many paths). $G$ is one specific path.

Pitfalls:

Thinking $G$ is stored and updated like $V$ or $Q$ — $G$ is a computation over a specific trajectory, not a persistent function. You compute it, use it as a target, and discard it. You never maintain a table of $G$ values.
Confusing $V$ and $Q$ when choosing an algorithm — TD(0) updates $V$ . SARSA and Q-Learning update $Q$ . If you implement a $V$ -update loop, compute targets using $Q$ , you are mixing prediction, control, the math does not check out.
Forgetting that $V^{π}$ and $Q^{π}$ depend on $π$ If someone says "the value of state $s$ is 10," the immediate follow-up question is "under. Policy?" There is no policy-independent state value.
Converting $V$ to $Q$ without a model — You can compute $V$ from $Q$ via $V (s) = \sum_{a} π (a ∣ s) Q (s, a)$ without a model. But to compute $Q$ from $V$ , you need the transition probabilities $p (s^{'} ∣ s, a)$ — you need a model.

Deduplicated Student Q&A:

Q: In TD(0) or dynamic programming we update $V$ . In SARSA we update $Q$ . Sometimes we update $G$ (the return). How do I remember which to use where?

A: Several students asked this. $V (s)$ is the value of a state — how good it is to be in that state, assuming you follow a policy. It is simpler but less informative. $Q (s, a)$ is the value of taking action $a$ in state $s$ — how good a specific action is in a specific state. $Q$ is more informative than $V$ . In most real-world scenarios, you will use $Q$ because to make decisions you need to compare actions. $G_{t}$ (the return) is the target used in Monte Carlo methods. The sum of all discounted rewards from time $t$ to the end. It is not a function you maintain in memory. Think: $V$ says "this person is generally in a bad situation." $Q$ says "this person is good at this specific thing. Bad at, specific thing." $Q$ associates actions, outcomes, which is what you need, control.

Recap + Bridge: $V$ answers "how good is this state?" $Q$ answers "how good is this action in this state?" $G$ answers "what actually happened. In this episode?". Prediction, use $V$ . For control, use $Q$ . For Monte Carlo targets, compute $G$ from the trajectory. Next, we survey the real-world landscape — where these algorithms are deployed and what researchers are working on.

Real-World & Domain Connection: The distinction between $V$ and $Q$ maps directly to different AI system architectures. A position evaluator in chess (like Stockfish's static evaluation) is a $V$ -function — it scores a board position. A move selector (like AlphaZero's policy head) is a $Q$ -function — it scores each candidate move. Modern systems often learn both: the $Q$ -function, move selection, the $V$ -function as a baseline to reduce variance in the learning signal. Understanding when to use each is a core architecture decision in RL system design.

10.13 Industry Applications and Research Directions

10.13.1 Real-World Uses

Temporal difference learning and its variants power systems across industries:

Game playing — Chess, Go, Atari, StarCraft. DQN (Mnih et al., 2015) achieved superhuman performance on 49 Atari games using Q-Learning with convolutional neural networks and experience replay. AlphaGo and AlphaZero use TD-style value estimation as a core component.
Robotics — Online motor control policies learned via TD methods. Robot arms learn grasping, locomotion, and manipulation by updating Q-values after every tiny movement rather than waiting for task completion.
Traffic signal control — Adaptive signal timing where exploration (trying new signal patterns) must be safe. SARSA is preferred because its target accounts for occasional exploratory timing changes.
Recommendation systems — Sequential user interactions (clicks, watches, purchases) are treated as an MDP. TD methods learn long-term user satisfaction, not just immediate click-through.
Dialogue systems and chatbots — RL from Human Feedback (RLHF) uses TD-style credit assignment to train language models from preference comparisons rather than explicit reward functions.
Autonomous driving — TD methods learn driving policies from a mix of human driving logs (off-policy) and simulation (on-policy).
Finance — Algorithmic execution, portfolio optimization, and option pricing all use TD learning for sequential decision-making under uncertainty.
Healthcare — Treatment optimization from electronic health records. Off-policy TD methods learn optimal treatment policies from historical doctor decisions.

10.13.2 Current Research

The professor highlighted a 2026 ICML paper from Google DeepMind on 3D maze navigation using purely visual input with deep Q-learning techniques. This represents the state of the art in combining deep learning with TD methods for complex visual navigation. ICML, NeurIPS, and ICLR are premier venues for RL research. RL papers also appear at robotics (CoRL, ICRA), process control, and domain-specific conferences.

10.13.3 Research Directions

Open problems mentioned by the professor:

Improving Q-value initialization — Better priors could dramatically reduce the exploration needed.
Incorporating past experience into online learning — Merging offline datasets with online interaction without catastrophic forgetting.
Alternatives to $ϵ$ -greedy exploration — Thompson sampling, upper confidence bounds (UCB), intrinsic motivation, and curiosity-driven exploration.
Mitigating overestimation bias — Double Q-Learning, clipped double Q-Learning (TD3, SAC), and ensemble methods.

In the current era of agentic AI, reinforcement learning sits at the heart of many systems. New directions open up constantly as compute scales and environments become more complex.

Deduplicated Student Q&A:

Q: What research directions exist in RL? Where are RL papers published?

A: Several students asked about RL research opportunities. Active areas include improving Q-value initialization, developing alternatives to epsilon-greedy exploration (Thompson sampling, UCB, intrinsic motivation), mitigating overestimation bias (Double Q-Learning. Clipped methods), and better ways to incorporate past experience into online learning. For staying current, ICML, NeurIPS, and ICLR are premier venues. RL papers also appear at robotics conferences (CoRL, ICRA) and domain-specific venues. Following RL researchers on social media and subscribing to research mailing lists can help track the latest work.

Recap: TD learning bridges the model-free world of Monte Carlo with the bootstrapping world of dynamic programming. From the simple TD(0) update to SARSA, Q-Learning, Expected SARSA, TD( $λ$ ), and $n$ -step methods, the same core idea. Adjust your estimate toward a better-informed target, drives every algorithm in this lecture. The choice between on-policy (SARSA), off-policy (Q-Learning), between one-step, multi-step, between sampling, expectation, these are variations on a single, elegant theme.

10.14 Key Takeaways

10.14.1 The Core Algorithms

TD learning bridges dynamic programming (model-based, expected updates, local) and Monte Carlo (model-free, returns, online-ish). It is model-free, online, and local — the best of both. Updates happen every step using the TD error.

The TD error $δ_{t} = R_{t + 1} + γ V (s_{t + 1}) - V (s_{t})$ is the surprise signal that drives all TD updates. Positive error pulls the estimate up. Negative error pulls it down.

TD(0) estimates $V^{π}$ — the value of states under a fixed policy. It updates every step without waiting for episode completion. Used for prediction (policy evaluation), not control.

10.14.2 The Control Algorithms

SARSA is on-policy TD control. The target uses $Q (s^{'}, a^{'})$ where $a^{'}$ is chosen by the same $ϵ$ -greedy policy. Safe and exploration-aware. Prefer for safety-critical online learning.

Q-Learning is off-policy TD control. The target uses $max_{a^{'}} Q (s^{'}, a^{'})$ . Learns the optimal policy directly but can suffer from maximization bias. Foundation for DQN and deep RL.

Expected SARSA computes the expectation over all next actions instead of sampling one or taking the max. More stable than both extremes. Eliminates sampling variance and max-bias at the cost of computing the full expectation.

10.14.3 Extensions and Key Concepts

TD( $λ$ ) provides a spectrum of credit assignment from one-step ( $λ = 0$ ) to full Monte Carlo ( $λ = 1$ ), decaying credit with $λ^{k}$ across steps. Intermediate $λ$ values often perform best.

$n$ -step TD varies how many real rewards are used in the target before bootstrapping. Larger $n$ reduces bias but increases variance and update delay.

On-policy vs off-policy: On-policy uses one policy for everything (SARSA). Off-policy separates behavior generation ( $b$ ) from the policy being learned ( $π$ ) (Q-Learning). Off-policy enables learning from experts, safety constraints, and past data.

V vs Q vs G: $V (s)$ is state value (prediction). $Q (s, a)$ is action value (control). $G_{t}$ is the return — a computed target from a trajectory, not a stored function. Use $V$ for evaluation, $Q$ for control, $G$ for Monte Carlo targets.

The unifying theme: Every algorithm in this lecture — from TD(0) to Expected SARSA — uses the same core update: $new \leftarrow old + α [target - old]$ . The only difference is what goes in the target box. TD(0) fills the box with $R + γ V (s^{'})$ . SARSA fills it with $R + γ Q (s^{'}, a^{'})$ . Q-Learning fills it with $R + γ max Q (s^{'}, \cdot)$ . Expected SARSA fills it with $R + γ E [Q (s^{'}, \cdot)]$ . Once you see the pattern, you see that all of TD learning is variations on a single elegant idea.

Exam Guidance Summary

Exam note — The three question types to prepare for:

1. Numerical problems: Expect to compute SARSA and Q-Learning updates given a grid or maze diagram, initial Q-values, rewards, and $γ$ . You must show every intermediate step: write the TD error, compute the target, and produce the final Q-value after each update. The most common mistake is using the wrong action in the target — SARSA uses the actually chosen $a^{'}$ , Q-Learning uses $max Q (s^{'}, \cdot)$ . Double-check which algorithm the question asks for before plugging in numbers.

2. Conceptual explanations: Be able to explain:

Why TD learning improves upon both dynamic programming and Monte Carlo (model-free + online + local)
Why SARSA is on-policy (same policy generates actions and provides the target $a^{'}$ )
Why Q-Learning is off-policy (behavior policy is $ϵ$ -greedy, target is greedy max)
Why these are control algorithms (the policy improves as Q-values improve — GPI in action)

3. Scenario analysis: Given a real-world scenario (traffic control, nuclear plant, game AI, robot in simulation), identify whether SARSA or Q-Learning is more appropriate. Justify your choice with reference to exploration sensitivity, safety, online vs offline training, and whether the policy must perform well during learning.

Textbook reference: Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.), Chapter 6, pages 119–138. The discussion of TD vs MC convergence (page 124) is especially relevant, proving, method converges faster is an open theoretical question. But TD methods have been found faster in practice on stochastic tasks.

Key Industry Applications

Traffic signal control — SARSA preferred for safe exploration. Untested signal timings must not cause accidents. The policy must perform well even while learning.
Game playing (chess, Go, Atari) — Q-Learning and DQN variants trained in simulation, where the cost of losing during training is zero. AlphaGo and AlphaZero use TD-style value estimation.
Robotics — Online motor control with TD methods. Robot arms learn grasping by updating Q-values after every movement, not just at task completion.
Recommendation systems — Sequential user interaction learning. TD methods optimize for long-term user satisfaction (retention, lifetime value), not just immediate click-through rate.
Dialogue systems — RL from Human Feedback (RLHF) trains language models using TD-style credit assignment from pairwise preference comparisons.
Autonomous navigation — 3D maze navigation with visual input (Google DeepMind, ICML 2026). Combines deep Q-learning with visual perception.
Finance — Algorithmic execution and portfolio optimization. TD methods handle the sequential nature of trading decisions under uncertainty.
Healthcare — Treatment policy optimization from electronic health records. Off-policy TD enables learning optimal treatments from historical doctor decisions.
Data center cooling — SARSA-based RL agents control cooling systems in real time, where exploration that risks overheating is unacceptable.

DRL Lecture 10 notes · Temporal Difference Learning: TD(0), SARSA, and Q-Learning

Deep Reinforcement Learning· postgraduate· 2026-07-11

Sections Breakdown

110.1 Temporal Difference Learning — The Bridge Between Two Worlds

210.2 The TD Error — The Signal That Drives Learning

310.3 TD(0) — The Basic Temporal Difference Algorithm for Policy Evaluation

410.4 Introduction to Control — Moving from V to Q

510.5 SARSA — On-Policy TD Control

610.6 Q-Learning — Off-Policy TD Control

710.7 Expected SARSA — The Middle Ground

810.8 SARSA vs Q-Learning — When to Use Which

910.9 TD($\lambda$) — The Credit Assignment Spectrum

1010.10 $n$-Step TD Prediction — Beyond One Step

1110.11 On-Policy vs Off-Policy — A Deeper Discussion

1210.12 Understanding V, Q, and G — What to Update When

1310.13 Industry Applications and Research Directions

1410.14 Key Takeaways

15Exam Guidance Summary

16Key Industry Applications

Postgraduate students in Deep Reinforcement Learning

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Every entry is built from the full textbook notes above. Use this section for rapid review — but if something doesn't make sense, go back to the full explanation in the main content.

TD Learning — the three targets

Must-know: TD learning sits between DP (expected, model-based) and Monte Carlo (full return). Its target is a one-step lookahead: R + gamma V(s'). It is model-free, online, and local.

$T a r g e t_{T D} = R_{t + 1} + γ V (s_{t + 1})$

⚠️ Top pitfall: Confusing TD with Monte Carlo — TD updates every step using a bootstrapped value; MC waits for episode end and uses the actual return.

Self-check: Why does TD(0) not need a model of the environment's transition probabilities?

Connects to: 10.2 The TD Error; 10.3 TD(0); 10.4 Moving from V to Q

The TD Error

Must-know: The TD error delta_t is the gap between the TD target and the current estimate. It is the universal surprise signal that drives every TD update.

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

⚠️ Top pitfall: Thinking the TD error equals the reward. It is reward PLUS the change in estimated future value, so a big reward can still give zero error if V drops equally.

Self-check: If V(s_t)=10, R=0, gamma=1, V(s')=8, what is delta_t and which way does V move?

Connects to: 10.1 TD Learning; 10.3 TD(0)

TD(0) for policy evaluation

Must-know: TD(0) estimates V^pi under a FIXED policy. It updates every step, never waits for episode end, and does NOT improve the policy — it only evaluates it.

$V (S) \leftarrow V (S) + α [R + γ V (S^{'}) - V (S)]$

⚠️ Top pitfall: Using alpha=1 in production — every update overwrites the old estimate and values oscillate forever. Use small alpha (0.01–0.1).

Self-check: Why can TD(0) handle continuing (non-episodic) tasks but Monte Carlo cannot?

Connects to: 10.1 TD Learning; 10.2 The TD Error

From V to Q — why control needs Q

Must-know: V(s) tells you how good a state is; Q(s,a) tells you how good each action is. Control (choosing actions) needs Q because argmax_a Q(s,a) gives the best move without a model.

$V^{π} (s) = a \sum π (a ∣ s) Q^{π} (s, a)$

⚠️ Top pitfall: Thinking V is useless for control. Actor-critic methods use V as a baseline; V needs less data. But to ACT you need Q.

Self-check: Why can you recover V from Q but not Q from V without a model?

Connects to: 10.3 TD(0); 10.5 SARSA; 10.6 Q-Learning

SARSA — on-policy TD control

Must-know: SARSA uses the quintuple (s,a,r,s',a'). The target uses a' chosen by the SAME epsilon-greedy policy that generated the experience. It learns a safe, exploration-aware policy.

$Q (s, a) \leftarrow Q (s, a) + α [R + γ Q (s^{'}, a^{'}) - Q (s, a)]$

⚠️ Top pitfall: Using max in the target by mistake — that makes it Q-Learning, not SARSA. SARSA uses the action the policy ACTUALLY picked next.

Self-check: On the cliff grid, why does SARSA learn a longer but safer path than Q-Learning?

Connects to: 10.6 Q-Learning; 10.8 SARSA vs Q-Learning

Q-Learning — off-policy TD control

Must-know: Q-Learning always uses max_a' Q(s',a') in the target, regardless of the exploratory action taken. It learns the optimal policy directly while exploring suboptimally.

$Q (s, a) \leftarrow Q (s, a) + α [R + γ a^{'} max Q (s^{'}, a^{'}) - Q (s, a)]$

⚠️ Top pitfall: Maximization bias — the max operator inflates Q-values because it picks the luckiest noisy estimate. Fix with Double Q-Learning or DQN target networks.

Self-check: Why is Q-Learning called off-policy when the same Q-table is shared?

Connects to: 10.5 SARSA; 10.7 Expected SARSA; 10.11 On-Policy vs Off-Policy

Expected SARSA — the middle ground

Must-know: Expected SARSA replaces the sampled a' (SARSA) and the max (Q-Learning) with the expectation over all next actions under the policy. No sampling variance, no max bias.

$Q (s, a) \leftarrow Q (s, a) + α [R + γ a^{'} \sum π (a^{'} ∣ s^{'}) Q (s^{'}, a^{'}) - Q (s, a)]$

⚠️ Top pitfall: Cost in large action spaces — every update evaluates Q for ALL actions, O(|A|) forward passes. At epsilon≈0 it equals Q-Learning.

Self-check: With epsilon=0.3 and Q(up)=100, Q(down)=20, others=20/10, what is the expected target value?

Connects to: 10.5 SARSA; 10.6 Q-Learning

SARSA vs Q-Learning — when to use which

Must-know: Pick SARSA when exploration is risky and training is online (robot, traffic, nuclear). Pick Q-Learning when you train in simulation and only deploy the final greedy policy (games, DQN).

$SARSA target = R + γ Q (s^{'}, a^{'}); Q-Learning target = R + γ a^{'} max Q (s^{'}, a^{'})$

⚠️ Top pitfall: Forgetting the gap closes as epsilon→0. Both converge to the same optimal policy at asymptote; the difference matters during high-exploration training.

Self-check: A self-driving car trains online in a city. Which algorithm is safer and why?

Connects to: 10.5 SARSA; 10.6 Q-Learning; 10.11 On-Policy vs Off-Policy

TD(lambda) — the credit assignment spectrum

Must-know: TD(lambda) interpolates between TD(0) (credit to one step) and Monte Carlo (equal credit to all). Credit decays as lambda^k with distance from the reward.

$credit at k steps back = λ^{k} \cdot δ_{t}, λ \in [0, 1]$

⚠️ Top pitfall: Assuming lambda=1 is always best. Intermediate lambda (0.3–0.7) often wins by balancing bootstrap bias against MC variance.

Self-check: With lambda=0.8 and delta=2, how much credit reaches a state 3 steps before the reward?

Connects to: 10.1 TD Learning; 10.10 n-Step TD

n-Step TD Prediction

Must-know: n-step TD collects n real rewards before bootstrapping from V n steps ahead. Larger n cuts bias but raises variance and delays updates by n steps.

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

⚠️ Top pitfall: Thinking n-step is just 'better TD(0)'. The error bound shrinks by gamma^n per extra reward, but update delay and variance grow with n.

Self-check: Why does a 3-step return reduce the worst-case error bound to 0.9^3 of the one-step error at gamma=0.9?

Connects to: 10.1 TD Learning; 10.9 TD(lambda)

On-Policy vs Off-Policy

Must-know: On-policy (SARSA) uses one policy for everything. Off-policy (Q-Learning) separates the behavior policy b (generates data) from the target policy pi (learned). Off-policy enables learning from experts and reusing data.

$On-policy: b = π; Off-policy: b \neq = π, b (a ∣ s) > 0 \forall a with π (a ∣ s) > 0$

⚠️ Top pitfall: Confusing off-policy with offline. They are orthogonal: you can have online off-policy or offline on-policy. Also never call epsilon-greedy Q-Learning 'on-policy'.

Self-check: In a nuclear plant, why must the behavior policy encode safety rules that the target policy never explores?

Connects to: 10.5 SARSA; 10.6 Q-Learning; 10.11 On-Policy vs Off-Policy

V, Q, and G — what to update when

Must-know: V(s) is a property of a place (prediction). Q(s,a) is a property of a choice in that place (control). G_t is the actual return of one trajectory — computed, not stored.

$G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots$

⚠️ Top pitfall: Mixing up G_t with V. G_t is a single sampled path (used by Monte Carlo); V is the average over many paths and is what you store and update.

Self-check: Which of V, Q, G is stored in memory and updated by TD? Which is discarded after each episode?

Connects to: 10.3 TD(0); 10.4 Moving from V to Q; 10.6 Q-Learning

Previous LectureLecture 09 · Off-Policy Monte Carlo Methods and Introduction to Temporal Difference Learning

Next LectureLecture 11 · Temporal Difference Learning, Maximization Bias, and Function Approximation

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

Temporal Difference Learning: TD(0), SARSA, and Q-Learning

10.1 Temporal Difference Learning — The Bridge Between Two Worlds

10.1.1 Definition and Explanation

10.1.2 The Three Targets — Side by Side

10.1.3 Why This Matters — The Best of Both Worlds

10.1.4 Symbol Registry — TD Learning Foundation

10.1.5 References

10.2 The TD Error — The Signal That Drives Learning

10.2.1 Definition and Explanation

10.3 TD(0) — The Basic Temporal Difference Algorithm for Policy Evaluation

10.3.1 Algorithm Overview

10.3.2 Algorithm Steps

10.3.3 Worked Numerical Example

10.4 Introduction to Control — Moving from V to Q

10.4.1 From Prediction to Control

10.5 SARSA — On-Policy TD Control

10.5.1 Definition and Explanation

10.5.2 The Update Expression

10.5.3 Why SARSA Is On-Policy

10.5.4 Why SARSA Is a Control Algorithm

10.5.5 Worked Numerical Example — SARSA on a Simple Grid

10.5.6 Student Questions and Answers

10.6 Q-Learning — Off-Policy TD Control

10.6.1 Definition and Explanation

10.6.2 Why Q-Learning Is Off-Policy

10.6.3 Worked Numerical Example — Q-Learning on the Same Grid

10.6.4 Aggressive Updates — The Max Effect

10.6.5 The Overestimation Problem

10.7 Expected SARSA — The Middle Ground

10.7.1 Definition and Explanation

10.7.2 Why Expected SARSA Is More Stable

10.7.3 Summary — The Three Targets Compared

10.8 SARSA vs Q-Learning — When to Use Which

10.8.1 Exploration Sensitivity

10.8.2 Use Cases and Comparative Summary

10.8.3 Worked Comparison — Same Episode, Different Targets

10.9 TD(λ) — The Credit Assignment Spectrum

10.9.1 The Credit Assignment Problem

10.9.2 The Executive Analogy (Professor's)

10.10 n-Step TD Prediction — Beyond One Step

10.10.1 Definition

10.10.2 Comparison of Targets

10.11 On-Policy vs Off-Policy — A Deeper Discussion

10.11.1 Behavior Policy and Target Policy

10.11.2 Algorithm Walkthrough (High-Level)

10.11.3 Terminology Note

10.12 Understanding V, Q, and G — What to Update When

10.12.1 The Three Value Objects — Definitions and Distinctions

10.13 Industry Applications and Research Directions

10.13.1 Real-World Uses

10.13.2 Current Research

10.13.3 Research Directions

10.14 Key Takeaways

10.14.1 The Core Algorithms

10.14.2 The Control Algorithms

10.14.3 Extensions and Key Concepts

Exam Guidance Summary

Key Industry Applications

DRL Lecture 10 notes · Temporal Difference Learning: TD(0), SARSA, and Q-Learning

Sections Breakdown

Exam Revision Notes

TD Learning — the three targets

The TD Error

TD(0) for policy evaluation

From V to Q — why control needs Q

SARSA — on-policy TD control

Q-Learning — off-policy TD control

Expected SARSA — the middle ground

SARSA vs Q-Learning — when to use which

TD(lambda) — the credit assignment spectrum

n-Step TD Prediction

On-Policy vs Off-Policy

V, Q, and G — what to update when

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

10.9 TD( $λ$ ) — The Credit Assignment Spectrum

10.10 $n$ -Step TD Prediction — Beyond One Step