Deep Reinforcement Learning

Feature Construction and Deep Q-Networks (DQN)

Published: 2026-07-26

Level: postgraduate

Audience: Postgraduate students in Deep Reinforcement Learning

Feature Construction and Deep Q-Networks (DQN)

12.1 Revision of Function Approximation and Semi-Gradient TD Methods

Hook: In tabular RL, each state has its own independently-learned value. But what happens when there are millions of states — or the state space is continuous? We need a function that generalizes from visited states to unvisited ones. That function is the heart of function approximation.

The agenda for this lecture covers three main topics: (1) a quick revision of function approximation methods, (2) feature construction for function approximation, and (3) the Deep Q-Network (DQN) algorithm — the first major breakthrough in deep reinforcement learning.

12.1.1 Tabular Representation vs. Parameterized Function Approximation

In the methods learned before function approximation — called tabular methods — the core idea is straightforward: we maintain a table where each row corresponds to a state (for state-value functions) or a state-action pair (for action-value functions), and the corresponding entry stores the estimated value. For instance, state $S_{1}$ has value 71, state $S_{2}$ has value 70, state $S_{3}$ has value $- 10$ , and so on. If we are working with state-action pairs, the table can be thought of as a matrix: rows $S_{1} A, S_{1} B, S_{1} C, S_{2} A, S_{2} B, S_{2} C$ , and so forth.

The critical property of tabular methods is that each entry can be learned independently. We can make the value of one particular state-action pair perfect while another row — one that has never been visited — remains untouched. This independence is both a strength and a limitation.

The limitation becomes apparent when the state space is large or continuous. Consider a scenario where states $S_{1}$ , $S_{2}$ , and $S_{4}$ are frequently visited, but state $S_{3}$ — which sits in their vicinity — has never been encountered. Because tabular methods require direct visits to update a value, $S_{3}$ would have no good estimate despite being surrounded by well-estimated states. This is where function approximation becomes essential: if nearby states have informative values, we should be able to estimate $S_{3}$ 's value from them.

Intuition: Think of a tabular method as a filing cabinet — each state gets its own folder. If you never visit a state, that folder stays empty. Function approximation is like having a formula that predicts any state's value based on what you've learned about similar states. A linear function

v^(s, w) = w^{⊤} x (s)

says: "the value of a state is a weighted combination of its features." Adjust the weights based on visited states, and the formula automatically predicts values for unvisited ones.

In function approximation, we replace the table with a parameterized function. Instead of storing a value for every state or state-action pair, we learn a function $v^(s, w)$ (for state values) or $q^(s, a, w)$ (for action values), where $w$ is the parameter vector (the weights we tune during learning). The input is the state (or state-action pair), and the output is the estimated value. The task shifts from filling a table to learning the parameters $w$ such that the function's estimates are close to optimal for all states or state-action pairs.

12.1.2 Symbol Registry — Function Approximation

Symbol	Meaning	LaTeX	Type
$s$	State	$s$	scalar or vector
$a$	Action	$a$	scalar
$w$	Parameter vector of the approximating function	$w$	vector in $R^{d}$
$v^(s, w)$	Approximate state-value function	$v^(s, w)$	scalar
$q^(s, a, w)$	Approximate action-value function	$q^(s, a, w)$	scalar
$x$ or $x_{i}$	Feature(s) representing the state	$x, x_{i}$	scalar or vector
$α$	Learning rate (step size)	$α$	scalar, $α > 0$
$γ$	Discount factor	$γ$	scalar, $γ \in [0, 1]$
$G$	Target return (Monte Carlo or n-step)	$G$	scalar
$\nabla_{w}$	Gradient with respect to $w$	$\nabla_{w}$	vector of partial derivatives

12.1.3 Limitations of Tabular Methods and Motivation for Function Approximation

With a nonlinear function representation, finding parameters that produce optimal values for all state-action pairs is a near-impossible task. The reasons are grounded in what we know from machine learning and deep learning:

Three fundamental challenges:

Continuous or enormous state spaces: Not all states can be visited. The state space may be continuous (e.g., a robot's joint angles), making exhaustive enumeration impossible. Even discrete spaces like Atari game screens have $25 6^{100800}$ possible states — visiting them all is infeasible.
The moving-parameter problem: When we adjust the parameter vector $w$ to improve the estimate for one particular state-action pair, the same parameter $w$ governs the values of all state-action pairs. Fixing one may break others. In the professor's words: "When you actually move $w$ to fix this combination, I would actually go wrong somewhere else." This is the core tension of function approximation in RL — unlike supervised learning where each training example is independent.
Global optimum is not the goal: With our background in machine learning, we know that global optimum is not what we are chasing. We want a useful approximation — one with which we can act effectively in the environment. A policy derived from a "good enough" value function can still be excellent.

The function can be as complex as a deep neural network (input: state representation, output: value) or as simple as a linear function $\sum_{i} w_{i} x_{i}$ . In either case, the job is to learn the parameters using gradient descent, and specifically stochastic gradient descent (SGD), where we estimate the loss for each individual example rather than summing over all examples.

12.1.4 Gradient Monte Carlo vs. Semi-Gradient TD(0) Update Rules

Gradient Monte Carlo Algorithm:

This algorithm evaluates a given policy $π$ using a differentiable function $v^(s, w)$ to approximate $v_{π}$ . A function is differentiable if it can be differentiated with respect to its parameters — this is what makes gradient-based learning possible. For a linear function $v^= w_{1} x_{1} + w_{0}$ , the derivatives are $\frac{\partial v ^}{\partial w _{1}} = x_{1}$ and $\frac{\partial v ^}{\partial w _{0}} = 1$ .

The algorithm proceeds as follows:

Initialize parameters $w$ .
Repeat forever (for each episode):
- Generate a complete episode: $S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, \dots, S_{T}$ .
- For each state $S_{t}$ in the episode:
  - Compute the target $G_{t} = \sum_{k = t + 1}^{T} γ^{k - t - 1} R_{k}$ (the discounted sum of all rewards from step $t$ to the end).
  - Update: $w \leftarrow w + α [G_{t} - v^(S_{t}, w)] \nabla_{w} v^(S_{t}, w)$

The error term is $G_{t} - v^(S_{t}, w)$ : the target (sum of discounted rewards) minus the current network's prediction. The gradient $\nabla_{w} v^(S_{t}, w)$ tells us which direction to move $w$ to increase $v^$ . Multiplying by the error and stepping in that direction reduces the prediction error. This is standard stochastic gradient descent — nothing unusual.

Quick check — linear gradient: For

v^(s, w) = w_{1} x + w_{0}

with

x = 5

$\nabla_{w} v^= (\frac{\partial v ^}{\partial w _{0}}, \frac{\partial v ^}{\partial w _{1}}) = (1, 5)$
If $G_{t} = 10$ and $v^= 4.7$ , the error is $10 - 4.7 = 5.3$
Update: $w_{1} \leftarrow w_{1} + α \times 5.3 \times 5 = w_{1} + 26.5 α$
The larger the error, the larger the step. The larger the feature value, the more that weight gets adjusted.

Transition to One-Step TD (Semi-Gradient TD(0)):

Monte Carlo methods require waiting until the end of an episode to compute $G_{t}$ . They are not online in the way that one-step TD, two-step TD, or three-step TD are. To convert the Monte Carlo algorithm into a one-step TD method, we replace the target $G_{t}$ with the one-step TD target — the immediate reward plus the discounted estimated value of the next state:

G_{t} = R_{t + 1} + γ v^(S_{t + 1}, w)

The update rule becomes:

w \leftarrow w + α [R_{t + 1} + γ v^(S_{t + 1}, w) - v^(S_{t}, w)] \nabla_{w} v^(S_{t}, w)

This is the semi-gradient TD(0) update. The term semi-gradient will be explained in Section 12.1.6.

12.1.5 Symbol Registry — Semi-Gradient TD Update

Symbol	Meaning	LaTeX	Type
$R_{t + 1}$	Immediate reward at time $t + 1$	$R_{t + 1}$	scalar
$S_{t}$	State at time $t$	$S_{t}$	state
$S_{t + 1}$	Next state at time $t + 1$	$S_{t + 1}$	state
$G_{t}$	Target (Monte Carlo return or n-step return)	$G_{t}$	scalar
$v^(S_{t}, w)$	Current estimate of state value	$v^(S_{t}, w)$	scalar
$v^(S_{t + 1}, w)$	Estimate of next state value (bootstrap)	$v^(S_{t + 1}, w)$	scalar

12.1.6 The Semi-Gradient Nature and Moving Target Problem

Analogy: Imagine you're adjusting a recipe while tasting it. In Monte Carlo, you wait until the dish is done, taste the final result, and adjust. In TD, you taste the dish halfway through cooking, compare it to your expectation of how it should taste at that point, and adjust. The problem: your expectation changes every time you adjust the recipe — you're chasing a moving target.

When we use the one-step TD target $R_{t + 1} + γ v^(S_{t + 1}, w)$ , a subtle but important issue arises: both the target and the estimate depend on the same parameter $w$ . This is bootstrapping — we are using our current estimate to form the target.

In true gradient descent, the target should represent a fixed, correct value. Think of supervised learning: the label is fixed (a cat is always a cat). In Monte Carlo, $G_{t}$ is the sum of discounted rewards — it does not depend on $w$ . It is a reasonably good target, independent of the current parameters.

But in TD methods, the target also depends on $w$ . Every time we update $w$ , the target shifts. This is the moving target problem: "If every example updates the parameter and uses the updated parameter to make a prediction and get the differences, that's a moving target."

Why it's called "semi-gradient":

Because the target depends on the same parameters we are updating, we are no longer performing true gradient descent. The gradient of the target with respect to $w$ is being ignored — we only differentiate the estimate term $v^(S_{t}, w)$ , not the bootstrap term $v^(S_{t + 1}, w)$ . We treat the bootstrap part as a fixed target, even though it is not.

In Sutton and Barto's words (Chapter 9): "Bootstrapping methods are not in fact instances of true gradient descent. They take into account the effect of changing the weight vector $w_{t}$ on the estimate, but ignore its effect on the target. They include only a part of the gradient and, accordingly, we call them semi-gradient methods."

Pitfall — Confusing semi-gradient with "wrong" gradient:

The semi-gradient approach is not a mistake — it is a deliberate simplification. It still produces usable results, even with large networks, despite the mathematical impurity. The professor shares his own experience: "That's sort of a confusion I actually got when I learned this course earlier. I'm just keeping my target to be bootstrapping, but my gradient becomes incomplete. Then I actually went closer and read the book, and that's when I actually understood that that's how it does."

For linear function approximation, semi-gradient TD(0) is proven to converge to the TD fixed point $w_{T D} = A^{- 1} b$ , where the value error is bounded by $\frac{1}{1 - γ}$ times the minimum possible error (Sutton & Barto, Eq. 9.14). This bound can be large when $γ$ is close to 1, but the method is still much faster than Monte Carlo in practice due to lower variance.

12.1.7 Student Questions and Answers

Q: In the semi-gradient TD target, should we use the approximated value or the actual next state value since the episode is already generated?

A: The professor clarifies that in online (one-step TD), we don't generate the whole episode first — we take a step, update parameters, take another step, update again. The bootstrap value $v^(S_{t + 1})$ uses the current parameters, not a pre-computed value from a completed episode. This is the key difference from Monte Carlo: TD learning happens during the episode, not after.

12.1.8 Multi-Step (n-Step) Semi-Gradient TD Methods and Tail-End Handling

Why n-step? One-step TD uses only one reward before bootstrapping — it's fast but heavily relies on the (possibly inaccurate) current estimate. Monte Carlo uses all rewards — it's accurate but slow (must wait for episode end). n-step methods are the sweet spot: use

n

rewards before bootstrapping, balancing speed and accuracy. Sutton & Barto (Chapter 7) show that intermediate values of

n

(e.g.,

n = 4

n = 8

) typically outperform both extremes.

The one-step TD target uses only one reward before bootstrapping. We can extend this to n-step targets, which use $n$ rewards before bootstrapping:

For a two-step target at state $S_{t}$ :

G_{t}^{(2)} = R_{t + 1} + γ R_{t + 2} + γ^{2} v^(S_{t + 2}, w)

For a three-step target:

G_{t}^{(3)} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + γ^{3} v^(S_{t + 3}, w)

The general n-step target:

G_{t}^{(n)} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{n - 1} R_{t + n} + γ^{n} v^(S_{t + n}, w)

where $n \geq 1$ and $0 \leq t < T - n$ . The first $n$ terms are observed rewards (discounted), and the last term is the bootstrap estimate $n$ steps into the future.

This matches Sutton & Barto (Eq. 7.1 / 9.16): $G_{t : t + n} = R_{t + 1} + γ R_{t + 2} + \dots + γ^{n - 1} R_{t + n} + γ^{n} v^(S_{t + n}, w_{t + n - 1})$ .

Tail-end handling: When we are near the end of an episode, there may not be

n

steps remaining. The rule is simple: take whatever rewards are available. If the terminal state is

S_{t + 3}

and we want a 2-step target from

S_{t + 2}

, there is only one step (

R_{t + 3}

), so the target is simply

R_{t + 3}

. The terminal state has value 0, so no bootstrap term appears.

More precisely (Sutton & Barto, Chapter 7): if $t + n \geq T$ , then $G_{t}^{(n)} = G_{t}$ — the full return. This is because all missing rewards are zero and the terminal state value is zero.

This tail-end handling is the part of the n-step algorithm that "people would actually look at and say, hey, that's getting very difficult." But it is not fundamentally difficult — it is just bookkeeping.

The algorithm uses a variable $τ$ (tau) to track which state to update: $τ = t - n + 1$ . When we reach time $t$ , we update the estimate for state $S_{τ}$ . This indexing ensures that each state gets updated once its n-step target is fully available. The update rule for n-step semi-gradient TD is:

w \leftarrow w + α [G_{t}^{(n)} - v^(S_{τ}, w)] \nabla_{w} v^(S_{τ}, w)

12.1.9 Symbol Registry — n-Step Semi-Gradient TD

Symbol	Meaning	LaTeX	Type
$n$	Number of steps before bootstrapping	$n$	positive integer
$G_{t}^{(n)}$	n-step target starting from time $t$	$G_{t}^{(n)}$	scalar
$R_{t + k}$	Reward at step $t + k$	$R_{t + k}$	scalar
$S_{t + n}$	State $n$ steps ahead	$S_{t + n}$	state
$τ$	Index of the state being updated ( $τ = t - n + 1$ )	$τ$	integer
$T$	Index of the terminal state	$T$	integer

Pitfall — Indexing confusion: The most common mistake in n-step TD is confusing

t

(the current time step) with

τ

(the state being updated). Remember: at time

t

, we update state

S_{τ}

where

τ = t - n + 1

. For a 2-step method, when

t = 2

, we update

S_{0}

. When

t = 3

, we update

S_{1}

. And so on.

Pitfall — Forgetting tail-end near termination: Don't try to bootstrap from beyond the terminal state. If the episode ends at $T$ , and you want a 2-step target from $S_{T - 1}$ , you only have one reward $R_{T}$ — the target is just $R_{T}$ with no bootstrap term.

12.1.10 Worked Computation: 2-Step Semi-Gradient TD Update on a Linear Function

Problem setup:

Episode: $S_{0} A R = 2 \to S_{1} B R = 3 \to S_{2} C R = 5 \to Terminal$
Linear function: $v^(x, w) = w_{1} x + w_{0}$
Initial parameters: $w_{0} = 0.7$ , $w_{1} = 0.8$
State representations (feature values): $S_{0} : x = 5$ , $S_{1} : x = 7$ , $S_{2} : x = 3$
Discount factor: $γ = 1$ (the professor explicitly says "assume gamma is 1")
Learning rate: $α$ (left as a parameter — the formula form is what matters for the exam)
We perform a 2-step semi-gradient TD update.

Step 1 — Compute the 2-step target for $S_{0}$ :

The 2-step target uses two rewards and bootstraps from $S_{2}$ :

G_{0}^{(2)} = R_{1} + γ R_{2} + γ^{2} v^(S_{2}, w)

First, compute $v^(S_{2}, w)$ using the current parameters with $x = 3$ :

v^(S_{2}, w) = w_{1} \cdot 3 + w_{0} = 0.8 \times 3 + 0.7 = 2.4 + 0.7 = 3.1

Now compute the target (with $γ = 1$ ):

G_{0}^{(2)} = 2 + 1 \times 3 + 1^{2} \times 3.1 = 2 + 3 + 3.1 = 8.1

Step 2 — Compute the estimate for $S_{0}$ :

v^(S_{0}, w) = w_{1} \cdot 5 + w_{0} = 0.8 \times 5 + 0.7 = 4.0 + 0.7 = 4.7

Step 3 — Compute the TD error:

δ = G_{0}^{(2)} - v^(S_{0}, w) = 8.1 - 4.7 = 3.4

Step 4 — Compute the gradient:

Since $v^(x, w) = w_{1} x + w_{0}$ :

\frac{\partial v ^}{\partial w _{1}} = x = 5, \frac{\partial v ^}{\partial w _{0}} = 1

Step 5 — Update $w_{1}$ :

w_{1} \leftarrow w_{1} + α \cdot δ \cdot \frac{\partial v ^}{\partial w _{1}} = 0.8 + α \times 3.4 \times 5 = 0.8 + 17 α

Step 6 — Update $w_{0}$ :

w_{0} \leftarrow w_{0} + α \cdot δ \cdot \frac{\partial v ^}{\partial w _{0}} = 0.7 + α \times 3.4 \times 1 = 0.7 + 3.4 α

The professor's narrative: "Now you should be able to make an update, $w_{1}$ . How do I make a $w_{1}$ update? The new $w_{1}$ — look at this expression. $w_{1}$ equals old $w_{1}$ plus alpha within bracket $G$ , your two-step target."

Step 7 — Continue for $S_{1}$ :

After updating $w_{1}$ and $w_{0}$ , we use the updated parameters to compute the target and estimate for $S_{1}$ . This is the sequential nature of the update within a single episode — within an episode of 1000 steps, we would make 1000 parameter updates.

Sense-check: The target (8.1) is larger than the estimate (4.7), so the error is positive (+3.4). The update increases both $w_{1}$ and $w_{0}$ , which will increase $v^(S_{0}, w)$ — pushing the estimate toward the target. This is exactly what gradient descent should do.

Key takeaway: The numerical walkthrough should not be challenging if you understand stochastic gradient descent from supervised learning. For each example: place a target, take an estimate, compare the difference to get an error, multiply by the gradient, and update. In reinforcement learning, the target changes depending on the method (Monte Carlo, 1-step TD, n-step TD), but the gradient update structure is always the same:

w \leftarrow w + α [target - estimate] \nabla v^

Exam note: Be able to solve this type of problem for 2-step and 3-step TD with linear functions. The professor explicitly expects this on the exam: "If you just during the exam, if you're taking a look at this algorithm and you get lost with these indexes, I think you will not be able to make it."

Recap: We have revised the core gradient-based methods for value prediction: Gradient Monte Carlo (true gradient, waits for episode end) and Semi-Gradient TD(0) (semi-gradient, updates online). The n-step methods bridge these two extremes. All follow the same update form:

w \leftarrow w + α [target - v^] \nabla v^

, differing only in how the target is constructed.

Bridge: Now that we understand the gradient update machinery, the natural question is: what features should we use? The professor chose to skip classical feature construction (polynomial, Fourier, tile coding) and jump directly to the deep learning approach — where the network learns its own features. This leads us to Section 12.2 and ultimately to DQN.

12.2 Classical Feature Construction vs. Deep Learning Feature Extraction

Hook: In classical RL, engineers hand-craft features like polynomial bases and tile coding to represent states. What if the algorithm could learn its own features directly from raw pixels? That question is what led to deep reinforcement learning.

12.2.1 Manual Feature Engineering in Classical RL

Before deep learning, the quality of function approximation in RL depended almost entirely on how well the engineer designed the feature representation. The lecture notes that these feature construction methods are "largely classical" — they were essential before neural networks became practical, but they require significant domain expertise.

The main classical methods, referenced in Sutton and Barto (Chapter 9.5), include:

Polynomial basis features: Represent states using polynomial combinations of state dimensions. For a 2D state $(s_{1}, s_{2})$ , a second-order polynomial basis would be $x (s) = (1, s_{1}, s_{2}, s_{1} s_{2}, s_{1}^{2}, s_{2}^{2})$ . These capture interactions between dimensions but grow exponentially with state dimension — $(n + 1)^{k}$ features for order $n$ and dimension $k$ .
Fourier basis features: Represent states using cosine functions at different frequencies: $x_{i} (s) = cos (π s^{⊤} c_{i})$ , where $c_{i}$ is an integer vector. Fourier features work well for smooth functions and are easy to select by frequency, but they struggle with discontinuities (they produce "ringing" artifacts).
Tile coding (coarse coding): The most practical classical method for continuous state spaces. The state space is covered by multiple overlapping grids (tilings), each offset slightly. A state activates one tile per tiling, producing a sparse binary feature vector. Tile coding gives controllable generalization: nearby states share tiles and thus generalize to each other. It was the go-to method for problems like Mountain Car.
Radial basis functions (RBFs): The continuous-valued generalization of coarse coding. Each feature is a Gaussian bell centered at a prototype state: $x_{i} (s) = exp (- \frac{∥ s - c _{i} ∥ ^{2}}{2 σ _{i}^{2}})$ . RBFs produce smooth, differentiable approximations but are computationally expensive in high dimensions.

Scope: All classical feature methods share a fundamental limitation: the engineer must decide the feature representation *before* learning begins. If the features don't capture the right aspects of the state, no amount of training will fix the problem. The number of features also grows rapidly with state dimension, making these methods impractical for high-dimensional inputs like images.

The professor chose to skip detailed coverage of these methods not because they are unimportant, but because the field has moved to automatic feature extraction. The key insight: instead of engineering features by hand, let a deep neural network learn them from data.

12.2.2 Transition to Automatic Feature Extraction in Deep RL

Why skip to DQN? The professor's reasoning is pedagogical efficiency: "There's a slight change in the original agenda in terms of just sequencing, not in terms of coverage." Rather than studying feature engineering as a standalone topic and then seeing how deep learning replaces it, we go directly to DQN — the algorithm where the network learns its own features from raw game screens.

In deep RL, the neural network's hidden layers act as automatic feature extractors. A convolutional neural network (CNN) processing Atari game screens learns to detect edges, shapes, objects, and game-specific patterns — all without human engineering. The first layers detect low-level features (edges, colors), middle layers combine these into higher-level patterns (objects, spatial relationships), and the final layers produce Q-values for each action.

This is the same principle that revolutionized computer vision: rather than hand-designing image features (SIFT, HOG), deep learning lets the network discover what features matter for the task. In RL, this means the same network architecture can work across different games without game-specific feature engineering — which is exactly what the DQN papers demonstrated on seven Atari games.

Recap: Classical RL relied on hand-crafted features (polynomials, Fourier basis, tile coding, RBFs) that required domain expertise and didn't scale to high-dimensional inputs. Deep RL replaces this with automatic feature extraction through neural networks. The professor's sequencing change — jumping directly to DQN — reflects the field's practical shift from manual to learned features. The classical methods are "largely classical" because deep learning made them unnecessary for the problems that matter most. Bridge: With this motivation in hand, we now turn to the Deep Q-Network itself — starting with the challenges that make combining deep learning with RL non-trivial.

12.3 Deep Q-Networks (DQN): Architecture and Challenges

Hook: Standard deep learning needs millions of labeled examples. In a game like Pong, you don't get labels — you get sparse rewards, delayed feedback, and correlated data. How do you train a neural network under these conditions? DQN was the first algorithm to solve this problem convincingly.

12.3.1 Historical Context and Breakthrough of DQN

The DQN algorithm is "one of the most popular algorithms which gave a first major breakthrough, first major arguably the first major breakthrough in the world of deep reinforcement learning." It was the first algorithm to use deep learning along with an established reinforcement learning framework and demonstrate that value functions can be learned through classic deep learning techniques.

The algorithm was demonstrated on seven Atari 2600 games using the Arcade Learning Environment (ALE) — a standard benchmark simulator created by Bellemare et al. (2013) for evaluating deep RL algorithms. The Atari 2600 console (released 1977) has a simple RAM (128 bytes) and a low-resolution screen (160×210 pixels), making it easy to emulate on modern computers while still presenting complex decision-making challenges. The most significant aspect of the DQN result: one network structure, without any changes, played all seven games. This generality was groundbreaking — the same architecture captured something fundamental about decision-making from visual input, without game-specific engineering.

The papers to study (shared by the professor in the course chat):

DQN1 — "Playing Atari with Deep Reinforcement Learning" (NIPS 2013, Mnih et al.) — introduces experience replay as the key innovation
DQN2 — "Human-level control through deep reinforcement learning" (Nature 2015, Mnih et al.) — adds the decoupled target network; this is the refined version
DDQN — "Deep Reinforcement Learning with Double Q-learning" (van Hasselt et al., 2015) — addresses overestimation bias

All three papers come from DeepMind (now Google DeepMind). The Nature 2015 publication was significant because it appeared in one of the world's most prestigious scientific journals, signaling that deep RL had reached mainstream credibility.

12.3.2 The Four Key Challenges in Combining Deep Learning with Reinforcement Learning

The DQN paper identifies fundamental challenges that make applying deep learning to RL non-trivial. Each challenge has a concrete consequence for training:

Challenge 1: Sparse, noisy, and delayed rewards.

In supervised learning, every training example has a correct label. In RL, the agent receives a single scalar reward at each step — and most steps have zero reward. Consider a chess game: you might take 100 moves before getting a win/loss signal. The reward is also noisy (randomness in the environment) and delayed (the consequence of move 1 might not appear until move 50). This makes it hard for the network to learn which actions were good.

Challenge 2: Delay between actions and resulting rewards (credit assignment).

The time gap between taking an action and seeing its consequence can be enormous. In Atari Breakout, you might bounce the ball 200 times before hitting the right brick. Which of those 200 actions mattered? This is the credit assignment problem — figuring out which actions in a long sequence were responsible for the reward.

Challenge 3: Correlated successive samples.

Deep learning assumes training data is independent and identically distributed (i.i.d.) — each example is unrelated to the others. In RL, consecutive states are highly correlated: state $S_{t + 1}$ is just one frame after $S_{t}$ . Training on correlated data leads to high-variance gradient updates and unstable learning. This is what experience replay solves.

Challenge 4: Non-stationarity.

In supervised learning, the data distribution is fixed (the dataset doesn't change). In RL, the distribution shifts as the agent's policy improves — the agent visits different states as it learns better actions. The network is trying to hit a target that keeps moving. This is what the target network addresses.

12.3.3 Input Preprocessing, Frame Stacking, and Hardware Artifact Mitigation

The DQN takes a screen image (raw pixels from the Atari game) as input. The raw Atari screen is 210×160 pixels with 3 color channels (RGB) — a total of 100,800 dimensions per frame. This is the state space the agent must learn from.

Preprocessing pipeline (from Mnih et al., Nature 2015):

Grayscale conversion: Color carries little useful information for most Atari games. Converting to grayscale reduces the input from 3 channels to 1, cutting dimensionality by a factor of 3.
Downsampling: The 210×160 grayscale image is downsampled to 84×84 pixels. This further reduces dimensionality while preserving the essential game information (objects, positions, movements).
Frame stacking: A single 84×84 frame cannot capture temporal information — a ball at one position doesn't tell you its direction. The solution is to stack the most recent 4 frames into a single input tensor of shape 84×84×4. This gives the network information about velocity, direction, and recent changes.

The preprocessed representation is denoted $ϕ_{t}$ (phi), representing the processed version of state $S_{t}$ . The professor uses $ϕ$ rather than $S$ to emphasize that the input is a transformation of the raw state — not the state itself. When we write $q^(ϕ_{t}, a; θ)$ , the network takes the 84×84×4 frame stack as input and outputs a Q-value for action $a$ .

Pitfall — Confusing $ϕ_{t}$ with $S_{t}$ : The raw state $S_{t}$ is the full game screen. The preprocessed state $ϕ_{t}$ is the 84×84×4 tensor. The network always sees $ϕ_{t}$ , never $S_{t}$ . When the algorithm says "observe state $S_{t}$ ", the next step is always "preprocess to form $ϕ_{t}$ ".

12.3.4 Detailed Deep Convolutional Network Architecture Specifications

Why a CNN? The input is an image (84×84×4). Convolutional neural networks are designed for spatial data — they detect patterns (edges, shapes, objects) regardless of position. A fully connected network would need a weight for every pixel, resulting in millions of parameters. A CNN uses shared weights (filters) that slide across the image, dramatically reducing the parameter count while capturing spatial structure.

The DQN architecture (from Mnih et al., Nature 2015):

Layer	Type	Details	Output Shape
Input	—	Preprocessed frame stack	84×84×4
1	Convolutional	32 filters, 8×8, stride 4, ReLU activation	20×20×32
2	Convolutional	64 filters, 4×4, stride 2, ReLU activation	9×9×64
3	Convolutional	64 filters, 3×3, stride 1, ReLU activation	7×7×64
4	Fully Connected	512 units, ReLU activation	512
Output	Linear	One Q-value per action	$∣ A ∣$

The network outputs Q-values for all possible actions simultaneously in a single forward pass. For example, if the game has 4 actions (up, down, left, right), the output layer has 4 neurons, each producing one Q-value.

Professor's explanation: "For S prime, there are four outcomes, you get four different values. And what will you do in the target? You get the max of all four."

This design simplifies the $max_{a}$ computation in Q-learning. Instead of calling the network once per action (4 calls for 4 actions) and taking the max, we call the network once and take the max of the output vector. This is both computationally efficient and architecturally elegant.

Pitfall — DQN only works with discrete actions: The $max_{a}$ operation in the target requires enumerating all actions. For continuous action spaces (e.g., robot joint torques), you can't enumerate infinitely many actions. DQN is fundamentally limited to discrete, finite action spaces. This is why it works for Atari (typically 4-18 actions) but not for continuous control.

12.3.5 Symbol Registry — Deep Q-Network Architecture

Symbol	Meaning	LaTeX	Type
$ϕ_{t}$	Preprocessed representation of state at time $t$ (84×84×4 tensor)	$ϕ_{t}$	tensor
$θ$	Parameters of the Q-network (current, updated every step)	$θ$	vector
$θ^{-}$	Parameters of the target Q-network (frozen for $C$ steps)	$θ^{-}$	vector
$q^(ϕ, a; θ)$	Q-network output for preprocessed state $ϕ$ , action $a$ , parameters $θ$	$q^(ϕ, a; θ)$	scalar
$D$	Replay memory / replay buffer (stores recent transitions)	$D$	set of transitions
$N$	Capacity of replay memory (typically 100K–1M)	$N$	integer
$C$	Frequency (in steps) for updating target network (typically 1K–10K)	$C$	integer
$ϵ$	Exploration parameter for $ϵ$ -greedy (decayed from 1.0 to 0.1)	$ϵ$	scalar in $[0, 1]$
$∣ A ∣$	Number of discrete actions	$∣ A ∣$	integer

12.3.6 Student Questions and Answers

Q: How does the Q-network handle multiple actions? Do we call the network once per action?

A: No — the network is structured to output Q-values for ALL possible actions in a single forward pass. The output layer has $∣ A ∣$ neurons (one per action). For example, with four actions (up, down, left, right), the network outputs four numbers at once. To compute $max_{a} q^(ϕ^{'}, a, θ^{-})$ in the target, we pass the next state through the network once and take the maximum of the outputs — this simplifies the computation from $∣ A ∣$ network calls to just 1.

Recap: DQN is the first deep RL breakthrough. It faces four challenges (sparse rewards, credit assignment, correlated samples, non-stationarity) and addresses them through preprocessing (grayscale, downsample, 4-frame stack), a CNN architecture (outputs all Q-values in one forward pass), and two key algorithmic innovations (experience replay + target network) covered in Section 12.4. The network only works with discrete action spaces.

Bridge: We've seen the architecture — how the network processes input and produces Q-values. Now we need to understand the two algorithmic innovations that make training stable: the target network and experience replay.

12.4 Core Algorithmic Components of DQN: Experience Replay and Target Network

Hook: Standard Q-learning with a neural network diverges — the value estimates explode or oscillate wildly. DQN solves this with two simple but powerful ideas: freeze the target temporarily, and randomize the training data. These two innovations turned unstable deep Q-learning into the first major deep RL success.

12.4.1 Purpose, Inputs, and Outputs of the DQN Architecture

Purpose: DQN extends Q-learning — an off-policy temporal difference control method — to work with deep neural networks. The fundamental challenge: standard Q-learning with function approximation is unstable because (1) the target changes with every parameter update (moving target problem from Section 12.1.6), and (2) consecutive training samples are highly correlated (violating the i.i.d. assumption). Two innovations solve these problems:

Innovation	Problem Addressed	Mechanism
Target Network ( $θ^{-}$ )	Moving target / non-stationarity	Freeze a copy of the Q-network for $C$ steps; use it to compute stable targets
Experience Replay ( $D$ )	Correlated samples	Store transitions in a buffer; sample random mini-batches for training

The agent-environment interaction flow:

The agent observes the current screen (preprocessed into $ϕ_{t}$ , an 84×84×4 tensor).
The Q-network (parameters $θ$ ) outputs Q-values for all actions given $ϕ_{t}$ .
An action is selected using $ϵ$ -greedy: with probability $ϵ$ choose random, otherwise choose $ar g max_{a} q^(ϕ_{t}, a; θ)$ .
The action is executed in the Arcade Learning Environment (ALE).
The environment returns a reward $r_{t}$ and the next screen.
The transition $(ϕ_{t}, a_{t}, r_{t}, ϕ_{t + 1})$ is stored in the replay buffer $D$ .
A mini-batch is randomly sampled from $D$ to update $θ$ .
Every $C$ steps, $θ^{-} \leftarrow θ$ (copy current parameters to target network).

12.4.2 Deep-Dive 1: Decoupled Target Q-Network ( $θ^{-}$ )

The problem it solves: In standard Q-learning with function approximation, the target is

y = r + γ max_{a^{'}} q^(s^{'}, a^{'}; θ)

. But

θ

is updated every step. So the target changes with every update — "like chasing a moving goalpost." This makes training unstable because the optimization objective keeps shifting.

The first innovation addresses the moving target problem discussed in Section 12.1.6. In standard Q-learning with function approximation, the target is:

y = r + γ a^{'} max q^(s^{'}, a^{'}; θ)

But $θ$ is being updated at every step. The target shifts with every update.

The solution: Maintain two copies of the Q-network:

Q-network (with parameters $θ$ ): Updated at every step via gradient descent. Used to compute the current estimate $q^(s, a; θ)$ .
Target Q-network (with parameters $θ^{-}$ ): Kept frozen for $C$ steps. Used to compute the target: $y = r + γ max_{a^{'}} q^(s^{'}, a^{'}; θ^{-})$ .

Every $C$ steps, the parameters are copied: $θ^{-} \leftarrow θ$ . Between copies, $θ^{-}$ remains fixed.

The modified update rule:

θ \leftarrow θ + α [r + γ a^{'} max q^(s^{'}, a^{'}; θ^{-}) - q^(s, a; θ)] \nabla_{θ} q^(s, a; θ)

Notice: the target uses $θ^{-}$ (frozen), the gradient uses $θ$ (current). This is the key difference from standard Q-learning.

The professor's explanation: "Think of it like this... I will always update my Q1 network and that's what my estimate always. And Q2 network, every time you actually complete 10 step, 100 step, I will copy the parameters here. So that this Q2 will stay same thing for say 10 step, 50 step, or 100 step, whatever you actually define."

Replacement vs. Polyak update: The textbook (T2 Ch5) describes two ways to update the target network:

Replacement update (used in the Nature 2015 paper): $θ^{-} \leftarrow θ$ every $C$ steps. Simple, but the target suddenly jumps when the copy happens.
Polyak (soft) update: $θ^{-} \leftarrow β θ^{-} + (1 - β) θ$ at every step. The target changes gradually. Hyperparameter $β$ controls how slowly $θ^{-}$ changes (larger $β$ = slower change, e.g., $β = 0.999$ ).

Neither is definitively better. The replacement update gives a stable target between copies; the Polyak update avoids sudden jumps. For the exam, the professor uses the replacement update form.

Typical values of $C$ : 1,000–10,000 for Atari games; 100–1,000 for simpler problems like CartPole.

Why this helps: By keeping the target network fixed for a period, the target does not shift with every parameter update. This transforms the problem into something closer to standard supervised regression — the network is fitting a fixed target. As the textbook notes: "Introducing a target network literally stops the target from moving." It is "technically look like 2 networks, but then you are actually learning parameter at only one place."

12.4.3 Deep-Dive 2: Experience Replay Buffer ( $D$ )

The problem it solves: In a typical RL episode, 10 consecutive transitions all come from the same trajectory — they are highly correlated. Using them as a mini-batch violates the i.i.d. assumption and leads to high-variance, unstable gradient updates. Experience replay (invented by Long-Ji Lin in 1992) solves this by storing past transitions and sampling randomly.

Experience replay addresses the correlated data problem. The solution: store transitions in a replay buffer and sample randomly from it to form mini-batches.

Transition format: Each transition stored in the buffer has the form

(ϕ_{t}, a_{t}, r_{t}, ϕ_{t + 1})

$ϕ_{t}$ : preprocessed 84×84×4 tensor of the current state
$a_{t}$ : action taken (discrete integer)
$r_{t}$ : reward received (scalar, clipped to $[- 1, + 1]$ in the Nature 2015 paper)
$ϕ_{t + 1}$ : preprocessed tensor of the next state

Buffer management:

Fixed capacity $N$ (typically 100,000 to 1,000,000 transitions)
When full, the oldest transition is discarded (FIFO — first in, first out)
Discarding old data is intentional: older transitions are from earlier policies and less relevant to the current policy

Mini-batch sampling:

Randomly sample $B$ transitions (typically $B = 32$ ) from the buffer
Compute the DQN loss for each transition: $L_{j} (θ) = [r_{j} + γ max_{a^{'}} q^(ϕ_{j + 1}, a^{'}; θ^{-}) - q^(ϕ_{j}, a_{j}; θ)]^{2}$
Average the losses: $L (θ) = \frac{1}{B} \sum_{j = 1}^{B} L_{j} (θ)$
Update $θ$ via gradient descent on $L (θ)$

Why this helps: Randomly sampling from a large buffer breaks temporal correlation. A mini-batch drawn from 200,000 stored transitions is much closer to i.i.d. than 32 consecutive steps from the same episode. Additionally, each transition can be reused multiple times across different updates — improving sample efficiency compared to on-policy methods that discard data after one use.

Pitfall — Buffer too small: If

N

is too small (e.g., 1,000), the buffer contains mostly recent transitions that are still correlated. A larger buffer (100K–1M) provides more diverse training data. Pitfall — Buffer too large: If

N

is very large (e.g., 10M), many transitions will be from very old policies that are irrelevant to the current agent. The Nature 2015 paper used

N = 1, 000, 000

12.4.4 Loss Formulation, Huber Error Clipping, and Optimization

The DQN loss for a single transition

(ϕ_{t}, a_{t}, r_{t}, ϕ_{t + 1})

is:

L (θ) = [r_{t} + γ a^{'} max q^(ϕ_{t + 1}, a^{'}; θ^{-}) - q^(ϕ_{t}, a_{t}; θ)]^{2}

The gradient update:

θ \leftarrow θ + α [r_{t} + γ a^{'} max q^(ϕ_{t + 1}, a^{'}; θ^{-}) - q^(ϕ_{t}, a_{t}; θ)] \nabla_{θ} q^(ϕ_{t}, a_{t}; θ)

This has the same structure as all the gradient-based updates we have seen — the universal form

w \leftarrow w + α [target - estimate] \nabla estimate

. The only differences are:

The target uses $θ^{-}$ (frozen) instead of $θ$ (current)
The training examples come from the replay buffer, not online interaction

Huber loss (Smooth L1 loss): In practice, the Nature 2015 paper uses the Huber loss instead of the squared error:

L_{δ} (a) = {\frac{1}{2} a^{2} ∣ a ∣ - \frac{1}{2} if ∣ a ∣ \leq 1 otherwise

where $a$ is the TD error. The Huber loss is quadratic for small errors (giving smooth gradients) and linear for large errors (preventing exploding gradients from outliers). This makes training more robust than pure MSE, especially when rewards are clipped to $[- 1, + 1]$ .

12.4.5 Theoretical Analysis of Overestimation Bias in Q-Learning

Overestimation bias: The Q-learning target uses

max_{a^{'}} q^(s^{'}, a^{'}; θ^{-})

. This maximization systematically overestimates the true Q-values. The reason: the max operator selects the action with the highest estimated value, and estimates have noise. Some estimates will be too high due to random fluctuations, and the max will preferentially pick those — creating a positive bias.

From the textbook (T2 Ch5): with $k$ actions and noisy but unbiased estimates, the expected maximum is already above the true maximum. For example, with $k = 10$ actions where the true Q-values are all zero, $E [max_{a} Q (s, a)] = 1.53$ — a significant positive bias.

This overestimation is problematic when combined with bootstrapping: incorrect high Q-values propagate backwards through time, compounding the error. Double DQN (van Hasselt et al., 2015) addresses this by using the training network $θ$ to select the action and the target network $θ^{-}$ to evaluate it — decoupling selection from evaluation. This will be covered in subsequent lectures.

12.4.6 Evolution of Deep Q-Learning: NIPS 2013 vs. Nature 2015 vs. Double DQN

The professor shows the algorithms from both DQN1 (NIPS 2013) and DQN2 (Nature 2015) side by side for comparison.

Feature	DQN1 (NIPS 2013)	DQN2 (Nature 2015)	DDQN (2015)
Experience Replay	Yes	Yes	Yes
Target Network	No (single network)	Yes ( $θ^{-}$ frozen for $C$ steps)	Yes
Target Construction	$r + γ max_{a^{'}} q^(s^{'}, a^{'}; θ)$	$r + γ max_{a^{'}} q^(s^{'}, a^{'}; θ^{-})$	$r + γ q^(s^{'}, ar g max_{a^{'}} q^(s^{'}, a^{'}; θ); θ^{-})$
Overestimation	Severe	Reduced (but still present)	Significantly reduced
Exam relevance	—	This is the exam version	Covered in later lectures

The professor emphasizes: "This algorithm is from 2015 and that's all what matters for the exam perspective."

12.4.7 Student Questions and Answers

Q: How is the mini-batch concept implemented in DQN? How do we get a mini-batch in an RL interaction?

A: The professor explains the implementation: store all transitions in a replay buffer as they occur during gameplay. When it's time to update the network, randomly sample $K$ examples (e.g., 16 or 32) from the buffer, compute the DQN loss on each, average the losses, and use that for one gradient descent step. This breaks temporal correlation — unlike sampling 10 consecutive steps from the same episode, which would still be highly correlated and would not represent a true mini-batch.

12.4.8 Symbol Registry — Core DQN Components

Symbol	Meaning	LaTeX	Type
$θ$	Current Q-network parameters (updated every step)	$θ$	vector
$θ^{-}$	Target Q-network parameters (frozen for $C$ steps)	$θ^{-}$	vector
$D$	Replay buffer (stores recent transitions)	$D$	set of transitions
$N$	Replay buffer capacity (100K–1M)	$N$	integer
$C$	Target network update frequency (1K–10K steps)	$C$	integer
$M$	Number of episodes for training	$M$	integer
$B$	Mini-batch size (typically 32)	$B$	integer
$ϕ_{t}$	Preprocessed state at time $t$ (84×84×4)	$ϕ_{t}$	tensor
$a_{t}$	Action at time $t$	$a_{t}$	scalar
$r_{t}$	Reward at time $t$ (clipped to $[- 1, + 1]$ )	$r_{t}$	scalar
$ϵ$	Exploration rate for $ϵ$ -greedy (decayed 1.0 → 0.1)	$ϵ$	scalar

12.4.9 Complete Pseudocode Walkthrough of Nature DQN (DQN2)

DQN Algorithm (Nature 2015) — Line by Line:

Step 1 — Initialization:

Initialize replay memory $D$ with capacity $N = 1, 000, 000$ .
Initialize the Q-network with random parameters $θ$ .
Initialize the target Q-network with parameters $θ^{-} = θ$ (both start identical).

Step 2 — Outer loop (for each episode, $m = 1$ to $M$ ):

Begin with the starting state.
Preprocess: obtain the last 4 frames, downsample to 84×84, convert to grayscale, stack → form $ϕ_{1}$ .

Step 3 — Inner loop (for each step within the episode):

Action selection: Feed $ϕ_{t}$ into the Q-network. The network outputs Q-values for all $∣ A ∣$ actions. Select action using $ϵ$ -greedy: $a_{t} = {random action ar g max_{a} q^(ϕ_{t}, a; θ) with probability ϵ with probability 1 - ϵ$ $ϵ$ is typically decayed from 1.0 to 0.1 over the first 1M frames.
Execute action: Execute $a_{t}$ in the ALE. Observe reward $r_{t}$ and next screen.
Preprocess next state: Process the new screen → form $ϕ_{t + 1}$ .
Store transition: Store $(ϕ_{t}, a_{t}, r_{t}, ϕ_{t + 1})$ in $D$ . If $D$ is full, discard the oldest transition.
Sample mini-batch and update: Randomly sample a mini-batch of $B$ transitions ${(ϕ_{j}, a_{j}, r_{j}, ϕ_{j + 1})}$ from $D$ . For each transition:
- Compute target: $y_{j} = r_{j} + γ max_{a^{'}} q^(ϕ_{j + 1}, a^{'}; θ^{-})$ (if terminal, $y_{j} = r_{j}$ )
- Compute loss: $L = \frac{1}{B} \sum_{j} [y_{j} - q^(ϕ_{j}, a_{j}; θ)]^{2}$
- Update: $θ \leftarrow θ - α \nabla_{θ} L$
Update target network: Every $C$ steps, copy: $θ^{-} \leftarrow θ$ .

The professor summarizes the three key changes from standard Q-learning:

"Since the target is moving, I want to have a target parameter to be different. So every $C$ step I would actually refresh the target. So I am kind of decoupling this network and this network."
"I'm actually introducing mini-batch gradient descent via sampling a mini-batch from the replay buffer."
The state representation uses preprocessed frames $ϕ$ rather than raw states $S$ .

Pitfall — $C$ too small: If the target network is updated too frequently (e.g., every 10 steps), the target still moves quickly and destabilizes training. Typical values: 1,000–10,000 for Atari. Pitfall — $C$ too large: If the target network is frozen for too long, the target becomes stale and training slows down because the network is optimizing against an outdated objective. Pitfall — Mini-batch from consecutive steps: Always sample randomly from the buffer. Sampling 32 consecutive transitions defeats the purpose of experience replay — the data is still correlated.

Exam note: The DQN algorithm from the 2015 Nature paper (DQN2) is the version that matters for the exam. Understand every component: the two networks (

θ

and

θ^{-}

), the replay buffer (

D

), the

ϵ

-greedy action selection, the mini-batch sampling, and the target network update. Know WHY each innovation is needed and HOW it works. The professor: "Understand the algorithm bit by bit — every component, every line."

Recap: DQN's two innovations — target network and experience replay — transform unstable deep Q-learning into a working algorithm. The target network freezes

θ^{-}

for

C

steps, giving the optimizer a stable target. Experience replay stores transitions and samples random mini-batches, breaking temporal correlation and approximating i.i.d. training. The loss is the standard semi-gradient TD error, computed over a mini-batch. Bridge: This concludes the core content of Lecture 12. The exam guidance summary and industry applications follow. The next lecture will cover Double DQN and other improvements to the basic DQN algorithm.

12.5 Pedagogical Insights: Mathematical Abstraction and AI Learning Partners

Hook: Should every algorithm be verified with hand calculations? When does numerical checking help, and when does it become a crutch that prevents higher-level understanding?

12.5.1 Numerical Hand Calculations vs. High-Level Systems Abstraction

A student (Chiranjit/Chirag) remarks that numerical examples help them understand the theory. The professor responds with an important pedagogical point about the role of abstraction and advocates for higher-level thinking.

Numerical examples are valuable and the professor uses them "very judiciously where I actually need it." For the N-step semi-gradient TD algorithm, numerical examples are possible and instructive — the professor demonstrated a complete 2-step TD update by hand (Section 12.1.10). Working through the algebra with real numbers builds confidence that you understand the mechanics of the update rule: what the target is, how the gradient is computed, and how parameters change.

However, for DQN with a CNN, hand-computing a mini-batch gradient update on paper is not feasible or meaningful. "Even for a mini batch update, I need to actually look at assume a reasonably good network. I don't think, you know, a numerical is possible in DQN. So if you start expecting numbers everywhere you get into trouble."

Scope: Numerical hand calculations are appropriate for:

Simple linear function approximation (2-3 parameters)
Small n-step TD problems (2-3 steps, 2-3 states)
Verifying that you understand the form of an update rule

They are NOT appropriate for:

Deep neural networks with thousands of parameters
Mini-batch updates over 32 or 64 transitions
CNN architectures with convolutional layers

The professor's point: "We should actually be comfortable with something known as abstraction, dealing things at different levels of abstraction."

The professor emphasizes that the ability to work at multiple levels of abstraction is a skill expected at this level of study: "For everything, I just want to look at the numbers and then feel convinced, I think my ability to look at things at a little higher level and be still be able to make sense out of it is something that I'm missing."

Certain things must be understood at a higher level. From that higher-level understanding, one should gain the confidence to handle lower-level details. The DQN algorithm should be understood as a coherent system — the interaction between experience replay, target network, and Q-learning — not as a sequence of matrix multiplications.

Exam note: For N-step semi-gradient TD, you MUST be able to solve numerical problems by hand. The professor explicitly worked through a 2-step TD example and expects similar problems on the exam. For DQN, the emphasis is on algorithmic understanding — the two innovations, why each is needed, and how the pseudocode works line by line. Hand-computing a CNN gradient update is NOT expected.

12.5.2 Student Dialogue: Using Interactive LLM Partners for Deep Technical Reading

A student shares their approach to reading research papers: they upload papers to ChatGPT, which knows their learning history, and ask it to explain the paper and suggest what textbook sections to study as prerequisites. The student finds this effective for building the prerequisite chain needed to understand advanced material.

Student approach: Upload research paper → ChatGPT (with learning history context) → explains paper + suggests prerequisite textbook sections → student studies prerequisites → returns to paper with better foundation. Professor's response: "It's going to be a partner in your learning, it's not, it's no longer a place where you actually take content and read it, but then you know, it's a partner who's going to be with you to improve your understanding and learning."

The professor observes that two years ago, people were reluctant to admit using ChatGPT for learning, viewing it as "outsourcing." Now there is maturity to accept AI tools as learning partners. The key distinction: "Ultimately, it matters as to what you gain, how much you actually gain, how much depth you actually gain."

At work, the objective is different — getting things done quickly and correctly. As long as the tool meets the objective, it is a valuable resource. But in a learning context, the goal is depth of understanding, not just output.

The professor also notes that classroom interaction from multiple perspectives provides a different kind of learning that AI cannot fully replace: "In a class which is where there's a question from multiple different perspectives, I think the learning is actually going to be immense." A student asking "why does this work?" from one angle, and another asking from a completely different angle, creates understanding that no single AI conversation can replicate.

12.5.3 Student Questions and Answers

Q: A student shares their approach: uploading papers to ChatGPT, which knows their learning history, and asking it to explain papers and suggest prerequisite textbook sections. A: The professor approves, noting AI has matured from being a secret tool to a recognized learning partner. The key is depth of understanding — "it matters as to what you gain, how much you actually gain, how much depth you actually gain." Classroom interaction from multiple perspectives still provides irreplaceable learning that AI cannot fully substitute.

Recap: The professor makes two important pedagogical points: (1) numerical hand calculations are valuable for simple algorithms (n-step TD) but not feasible for complex ones (DQN with CNN) — abstraction is a required skill, not a weakness; (2) AI tools like ChatGPT are legitimate learning partners when used to deepen understanding, not to shortcut it. Bridge: This concludes Lecture 12's conceptual content. The exam guidance summary and industry applications follow.

Exam Guidance Summary

Exam note: DQN Algorithm (Nature 2015). The DQN algorithm from the 2015 Nature paper (DQN2) is the version that matters for the exam. Understand the algorithm bit by bit — every component, every line. The three key changes from standard Q-learning are: (1) decoupled target network with periodic updates every

C

steps, (2) mini-batch gradient descent via experience replay sampling, and (3) preprocessed frame representation

ϕ

instead of raw states

S

Exam note: N-Step Semi-Gradient TD Numericals. You should be able to solve numerical problems for N-step semi-gradient TD. The professor explicitly worked through a 2-step TD example and expects students to handle similar problems. "If you just during the exam, if you're taking a look at this algorithm and you get lost with these indexes, I think you will not be able to make it." Practice the indexing:

τ = t - n + 1

, and remember tail-end handling near the terminal state.

Exam note: Form of the Update Expression. Understanding the form of the update expression is critical across all methods. "If you have these two things [the target form and the update rule form] and if you are okay with this form of this expression, you should be okay technically because you've done 2 courses." The universal form is:

w \leftarrow w + α [target - estimate] \nabla estimate

. The target changes depending on the method (MC, TD, n-step, DQN), but the gradient update structure is always the same.

Exam note: DQN Conceptual Understanding. For DQN, the emphasis is on understanding the algorithm conceptually — the two innovations (experience replay and target network), why each is needed, and how they work together. Hand-computing a full CNN gradient update on the exam is NOT expected. Know the pseudocode, the flow, and the motivation for each component.

Exam note: Study Materials. The professor plans to provide summarized notes covering all 16 classes. These notes will serve as quick revision material for the exam. Focus on the algorithmic patterns — once you understand the semi-gradient update form, every method in the course follows the same structure with different targets.

Key Industry Applications

Atari game playing. DQN was demonstrated on seven Atari 2600 games using the Arcade Learning Environment (ALE), a standard benchmark simulator created by Bellemare et al. (2013). The same network architecture — a convolutional neural network with three convolutional layers and one fully connected layer — played all seven games without structural changes. This generality was the key result: a single learning algorithm could master diverse games from raw pixel input, suggesting the approach captured something fundamental about decision-making from visual data. The Atari benchmark remains one of the most widely used testbeds for deep RL research.

DeepMind's breakthrough. The DQN papers come from DeepMind (now part of Google DeepMind), the same research group behind AlphaGo, AlphaFold, and other landmark AI systems. Vladimir Mnih is the lead author on both the NIPS 2013 and Nature 2015 papers. The Nature 2015 paper was published in one of the most prestigious scientific journals, signaling that deep RL had reached mainstream scientific credibility. DeepMind's subsequent work built directly on DQN: Double DQN, Prioritized Experience Replay, Dueling DQN, and eventually Rainbow DQN (combining all improvements).

Game AI as a benchmark. The Arcade Learning Environment (ALE) serves as a standard benchmark for evaluating deep RL algorithms. It provides a simulator interface where agents interact with games step by step, receiving screen images as observations and discrete actions as inputs. The ALE's design — low-resolution images, discrete actions, diverse game mechanics — makes it an ideal testing ground. After Atari, the field moved to more complex benchmarks: 3D navigation (ViZDoom, DeepMind Lab), multiplayer games (StarCraft II, Dota 2), and robotics simulations.

ChatGPT as a learning partner. Students are using ChatGPT and similar LLMs as interactive learning partners for reading technical papers, understanding prerequisites, and getting personalized explanations. This represents a fundamental shift in how technical material is consumed: from passive reading to active dialogue. The professor endorses this approach when used to deepen understanding rather than shortcut it. The key differentiator is whether the tool helps you build mental models or merely produces outputs you don't understand.

DRL Lecture 12 notes · Feature Construction and Deep Q-Networks (DQN)

Deep Reinforcement Learning· postgraduate· 2026-07-26

Sections Breakdown

1Revision of Function Approximation and Semi-Gradient TD Methods

Covers tabular vs parameterized methods, gradient Monte Carlo, semi-gradient TD, and n-step TD with worked examples.

2Classical Feature Construction vs. Deep Learning Feature Extraction

Contrasts hand-crafted features with automatic neural network feature extraction.

3Deep Q-Networks (DQN): Architecture and Challenges

DQN breakthrough, four key challenges, CNN architecture, input preprocessing.

4Core Algorithmic Components of DQN

Target network, experience replay, loss formulation, overestimation bias, DQN algorithm.

5Pedagogical Insights

Abstraction levels and AI as learning partners.

Postgraduate students in Deep Reinforcement Learning

Exam Revision Notes

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

Function Approximation and Semi-Gradient TD

Must-know: Solve 2-step and 3-step semi-gradient TD numerical problems with linear functions. Understand the universal update form. Know why it's called 'semi-gradient'.

$w \leftarrow w + α [R_{t + 1} + γ v^(S_{t + 1}, w) - v^(S_{t}, w)] \nabla_{w} v^(S_{t}, w)$

⚠️ Top pitfall: Confusing t (current time) with τ (state being updated) in n-step methods. Forgetting tail-end handling.

Self-check: Why is TD(0) called 'semi-gradient'? What gradient is being ignored?

Connects to: Classical Feature Construction, DQN Architecture, DQN Algorithmic Components

Classical Feature Construction

Must-know: Classical methods are 'largely classical' — the professor skipped them to go directly to DQN where deep learning handles feature extraction automatically.

⚠️ Top pitfall: Confusing the professor's sequencing choice with content being unimportant.

Self-check: Why did the professor skip detailed coverage of polynomial basis, Fourier basis, and tile coding?

Connects to: Function Approximation, DQN Architecture

DQN Architecture and Challenges

Must-know: DQN from 2015 Nature paper. 4 challenges in DL+RL. CNN outputs all Q-values in one pass. Only discrete actions. Input: 84x84x4.

$L (θ) = [r + γ a^{'} max q^(s^{'}, a^{'}; θ^{-}) - q^(s, a; θ)]^{2}$

⚠️ Top pitfall: Confusing φ (preprocessed) with S (raw state). Forgetting DQN requires discrete actions.

Self-check: Why stack 4 frames? Why output all Q-values at once?

Connects to: Function Approximation, DQN Algorithmic Components

DQN Algorithmic Components

Must-know: Target network: θ⁻ frozen for C steps. Experience replay: store transitions, random sample mini-batches. Huber loss. Overestimation bias.

$θ \leftarrow θ + α [r + γ a^{'} max q^(s^{'}, a^{'}; θ^{-}) - q^(s, a; θ)] \nabla_{θ} q^(s, a; θ)$

⚠️ Top pitfall: Confusing θ (updated) with θ⁻ (frozen). Sampling consecutive transitions instead of random.

Self-check: What two problems do experience replay and target network solve?

Connects to: Function Approximation, DQN Architecture

Abstraction and Learning Partners

Must-know: n-step TD numericals by hand YES. DQN CNN gradients by hand NO. Abstraction is a skill.

⚠️ Top pitfall: Expecting to verify every algorithm with numerical examples.

Self-check: Why can you do a numerical walkthrough for 2-step TD but not for DQN with CNN?

Connects to: Function Approximation, DQN Algorithmic Components

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

Next LectureLecture 13 · Deep Q-Networks and Policy Gradient Methods

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.

Feature Construction and Deep Q-Networks (DQN)

12.1 Revision of Function Approximation and Semi-Gradient TD Methods

12.1.1 Tabular Representation vs. Parameterized Function Approximation

12.1.2 Symbol Registry — Function Approximation

12.1.3 Limitations of Tabular Methods and Motivation for Function Approximation

12.1.4 Gradient Monte Carlo vs. Semi-Gradient TD(0) Update Rules

12.1.5 Symbol Registry — Semi-Gradient TD Update

12.1.6 The Semi-Gradient Nature and Moving Target Problem

12.1.7 Student Questions and Answers

12.1.8 Multi-Step (n-Step) Semi-Gradient TD Methods and Tail-End Handling

12.1.9 Symbol Registry — n-Step Semi-Gradient TD

12.1.10 Worked Computation: 2-Step Semi-Gradient TD Update on a Linear Function

12.2 Classical Feature Construction vs. Deep Learning Feature Extraction

12.2.1 Manual Feature Engineering in Classical RL

12.2.2 Transition to Automatic Feature Extraction in Deep RL

12.3 Deep Q-Networks (DQN): Architecture and Challenges

12.3.1 Historical Context and Breakthrough of DQN

12.3.2 The Four Key Challenges in Combining Deep Learning with Reinforcement Learning

12.3.3 Input Preprocessing, Frame Stacking, and Hardware Artifact Mitigation

12.3.4 Detailed Deep Convolutional Network Architecture Specifications

12.3.5 Symbol Registry — Deep Q-Network Architecture

12.3.6 Student Questions and Answers

12.4 Core Algorithmic Components of DQN: Experience Replay and Target Network

12.4.1 Purpose, Inputs, and Outputs of the DQN Architecture

12.4.2 Deep-Dive 1: Decoupled Target Q-Network (θ−)

12.4.3 Deep-Dive 2: Experience Replay Buffer (D)

12.4.4 Loss Formulation, Huber Error Clipping, and Optimization

12.4.5 Theoretical Analysis of Overestimation Bias in Q-Learning

12.4.6 Evolution of Deep Q-Learning: NIPS 2013 vs. Nature 2015 vs. Double DQN

12.4.7 Student Questions and Answers

12.4.8 Symbol Registry — Core DQN Components

12.4.9 Complete Pseudocode Walkthrough of Nature DQN (DQN2)

12.5 Pedagogical Insights: Mathematical Abstraction and AI Learning Partners

12.5.1 Numerical Hand Calculations vs. High-Level Systems Abstraction

12.5.2 Student Dialogue: Using Interactive LLM Partners for Deep Technical Reading

12.5.3 Student Questions and Answers

Exam Guidance Summary

Key Industry Applications

DRL Lecture 12 notes · Feature Construction and Deep Q-Networks (DQN)

Sections Breakdown

Exam Revision Notes

Function Approximation and Semi-Gradient TD

Classical Feature Construction

DQN Architecture and Challenges

DQN Algorithmic Components

Abstraction and Learning Partners

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

12.4.2 Deep-Dive 1: Decoupled Target Q-Network ( $θ^{-}$ )

12.4.3 Deep-Dive 2: Experience Replay Buffer ( $D$ )