Deep Q-Networks and Policy Gradient Methods

This lecture has two halves. The first half reviews the family of deep Q-network (DQN) algorithms — the 2013 original, the 2015 improved version, and Double DQN — as a progression where each version fixes a specific problem in the previous one. The second half introduces a fundamentally different paradigm: policy gradient methods, where the agent learns the policy directly instead of learning action values, and walks through the derivation of the REINFORCE algorithm step by step.

13.1 Deep Q-Network (DQN) — The Original Algorithm (2013)

The lecture begins with a recap of the DQN family — the story of three papers that mark the entry of deep learning into reinforcement learning: the original DQN (2013), the improved DQN (2015, same authors), and Double DQN, which addresses maximization bias. The central message of the review: understand these as a progression, where each new paper fixes a specific problem in the previous version. The 2013 version introduces deep Q-learning; the 2015 version fixes the instability caused by chasing a moving target; Double DQN fixes the overestimation caused by the \(\max\) operator. The professor's exam guidance: focus on the 2015 DQN and DDQN for exams, not the 2013 version — which is why the recap treats the 2013 paper mostly as the problem setup that motivates the later fixes.

13.1.1 What a DQN does

A Deep Q-Network takes a state (typically a stack of preprocessed game frames) as input, passes it through a convolutional neural network, and outputs the estimated Q-value for every possible action. For example, in an Atari game, the network might output five values: the value of pressing "up", the value of pressing "down", the value of pressing "left", the value of pressing "right", and the value of pressing the fire button. These Q-values estimate the expected long-term return (total discounted reward) of taking each action in the current state and following the current policy thereafter.

The input to the network is a stack of four preprocessed frames, each resized to \(84 \times 84\) pixels and converted to grayscale. The input tensor therefore has shape \(84 \times 84 \times 4\) (height \(\times\) width \(\times\) frames). Why stack four frames instead of feeding one? A single image gives no information about motion — a ball frozen at one position could be moving in any direction. Four consecutive frames reveal direction and speed of moving objects, which is exactly the information a game-playing agent needs. The choice of four frames is a documented design decision from the original paper: more frames give a longer history but cost more computation and memory.

13.1.2 The network architecture

The DQN architecture uses a deep convolutional neural network. The convolutional layers detect spatial patterns — edges, then shapes, then objects — exactly as in image classification networks:

• First convolutional layer: 32 filters of size \(8 \times 8\) with stride 4
• Second convolutional layer: 64 filters of size \(4 \times 4\) with stride 2
• Third convolutional layer: 64 filters of size \(3 \times 3\) with stride 1
• Fully connected layer: 512 units
• Output layer: one unit per action (no activation — raw Q-values)

The network takes the preprocessed frames as input and outputs the Q-value for each action directly. Note the contrast with older designs that fed both state and action as inputs: here only the state is an input, and each action gets its own output neuron. One forward pass then computes the Q-values of all actions at once — a single pass replaces \(K\) separate forward passes, where \(K\) is the number of actions.

13.1.3 From tables to networks — the core idea

The network is trained with the standard Q-learning update, applied to network parameters rather than table entries:

\[ \theta \leftarrow \theta + \alpha \left( Y - Q(s, a; \theta) \right) \nabla_\theta Q(s, a; \theta) \]

where:

• \(\theta\) (theta) is the vector of network parameters (all the weights and biases)
• \(\alpha\) (alpha) is the learning rate, the step size of the update
• \(Q(s, a; \theta)\) is the network's current estimate of the Q-value of action \(a\) in state \(s\) — the "current guess"
• \(Y\) is the target — the value we want the current guess to move towards
• \(\nabla_\theta Q(s, a; \theta)\) is the gradient of the network output with respect to the parameters, computed by backpropagation

The update is a step of gradient descent on the squared error \((Y - Q(s, a; \theta))^2\): if the current estimate \(Q(s, a; \theta)\) is below the target \(Y\), the update pushes \(\theta\) in the direction that raises the estimate; if above, it lowers it. The size of the push is scaled by \(\alpha\).

The target in the original 2013 DQN is:

\[ Y = r + \gamma \max_{a'} Q(s', a'; \theta) \]

Here:

• \(r\) is the reward received after taking action \(a\) in state \(s\)
• \(\gamma\) (gamma) is the discount factor in \([0, 1]\) — it decides how much future rewards count compared to immediate ones (close to 1: patient agent; close to 0: myopic agent)
• \(s'\) is the next state
• \(\max_{a'}\) selects the highest Q-value over all possible next actions \(a'\) — the "best guess" of the value of the next state

This is the Bellman equation applied as an update rule: the value of an action should equal the immediate reward plus the discounted best value of where you end up next. Note that the same network parameters \(\theta\) are used for both computing the current Q-value \(Q(s, a; \theta)\) and computing the target \(Q(s', a'; \theta)\) — and this, as we will see in section 13.2, is exactly the seed of a stability problem.

13.1.4 Experience Replay Buffer

The replay buffer serves two purposes:

1. Breaking temporal correlation. Consecutive frames in a game are highly correlated — frame 10 is nearly identical to frame 11. If the network learned from consecutive samples, its gradient updates would all point in nearly the same direction, like studying the same exam question ten times in a row. Random sampling from the buffer mixes old and new transitions, producing approximately independent training samples, which stabilizes gradient descent.

1. Data efficiency. Each transition is reused in many updates rather than being used once and thrown away. In the 2013 paper, each transition is used in multiple weight updates; this matters enormously because collecting experience through environment interaction is slow.

In the original 2013 paper the buffer held the last \(N = 1{,}000{,}000\) frames, and mini-batches of size 32 were sampled. As with all hyperparameter numbers, these are reference values, not exam material.

13.1.5 DQN Training Loop — Detailed Walkthrough

The full DQN algorithm is a procedure, so it is best read as one. The loop runs over episodes; within each episode, these steps repeat:

Step 1: Obtain the current state. Start with the initial state of the environment. Extract the current frame from the emulator after executing the most recent action. Combine it with the previous three frames, preprocess (resize to \(84 \times 84\), convert to grayscale), and stack them to form the state representation \(\phi\) (phi). This \(\phi\) is the input to the Q-network.

Step 2: Select an action using epsilon-greedy. With probability \(\epsilon\) choose a random action (exploration); with probability \(1 - \epsilon\) choose the action with the highest Q-value (exploitation). The professor marks this as the epsilon-greedy step. Early in training \(\epsilon\) is high (often 1.0, fully random) and anneals down to a small floor (often 0.1) — the agent explores wildly at first, then settles into exploiting what it has learned.

Step 3: Execute the action in the emulator. The emulator processes the action and returns the reward \(r\) and the next raw frame.

Step 4: Construct the next state. Append the new frame to the stack of previous frames, preprocess, and form the next state representation \(\phi'\).

Step 5: Store the transition. Add \((\phi, a, r, \phi')\) to the replay buffer. If the buffer is full, the oldest entry is removed (FIFO).

Step 6: Sample a mini-batch and update. Sample a mini-batch of transitions from the replay buffer. For each transition in the mini-batch, compute the target \(Y\):

• If the transition ends in a terminal state (game over): \(Y = r\) — there is no future, so the target is just the reward
• Otherwise: \(Y = r + \gamma \max_{a'} Q(s', a'; \theta)\)

The parameters are then updated using gradient descent to minimize the loss between \(Y\) and \(Q(s, a; \theta)\):

\[ \theta \leftarrow \theta + \alpha \left( Y - Q(s, a; \theta) \right) \nabla_\theta Q(s, a; \theta) \]

13.1.6 The Problem with the 2013 DQN — Chasing the Target

The professor's analogy: imagine trying to follow someone who is walking ahead of you, but every time you take a step forward, they also take a step forward. You never catch up, and your path becomes erratic. Applied to Q-learning: an update that increases \(Q(s, a)\) often also increases \(Q(s', a')\) for all \(a'\) — because the same weights serve both states — and therefore increases the target the network is chasing. In the worst case this feedback loop causes oscillations or outright divergence of the parameters, which is why combining Q-learning with neural networks had a reputation for being unstable before DQN.

This instability was a recognized problem in the original 2013 paper, and the 2015 version introduced the fix: a second network whose only job is to compute targets, kept deliberately out of date. That is the subject of the next section.

13.2 Improved DQN (2015) — The Target Network

13.2.1 The fix — a second, frozen network

The 2015 DQN addresses the chasing-the-target problem by introducing a target network — a second Q-network with parameters \(\theta^-\) (theta-minus). The key change is in how the target \(Y\) is computed:

2013 DQN target:

\[ Y = r + \gamma \max_{a'} Q(s', a'; \theta) \]

2015 DQN target:

\[ Y = r + \gamma \max_{a'} \hat{Q}(s', a'; \theta^-) \]

The only difference: the target computation uses \(\hat{Q}\) (the target network) with parameters \(\theta^-\) instead of \(Q\) (the online network) with parameters \(\theta\). Everything else — the replay buffer, the epsilon-greedy action selection, the gradient descent update of the main network — is unchanged.

The target network \(\hat{Q}\) is a copy of the main Q-network, but its parameters are frozen: they are not updated by gradient descent. Every \(C\) steps, the parameters of the target network are updated by copying the current parameters from the main network:

\[ \theta^- \leftarrow \theta \]

This means the target remains stable for \(C\) steps, breaking the feedback loop. The main network can now converge towards a fixed target; only after \(C\) steps does the target shift to a new position. The professor describes the mechanism as "a teeny bit of work" — a single parameter copy every few thousand steps — that improves performance to a great extent. In the 2015 paper, \(C = 10{,}000\) frames.

13.2.2 The two networks at a glance

In the 2013 version, the same Q-network is used everywhere — for action selection and target computation. In the 2015 version:

• The online network \(Q(\cdot; \theta)\) is the "player": it selects actions (via epsilon-greedy) and is updated by gradient descent at every training step.
• The target network \(\hat{Q}(\cdot; \theta^-)\) is the "referee": it is used only for computing targets \(Y\), and it receives a fresh copy of the learned parameters every \(C\) steps.

The target network is therefore always "lagging behind" the main network — deliberately outdated — and precisely this staleness is what stabilizes learning. The professor summarizes: in 2013, one network everywhere; in 2015, a second network for targets that trails the learner.

13.2.3 Student Question — Understanding the Two Networks

13.3 Double DQN (DDQN) — Addressing Maximization Bias

13.3.1 Maximization bias — the professor's analogy

The professor explains maximization bias with a classroom story. A principal asks a professor: "Identify the best student in the class and give me that student's score." The professor looks at all the scores, finds that student Rajamani has the highest score (9.5 out of 10), and reports: "Rajamani is the best, and his score is 9.5." But the principal then conducts an independent evaluation and finds that Rajamani's true score is only 8.

The professor's 9.5 was an overestimate — not because the professor was careless, but because the \(\max\) operator selected Rajamani based on the professor's (noisy) scores. The highest observed score is typically a combination of high true ability plus favorable noise: of all the students, the one with the biggest lucky error is the one who looks like the best. The \(\max\) therefore inherits an upward bias — it is systematically too optimistic about whoever it picks.

13.3.2 The same bias in Q-learning

In Q-learning, the same thing happens. The step \(\max_{a'} Q(s', a')\) does two things simultaneously:

1. Select the action \(a'\) that has the highest estimated Q-value
2. Return that Q-value as the target

If the Q-value estimates are noisy — and they always are, especially early in training — the action selected by \(\max\) is likely the one whose noise happened to be positive, and its inflated Q-value is then used as the target. This is the maximization bias: the max operator overestimates the value of the best action, and the overestimate is fed back into the targets, where it propagates through bootstrapping.

13.3.3 The Double DQN Update

Double DQN decouples the two roles of the \(\max\) operator. Instead of using one network to both select and evaluate the best action, it uses two networks:

Standard DQN target:

\[ Y = r + \gamma \max_{a'} Q(s', a'; \theta) \]

Double DQN target:

\[ Y = r + \gamma Q\left(s', \arg\max_{a'} Q(s', a'; \theta); \theta^-\right) \]

Read the Double DQN expression carefully — it contains the same pieces as standard DQN, just with the selection and evaluation split across two networks:

• The online network \(Q\) with parameters \(\theta\) selects the best action: \(\arg\max_{a'} Q(s', a'; \theta)\) — it finds which action looks best in the next state
• The target network with parameters \(\theta^-\) evaluates that action: \(Q(s', a_{\text{selected}}; \theta^-)\) — it scores the chosen action using the stale, independent snapshot

The professor emphasizes: "Look at this expression. This is the only expression that is different." Compared to the 2015 DQN target \(Y = r + \gamma \max_{a'} \hat{Q}(s', a'; \theta^-)\), Double DQN moves the \(\max\) out and replaces it with an \(\arg\max\) evaluated by the target network. Nothing else changes — same replay buffer, same target refresh schedule, same loss.

13.3.4 Implementation Note — Alternating Networks

In the original Double Q-learning formulation (van Hasselt, 2010, before the deep learning version), two Q-networks are learned separately, each trained on half of the experience. Their roles can alternate: for some number of steps, \(Q\) selects actions and \(Q'\) evaluates them, and then they switch — \(Q'\) selects and \(Q\) evaluates. This is one valid way to implement Double DQN.

However, in practice the more common implementation uses the DQN 2015 framework: the main network learns continuously from the replay buffer, and the target network is a frozen copy refreshed every \(C\) steps. Double DQN simply changes the target computation — the main network does the selecting, the target network does the evaluating — while keeping everything else identical. This is the "minimal possible change" design: it gives most of the benefit of Double Q-learning without adding a third network or changing the training pipeline.

13.4 DQN Summary — Framework, Not Just an Algorithm

The professor makes an important conceptual point: DQN should be understood as more than a step-by-step algorithm. It is a framework established in 2013–2015 that remains relevant today (2025). The specific design choices — the network architecture, the preprocessing pipeline, the replay buffer, the target network — can all be customized with modern techniques while preserving the core DQN learning structure.

For example, the original DQN processed \(84 \times 84 \times 4\) input frames. Modern implementations can use higher-resolution inputs, longer frame histories, or different network architectures (such as attention-based architectures or transformer backbones). The algorithm within the DQN framework still learns Q-values for each action, but the representation of the input and the specific learning steps can be upgraded with state-of-the-art methods.

DQN is fundamentally a value-based algorithm: it learns Q-values (preferences for each action) and then uses those values to select actions, typically via epsilon-greedy. This is the defining characteristic that distinguishes it from the policy-based approaches introduced later in this lecture — value-based methods learn how good each action is and act greedily on that; policy-based methods (section 13.6 onwards) learn how likely each action should be directly.

13.4.1 A practical engineering insight — supervised pre-training

13.4.2 Comparison Table — Three DQN Variants

The professor provided this comparison so students do not need to read all three papers in full — it is the reference sheet for the DQN family. Read it column by column: the 2013 column has one network doing everything; the 2015 column freezes a copy for targets; the Double DQN column keeps that frozen copy but changes only the target formula.

13.4.3 Student Questions and Answers

13.5 Feature Construction in Classical RL

Before introducing policy gradient methods, the professor briefly discusses feature construction methods used in classical reinforcement learning — the era before deep learning made them largely obsolete.

13.5.1 Manual Feature Extraction Methods

In the classical approach, features were not extracted automatically by a neural network. Instead, engineers wrote algorithms to manually analyze the input — such as an image — and extract features: the positions of objects, their shapes, how they are connected, and so on. These features were then represented using various methods:

Polynomial features. Given input features \(x\) and \(y\), a polynomial transformation creates multiple derived features: a bias term (constant 1), \(x\), \(y\), \(xy\), \(x^2\), \(y^2\), and so on for higher degrees. The product terms \(xy\) are what make this powerful: they make interactions between features explicit before the learning algorithm sees the data. In modern deep learning, the network learns these interactions automatically in its hidden layers; in the classical approach, an engineer had to decide in advance which interactions to build.

Fourier basis. Features constructed using sines and cosines of the input variables, \(\sin(kx)\) and \(\cos(kx)\) for various frequencies \(k\). This is the same idea as decomposing a signal into frequencies: smooth functions can be represented well with a few low-frequency basis functions. The agent's value function is then a weighted sum of these basis functions.

13.5.2 Tile Coding (Radial Basis Features)

Tile coding (radial basis): the state space is filled with overlapping circles (tiles). Each circle represents a feature. A point in the state space is described by which circles it falls inside. For example, if a point falls inside circles \(C_7\), \(C_9\), \(C_{21}\), and \(C_{38}\), then the features corresponding to those four circles are active (value 1), and the point's representation is a function of these four features and their corresponding weights.

Concretely, the value of a point is approximated as:

\[ v(s) \approx \sum_{i \in \text{active tiles}(s)} w_i \]

where the sum runs over the tiles containing the point, and each tile \(i\) has a weight \(w_i\) that the learning algorithm adjusts. Because the tiles overlap, nearby points share tiles, so nearby points get similar values — this "sharing" is what makes generalization possible in classical RL. The representation is sparse: with a hundred tiles, each point activates only a handful, so only a few weights need to be examined (and updated) per state.

The professor describes three types of tiles — narrow, medium, and broad — and how they affect the approximation:

• Narrow tiles capture fine details but produce noisy, jagged approximations — like zooming in so far that you see the texture but miss the shape
• Broad tiles produce smooth approximations but are less precise — like squinting so much that details blur
• Medium tiles offer a balance between the two

This is the classical bias–variance trade-off in a spatial disguise: small tiles = low bias, high variance; large tiles = high bias, low variance. The right tile width depends on how smooth the true value function is.

13.5.3 Why Classical Feature Construction Is Obsolete

The features learned by a deep network have two advantages over hand-built ones: they are task-tuned (the network only spends capacity on features that improve Q-value prediction, whereas a hand design must hedge across many possibilities), and they are hierarchical (edges → shapes → objects → abstract game concepts), which matches the structure of visual input.

The reason the lecture briefly covers this material: the textbook (written before the deep learning era) devotes space to these methods, and understanding them helps appreciate why deep learning was such a significant breakthrough for reinforcement learning. The tile-coding discussion is a window into the old world: an entire research field spent on the question "how should we represent a state?" — and the deep learning answer is simply "let the network figure it out."

13.6 Transition to Policy-Based Methods — A New Paradigm

Up to this point, all algorithms discussed follow the same paradigm: compute Q-values for each action, then use those values to select an action (via epsilon-greedy or similar). This is the value-based approach.

The professor now introduces the alternative: instead of computing values and then deriving a policy from those values, the agent directly learns the policy. This is the policy-based approach, and the specific methods for learning the policy are called policy gradient methods. The rest of the lecture is about this paradigm.

13.6.1 The Policy Network

For example, in a game with five actions (up, down, left, right, do nothing), the network might output:

• \(\pi(\text{up} \mid s) = 0.3\)
• \(\pi(\text{down} \mid s) = 0.4\)
• \(\pi(\text{left} \mid s) = 0.1\)
• \(\pi(\text{right} \mid s) = 0.1\)
• \(\pi(\text{do nothing} \mid s) = 0.1\)

These probabilities sum to 1: the output layer uses a softmax activation, which turns any real-valued network outputs into a valid probability distribution. The agent then samples an action from this distribution — it does not pick the argmax; it draws from the distribution, so even the 0.1 actions get tried sometimes, exactly in proportion to their probability.

This is fundamentally different from epsilon-greedy. In epsilon-greedy, one action gets a dominant probability and all others share the remainder equally — the shape of the distribution is rigid. In a policy network, the distribution can have any shape: 0.4/0.3/0.1/0.1/0.1 is a graded preference, not a binary split.

13.6.2 Stochastic Policy vs. Epsilon-Greedy — The Key Distinction

The professor draws a sharp contrast between epsilon-greedy policies and stochastic policies learned by policy networks.

Epsilon-greedy. Suppose the action values are \(Q(\text{up}) = 79\), \(Q(\text{down}) = 76\), \(Q(\text{right}) = 80\), \(Q(\text{left}) = 84\). With \(\epsilon = 0.5\), the greedy action (left) gets probability 0.6, and each non-greedy action gets probability 0.1. At the next step, if \(Q(\text{right})\) becomes 85, there is an abrupt shift — right suddenly becomes the greedy action and gets probability 0.6, while left drops to 0.1. This sudden change in behavior is problematic: a single value crossing a threshold rewrites the entire behavior profile in one step.

Stochastic policy. The policy network might output probabilities like 0.3, 0.4, 0.1, 0.1, 0.1 — a nuanced, graded preference rather than a binary greedy/non-greedy split. As learning progresses, these probabilities change smoothly and gradually — a network weight change shifts all probabilities a little — rather than jumping abruptly when a single value crosses a threshold.

13.6.3 Worked Example — Why Stochastic Policies Can Be Optimal

The professor presents a small grid-world environment, taken from the textbook's classic example, demonstrating that stochastic policies can outperform any deterministic policy.

Environment setup:

• Three states in a line: state 1 (start) → state 2 → state 3 (goal)
• Two actions: left, right
• Each step incurs a reward of \(-1\)
• From state 1, trying to go left keeps the agent in state 1 (wall)
• From states 2 and 3, left and right work normally
• State 2 is adversarial: taking "right" moves the agent left (back to state 1), and taking "left" moves the agent right (toward the goal)
• The agent cannot distinguish which state it is in — all states have identical features (aliasing), so one shared policy must serve all three states

Analysis of deterministic policies:

A "left-greedy" policy (epsilon-greedy with left dominant, e.g., left with probability 0.9, right with 0.1): since the goal is to the right, this policy takes a very long time to reach it — the agent must rely on the small 0.1 probability of pressing right to make any forward progress at all.

A "right-greedy" policy (epsilon-greedy with right dominant): from state 1 it moves right to state 2 quickly. But at state 2, taking right — which happens 90% of the time — sends the agent back to state 1 because of the adversarial flip. This creates a cycle: state 1 → state 2 → state 1 → state 2… The expected value for this policy is approximately \(-55\) steps' worth of reward.

The optimal stochastic policy:

\[ \pi(\text{right} \mid s) = 0.59, \quad \pi(\text{left} \mid s) = 0.41 \]

This balanced policy, learned directly by a policy-based algorithm, reaches the goal in approximately 12–13 steps. It works because:

• From state 1: pressing right (59% of the time) moves to state 2 quickly
• At state 2: pressing right (59% of the time) sends the agent back to state 1 (adversarial flip), but pressing left (41% of the time) sends the agent to state 3 — the goal
• The near-even split means the agent does not get locked into the adversarial state-2 loop: whichever way it is pushed, it has a substantial chance of escaping in the useful direction

The two deterministic policies each fail in a distinct way: left-greedy starves the agent of forward progress (right is the only way out of state 1), while right-greedy feeds the state-2 trap (right is exactly the wrong action there). Only a balance between the two actions — which neither greedy policy can express — threads between the two failure modes.

13.6.4 Benefits of Policy-Based Approaches

The professor summarizes four advantages of policy-based over value-based methods:

1. Better convergence properties. The stochastic policy changes smoothly, avoiding the abrupt preference shifts of epsilon-greedy. This leads to more stable learning — no single threshold crossing can rewrite the whole behavior profile.

1. Natural handling of continuous action spaces. Q-learning requires computing \(\max_{a'} Q(s', a')\), which is only feasible when the action space is discrete and small. Policy-based methods can output the parameters of a continuous distribution — such as the mean and variance of a Gaussian, \(\mathcal{N}(\mu(s), \sigma^2(s))\) — from which the action (a torque, a steering angle) is sampled. This makes them applicable to continuous control tasks like robotic manipulation and autonomous driving, where Q-learning has no practical answer to "max over an infinite set of actions."

1. Domain knowledge incorporation. The policy network directly maps states to action probabilities, a form of knowledge that is intuitive and easy to encode as prior knowledge. For example, a doctor's decision-making can be captured directly as "in this state, the probability of choosing treatment A is 0.7" — and the network can be initialized to reflect exactly that. In contrast, a value-based network outputs Q-values, which are less intuitive and harder to seed with expert knowledge.

1. Can represent stochastic policies. Some problems — like the adversarial state-2 example above — have optimal solutions that are inherently stochastic. Policy-based methods can represent these directly; value-based methods with epsilon-greedy cannot.

13.7 Performance Measure and Policy Gradient Objective

13.7.1 Performance Measure for Episodic Tasks

For episodic tasks (tasks with a clear beginning and end, like playing a game), the performance measure is the expected return from the starting state under the current policy:

\[ J(\theta) = v_{\pi_\theta}(s_0) \]

where:

• \(J(\theta)\) is the performance measure — a scalar that ranks policies: larger \(J\) means better policy
• \(s_0\) is the starting state of the episode
• \(\pi_\theta\) is the policy parameterized by \(\theta\)
• \(v_{\pi_\theta}(s_0)\) (v) is the state-value function — the expected total discounted reward the agent collects from state \(s_0\) onward, following policy \(\pi_\theta\)

In plain words: "If I use policy \(\pi_\theta\) to play the game starting from the initial state, what is my expected total reward?" Note that the value depends on \(\theta\) through the policy: \(J(\theta) = v_{\pi_\theta}(s_0)\) changes only because changing \(\theta\) changes \(\pi_\theta\), which changes the states visited and rewards collected.

To get a reliable estimate of \(J(\theta)\), multiple episodes are played with the current policy and the returns are averaged. This average is the performance measure \(J(\theta)\) — the Monte Carlo estimate. One episode gives a noisy sample; averaging over many episodes shrinks the noise.

13.7.2 Gradient Ascent — Not Descent

In supervised learning, the goal is to minimize a loss function, so we use gradient descent:

\[ \theta \leftarrow \theta - \alpha \nabla_\theta L \]

In policy gradient methods, the goal is to maximize performance \(J(\theta)\), so we use gradient ascent:

\[ \theta \leftarrow \theta + \alpha \nabla_\theta J(\theta) \]

The only difference is the sign — ascent instead of descent. (In practice, most software frameworks minimize, so the objective is typically implemented as the negative of the performance, but conceptually: up is good here.)

The direction of \(\nabla_\theta J(\theta)\) (the gradient — an arrow pointing in the direction of steepest increase of \(J\) in parameter space) tells us which way to change \(\theta\) to improve performance, and its magnitude tells us how much performance responds to changes in \(\theta\). The learning rate \(\alpha\) (alpha) controls the step size: too large and the updates overshoot and oscillate; too small and learning crawls.

13.8 The Policy Gradient Theorem

13.8.1 The Core Challenge

The fundamental difficulty in policy gradient methods is that the parameter \(\theta\) does not directly determine the performance \(J(\theta)\). In supervised learning, changing a weight directly changes the loss — the relationship is immediate and deterministic: loss \(\to\) backprop \(\to\) weight update, all inside one differentiable function. In reinforcement learning, the chain is long:

\[ \theta \;\to\; \text{policy } \pi_\theta \;\to\; \text{action probabilities} \;\to\; \text{sampled actions} \;\to\; \text{trajectory through the environment} \;\to\; \text{(environment's stochastic dynamics)} \;\to\; \text{rewards} \;\to\; J \]

The environment's transition probabilities \(p(s' \mid s, a)\) and reward function \(r(s, a)\) are part of this chain, but they are not differentiable functions we control — they are external black boxes (an emulator, a robot, a simulator). We cannot backpropagate through them.

This means we cannot simply compute \(\nabla_\theta J(\theta)\) by standard backpropagation. We need a way to compute (or approximate) this gradient using only quantities available within the network — probabilities the network itself outputs, and rewards that arrive as observed numbers.

13.8.2 The Theorem Statement

The policy gradient theorem provides an analytic expression for the gradient of the performance measure. It states:

\[ \nabla_\theta J(\theta) \propto \sum_{s} \mu(s) \sum_{a} q_\pi(s, a) \nabla_\theta \pi(a \mid s; \theta) \]

where:

• \(\mu(s)\) (mu) is the state visitation frequency — the fraction of time the agent spends in state \(s\) under policy \(\pi\), which plays the role of a weighting: states visited more often contribute more to the gradient, states visited rarely contribute almost nothing. (Formally, for episodic tasks this is the discounted weighting \(\mu(s)\) of the on-policy state distribution; the subscript is dropped for readability.)
• \(q_\pi(s, a)\) is the action-value function — the expected return when taking action \(a\) in state \(s\) and following policy \(\pi\) thereafter. It is the "quality signal": how good was the choice of action \(a\)?
• \(\nabla_\theta \pi(a \mid s; \theta)\) is the gradient of the policy network's output — the probability of action \(a\) in state \(s\) — with respect to the network parameters \(\theta\). This is computed entirely within the network via backpropagation.

The proportionality sign (\(\propto\)) indicates that the expression is proportional to the true gradient, not equal to it. The constant of proportionality (which involves \(\gamma\), the discount, and normalization factors) is a positive scalar, so it points in the same direction as the true gradient. Since gradient ascent only needs a direction, any quantity pointing the right way is sufficient — the constant is silently absorbed into the learning rate \(\alpha\).

13.8.3 Why This Theorem Matters

The beauty of this expression is that the differentiation \(\nabla_\theta\) applies only to the policy network's parameters. Look at where the gradient symbol sits:

\[ \nabla_\theta J(\theta) \propto \sum_{s} \mu(s) \sum_{a} q_\pi(s, a)\; \nabla_\theta \pi(a \mid s; \theta) \]

The environment dynamics, the state transition probabilities, and the reward function — none of these appear inside a gradient operator. They appear only as multipliers: \(\mu(s)\) and \(q_\pi(s, a)\) are plain numbers (or estimated numbers) sitting outside \(\nabla_\theta\). Everything that needs to be differentiated — \(\pi(a \mid s; \theta)\) — is available within the network.

The professor emphasizes: "There is no aspect outside the network that has to be differentiated. The delta (gradient) applies to parameters of only the network." This is the whole point: the theorem converts "differentiate through the environment" into "multiply the network's own gradient by two numbers we can estimate from experience."

13.9 From Theorem to Algorithm — Deriving the REINFORCE Update

13.9.1 Step 1 — Convert to Expectation

Recognizing that \(\mu(s)\) is the probability of being in state \(s\) under policy \(\pi\) — a probability distribution over states — we can rewrite the sum over states as an expectation:

\[ \nabla_\theta J(\theta) \propto \mathbb{E}_\pi \left[ \sum_{a} q_\pi(s, a) \nabla_\theta \pi(a \mid s; \theta) \right] \]

The professor motivates this with an everyday example: to find the expected height of students in a class, you do not measure every student — you sample students, measure their heights, and average. The sample average approaches the true average as you sample more. Similarly, to compute this expectation we can sample states from the policy (just by playing episodes) and compute the inner sum for each sampled state. We do not need to enumerate all states — we just need enough samples. The states that appear in the sum are naturally weighted by how often the policy visits them, which is exactly what \(\mu(s)\) does.

13.9.2 Step 2 — Remove the Sum Over Actions

The expression still contains a sum over all actions \(\sum_a\), which is undesirable for large action spaces. The professor shows a clever algebraic manipulation: multiply and divide by \(\pi(a \mid s; \theta)\) — a mathematically legal move, since \(\frac{\pi}{\pi} = 1\), but one that re-arranges the expression into the shape of an expectation:

\[ \sum_{a} q_\pi(s, a) \nabla_\theta \pi(a \mid s; \theta) = \sum_{a} \pi(a \mid s; \theta) \cdot q_\pi(s, a) \cdot \frac{\nabla_\theta \pi(a \mid s; \theta)}{\pi(a \mid s; \theta)} \]

Now look at the structure: a sum over actions of "probability \(\pi(a \mid s; \theta)\) times something" — that is precisely the definition of an expectation over \(a \sim \pi\):

\[ = \mathbb{E}_{a \sim \pi} \left[ q_\pi(s, a) \cdot \frac{\nabla_\theta \pi(a \mid s; \theta)}{\pi(a \mid s; \theta)} \right] \]

Since this is an expectation, we do not need to sum over all actions — we can sample one action from the policy and use that single sample as an unbiased estimate of the whole sum. This is the same logic as the class-height example, applied to the action axis: one sampled action, scaled appropriately, replaces the full enumeration.

13.9.3 Step 3 — Apply the Log-Derivative Trick

The term \(\frac{\nabla_\theta \pi(a \mid s; \theta)}{\pi(a \mid s; \theta)}\) is recognized as the gradient of the natural logarithm — the standard identity \(\frac{d}{dx} \ln f(x) = \frac{f'(x)}{f(x)}\):

\[ \frac{\nabla_\theta \pi(a \mid s; \theta)}{\pi(a \mid s; \theta)} = \nabla_\theta \ln \pi(a \mid s; \theta) \]

The professor notes this transformation is done for "mathematical convenience": the ratio of a gradient to a function is awkward to compute and numerically unstable, while the gradient of a log-probability is a clean quantity that deep learning frameworks compute natively and stably. This log-derivative trick has been a standard tool since the early days of machine learning — it appears in many derivations, not just this one.

13.9.4 Step 4 — Replace the Quality Signal

The gradient now reads \(\mathbb{E}[q_\pi(s, a) \nabla_\theta \ln \pi(a \mid s; \theta)]\) — but \(q_\pi(s, a)\), the true action-value, is still unknown. We need a practical estimate of it. In the REINFORCE algorithm (a Monte Carlo policy gradient method), the quality signal is simply the return \(G_t\) — the total discounted reward actually observed from time step \(t\) until the end of the episode:

\[ G_t = \sum_{k=0}^{T-t} \gamma^k r_{t+k} \]

where \(T\) is the final time step of the episode. Because REINFORCE is a Monte Carlo method, it waits until the episode is complete, computes the actual return \(G_t\) for each step, and uses it as the quality signal in place of \(q_\pi(s_t, a_t)\). This replacement is justified: \(G_t\) is an unbiased estimate of \(q_\pi(s_t, a_t)\) — on average it equals the true action-value, because the return is exactly what the action-value is defined to predict. No model of the environment is needed — just the observed rewards.

13.9.5 The Final REINFORCE Update Rule

Combining all the simplifications, the REINFORCE update rule is:

\[ \theta \leftarrow \theta + \alpha \, G_t \, \nabla_\theta \ln \pi(a_t \mid s_t; \theta) \]

where:

• \(\alpha\) is the learning rate (which also absorbs the constant of proportionality from the theorem)
• \(G_t\) is the discounted return from time step \(t\) — the quality signal
• \(\nabla_\theta \ln \pi(a_t \mid s_t; \theta)\) is the gradient of the log-probability of the action that was actually taken, computed via backpropagation

The complete chain of simplifications, in one place:

\[ \begin{aligned} \nabla_\theta J(\theta) &\propto \sum_{s} \mu(s) \sum_{a} q_\pi(s, a) \nabla_\theta \pi(a \mid s; \theta) &&\text{(policy gradient theorem)}\\ &= \mathbb{E}_\pi\left[\sum_{a} q_\pi(s, a) \nabla_\theta \pi(a \mid s; \theta)\right] &&\text{(mu(s) is a distribution over states)}\\ &= \mathbb{E}_{a \sim \pi}\left[q_\pi(s, a) \frac{\nabla_\theta \pi(a \mid s; \theta)}{\pi(a \mid s; \theta)}\right] &&\text{(multiply and divide by } \pi \text{, recognize expectation)}\\ &= \mathbb{E}_{a \sim \pi}\left[q_\pi(s, a) \nabla_\theta \ln \pi(a \mid s; \theta)\right] &&\text{(log-derivative trick)}\\ &\approx G_t \, \nabla_\theta \ln \pi(a_t \mid s_t; \theta) &&\text{(one sample: } a_t \sim \pi,\; G_t \approx q_\pi \text{)} \end{aligned} \]

Each step is reversible and standard; the result is a single-sample estimate of the gradient direction, which gradient ascent turns into the update \(\theta \leftarrow \theta + \alpha G_t \nabla_\theta \ln \pi(a_t \mid s_t; \theta)\).

13.9.6 Interpreting the REINFORCE Update

The update has an intuitive interpretation:

• \(G_t\) measures how good the trajectory turned out to be from step \(t\) onward — the outcome of the experiment
• \(\nabla_\theta \ln \pi(a_t \mid s_t; \theta)\) points in the direction that increases the probability of the action that was taken
• If \(G_t\) is high (good outcome), the update increases the probability of taking action \(a_t\) in state \(s_t\)
• If \(G_t\) is low (poor outcome), the update decreases that probability
• The learning rate \(\alpha\) scales the magnitude of the update

This is a form of trial and error learning reinforced by outcomes — exactly the spirit of reinforcement learning: actions that worked become more likely, actions that failed become less likely, and the direction of adjustment is provided by the network's own gradient.

13.10 Exam Guidance Summary

This section consolidates the professor's explicit exam guidance given during the lecture. It is a summary of what was said — the details behind each bullet live in the corresponding sections above.

13.10.1 DQN Exam Focus

• Focus on the 2015 DQN and DDQN for exams, not the 2013 version (the 2013 version matters as history — its instability motivates everything that follows)
• Bayesian DQN is not required for the exam — it is "nice to know" only
• The specific numerical hyperparameters (filter sizes, buffer capacities, discount factors) are not required to memorize — understand the structure and reasoning instead
• Use the class PPT as the primary reference for exam preparation
• The comparison table of the three DQN variants (section 13.4.1) is valuable for quick revision

13.10.2 Policy Gradient Exam Focus

• The professor will provide one worked numerical example for each algorithm (REINFORCE, REINFORCE with baseline, Actor-Critic) in the next class — students should attempt them and share solutions for group discussion
• The policy gradient theorem — understand its form and its significance, but detailed mathematical proofs are not required
• The stochastic policy example (0.59 vs 0.41 in the adversarial grid world) is important for understanding why policy-based methods can outperform value-based methods

13.11 Key Industry Applications

13.11.1 DQN Framework in Practice

• DQN framework — The DQN architecture (convolutional network + replay buffer + target network) is a foundational framework used in many modern deep RL systems. The specific network architecture and learning steps can be upgraded with state-of-the-art techniques — higher-resolution inputs, attention-based backbones, prioritized replay — while preserving the core DQN structure: learn Q-values from experience, replay them, stabilize with a target.
• Hybrid supervised + RL training — When prior knowledge of action values is available (e.g., from historical data or domain expertise), the DQN can be pre-trained in a supervised manner against those known values and then fine-tuned online through environment interaction. This engineering pattern — warm-start from data, then refine in the field — applies to many real-world problems where pure RL from scratch would be too slow or too unsafe.

13.11.2 Policy Gradient Applications

• Policy gradient methods for continuous control — Robotics, autonomous driving, and other continuous control tasks benefit from policy gradient methods because they naturally handle continuous action spaces (torques, steering angles, throttle values sampled from a parameterized distribution), unlike Q-learning which requires discrete actions to compute \(\max_{a'} Q(s', a')\).
• Domain knowledge integration — Policy networks make it easy to incorporate expert knowledge as prior probability distributions over actions — "in this state, choose treatment A with probability 0.7" — which is useful in medical decision-making, financial trading, and other domains where expert intuition is valuable and data is scarce.

13.12 Named References

13.12.1 Research Papers

• DQN (2013) — original deep Q-learning paper: "Playing Atari with Deep Reinforcement Learning" (Mnih et al.). One of the first and most successful deep reinforcement learning algorithms: it learns to play Atari games from raw pixels with a convolutional network, experience replay, and epsilon-greedy exploration.
• DQN (2015) — improved version with target network: "Human-level control through deep reinforcement learning" (Mnih et al., Nature 518), by the same authors. Introduces the target network and scales to 49 Atari games, reaching a level comparable to a professional human games tester.
• Double DQN — extension addressing maximization bias: "Deep Reinforcement Learning with Double Q-learning" (van Hasselt, Guez & Silver, 2016). Builds on Double Q-learning (van Hasselt, 2010) and adapts it to the deep setting using the existing target network.

13.12.2 Textbooks and Courses

• Sutton and Barto — chapter on policy gradient methods: Reinforcement Learning: An Introduction (Chapter 13) is the source of the policy gradient theorem derivation and the classic stochastic-policy example (the adversarial three-state grid world, Example 13.1); it is the course's core reference.
• Andrew Ng machine learning courses — J(theta) notation convention: referenced for the use of \(J(\theta)\) as the cost/objective function notation, a convention this lecture reuses for the performance measure.