Temporal Difference Learning, Maximization Bias, and Function Approximation

11.1 Revision of Temporal Difference Learning

Symbol registry — TD Learning

• $V(s)$ — state value function — scalar, expected return from state $s$
• $Q(s,a)$ — action value function — scalar, expected return from state $s$ taking action $a$
• $\alpha$ — learning rate / step size — scalar in $(0,1]$
• $\gamma$ — discount factor — scalar in $[0,1]$
• $R_t$ — reward at time $t$ — scalar
• $S_t$ — state at time $t$
• $A_t$ — action at time $t$
• $G_{t:t+n}$ — $n$-step return from time $t$ — scalar
• $ϵ$ — exploration rate in $ϵ$-greedy — scalar in $[0,1]$
• ${\delta }_t$ — TD error at time $t$ — scalar, ${\delta }_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$

11.1.1 The TD Learning Framework

Visual intuition: Imagine a graph tracking your drive-home estimates over time. The x-axis is time (6:00 to 6:43). The y-axis is predicted total travel time (30 to 43 minutes). Your estimates start at 30, jump to 40 at 6:05, dip to 35 at 6:20, climb back to 40 at 6:30, then to 43 at 6:40. TD updates (with $\alpha =1$) are proportional to the vertical gaps between consecutive estimates — the temporal differences. If a prediction changes by $+10$ minutes, TD says the earlier state should also shift up. The takeaway: TD chases its own changing predictions, learning from how predictions evolve through time.

Real-world connection: TD learning is behind many practical systems. In finance, TD methods price options by learning value functions from market data without modeling the full stochastic process. In robotics, TD enables robots to learn walking gaits from trial and error — each step gives a reward signal, and the robot updates its value estimates online rather than waiting until it falls over. The DQN agent that learned to play Atari games at superhuman level (Mnih et al., 2015) uses Q-learning, the control variant of TD, as its core learning rule.

11.1.2 Multi-Step Targets (n-Step TD)

The target does not have to be one-step. You can use a two-step target, a three-step target, or any $n$-step target. The general $n$-step return is:

$$G_{t:t+n}=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^{n}V(S_{t+n})$$

For a two-step target ($n=2$):

$$G_{t:t+2}=R_{t+1}+\gamma R_{t+2}+{\gamma }^{2}V(S_{t+2})$$

For a three-step target ($n=3$):

$$G_{t:t+3}=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+{\gamma }^{3}V(S_{t+3})$$

The $n$-step return spans the spectrum between one-step TD ($n=1$, high bias, low variance — relies heavily on the bootstrap estimate) and Monte Carlo ($n=$ episode length, zero bias, high variance — no bootstrap, waits for actual return). The lecture calls this the "depth and breadth" trade-off. Shorter $n$ means the target is mostly estimated value (biased but stable). Longer $n$ means the target is mostly actual rewards (unbiased but noisy).

The textbook (Sutton & Barto §7.1) proves the error reduction property: the worst-case error of the expected $n$-step return is at most ${\gamma }^n$ times the worst-case error in $V$:

$$\underset{s}{\max }\left|{\mathbb{E}}_{\pi }[G_{t:t+n}\mid S_t=s]-v_{\pi }(s)\right|\le {\gamma }^n\underset{s}{\max }\left|V(s)-v_{\pi }(s)\right|$$

This guarantees that $n$-step returns are always better targets in expectation than the raw bootstrap — the improvement factor ${\gamma }^n$ shrinks as $n$ grows (when $\gamma <1$).

11.1.3 SARSA — On-Policy TD Control

SARSA stands for State-Action-Reward-State-Action. It is an on-policy algorithm: it learns the value of the policy it is currently following. The name describes the transition quintuple: you are in a state $S$, you take an action $A$, you receive a reward $R$, you land in a next state $S^{\prime }$, and you choose a next action $A^{\prime }$.

The update is:

$$Q(S,A)\leftarrow Q(S,A)+\alpha \left[R+\gamma Q(S^{\prime },A^{\prime })-Q(S,A)\right]$$

The target uses $Q(S^{\prime },A^{\prime })$ — the value of the action actually taken next according to the current policy (typically $ϵ$-greedy). This is what makes it on-policy: the update uses the action the policy actually selects. SARSA learns $q_{\pi }$ for the behavior policy $\pi$, and as $\pi$ becomes greedier, SARSA converges to the optimal policy, provided all state-action pairs are visited infinitely often (e.g., with $ϵ=1/t$ decay).

11.1.4 Q-Learning — Off-Policy TD Control

Q-learning is an off-policy algorithm. The update uses the maximum action value from the next state — not the action the policy would actually take:

$$Q(S,A)\leftarrow Q(S,A)+\alpha \left[R_{t+1}+\gamma \underset{a}{\max }Q(S^{\prime },a)-Q(S,A)\right]$$

The target uses ${\max }_{a}Q(S^{\prime },a)$ — the best possible value from $S^{\prime }$, regardless of what action is actually taken next. The behavior policy (which selects actions in the environment) can be $ϵ$-greedy for exploration, but the update always assumes greedy continuation. The policy being learned (greedy with respect to $Q$) differs from the policy being followed ($ϵ$-greedy) — so it is off-policy.

Q-learning directly approximates the optimal action-value function $q_{\ast }$, independent of the policy being followed. This makes it simpler to analyze — the early convergence proofs for TD control were for Q-learning. The requirement: all state-action pairs must continue to be updated (achieved through exploration).

Real-world: Q-learning and its deep variant (DQN) are the foundation of many practical RL systems — from game-playing AI (Atari, Go) to robotic control. DQN used Q-learning with a convolutional neural network to achieve human-level performance on 49 Atari games from raw pixels (Mnih et al., 2015, Nature).

11.2 Maximization Bias

Symbol registry — Maximization Bias MDP

• $Q(A,\text{right})$ — value of taking right from A — scalar, always 0
• $Q(A,\text{left})$ — value of taking left from A — scalar, overestimated under Q-learning
• $Q(B,a)$ — value of action $a$ from B — scalar, drawn from distribution with mean $-0.1$
• ${\max }_{a}Q(S^{\prime },a)$ — maximum over action values from next state — scalar, the source of bias
• ${\mathrm{argmax}}_{a}Q(s,a)$ — the action that maximizes Q — used for selection in Double Q-learning
• $N(\mu ,{\sigma }^2)$ — normal distribution with mean $\mu$ and variance ${\sigma }^2$

11.2.1 The Problem

11.2.2 Textbook Example: The Small MDP

The classic illustration comes from Sutton & Barto (§6.7, Example 6.7). You always start in state A. From A you have two actions:

• Right: You get a reward of 0 and reach a terminal state. So $Q(A,\text{right})=0$ always — it is deterministic.
• Left: You get a reward of 0 and move to state B.

From state B, there are many actions available — all leading to a terminal state. The reward for each action from B is drawn from a normal distribution with true mean $-0.1$ and standard deviation $1$. So the long-term average reward for taking left is $-0.1$. But individual samples vary: sometimes you get 0, sometimes 1, sometimes even a larger positive number (with small probability).

Under Q-learning, when you take left from A you receive 0 and land in B. The target for $Q(A,\text{left})$ is:

$$0+\gamma \underset{a}{\max }Q(B,a)$$

Now suppose one of the actions from B happened to give a reward of $+3$ at some point in the past. Q-learning stores that as $Q(B,\text{that action})=3$. The max over all actions from B then becomes $3$ (or higher if any other action gave more). So:

$$Q(A,\text{left})\leftarrow Q(A,\text{left})+\alpha \left[0+\gamma \cdot 3-Q(A,\text{left})\right]$$

This pushes $Q(A,\text{left})$ to a positive value. At a later time, some other action from B might give $+10$. Now the max becomes $10$, and $Q(A,\text{left})$ gets pushed even higher.

The result: $Q(A,\text{left})$ stays consistently positive — always greater than $Q(A,\text{right})=0$. Even with $ϵ$-greedy action selection (which picks the greedy action ~90% of the time), the agent will almost always choose left. And every time it does, it actually receives rewards drawn from a distribution with mean $-0.1$ — accumulating negative returns while believing left is good. The agent keeps going left, keeps getting negative rewards, and the overestimation persists.

Visual intuition: The textbook (Sutton & Barto Figure 6.5) shows a plot with episodes on the x-axis and "% left actions from A" on the y-axis. Standard Q-learning shoots to nearly 100% left actions within ~50 episodes and stays there — the agent is trapped choosing the worse action. Double Q-learning hovers near the optimal 5% (the $ϵ$-greedy minimum). The gap between the two curves is the cost of maximization bias: Q-learning wastes exploration on a provably bad action because its value estimates are inflated by noise.

Real-world connection: Maximization bias is not just a toy problem — it affects real deep RL systems. The original DQN algorithm (which plays Atari games from pixels) was found to overestimate Q-values substantially, sometimes by 50% or more above true values. This led to the development of Double DQN (van Hasselt et al., 2016), which applies the Double Q-learning idea to deep networks and consistently improves performance across dozens of Atari games. The bias is particularly dangerous in healthcare applications of RL, where overestimating a treatment's value could lead to recommending harmful interventions.

11.2.3 Consequences

With maximization bias, Q-learning can take a very long time — many episodes — to realize that left is actually worse than right. The algorithm essentially needs enough exploratory samples of all B-actions for their Q-values to converge to the true mean of $-0.1$, at which point the max would also approach $-0.1$. Until then, the bias dominates. In complex environments with many actions per state, this problem compounds: the more actions, the larger the expected overestimation, and the longer it takes for all action values to converge.

11.3 Double Q-Learning

Symbol registry — Double Q-Learning

• $Q_1(s,a)$ — first action-value function — scalar
• $Q_2(s,a)$ — second action-value function — scalar
• $\arg {\max }_{a}Q(s,a)$ — the action that maximizes Q — used for selection (one function)
• $Q_{\text{other}}(s^{\prime },\arg {\max }_a{Q}_{\text{this}}(s^{\prime },a))$ — evaluation of the selected action by the other function — scalar

11.3.1 The Key Insight

11.3.2 The Double Q-Learning Update

You maintain two action-value functions, $Q_1$ and $Q_2$. At each update step, you flip a fair coin (probability 0.5):

With probability 0.5 — $Q_1$ selects, $Q_2$ evaluates:

$$Q_1(S,A)\leftarrow Q_1(S,A)+\alpha \left[R+\gamma Q_2\left(S^{\prime },\arg \underset{a}{\max }{Q}_1(S^{\prime },a)\right)-Q_1(S,A)\right]$$

With probability 0.5 — the roles reverse, $Q_2$ selects, $Q_1$ evaluates:

$$Q_2(S,A)\leftarrow Q_2(S,A)+\alpha \left[R+\gamma Q_1\left(S^{\prime },\arg \underset{a}{\max }{Q}_2(S^{\prime },a)\right)-Q_2(S,A)\right]$$

The action selection policy (for actually acting in the environment) uses the sum $Q_1+Q_2$ with $ϵ$-greedy. This is the same form as the textbook algorithm (Sutton & Barto §6.7, page 136).

11.3.3 Algorithm Summary

1. Initialize $Q_1$ and $Q_2$ arbitrarily (e.g., all zeros or small random values). 2. Initialize step size $\alpha$ (small) and exploration rate $ϵ$ (small). 3. Start in initial state $S$. 4. Choose action $A$ from $S$ using policy derived from $Q_1+Q_2$ (e.g., $ϵ$-greedy on the sum). 5. Execute $A$, observe reward $R$ and next state $S^{\prime }$. 6. With probability 0.5: update $Q_1$ using $Q_2$ as the evaluator. 7. With probability 0.5: update $Q_2$ using $Q_1$ as the evaluator. 8. $S\leftarrow S^{\prime }$; repeat from step 4.

At each step, only one of the two Q-functions is updated — not both. The other one serves as the unbiased evaluator for that step. This doubles the memory (two tables instead of one) but does not increase computation per step.

11.3.4 Why Double Q-Learning Works

In the small MDP example from §11.2, Double Q-learning learns much faster that left is not good. The textbook results (Sutton & Barto, Figure 6.5) show standard Q-learning taking left ~95% of the time even after hundreds of episodes, while Double Q-learning drops to near the optimal 5% (the $ϵ$-greedy minimum).

The reason: even if $Q_1$ has an overestimated value for some action at B (because it saw a lucky $+3$ reward), $Q_2$ is unlikely to have the same overestimation for the same action — they have seen different update histories. When $Q_1$ selects the action it thinks is best, $Q_2$ evaluates it more honestly. The roles swap, so both functions get regularized by the other.

In theory, 10 consecutive coin flips could all update $Q_1$ and never $Q_2$, letting $Q_1$'s bias grow. In practice, this is improbable and does not cause issues over many steps. The two functions track similar values but with decorrelated noise — enough to break the selection-evaluation coupling that creates maximization bias.

Visual intuition: Picture two thermometers measuring the same room. Thermometer A reads slightly high, B slightly low — each has its own noise pattern. If you always take the maximum reading, you will get a biased (too hot) estimate. But if A picks the spot to measure and B takes the actual reading there, the reading is honest. In the textbook plot (Figure 6.5), this translates to a dramatic gap: Q-learning (red line) stays at ~95% left actions; Double Q-learning drops rapidly to ~5%.

11.3.5 Practical Recommendations

In practice, when solving an RL problem, Double Q-learning and Expected SARSA are both good options for avoiding maximization bias. Expected SARSA requires a bit more computation — you need to compute an expectation over all actions from the next state rather than just a max — but it avoids maximization bias in a different way. Double Q-learning maintains the simplicity of the max operator while controlling the bias through the two-function split.

Comparison — Q-learning vs Double Q-learning vs Expected SARSA:

All three have the same per-step cost (finding the max requires scanning all actions anyway), but Expected SARSA additionally computes a weighted average. Double Q-learning's main overhead is storing two Q-tables (or two networks in the deep case).

11.3.6 Student Q&A

Real-world connection: Double DQN (van Hasselt et al., 2016, AAAI) applies the Double Q-learning idea to deep neural networks, using the online network for action selection and the target network for evaluation. It is now a standard component of deep RL systems. In the Atari benchmark, Double DQN reduces overestimation by 30–50% and improves final performance on most games. The technique also applies to actor-critic methods and policy gradient algorithms — any method that uses a max or argmax over value estimates can benefit from the double estimator trick.

11.4 From Tabular Methods to Function Approximation

Symbol registry — Function Approximation

• $\hat{V}(s;\mathbf{w})$ — approximate state-value function with parameters $\mathbf{w}$ — scalar
• $\hat{Q}(s,a;\mathbf{w})$ — approximate action-value function — scalar
• $\mathbf{w}$ — weight vector / parameters of the approximator — vector in ${\mathbb{R}}^d$
• $f_i(s)$ — $i$-th feature of state $s$ — scalar
• $d$ — number of features / parameters — integer
• $|S|$ — number of states — integer, can be huge or infinite

11.4.1 The Tabular Method

So far, all methods discussed — TD learning, SARSA, Q-learning, Double Q-learning — have been tabular methods. A tabular method stores a table of values:

• For state-value functions: a table with entries $V(s_1),V(s_2),V(s_3),\dots$
• For action-value functions: a table with entries $Q(s,a_1),Q(s,a_2),\dots$ for each state

When you update, you change exactly one entry in the table without affecting any other entry. For example, $V(s)\leftarrow V(s)+\alpha [\dots ]$ touches only row $s$. This independence means that, given enough experience in each cell, you can drive the table to a global optimum — each entry can move independently toward its true value. Convergence guarantees exist for all tabular methods under standard conditions.

11.4.2 Why Function Approximation?

11.4.3 Types of Approximating Functions

The function can be simple or complex:

• Linear function: $\hat{V}(s,\mathbf{w})={\sum }_{i=1}^d{w}_i\cdot f_i(s)$, where $f_i(s)$ are features of the state — numbers computed from the state description. The parameters are just $d$ weights $w_1,\dots ,w_d$. Each weight says "how much does feature $i$ contribute to value?"

• Nonlinear function (neural network): A deep network takes the state representation (e.g., raw pixels) and outputs an estimated value. The network may have millions or billions of weights. It learns its own internal features through hidden layers — no manual feature design required.

In many real-world problems, the number of parameters is far less than the number of possible states. You are approximating the values of billions of possible states with (say) thousands of parameters. Approximation is inevitable — you cannot represent a billion values exactly with a thousand parameters. The hope is that states that are similar (in feature space) have similar values, so the function can generalize.

11.4.4 The Core Challenge

Your learning objective: keep updating the parameters $\mathbf{w}$ until the function returns values that are close to the true (or optimal) values for all states — weighted by how often each state occurs.

11.4.5 The Pac-Man Example

Consider the Pac-Man game. A state can be described by features like:

• Distance to ghost 1
• Distance to ghost 2
• Distance to nearest food
• Pac-Man's location

State 1 (ghost at distance 2, food at distance 5) should have a lower value than State 2 (ghost at distance 10, food at distance 3), because the ghost proximity is more important than food proximity for survival. After seeing many such labeled examples — this state has this value, that state has that value — the function should generalize: given a new state never seen before (e.g., two ghosts at specific distances), it should estimate a reasonable value based on the pattern learned from similar states.

The representation could also be raw pixels — the entire 160×210 game screen fed to a neural network, which extracts features automatically. DQN (Mnih et al., 2015) used exactly this approach: a convolutional neural network that takes 84×84×4 pixel input (four grayscale frames) and outputs Q-values for each possible joystick action.

11.4.6 Student Q&A on Learning from Scratch

Real-world connection: Function approximation is what makes RL practical. Without it, self-driving cars would need a separate table entry for every possible road configuration — impossible. Deep RL systems (AlphaGo, OpenAI Five, autonomous vehicle control) all rely on neural network function approximators. AlphaGo's value network had millions of parameters but evaluated board positions far better than any tabular approach could — because it generalized patterns (ladders, life-and-death shapes) across board positions that were not identical but structurally similar.

11.5 The Objective Function: Mean Squared Value Error

Symbol registry — Objective Function

• $\overline{\text{VE}}(\mathbf{w})$ — Mean Squared Value Error — scalar, the objective to minimize
• $\mu (s)$ — state importance / visitation weight for state $s$ — scalar in $[0,1]$, ${\sum }_s\mu (s)=1$
• $V_{\pi }(s)$ — true value of state $s$ under policy $\pi$ — scalar
• $\mathcal{S}$ — state space — set of all states
• $\eta (s)$ — expected number of visits to state $s$ per episode — scalar (from Sutton & Barto §9.2)

11.5.1 Defining the Error

11.5.2 State Importance Weighting $\mu (s)$

Not all states are equally important. Some states occur very frequently (e.g., the starting region of a game), others almost never. The term $\mu (s)$ captures this: it is the fraction of time spent in state $s$ under the policy — a probability distribution over states, with ${\sum }_s\mu (s)=1$.

States with high $\mu (s)$ are frequent — you cannot afford large errors there, because you visit them often. States with low $\mu (s)$ are rare — errors there matter less. The $\mu (s)$ weighting prevents the optimization from wasting capacity on rarely-visited states at the expense of common ones.

From Sutton & Barto (§9.2): "In continuing tasks, the on-policy distribution is the stationary distribution under $\pi$. In episodic tasks, let $h(s)$ be the probability an episode begins in $s$, and $\eta (s)$ the expected number of time steps spent in $s$ per episode. Then:

$$\eta (s)=h(s)+\sum _{\bar{s}}\eta (\bar{s})\sum _a\pi (a|\bar{s})p(s|\bar{s},a)$$

and $\mu (s)=\frac{\eta (s)}{{\sum }_{s^{\prime }}\eta (s^{\prime })}$."

In supervised learning terms, this is like weighting each training example by how often it appears. States you visit 100 times per episode get 100× the weight of states you visit once.

11.5.3 Practical Considerations

Visual intuition: Imagine a 2D plot with states sorted on the x-axis and value on the y-axis. The true value function $V_{\pi }(s)$ is some smooth curve. Your approximator $\hat{V}(s;\mathbf{w})$ is a simpler curve (maybe a straight line for linear, or a wiggly curve for a network). $\overline{\text{VE}}$ measures the area between these two curves, weighted by $\mu (s)$ — regions the agent visits often contribute more to the area. The goal of gradient descent is to adjust the parameters so the approximator curve hugs the true curve tightly in the high-$\mu (s)$ regions.

Real-world connection: The weighted least-squares formulation appears throughout engineering. In control theory, the Linear Quadratic Regulator (LQR) minimizes a weighted sum of state errors and control effort — exactly the same mathematical structure as $\overline{\text{VE}}$. In recommendation systems, collaborative filtering minimizes a weighted squared error between predicted and actual ratings, with weights for user frequency. The $\overline{\text{VE}}$ formulation connects RL to decades of work in optimization and statistical estimation.

11.6 Gradient Descent for Value Function Approximation

Symbol registry — Gradient Descent

• ${\nabla }_{\mathbf{w}}\hat{V}(S_t;\mathbf{w})$ — gradient of the value estimate with respect to parameters — vector in ${\mathbb{R}}^d$
• $G_t$ — return (sum of discounted rewards) from time $t$ — scalar
• $T$ — terminal time step of an episode — integer
• $U_t$ — generic update target at time $t$ — scalar (from Sutton & Barto §9.3)
• For linear function $\hat{V}(s,\mathbf{w})={\sum }_i{w}_i{f}_i(s)$: ${\nabla }_{\mathbf{w}}\hat{V}=\mathbf{f}(s)$ — the feature vector itself

11.6.1 The General Update Form

11.6.2 Monte Carlo Target: $G_t$

If you generate a full episode — states $S_0,S_1,\dots ,S_{T-1}$ with rewards — you can compute the actual return $G_t$ for each state:

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots +{\gamma }^{T-t-1}{R}_T$$

$G_t$ is an unbiased estimate of $v_{\pi }(S_t)$. Using $U_t=G_t$ in the SGD update yields Gradient Monte Carlo — a true gradient method that converges to a local minimum of $\overline{\text{VE}}$ under standard SGD conditions.

With a linear function approximator $\hat{V}(s,\mathbf{w})={\sum }_i{w}_i{f}_i(s)$, the gradient ${\nabla }_{\mathbf{w}}\hat{V}(s,\mathbf{w})$ is simply the feature vector $\mathbf{f}(s)$ itself. The update for each weight $w_i$ becomes:

$$w_i\leftarrow w_i+\alpha \left[G_t-\hat{V}(S_t;\mathbf{w})\right]\cdot f_i(S_t)$$

11.6.3 Worked Example: Gradient Monte Carlo

11.6.4 The Semi-Gradient Problem

11.6.5 Worked Example: Semi-Gradient TD(0)

11.6.6 RL vs. Supervised Learning

In supervised learning, examples are assumed to be independent and identically distributed (IID). For classifying cat vs. rat vs. bat, each image-label pair is independent — the first example being a bat does not constrain what the second example must be.

In reinforcement learning, this assumption does not hold. Consecutive states in an episode are strongly dependent — each step's state depends on the previous action and state. The examples come from the agent's own trajectory, which depends on the policy being followed. The same state can have different true values depending on the policy. And you do not know the true value until the episode completes (or ever, in continuing tasks).

Real-world connection: Semi-gradient methods are the backbone of practical RL. The DQN algorithm uses semi-gradient Q-learning with a neural network: the target $r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime };{\theta }^{-})$ uses a target network ${\theta }^{-}$ (frozen copy of $\theta$) precisely to stabilize the semi-gradient — the target network reduces the coupling between the target and the current parameters. This combination of semi-gradient updates with target networks enabled DQN to achieve human-level Atari performance.

11.7 N-Step Semi-Gradient Methods

Symbol registry — N-Step Semi-Gradient

• $G_{t:t+n}$ — $n$-step return from time $t$ — scalar
• $x(s)$ — simplified scalar feature for the worked example (each state represented as 1)
• $w$ — scalar weight for the simplified example — scalar

11.7.1 Extending to Multiple Steps

Just as tabular TD can use $n$-step returns, function approximation methods can too. The general $n$-step semi-gradient update is:

$${\mathbf{w}}_{\text{new}}={\mathbf{w}}_{\text{old}}+\alpha \left[G_{t:t+n}-\hat{V}(S_t;\mathbf{w})\right]{\nabla }_{\mathbf{w}}\hat{V}(S_t;\mathbf{w})$$

where $G_{t:t+n}$ is the $n$-step return as defined in §11.1.2. For $n=1$ this reduces to the semi-gradient TD(0) update from §11.6.4. For $n$ equal to the episode length, it approximates Gradient Monte Carlo (the target still bootstraps slightly through $\hat{V}$ at the horizon unless the episode ends exactly at the horizon).

The textbook (Sutton & Barto §7.1) proves the error reduction property: the expected $n$-step return is always a better estimate than the current $V$ by a factor of at least ${\gamma }^n$ in worst-case error.

11.7.2 Worked Example: 3-Step Semi-Gradient with Simple Features

To make the computation tractable, this example uses the exact setup from the lecture slides (S P Vimal). Every state is represented by a single constant feature $x(s)=1$. The function approximator has a single weight $w$, so $\hat{V}(s;w)=w\cdot 1=w$ and ${\nabla }_{\mathbf{w}}\hat{V}(s;w)=1$.

Parameters: $T=10$ (episode length), $n=3$ (3-step window), discount factor $\gamma =0.9$, step size $\alpha =0.1$, initial weight $w_0=2.0$.

Trajectory & Rewards:

$$S_0\stackrel{R_1=1}{\to }{S}_1\stackrel{R_2=2}{\to }{S}_2\stackrel{R_3=0}{\to }{S}_3\stackrel{R_4=3}{\to }{S}_4\stackrel{R_5=1}{\to }{S}_5\stackrel{R_6=2}{\to }{S}_6\stackrel{R_7=0}{\to }{S}_7\stackrel{R_8=1}{\to }{S}_8\stackrel{R_9=4}{\to }{S}_9\stackrel{R_{10}=2}{\to }{S}_{10}(\text{terminal})$$

The update rule at step $t$ updates state $S_{\tau }$ where $\tau =t-n+1$:

$$G_{\tau :\tau +3}=R_{\tau +1}+\gamma R_{\tau +2}+{\gamma }^2{R}_{\tau +3}+{\mathbb{I}}_{\{\tau +3<T\}}{\gamma }^3\hat{V}(S_{\tau +3};w),\delta =G_{\tau :\tau +3}-w_{\text{old}},w_{\text{new}}=w_{\text{old}}+0.1\times \delta$$

11.7.3 Handling the End of an Episode (Terminal Truncation)

When doing $n$-step updates near the end of an episode, the lookahead window reaches or exceeds the terminal time step $T$ (here $T=10$). For $\tau =7,8,9$, because $\tau +3\ge T$, the indicator ${\mathbb{I}}_{\{\tau +3<T\}}=0$. There is no bootstrap term; the return is truncated to sum only the remaining actual rewards before termination.

11.7.4 Summary Tables: Complete 10-Step Episode Update Trace

The tables below consolidate the complete trajectory trace across all 10 updates for $\tau =0,\dots ,9$:

Summary Table: First Five Updates ($\tau =0$ to $4$)

Summary Table: Remaining Updates ($\tau =5$ to $9$)

11.7.5 Teaching Insights & Key Observations

• Full Window vs. Truncated Target: Until $\tau =6$, the target incorporates three rewards plus a discounted bootstrap estimate ${\gamma }^3\hat{V}(S_{\tau +3};w)$. For $\tau =7,8,9$, the target is truncated because the episode terminates at $T=10$.
• Weight Flow & Gradient Simplicity: Because $x(s)=1$, the gradient is identically 1. Each update directly increments $w$ by $\alpha \times \text{error}$. The updated weight immediately influences the bootstrap value in subsequent updates.
• Generalization to Higher Dimensions: In higher-dimensional linear function approximation, ${\nabla }_{\mathbf{w}}\hat{V}(S_{\tau };\mathbf{w})$ is replaced by the full state feature vector $\mathbf{x}(S_{\tau })$, so the error scales each feature independently.