Policy Gradient Methods
14.1 Policy-Based vs. Value-Based Methods
Hook: In all the value-based methods we studied so far — DQN, Double DQN, Dueling DQN — the agent never directly says "do this action." Instead, it estimates how good each action is and then picks the best one. But what if we could skip the middleman and have the agent learn what to do directly?
14.1.1 The Two Paradigms
In value-based reinforcement learning, the primary quantity we estimate is the value of a state or state-action pair — that is, we learn the state-value function \(V(s)\) or the action-value function \(Q(s, a)\). We then use these estimated values to make decisions about which actions to take. DQN (Deep Q-Network) is a classic example: it computes value functions and selects actions by picking the one with the highest estimated Q-value. In that setup, there is no explicit policy gradient theorem — the learning is driven by reducing value error (mean squared value error), which works much like supervised learning.
Policy-based methods take a fundamentally different approach. Instead of estimating values and deriving a policy indirectly, we learn the policy directly. The policy network takes a state representation as input and outputs action probabilities. Concretely, the network produces \(\pi(a \mid s; \theta)\) — the probability of taking action \(a\) given state \(s\), parameterized by \(\theta\). For every possible action \(a\), the network outputs a probability. This is the policy network, and \(\theta\) denotes all of its parameters.
Intuition: Think of it like two ways to decide what to eat for dinner. The value-based approach is like rating every restaurant in town (assigning Q-values) and then picking the highest-rated one. The policy-based approach is like having a friend who just tells you "go to this restaurant" — they have internalized what makes a good choice and skip the explicit rating step.
The key design shift: one network, same state representation in, probability distribution over actions out. No separate value estimation step is needed to select actions — the policy itself tells you what to do.
| Aspect | Value-Based | Policy-Based |
|---|---|---|
| What is learned | \(Q(s, a)\) or \(V(s)\) | \(\pi(a \mid s; \theta)\) directly |
| Action selection | \(\arg\max_a Q(s, a)\) | Sample from \(\pi(a \mid s; \theta)\) |
| Policy type | Deterministic (derived) | Can be stochastic naturally |
| Continuous actions | Hard (need discretization) | Natural (Gaussian output) |
| Convergence | Can oscillate (value estimates → policy changes) | Smoother (direct optimization) |
14.1.2 When Policy-Based Methods Are Preferred
Policy-based methods are especially valuable in three situations:
- Continuous action spaces: When actions are real-valued (like steering angles or joint torques), it is impractical to enumerate all actions and pick the one with the highest Q-value. Learning a policy that directly outputs a continuous action (or a distribution over continuous actions) is far more natural.
- Stochastic policies: Some problems require randomized behavior. For example, in games with imperfect information (like poker), a deterministic policy can be exploited by opponents who can predict your moves. Policy parameterization can naturally represent stochastic strategies — "70% of the time I raise, 30% I fold."
- Complex policy structures: When the best action for a given state is hard to represent as an argmax over a value function, a direct policy representation can be simpler.
The professor's framing: "In many serious problems, it is always good to learn the policy directly. Continuous action spaces, stochastic policies — this is a good idea."
Example — Why continuous actions break value methods: Imagine a robotic arm with 6 joints, each controlled by a torque in the range \([-10, +10]\) Nm. If we discretize each joint into 20 levels, we have \(20^6 = 64\) million actions per state. Computing \(Q(s, a)\) for all of them at every step is impractical. A policy network that directly outputs 6 continuous torques handles this naturally.
14.1.3 The Performance Metric \(J(\theta)\)
When we learn the policy directly, we need a performance metric to maximize. Call it \(J(\theta)\) — a scalar that measures how good the current policy \(\pi_\theta\) is. The goal is to adjust \(\theta\) in the direction that increases \(J(\theta)\). This is stochastic gradient ascent (not descent — we are maximizing, not minimizing), so the update rule has a plus sign:
\[ \theta_{\text{new}} = \theta_{\text{old}} + \alpha \, \nabla_\theta J(\theta) \]
where \(\alpha\) (alpha) is the learning rate and \(\nabla_\theta J(\theta)\) is the gradient of the performance measure with respect to each parameter. If the neural network has a million parameters, we compute the gradient for each one and adjust accordingly.
Key distinction: In supervised learning, we minimize a loss function using gradient descent (minus sign). Here, we maximize a performance measure using gradient ascent (plus sign). The gradient computation itself also differs from supervised learning, for reasons discussed next.
14.1.4 How Policy Gradient Differs from Supervised Learning
Three dimensions separate policy gradient learning from standard supervised learning:
1. Learning objective. In supervised learning, we minimize a loss — we want the network's predictions to match known labels. In policy gradient, we maximize a performance measure — we want the policy to yield higher returns.
2. Nature of the data. In supervised learning, data items are drawn independently from a distribution representing classes. Each sample is unrelated to the next — knowing that image #47 is a cat tells you nothing about image #48. In reinforcement learning, the agent moves through an episode (or ongoing experience), where each step depends strongly on previous steps. If the agent took action "go left" at step 10, the state at step 11 is entirely determined by that choice. The transitions are correlated, not independent.
3. Non-stationarity. In supervised learning, the target distribution is fixed — a cat is always a cat, regardless of how many cats the model has seen. In reinforcement learning, the "good behavior" — the ideal policy — changes over time. As the policy improves, the agent visits different parts of the state space, which changes the distribution of experiences. The target is moving.
The professor summarizes: "In supervised learning, you have data which is drawn from a distribution that represents classes, and you expect each data item to be independent of each other. In Reinforcement Learning, you would actually be going through an episode, where each step depends on the previous steps, strongly correlated."
Professor's analogy for non-stationarity: "What was a good investment a month ago may not be a good investment today. What was appropriate driving behavior in one scenario may not apply in another." The distribution itself keeps shifting as the policy improves and the agent visits different parts of the state space.
Because of these three differences, computing \(\nabla_\theta J(\theta)\) is not the same as computing the gradient of a loss function in a supervised network. The gradient is computed differently when the network serves as a policy network — and the rest of this lecture shows exactly how.
Pitfall — Treating policy gradient like supervised learning: A common mistake is to try to apply standard cross-entropy loss to train a policy network, treating the actions taken in successful episodes as "labels." This ignores the temporal correlation, the non-stationarity, and the fact that the quality signal (return) varies with the action taken — all of which require the specialized policy gradient machinery we develop next.
Recap: Policy-based methods learn \(\pi(a \mid s; \theta)\) directly, bypassing value estimation. They excel in continuous action spaces, stochastic environments, and complex policy structures. The performance metric \(J(\theta)\) is maximized via gradient ascent, and the gradient computation differs fundamentally from supervised learning due to correlated data, non-stationarity, and a different objective. Next, we derive how to compute that gradient — the policy gradient theorem.
14.2 The Policy Gradient Theorem
Hook: We know we want to maximize \(J(\theta)\) by following its gradient. But how do we actually compute \(\nabla_\theta J(\theta)\)? The performance depends on the environment's dynamics, the rewards, and the policy — and we cannot differentiate through the environment. The policy gradient theorem shows us a way around this.
14.2.1 The Theorem
Computing \(\nabla_\theta J(\theta)\) directly is challenging because it involves summing over all states and all actions, weighted by how likely they are under the current policy. The full expression involves the state distribution \(\mu(s)\) (how often state \(s\) is visited under the current policy), the action-value function \(Q_\pi(s, a)\) (how good action \(a\) is from state \(s\) under policy \(\pi\)), and the gradient of the policy \(\nabla_\theta \pi(a \mid s; \theta)\):
\[ \nabla_\theta J(\theta) \;\propto\; \sum_{s} \mu(s) \sum_{a} Q_\pi(s, a) \, \nabla_\theta \pi(a \mid s; \theta) \]
This is the policy gradient theorem (Sutton et al., 1999). The professor's verbal description: "The gradient of performance measure with respect to theta is directly proportional to a particular quantity, in which the gradient has to be performed only on the network."
What the theorem says: To improve the policy, for each state \(s\), weight the gradient of each action's probability by how good that action is (measured by \(Q_\pi(s, a)\)), then average over all states weighted by how often they are visited (\(\mu(s)\)). Actions with high Q-values get their probabilities pushed up; actions with low Q-values get pushed down.
14.2.2 Full Derivation from First Principles
The policy gradient theorem can be derived rigorously. Here is the complete derivation, following the standard approach from the reference texts.
Starting point — the objective function. The performance of a policy \(\pi_\theta\) is the expected return over all trajectories \(\tau\) generated by that policy:
\[ J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)] = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum_{t=0}^{T} \gamma^t r_t\right] \]
where a trajectory \(\tau = s_0, a_0, r_0, s_1, a_1, r_1, \ldots, s_T, a_T, r_T\).
The problem. We want \(\nabla_\theta J(\theta)\), but we cannot differentiate \(R(\tau)\) with respect to \(\theta\) — the rewards \(r_t\) come from the environment's reward function \(\mathcal{R}(s_t, a_t, s_{t+1})\), which is a black box we cannot differentiate through. The only way \(\theta\) influences \(R(\tau)\) is by changing which states and actions are visited.
Step 1 — Rewrite as an integral. Using the definition of expectation:
\[ \nabla_\theta J(\theta) = \nabla_\theta \int p(\tau \mid \theta) \, R(\tau) \, d\tau \]
where \(p(\tau \mid \theta)\) is the probability of trajectory \(\tau\) under policy \(\pi_\theta\).
Step 2 — Bring the gradient inside. Since the integral is over \(\tau\) and the gradient is over \(\theta\), we can swap them:
\[ \nabla_\theta J(\theta) = \int \nabla_\theta p(\tau \mid \theta) \, R(\tau) \, d\tau \]
Step 3 — Apply the log-derivative trick. We use the identity:
\[ \nabla_\theta p(\tau \mid \theta) = p(\tau \mid \theta) \, \nabla_\theta \ln p(\tau \mid \theta) \]
This identity holds because \(\nabla_\theta \ln p = \frac{\nabla_\theta p}{p}\), so multiplying both sides by \(p\) gives \(\nabla_\theta p = p \, \nabla_\theta \ln p\). Substituting:
\[ \nabla_\theta J(\theta) = \int p(\tau \mid \theta) \, \nabla_\theta \ln p(\tau \mid \theta) \, R(\tau) \, d\tau = \mathbb{E}_{\tau \sim \pi_\theta}\left[R(\tau) \, \nabla_\theta \ln p(\tau \mid \theta)\right] \]
Step 4 — Expand the trajectory probability. A trajectory is a sequence of state-action transitions. The probability of the whole trajectory is the product of the individual transition probabilities:
\[ p(\tau \mid \theta) = \prod_{t \geq 0} p(s_{t+1} \mid s_t, a_t) \, \pi_\theta(a_t \mid s_t) \]
Taking the logarithm:
\[ \ln p(\tau \mid \theta) = \sum_{t \geq 0} \left[\ln p(s_{t+1} \mid s_t, a_t) + \ln \pi_\theta(a_t \mid s_t)\right] \]
Step 5 — Take the gradient. Applying \(\nabla_\theta\) to both sides:
\[ \nabla_\theta \ln p(\tau \mid \theta) = \sum_{t \geq 0} \nabla_\theta \ln \pi_\theta(a_t \mid s_t) \]
The term \(\ln p(s_{t+1} \mid s_t, a_t)\) disappears because the environment's transition dynamics do not depend on \(\theta\) — its gradient is zero.
Step 6 — Combine. Substituting back into the expectation:
\[ \nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\left[\sum_{t=0}^{T} R(\tau) \, \nabla_\theta \ln \pi_\theta(a_t \mid s_t)\right] \]
This can be shown to be proportional to the expression in the theorem. Using the return from time step \(t\) instead of the full trajectory return, and using Monte Carlo sampling, we get the practical REINFORCE update.
Why this matters — the scope of the gradient: The critical insight is that \(\nabla_\theta\) is applied only to the policy network \(\pi_\theta(a_t \mid s_t)\). Everything outside the network — the environment's transition probabilities \(p(s_{t+1} \mid s_t, a_t)\), the reward function, the model dynamics — vanishes during differentiation. We do not need to know or model the environment. We only need to compute derivatives through the policy network itself.
The professor explains: "The good thing about policy gradient theorem is the gradient operation is applied to those elements of network, and the scope is entirely within the network. There is nothing outside. For example, model dynamics — you don't really care for all that. Anything that actually happens outside the network doesn't really influence this gradient."
14.2.3 Why the Theorem Matters
The policy gradient theorem is the foundation of all policy gradient methods. It converts an impossible problem (differentiating through the environment) into a tractable one (differentiating through the policy network only).
The log-derivative trick in one sentence: By writing \(\nabla_\theta p = p \cdot \nabla_\theta \ln p\), we turn a gradient of a probability into an expectation that can be estimated from samples — the environment's dynamics cancel out entirely.
14.2.4 Why Direct Implementation Is Still Impractical
Even with the theorem, directly implementing this expression is impractical. It requires summing over all states and all actions. If there are a million states and a million actions, the double sum has a trillion terms. This is not feasible in a data-driven setup where we interact with the environment step by step.
The professor asks: "Should I actually be doing summing over all the states, summing over all the actions? For example, there are a million states, million actions, million into million into... This expression is still difficult for us to directly implement."
Scope — when the theorem applies and when it breaks:
- Applies when the policy \(\pi_\theta(a \mid s)\) is differentiable with respect to \(\theta\) — this is the core requirement.
- Applies regardless of the environment's dynamics (model-free).
- Breaks if the policy has non-differentiable components (e.g., hard argmax without softmax relaxation).
- Breaks if actions are discrete and we try to differentiate with respect to the action itself (the gradient is with respect to \(\theta\), not \(a\)).
What we need is a sample-driven simplification — one that uses the agent's actual experience (a single episode or a single step) rather than exhaustively enumerating the state-action space. This leads to the REINFORCE algorithm.
Recap: The policy gradient theorem gives us \(\nabla_\theta J(\theta) \propto \sum_s \mu(s) \sum_a Q_\pi(s,a) \nabla_\theta \pi(a|s;\theta)\). The gradient applies only to the policy network — the environment's dynamics vanish. But the double sum over all states and actions is still impractical. Next: REINFORCE converts this into a sample-based update using actual episode experience.
14.3 The REINFORCE Algorithm
Hook: The policy gradient theorem tells us what to compute, but its double sum over all states and actions is impractical. REINFORCE (Williams, 1992) was the first algorithm to convert this theorem into a practical, sample-based update rule using actual experience.
14.3.1 The Simplified Update Rule
REINFORCE solves the practical problem of estimating the policy gradient from real experience rather than exhaustive enumeration. It is a MC policy gradient approach — it waits for a full trial to complete, obtains the quality signal from each step, and uses those signals to update the policy.
The key simplification: instead of summing over all states and actions, we use the discounted cumulative reward \(G_t\) from the current time step as the quality signal. The update becomes:
\[ \theta_{t+1} = \theta_t + \alpha \, G_t \, \nabla_\theta \ln \pi(A_t \mid S_t; \theta) \]
where:
- \(\theta_t\) are the current policy parameters (all the weights and biases of the neural network)
- \(\alpha\) (alpha) is the learning rate — a small positive scalar controlling step size
- \(G_t\) is the discounted cumulative reward from time step \(t\) — the total discounted reward from that point to the end: \(G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots\)
- \(A_t\) is the action actually taken at time \(t\)
- \(S_t\) is the state at time \(t\)
- \(\nabla_\theta \ln \pi(A_t \mid S_t; \theta)\) is the gradient of the log-probability of the taken action with respect to the parameters
How we get here from the theorem. The professor's derivation: the original complicated expression (summing over all states and actions) simplifies to "G_T multiplied by the gradient of the PI network divided by the probability of the action taken in state S." Then, using the identity \(\frac{\nabla_\theta \pi}{\pi} = \nabla_\theta \ln \pi\) (because \(\frac{d}{dx} \ln f(x) = \frac{f'(x)}{f(x)}\)), the fraction collapses into the natural logarithm form.
The professor notes: "Delta X by X is Delta LNX. That's what happened here. This fraction is actually returned in a pretty compact manner."
The log-derivative trick applied: Starting from \(\nabla_\theta \pi(a \mid s; \theta)\), we multiply and divide by \(\pi\):
\[ \nabla_\theta \pi(a \mid s; \theta) = \pi(a \mid s; \theta) \cdot \frac{\nabla_\theta \pi(a \mid s; \theta)}{\pi(a \mid s; \theta)} = \pi(a \mid s; \theta) \cdot \nabla_\theta \ln \pi(a \mid s; \theta) \]
The \(\pi\) in the numerator cancels with the sampling probability, leaving just \(\nabla_\theta \ln \pi\).
14.3.2 The Role of the Return \(G_t\)
The quantity \(G_t\) serves as the action quality signal — it tells the algorithm how good the taken action was. If the quality signal from a particular step is high (say, 100), the update strongly reinforces the action that was taken. If it is low or negative, the update pushes the policy away from that action.
The professor explains the intuition: "G is the action quality signal. How good is the action taken? How bad is action taken? That depends on G."
Intuition: Think of \(G_t\) as a "report card" for the action taken at step \(t\). If the agent took action "go left" and then went on to earn 100 total reward, that action gets a high report card score. If it earned only 2 reward, the score is low. The policy adjusts to make high-scoring actions more likely and low-scoring actions less likely.
14.3.3 Why Dividing by the Action Probability Helps
The update includes \(\nabla_\theta \ln \pi(A_t \mid S_t; \theta)\), which implicitly divides by \(\pi(A_t \mid S_t; \theta)\). This normalization matters for balance across actions:
- High-probability action: The action is taken frequently, so the policy keeps getting updated in its favor again and again. Dividing by a large probability (close to 1) keeps the update moderate, preventing runaway reinforcement.
- Low-probability action: The action is rarely encountered. When it does occur, the return might be very high. Dividing by a small probability amplifies the update, ensuring a meaningful learning signal even for rare actions.
The professor explains: "If the probability of an action is so high, you will keep that action so many number of times. Again and again, you actually keep an update that would bias that particular action comparing to others. So I'm just normalizing it."
Concrete example: Suppose action \(a_1\) has probability \(\pi(a_1 \mid s) = 0.9\) and action \(a_2\) has probability \(\pi(a_2 \mid s) = 0.1\). If both earn the same return \(G = 50\):
- Update from \(a_1\): \(50 \times \frac{\nabla_\theta \pi(a_1)}{0.9}\) — moderate (divided by large probability)
- Update from \(a_2\): \(50 \times \frac{\nabla_\theta \pi(a_2)}{0.1}\) — amplified 9× (divided by small probability)
This ensures that rare but valuable actions get a strong learning signal when they do occur.
14.3.4 REINFORCE Algorithm Steps
The full algorithm, following the procedural spine:
Inputs:
- A differentiable policy parameterization \(\pi(a \mid s; \theta)\) — the policy network
- Learning rate \(\alpha\)
- Discount factor \(\gamma\)
Outputs:
- Updated policy parameters \(\theta\) that (hopefully) yield higher returns
Steps:
- Initialize policy parameters \(\theta\) (for example, all zeros, or small random values like 0.5, 0.25)
- Repeat forever:
- Generate a complete trial \(S_0, A_0, R_1, S_1, A_1, R_2, \ldots, S_{T-1}, A_{T-1}, R_T\) following \(\pi_\theta\)
- For each step \(t = 0, 1, \ldots, T-1\) in the trial:
- Compute the cumulative discounted reward \(G_t = \sum_{k=t+1}^{T} \gamma^{k-t-1} R_k\)
- Update: \(\theta \leftarrow \theta + \alpha \, G_t \, \nabla_\theta \ln \pi(A_t \mid S_t; \theta)\)
Key point: REINFORCE is an MC method. It requires the complete trial to be finished before any updates, because \(G_t\) needs all future rewards.
Pitfall — REINFORCE is on-policy: The trajectory must be generated by the current policy \(\pi_\theta\). You cannot reuse old trajectories from a previous policy. After updating \(\theta\), the old trajectory is stale — it was generated by the old policy, not the new one.
14.3.5 Simple Policy Parameterization Example
The simplest policy parameterization is a linear model: \(\pi(a \mid s; \theta)\) uses \(\theta^\top \mathbf{x}(s)\), where \(\mathbf{x}(s)\) is the feature representation of state \(s\).
For example, if a state is represented by two coordinates \((x_1, x_2)\), then \(\theta^\top \mathbf{x}(s) = \theta_1 x_1 + \theta_2 x_2\).
The professor walks through this: "If your X has got two coordinates, say X1 and X2, each state can be represented by X and Y coordinate. So this X's will have X1 and X2. In such case, Theta transpose XS could be Theta 1 X1 plus Theta 2 X2."
This can be as simple or as complex as needed — it could be a single linear function or a deep neural network with millions of parameters. The algorithm is the same; only the parameterization changes.
14.3.6 Worked Walkthrough of a REINFORCE Episode
Full worked example with real numbers:
Step 1 — Initialize parameters: Say \(\theta_1 = 0.5\), \(\theta_2 = 0.25\). The state representation might be coordinates like (20, 30).
Step 2 — Compute action probability: The raw score is \(\theta^\top \mathbf{x}(s) = 0.5 \times 20 + 0.25 \times 30 = 10 + 7.5 = 17.5\). This is much larger than 1, so a softmax function converts it to probabilities. For two actions, \(\pi(a_1 \mid s) = \frac{e^{17.5}}{e^{17.5} + e^{7.5}} \approx 0.9999\). (In practice, the network learns representations that produce more balanced logits.)
Step 3 — Generate a trial following the policy: Starting from state \(S_0\), use the policy probabilities to sample actions. Execute each action, observe the reward and next state.
Step 4 — Suppose the sequence is: \(S_0, A_0, R_1 = 10, S_1, A_1, R_2 = 15, S_2\) (terminal). With \(\gamma = 1\):
Step 5 — Update from step 0: The return from \(S_0\) is \(G_0 = R_1 + R_2 = 10 + 15 = 25\). Update: \(\theta \leftarrow \theta + \alpha \times 25 \times \nabla_\theta \ln \pi(A_0 \mid S_0; \theta)\)
Step 6 — Update from step 1: The return from \(S_1\) is \(G_1 = R_2 = 15\). Update: \(\theta \leftarrow \theta + \alpha \times 15 \times \nabla_\theta \ln \pi(A_1 \mid S_1; \theta)\)
Step 7 — Repeat: Generate the next trial and continue updating.
Sense-check: Step 0 got a higher return (25 > 15), so its update should be stronger. Actions taken earlier in successful trials are reinforced more because they "caused" more of the total reward.
The professor: "Once you have the full episode, you start making update from the beginning. For each step, you go and update the parameter for this episode. Once you complete it, you go back to the beginning, generate the next episode, and you keep learning the parameters."
Q: For this REINFORCE, we use MC (Monte Carlo), which means we have to generate the full trial, or at least a set of trials, and then you operate with the computed G values?
A: Exactly. You need the full trial. You generate the full trial, and then you start from the beginning of the trial and keep updating the parameters. Because you have to compute G.
14.3.7 Learning Rate Sensitivity: The Crazy Corridor Domain
The professor discusses a specific test domain called the crazy corridor to illustrate how sensitive REINFORCE is to the learning rate \(\alpha\). In this domain, there are states where the transitions are "crazy" — at some states, moving left takes you right, and moving right takes you left. This reversal makes the problem tricky.
Key observation from the performance plot: Three different learning rates produce very different outcomes:
- \(\alpha = 2^{-13}\): Performance improves well. The return approaches \(-10\), meaning the agent reaches the goal within about 10 steps from the starting state. A good policy is found.
- \(\alpha = 2^{-4}\): Learning is slow but eventually picks up.
- \(\alpha = 2^{-12}\): Performance saturates — the policy is not good enough.
The professor's takeaway: "With the right sort of learning rate, you get a better performance. The key aspect here is getting the right sort of learning parameters, which you need to experiment. There is an analytic expression that you actually can use to make an initial guess of this learning rate, and then you actually need to experiment."
Exam note: Getting the right hyperparameters (especially the learning rate) for REINFORCE requires experimentation. There is no single formula that works for all problems. The crazy corridor domain demonstrates that even small changes in \(\alpha\) can dramatically affect convergence.
14.3.8 Complexity and Practical Considerations
Time cost: Each episode requires \(T\) forward passes through the policy network (to sample actions) and \(T\) backward passes (to compute gradients). The total cost per episode is \(O(T \cdot d)\) where \(d\) is the number of parameters.
Space cost: We must store the entire episode (all states, actions, rewards) until the episode ends, because we need to compute \(G_t\) for every step. This is \(O(T)\).
When to use REINFORCE:
- Episodic tasks (must have a terminal state)
- Simple environments where full episodes are cheap
- When an unbiased estimate is important
When NOT to use REINFORCE:
- Continuing (non-episodic) tasks — no terminal state, so \(G_t\) is infinite
- Very long episodes — high variance in \(G_t\)
- When fast convergence is critical — use actor-critic instead
Recap: REINFORCE converts the policy gradient theorem into a practical sample-based update: \(\theta \leftarrow \theta + \alpha G_t \nabla_\theta \ln \pi(A_t \mid S_t; \theta)\). The return \(G_t\) acts as the action quality signal. The log-probability gradient normalizes updates across actions of different probabilities. REINFORCE is Monte Carlo (needs full episodes), on-policy (cannot reuse old data), and sensitive to learning rate. Next: reducing its high variance with a baseline.
14.4 REINFORCE with Baseline
Hook: REINFORCE works, but its gradient estimates have high variance — the return \(G_t\) can swing wildly between episodes, making learning unstable and slow. Can we reduce this variance without changing the direction the policy is learning? Yes, by subtracting a baseline.
14.4.1 The Problem: High Variance in REINFORCE
REINFORCE suffers from high variance in its gradient estimates. The raw return \(G_t\) can fluctuate wildly between episodes because:
- Actions are sampled from a probability distribution (randomness in behavior)
- The starting state may vary per episode
- The environment's transition function may be stochastic
This means the same action in the same state might earn very different returns across episodes, leading to noisy gradient estimates and unstable learning.
14.4.2 The Modified Update Rule
The only change: replace \(G_t\) with \(G_t - b(S_t)\):
\[ \theta_{t+1} = \theta_t + \alpha \, \bigl(G_t - b(S_t)\bigr) \, \nabla_\theta \ln \pi(A_t \mid S_t; \theta) \]
where \(b(S_t)\) is a baseline — a function of the state only, not of the action taken.
The professor explains the simplicity of the change: "I am going to replace this G with G minus B of T. I'm not going to change the algorithm by so much. I am going to replace this G with exactly put this quantity in bracket and insert there."
14.4.3 Why the Baseline Does Not Change the Gradient Direction
This is a critical mathematical result. Subtracting a state-dependent baseline does not alter the expected gradient direction. Here is the complete proof:
Claim: \(\mathbb{E}\left[b(S_t) \, \nabla_\theta \ln \pi(A_t \mid S_t; \theta)\right] = 0\)
Proof:
\[ \begin{aligned} \mathbb{E}\left[b(S_t) \, \nabla_\theta \ln \pi(A_t \mid S_t; \theta)\right] &= \sum_s \mu(s) \, b(s) \sum_a \pi(a \mid s; \theta) \, \nabla_\theta \ln \pi(a \mid s; \theta) \\ &= \sum_s \mu(s) \, b(s) \sum_a \pi(a \mid s; \theta) \, \frac{\nabla_\theta \pi(a \mid s; \theta)}{\pi(a \mid s; \theta)} \\ &= \sum_s \mu(s) \, b(s) \sum_a \nabla_\theta \pi(a \mid s; \theta) \\ &= \sum_s \mu(s) \, b(s) \, \nabla_\theta \underbrace{\sum_a \pi(a \mid s; \theta)}_{= 1} \\ &= \sum_s \mu(s) \, b(s) \, \nabla_\theta (1) \\ &= 0 \end{aligned} \]
The key step: since probabilities sum to 1 for any state, \(\sum_a \pi(a \mid s; \theta) = 1\), and the gradient of the constant 1 is zero.
The professor walks through this carefully: "For all a, pi of a given S — if you are in a state S, assume there are four actions, the probability of each action can be different: 0.7, 0.1, 0.1, but when I actually sum it, it will be one. So this term will be one. And that makes gradient of 1, gradient of 1 is 0."
Professor's cricket analogy: "Think of it — when India plays against a team, you would judge the winning depending on with whom you are performing. Are you playing against Australia or against a new team? You compare your performance with a baseline." The baseline provides context without distorting the learning direction.
Intuition with numbers: Suppose in state \(s\), there are 3 actions with probabilities \([0.7, 0.2, 0.1]\). The baseline \(b(s) = 50\). The extra update term is:
\(-50 \times [0.7 \nabla \ln 0.7 + 0.2 \nabla \ln 0.2 + 0.1 \nabla \ln 0.1]\)
This simplifies to \(-50 \times \nabla_\theta(0.7 + 0.2 + 0.1) = -50 \times \nabla_\theta(1) = 0\).
The baseline adds nothing to the expected gradient — it only changes the variance of individual samples.
14.4.4 What Makes a Good Baseline
The baseline \(b(s)\) must satisfy one strict requirement: it must not depend on the action. It is a function of the state only.
Professor's classroom analogy: "A teacher evaluates 100 students. I set a paper and expect the class average to be about 70%. A student scored 90%. I measure your performance with respect to the class average. That is a baseline. But if I say Raja scored 90, and I expect somebody else to score 85, how was he scoring with respect to him? That is not a baseline — you are comparing with a specific other person."
If the baseline depended on the action, it would not factor out of the gradient sum, and the zero-gradient proof above would fail. The baseline would then distort the gradient direction.
The most useful baseline choice: the value of the state \(V_\pi(s)\). This is the expected return from state \(s\) under the current policy — the "average" performance you expect from that state. Using \(V_\pi(s)\) as the baseline gives us the advantage function.
Scope — baseline requirements:
- \(b(s)\) must be a function of state only, not action
- \(b(s)\) can be anything (constant, learned, hand-designed) as long as it doesn't depend on action
- Using \(V_\pi(s)\) is optimal in the sense of minimizing variance (among baselines that don't depend on action)
- If \(b\) depended on \(a\), the proof breaks and the gradient direction is corrupted
14.4.5 The Advantage Function
When the baseline is \(V_\pi(s)\), the quantity \(Q_\pi(s, a) - V_\pi(s)\) has a special name: the advantage function.
\[ A^\pi(s, a) = Q_\pi(s, a) - V_\pi(s) \]
The advantage function measures how much better (or worse) action \(a\) is compared to the average action in state \(s\). It answers: "Compared to what I normally expect from this state, how much extra value does this specific action give me?"
The professor uses vivid examples to explain:
- "A state whose value is 100. You gain 200, so the advantage is 100."
- "A state whose expected value is only 2. The value of taking an upper action is 150. So the advantage is 148."
Professor's analogy for advantage: "I thought you were only capable of doing this, but you did so and so. You are measuring certain things with what is expected of you and what you have done. It is benchmarked with what you think someone is capable of."
The advantage function puts actions in context. A raw Q-value of 100 means very different things depending on whether the state's average value is 2 or 95. The advantage strips away the baseline and isolates the extra quality of the specific action.
Key property of the advantage: \(\mathbb{E}_{a \sim \pi}[A^\pi(s, a)] = 0\). The expected advantage of any action under the current policy is zero — by definition, the average action has zero advantage. This means:
- If all actions are essentially equivalent, the advantage is 0 for all of them, and no action gets reinforced over others.
- If an action is worse than average but still has positive Q-value, the advantage correctly identifies it as suboptimal.
This function is used very frequently in policy gradient methods going forward.
14.4.6 Worked Example: Advantage in Different States
State \(s_1\) — a favorable state: Four actions with Q-values:
- Left: 400
- Down: 300
- Right: 200
- Up: 100
The state value \(V_\pi(s_1) = \mathbb{E}[Q_\pi(s_1, a)] = \frac{400 + 300 + 200 + 100}{4} = 250\) (assuming uniform policy for simplicity; with the actual policy probabilities, it would be the weighted average).
Actually, let us use the professor's stated value: \(V_\pi(s_1) = 200\).
Advantages:
- Left: \(400 - 200 = \mathbf{200}\) (200 more than expected — strongly reinforce!)
- Down: \(300 - 200 = \mathbf{100}\) (100 more than expected — reinforce)
- Right: \(200 - 200 = \mathbf{0}\) (exactly average — no change)
- Up: \(100 - 200 = \mathbf{-100}\) (100 less than expected — discourage)
State \(s_2\) — a difficult state: The best expected return is only about 30. Actions:
- Up: 150
- Right: 20
- Down: 5
- Left: \(-100\)
The state value \(V_\pi(s_2) = 30\).
Advantages:
- Up: \(150 - 30 = \mathbf{120}\) (extraordinary for this state!)
- Right: \(20 - 30 = \mathbf{-10}\) (slightly below average)
- Down: \(5 - 30 = \mathbf{-25}\) (poor)
- Left: \(-100 - 30 = \mathbf{-130}\) (terrible)
Sense-check: In state \(s_1\), even a "bad" action (Up, Q=100) looks reasonable in absolute terms — it's still a positive reward. In state \(s_2\), the same raw Q-value (100) would be extraordinary. The advantage normalizes the scale, letting us compare actions across states on a common scale. An action with advantage +120 in \(s_2\) is more "surprising" than an action with advantage +100 in \(s_1\).
14.4.7 REINFORCE with Baseline Algorithm
The algorithm now learns two networks simultaneously:
- Policy network \(\pi(a \mid s; \theta)\) — parameters \(\theta\)
- Value network \(V(s; w)\) — parameters \(w\), which provides the baseline
Inputs: Two step sizes — \(\alpha_\theta\) for the policy network, \(\alpha_w\) for the value network
Steps:
- Initialize policy parameters \(\theta\) and value parameters \(w\)
- Repeat forever:
- Generate a complete episode following \(\pi_\theta\)
- For each step \(t = 0, 1, \ldots, T-1\):
- Compute the return \(G_t\)
- Compute the advantage (delta): \(\delta_t = G_t - V(S_t; w)\)
- Update value parameters: \(w \leftarrow w + \alpha_w \, \gamma^t \, \delta_t \, \nabla_w V(S_t; w)\)
- Update policy parameters: \(\theta \leftarrow \theta + \alpha_\theta \, \gamma^t \, \delta_t \, \nabla_\theta \ln \pi(A_t \mid S_t; \theta)\)
The professor draws attention to the two different update rules: "Look at the update to value W and update to theta very closely. The value network is not learning policy, so it does not use policy gradient theorem. The PI Network is a policy network, so this actually uses update as per the policy gradient."
Why both updates use \(\delta_t\): The advantage \(\delta_t = G_t - V(S_t; w)\) appears in both updates, but for different reasons:
- Policy update: Uses the policy gradient theorem. \(\delta_t\) acts as the quality signal — positive advantage means "this action was better than expected, make it more likely."
- Value update: Uses standard gradient descent on squared error. A positive \(\delta_t\) means the value estimate was too low (the agent did better than expected), so the value should increase — and vice versa.
14.4.8 Why Learn Both Simultaneously?
A natural question: if we already knew the value of every state, we would not need the value network. But we do not know \(V_\pi(s)\) at the start. Learning it from scratch before using it as a baseline would require running the algorithm many times first, which defeats the purpose.
The professor addresses this: "I don't know the value of each state to begin with. So what does it actually mean? It means I have to learn the baseline simultaneously."
So REINFORCE with baseline iteratively refines both the value estimate and the policy parameters. As the policy improves, the values change; as the values become more accurate, the baseline becomes better at reducing variance.
14.4.9 Convergence Properties
REINFORCE with baseline converges to at least a local optimum because the baseline does not change the expected gradient (as proven above). It is an unbiased estimate. The variance reduction from the baseline makes convergence faster and more stable, but it introduces a second learning rate that must be calibrated.
The professor notes: "Calibrating the right hyperparameter itself will take its own time. What is actually displayed is for only the two best learning rates."
14.4.10 Student Questions and Answers
Q: So for REINFORCE with baseline, we are learning both the value and the policy. If I just know the value of each state, should I still learn policy?
A: Value of a state is not enough to learn the policy. You want \(Q(s, a)\), not \(V(s)\). In serious problems, \(V(s)\) is not enough to get the policy. If you have only \(V(s)\), you need model dynamics to decide the policy. Simply learning \(V(s)\) is not going to help getting the policy in real problems. But if you are learning the Q function, you can learn the policy. If you derive a policy from Q, it has its own disadvantages (as discussed in earlier lectures on value-based methods).
Pitfall — Confusing \(V(s)\) with \(Q(s,a)\): \(V(s)\) tells you how good a state is on average under the current policy. \(Q(s,a)\) tells you how good a specific action is from that state. To derive a policy from \(Q\), you take \(\arg\max_a Q(s,a)\). To derive a policy from \(V\), you need the environment's transition model — which we typically don't have.
Recap: REINFORCE with baseline subtracts a state-dependent baseline \(b(s)\) from the return, reducing variance without changing the expected gradient direction (proven via \(\sum_a \nabla_\theta \pi = 0\)). The best baseline is \(V_\pi(s)\), giving the advantage function \(A^\pi(s,a) = Q_\pi(s,a) - V_\pi(s)\). The algorithm learns two networks (policy + value) simultaneously. It is still Monte Carlo (needs full episodes) and still on-policy. Next: Actor-Critic methods replace Monte Carlo returns with bootstrapped TD estimates.
14.5 Actor-Critic Methods
Hook: REINFORCE with baseline reduces variance by subtracting \(V(s)\) from the return, but it still waits for the full episode to compute \(G_t\). What if we could update during the episode, step by step, without waiting? Actor-critic methods achieve this by replacing the Monte Carlo return with a bootstrap estimate.
14.5.1 What Are the Actor and Critic?
Actor: The policy network \(\pi(a \mid s; \theta)\). It decides what action to take. "The policy decides, suggests what action to take in a given environment."
Critic: The value network \(V(s; w)\). It evaluates how good the current state is. "In every state, this person will say, how good are you? How bad are you? It criticizes the state you are in."
The actor and critic are two separate networks that are learned jointly. The actor uses the critic's evaluation to improve its decisions.
14.5.2 Why REINFORCE with Baseline Is NOT Actor-Critic
This is a subtle but important distinction that the professor emphasizes.
The key difference: In REINFORCE with baseline, the value function serves only as a normalizer for the quality signal. It subtracts a baseline from \(G_t\), but it does not change which actions are taken. The actor does not use the critic's feedback when deciding what to do.
The professor clarifies: "A critic becomes a critic if the actor takes it into consideration taking action. If the actor takes critic's input actively in deciding what to do, that's when it actually becomes actor-critic."
In actor-critic methods, the critic's value estimate is embedded in the quality signal itself. Instead of using the full Monte Carlo return \(G_t\), we use a bootstrap estimate that includes the critic's prediction about the next state. This means the critic directly influences the learning signal for the actor.
| Aspect | REINFORCE with Baseline | Actor-Critic |
|---|---|---|
| Quality signal | \(G_t\) (full Monte Carlo return) | \(R_{t+1} + \gamma V(S_{t+1}; w)\) (bootstrap) |
| Baseline | \(b(S_t) = V(S_t; w)\) subtracted from \(G_t\) | Embedded in the TD error |
| Critic's role | Passive normalizer | Active participant in quality signal |
| Update timing | End of episode | Each step (online) |
14.5.3 The Bootstrap Quality Signal
In actor-critic, the quality signal for an action taken in state \(s\) is:
\[ R_{t+1} + \gamma \, V(S_{t+1}; w) \]
This is a one-step bootstrap: the immediate reward plus the critic's estimate of how good the next state is. Compare this to REINFORCE's \(G_t\), which sums all future rewards to the end of the episode.
The professor explains the motivation: "Don't use Monte Carlo because G_T has high variance — it uses whatever you receive after the current step, sum of all, as the quality signal. Instead, use a bootstrap. This is the place I would use a bootstrap value."
Intuition: Imagine you're evaluating a chess move. REINFORCE says: "Play the entire game to the end, then come back and judge this move." Actor-critic says: "Make the move, see the immediate effect, and ask the critic how good the resulting position is." The second approach is faster but relies on the critic's accuracy.
The bootstrap reduces variance (we are not waiting for the full episode) at the cost of some bias (the critic's estimate may be wrong). This tradeoff is the hallmark of temporal-difference learning.
The bias-variance tradeoff:
- Monte Carlo (REINFORCE): Unbiased (uses real returns) but high variance (returns vary across episodes)
- Bootstrap (Actor-Critic): Lower variance (single-step estimate) but biased (depends on critic's accuracy)
- The critic's value function is itself being learned, so early in training the bootstrap targets may be inaccurate
14.5.4 One-Step Actor-Critic Algorithm
The one-step actor-critic algorithm processes the episode step by step (not waiting for the end), updating after each transition.
Inputs: Step sizes \(\alpha_\theta\) and \(\alpha_w\), discount factor \(\gamma\)
Steps:
- Initialize policy parameters \(\theta\) and value parameters \(w\)
- Repeat forever:
- Initialize \(S\) (first state of episode), set \(I = 1\) (importance weight, initially 1)
- For each step:
- Choose \(A \sim \pi(\cdot \mid S; \theta)\)
- Take action \(A\), observe reward \(R\) and next state \(S'\)
- Compute the TD error: \(\delta = R + \gamma \, V(S'; w) - V(S; w)\)
- Update value parameters: \(w \leftarrow w + \alpha_w \, I \, \delta \, \nabla_w V(S; w)\)
- Update policy parameters: \(\theta \leftarrow \theta + \alpha_\theta \, I \, \delta \, \nabla_\theta \ln \pi(A \mid S; \theta)\)
- Update importance weight: \(I \leftarrow \gamma I\)
- Set \(S \leftarrow S'\)
The TD error \(\delta = R + \gamma V(S'; w) - V(S; w)\) plays the role of the advantage estimate. It measures: "I got reward \(R\), and the critic says the next state is worth \(V(S'; w)\). Compared to what I expected from the current state \(V(S; w)\), how surprised am I?"
The professor points out the structural difference from REINFORCE: "Since it is one-step, the structure slightly changes exactly in the manner that we actually have studied earlier on TD algorithms. Start with the first state, and go through the episode step by step because it's a TD style algorithm."
The importance weight \(I\): Starts at 1 and is multiplied by \(\gamma\) at each step. It serves as a discount factor that reduces the influence of later steps, exactly matching the discount factor convention used in the return. After \(k\) steps, \(I = \gamma^k\). This ensures that updates from later in the episode have progressively less weight, consistent with the discounted return formulation.
14.5.5 The Role of the Critic (Detailed)
The critic has two jobs:
- Provide the bootstrap target: The critic's value estimate \(V(S'; w)\) replaces the unknown future return. Instead of waiting for all rewards, we trust the critic's prediction of what comes next.
- Provide the baseline: The current state's value \(V(S; w)\) serves as the baseline, just as in REINFORCE with baseline. The TD error \(\delta\) is the difference between the bootstrap target and the baseline.
The professor emphasizes: "The job of a critic is to give a better approximation of the quality signal. From the critic's viewpoint, taking into account the critic's viewpoint, it actually gives you a better estimate of your quality. Earlier, you estimate your quality and add a baseline. Now, I am a critic, you include me in your own estimate."
The critic is trained via bootstrapping as well — its target is \(R + \gamma V(S'; w)\), and its loss is the squared TD error. This is standard TD learning for the value function.
14.5.6 Advantage Actor-Critic (A2C)
Advantage Actor-Critic, often abbreviated A2C, is essentially the same as one-step actor-critic. The name emphasizes that the update uses the advantage (TD error) rather than the raw return.
The professor states: "The last algorithm that I've talked about is actually advantage actor-critic. It is exactly the same thing. Only thing is, it is exactly the same thing that I talked about one-step actor-critic. It is slightly in a general form."
The updates are identical. The quality signal is:
\[ \delta = R_{t+1} + \gamma \, V(S_{t+1}; w) - V(S_t; w) \]
And both the actor and critic are updated using this advantage signal. In many references, A2C is written as a shorthand for this family of algorithms. The professor notes: "In short, you would actually write it as A2C."
n-step extensions: Instead of one-step, you can use two-step, three-step, or \(n\)-step actor-critic. The quality signal becomes:
\[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n}; w) \]
The more steps you include before invoking the critic, the closer you get to Monte Carlo (higher variance, lower bias). The fewer steps, the more you rely on the critic (lower variance, higher bias).
The professor: "You also can have two-step actor-critic, three-step actor-critic. The whole idea is in the quality signal, involve critic."
14.5.7 Comparison: REINFORCE with Baseline vs. Actor-Critic
| Aspect | REINFORCE with Baseline | Actor-Critic |
|---|---|---|
| Quality signal | \(G_t\) (full Monte Carlo return) | \(R_{t+1} + \gamma V(S_{t+1}; w)\) (bootstrap) |
| Baseline | \(b(S_t) = V(S_t; w)\) | Same, but embedded in the TD error |
| Update timing | End of episode (Monte Carlo) | Each step (online/TD) |
| Variance | Higher (full return) | Lower (bootstrap) |
| Bias | Unbiased | Biased (depends on critic accuracy) |
| Number of networks | 2 (policy + value) | 2 (policy + value) |
| Continuing tasks | No (needs episode end) | Yes (works step by step) |
The professor: "Reinforcement with baseline is an unbiased estimate and will converge. A critic comes in with bias by the critic's estimates, but it would ensure the convergence is actually faster."
Connection to policy iteration: Actor-critic algorithms are derivatives of policy iteration, alternating between:
- Policy evaluation: computing how good the current policy is (the critic's job)
- Policy improvement: making the policy better based on the evaluation (the actor's job)
Recap: Actor-critic methods replace Monte Carlo returns with bootstrapped TD estimates: \(\delta = R + \gamma V(S';w) - V(S;w)\). The critic is embedded in the quality signal (not just a baseline), enabling step-by-step updates without waiting for episode end. A2C is the standard name for one-step advantage actor-critic. The tradeoff: lower variance but biased (depends on critic accuracy). Next: extending these ideas to continuous action spaces.
14.6 Continuous Action Spaces
Hook: Everything we've discussed so far assumes discrete actions — a finite set like {left, right, up, down}. But many real-world problems involve continuous actions: steering angles, joint torques, throttle levels. How do we output a probability distribution over infinitely many possible actions?
14.6.1 The Fundamental Difference
For discrete actions, the policy network outputs a probability for each action: \(\pi(a_1 \mid s), \pi(a_2 \mid s), \ldots\). We learn these probabilities.
For continuous actions, there are infinitely many possible values between any two bounds. We cannot learn a separate probability for each one. Instead, we learn a distribution — specifically, the parameters of a Gaussian (normal) distribution.
The professor: "You are not learning the probability of each action, because it is continuous, there is an innumerable number of possibilities between -1 to plus one; you can't learn the probability for each of them. So you are actually learning the mean of an action, and also learning the standard deviation of that action."
Intuition: Think of a thermostat. With discrete actions, you'd choose from {set to 18°C, set to 19°C, set to 20°C, ...}. With continuous actions, you can set it to any real number — 19.3°C, 19.37°C, etc. The policy doesn't output probabilities for each temperature; it outputs a distribution centered on a "best guess" temperature, and samples from that distribution.
14.6.2 Gaussian Policy Parameterization
In the simplest case, we parameterize the mean of the action distribution:
\[ \mu_\theta(s) = \theta^\top \mathbf{x}(s) \]
where \(\mathbf{x}(s)\) is the state representation and \(\theta\) are the parameters. The policy samples actions from:
\[ A \sim \mathcal{N}\bigl(\mu_\theta(s), \, \sigma^2\bigr) \]
where \(\sigma\) is the standard deviation. In the lecture's example, \(\sigma = 0.2\) is fixed — we only learn the mean, not the standard deviation.
The professor explains: "Your mean of an action is minus 0.7. You would actually be choosing a random number around this minus 0.7, subject to the normal distribution fitted with that minus 0.7, with that particular standard deviation."
Over time, as learning progresses, the normal curve around the mean becomes sharper (if \(\sigma\) decreases) or the mean itself moves toward better actions, making the policy more confident.
Concrete example: If the mean action is \(\mu = -0.7\) and \(\sigma = 0.2\), then:
- The action will most likely be near \(-0.7\)
- About 68% of sampled actions fall in \([-0.9, -0.5]\) (within 1 standard deviation)
- About 95% fall in \([-1.1, -0.3]\) (within 2 standard deviations)
- An action of \(-0.65\) would be sampled with high probability; \(-0.2\) would be very rare
14.6.3 Log-Probability Gradient for Gaussian Policy
The update rule still uses \(\nabla_\theta \ln \pi(A \mid s; \theta)\), but now \(\pi\) is a Gaussian density. We need to derive this gradient from first principles.
Full derivation of the Gaussian log-probability gradient:
The Gaussian probability density function is:
\[ \pi(A \mid s; \theta) = \frac{1}{\sigma \sqrt{2\pi}} \exp\left(-\frac{(A - \mu_\theta(s))^2}{2\sigma^2}\right) \]
Step 1 — Take the logarithm:
\[ \begin{aligned} \ln \pi(A \mid s; \theta) &= \ln\left(\frac{1}{\sigma \sqrt{2\pi}}\right) + \ln\left(\exp\left(-\frac{(A - \mu_\theta(s))^2}{2\sigma^2}\right)\right) \\ &= -\ln(\sigma) - \frac{1}{2}\ln(2\pi) - \frac{(A - \mu_\theta(s))^2}{2\sigma^2} \end{aligned} \]
Step 2 — Identify what depends on \(\theta\): Only \(\mu_\theta(s)\) depends on \(\theta\). The terms \(-\ln(\sigma) - \frac{1}{2}\ln(2\pi)\) are constants with respect to \(\theta\). So:
\[ \ln \pi(A \mid s; \theta) = -\frac{(A - \mu_\theta(s))^2}{2\sigma^2} + \text{const} \]
Step 3 — Take the gradient with respect to \(\theta\):
\[ \begin{aligned} \nabla_\theta \ln \pi(A \mid s; \theta) &= \nabla_\theta \left[-\frac{(A - \mu_\theta(s))^2}{2\sigma^2}\right] \\ &= -\frac{1}{2\sigma^2} \cdot 2(A - \mu_\theta(s)) \cdot (-\nabla_\theta \mu_\theta(s)) \\ &= \frac{A - \mu_\theta(s)}{\sigma^2} \, \nabla_\theta \mu_\theta(s) \end{aligned} \]
Each step is annotated:
- Line 1: Apply the gradient operator to the only term containing \(\theta\)
- Line 2: Chain rule — derivative of \((A - \mu)^2\) with respect to \(\mu\) is \(2(A - \mu) \cdot (-1)\), then multiply by \(\nabla_\theta \mu\)
- Line 3: Simplify the signs and cancel the 2
The final result:
\[ \nabla_\theta \ln \pi(A \mid s; \theta) = \frac{A - \mu_\theta(s)}{\sigma^2} \, \nabla_\theta \mu_\theta(s) \]
Interpretation of each factor:
- \(A - \mu_\theta(s)\): How far the sampled action deviates from the mean. If the action is above the mean, this is positive; below, negative.
- \(\frac{1}{\sigma^2}\): Normalizes by the variance. If \(\sigma\) is large (high uncertainty), the gradient is smaller — we're less confident about which direction to adjust.
- \(\nabla_\theta \mu_\theta(s)\): How changing the parameters \(\theta\) would shift the mean. This is just the gradient through the network that computes \(\mu_\theta(s)\).
For the linear case \(\mu_\theta(s) = \theta^\top \mathbf{x}(s)\), we have \(\nabla_\theta \mu_\theta(s) = \mathbf{x}(s)\), so the gradient simplifies to:
\[ \nabla_\theta \ln \pi(A \mid s; \theta) = \frac{A - \mu_\theta(s)}{\sigma^2} \, \mathbf{x}(s) \]
The professor notes: "This is there in a textbook somewhere. You actually can pick it up. Or you take it as an exercise to ensure that you are computing \(\nabla_\theta \ln \pi\)."
Numerical spot-check: Suppose \(\theta = [-0.5, 0, 0.5]\), state \(\mathbf{x}(s) = [1, 0, 0]\) (left), \(\sigma = 0.2\), and the sampled action is \(A = -0.3\).
- Mean: \(\mu = -0.5 \times 1 + 0 \times 0 + 0.5 \times 0 = -0.5\)
- Deviation: \(A - \mu = -0.3 - (-0.5) = 0.2\)
- Gradient factor: \(\frac{0.2}{0.04} = 5\)
- Full gradient: \(5 \times [1, 0, 0] = [5, 0, 0]\)
The positive gradient on \(\theta_1\) means: "the sampled action was to the right of the mean, so shift the mean to the right (increase \(\theta_1\))." This makes sense — if the action \(-0.3\) earned good reward, we want the policy to sample more actions near \(-0.3\) rather than \(-0.5\).
Scope — Gaussian policy assumptions:
- Actions must be continuous and (approximately) unimodal per state
- The Gaussian assumption works well for smooth action spaces; it breaks for multi-modal distributions (e.g., "go hard left OR hard right, but never straight")
- For multi-modal continuous actions, mixtures of Gaussians are used instead
- The variance \(\sigma\) can be fixed (simpler) or learned (more flexible)
The update rule for continuous actions is otherwise the same as before — the only change is in how we compute the log-probability gradient.
Recap: For continuous actions, the policy outputs a Gaussian distribution — we learn the mean \(\mu_\theta(s)\) and optionally the standard deviation \(\sigma\). The log-probability gradient is \(\nabla_\theta \ln \pi = \frac{A - \mu_\theta(s)}{\sigma^2} \nabla_\theta \mu_\theta(s)\). The update rule is the same as REINFORCE/actor-critic, just with this Gaussian gradient. Next: a concrete worked example with the lane-keeping assistant.
14.7 Lane-Keeping Assistant: A Continuous-Action Worked Example
Hook: We've derived all the theory — policy gradient, REINFORCE, baselines, Gaussian policies. Now let's put it all together in a concrete problem that the professor indicates will be the basis for exam numerical problems.
14.7.1 Problem Setup
The professor presents a concrete problem to tie together all the concepts. This is a lane-keeping assistant — a car must stay in the center of its lane by adjusting its steering.
States: Three possible states — the car is in the left of the lane, the center, or the right. Each state is represented as a one-hot vector:
- Left: \(\mathbf{x} = [1, 0, 0]\)
- Center: \(\mathbf{x} = [0, 1, 0]\)
- Right: \(\mathbf{x} = [0, 0, 1]\)
Actions: Continuous in the range \([-1, +1]\). An action of \(-1\) means sharp left, \(+1\) means sharp right, and \(0\) means go straight. All intermediate values are possible (e.g., \(-0.3\), \(+0.7\)).
Reward: \(+1\) if the car is at the center, \(0\) if the car is in the left or right.
Goal: Learn a policy that steers the car back to center. When in the left, the policy should sample actions around a negative value (steer left to return to center). When in the right, the policy should steer right. When at center, go straight.
Why this is a good exam example: It has all the ingredients — continuous actions (Gaussian policy), one-hot state representation, simple rewards, and a clear geometric interpretation. The professor can ask you to compute \(\mu_\theta(s)\), sample an action, compute the log-probability gradient, and perform the parameter update.
14.7.2 Initial Policy (Before Learning)
Full worked example with real numbers:
With initial parameters \(\theta = [-0.5, 0, 0.5]\) and fixed \(\sigma = 0.2\), the policy means for each state are:
State Left \(\mathbf{x} = [1, 0, 0]\): \[ \mu = \theta^\top \mathbf{x} = (-0.5)(1) + (0)(0) + (0.5)(0) = -0.5 \] The policy samples actions from \(\mathcal{N}(-0.5, 0.04)\). This means steering left — the correct direction to return to center from the left side.
State Center \(\mathbf{x} = [0, 1, 0]\): \[ \mu = \theta^\top \mathbf{x} = (-0.5)(0) + (0)(1) + (0.5)(0) = 0 \] The policy samples actions from \(\mathcal{N}(0, 0.04)\). Go straight — correct, since we're already centered.
State Right \(\mathbf{x} = [0, 0, 1]\): \[ \mu = \theta^\top \mathbf{x} = (-0.5)(0) + (0)(0) + (0.5)(1) = 0.5 \] The policy samples actions from \(\mathcal{N}(0.5, 0.04)\). Steer right — correct direction to return to center from the right side.
Sense-check: The initial policy already has the right qualitative behavior — steer toward center from either side. But the magnitudes may not be optimal, and the policy will refine them through learning.
The professor explains: "When the car is in left, the current policy samples around -0.5. It can actually sample around -0.5. Maybe the sampling will come to -0.3, so you are still asking to go straight, but you are asking the driver to improve the steering."
14.7.3 How to Update
The update uses the same REINFORCE or actor-critic rule, but now:
- The log-probability gradient is computed using the Gaussian form (see Section 14.6.3).
- The advantage signal (or return minus baseline) is computed as before.
Two one-step episodes — full numerical walkthrough:
Episode 1: Start in state Left, take action \(a_1\), receive reward \(R_1\), transition to state Center.
Given: \(\theta = [-0.5, 0, 0.5]\), \(\sigma = 0.2\), \(\mathbf{x}(s_{\text{left}}) = [1,0,0]\)
- Compute mean: \(\mu_\theta(s_{\text{left}}) = -0.5\)
- Sample action: Suppose \(a_1 = -0.3\) (sampled from \(\mathcal{N}(-0.5, 0.04)\))
- Receive reward: \(R_1 = 0\) (car was in left, not center)
- Next state: Center (reward +1 at center in next step, but this is a one-step episode)
For a one-step episode with return \(G_0 = R_1 = 0\):
- The update is small (return is 0), so the policy barely changes.
Episode 2: Start in state Right, take action \(a_2\), receive reward \(R_2\), transition to Center.
Given: \(\mathbf{x}(s_{\text{right}}) = [0,0,1]\)
- Compute mean: \(\mu_\theta(s_{\text{right}}) = 0.5\)
- Sample action: Suppose \(a_2 = 0.4\)
- Receive reward: \(R_2 = 0\) (car was in right)
- Compute gradient:
\[ \nabla_\theta \ln \pi(a_2 \mid s_{\text{right}}) = \frac{a_2 - \mu_\theta(s_{\text{right}})}{\sigma^2} \, \mathbf{x}(s_{\text{right}}) = \frac{0.4 - 0.5}{0.04} \, [0, 0, 1] = -2.5 \, [0, 0, 1] \]
- Update: \(\theta \leftarrow \theta + \alpha \times 0 \times (-2.5) [0, 0, 1]\) — no change (return is 0)
With a richer episode: If the episode had multiple steps and earned positive return, the updates would shift \(\theta\) to make the taken actions more probable.
The professor's request: "Go through this document. If you are good at putting these expressions right, and then putting these values, there is nothing much that you should do."
Exam note: The professor indicates this lane-keeping example will be the basis for exam numerical problems involving continuous-action policy gradient. Be prepared to:
- Compute \(\mu_\theta(s)\) from \(\theta\) and \(\mathbf{x}(s)\)
- Sample an action from \(\mathcal{N}(\mu, \sigma^2)\)
- Compute the log-probability gradient \(\nabla_\theta \ln \pi\)
- Compute the return \(G_t\) or TD error \(\delta\)
- Perform the parameter update \(\theta \leftarrow \theta + \alpha \cdot \text{signal} \cdot \nabla_\theta \ln \pi\)
14.8 Student Questions and Answers
14.8.1 REINFORCE and Monte Carlo
Q: For this REINFORCE, we use MC, which means we have to generate the full episode, or at least a set of episodes, and then you operate with the returns?
A: Exactly. You need the full episode. You generate the full episode, and then you start from the beginning of the episode and keep updating the parameters. Because you have to compute G.
Why this matters: This is a fundamental constraint of REINFORCE. It cannot be used for continuing (non-episodic) tasks because there is no terminal state and \(G_t\) would be infinite. For such tasks, actor-critic methods (which use bootstrapping) are necessary.
14.8.2 Sufficiency of Value Functions
Q: So for REINFORCE with baseline, we are learning both the value and the policy. If I just know the value of each state, should I still learn policy?
A: Value of a state is not sufficient enough to learn the policy. You want \(Q(s, a)\), not \(V(s)\). In serious problems, \(V(s)\) is not sufficient to get the policy. If you have only \(V(s)\), you need model dynamics to decide the policy. So simply learning \(V(s)\) is not going to help getting the policy in real problems. But if you are learning the Q function, you can learn the policy. If you derive a policy from Q, it has its own disadvantages (as discussed in earlier lectures on value-based methods).
Key insight: \(V(s)\) tells you "how good is this state?" but not "what should I do?" To get a policy from \(V(s)\), you need the transition model: \(\pi(s) = \arg\max_a \sum_{s'} p(s'|s,a) [r + \gamma V(s')]\). Without the model, \(V(s)\) alone is insufficient. \(Q(s,a)\) directly tells you the value of each action, so \(\pi(s) = \arg\max_a Q(s,a)\) needs no model.
14.8.3 Exam Logistics
Q: What will be the syllabus for the examination? Will it also contain the portion of EC3 or only the portion of the course?
A: It is everything. You don't really have to read two documents — everything that has been discussed across all lectures is included.
Q: Can you share the PPT in advance? That will be really helpful.
A: (The professor shared the numerical PPT and companion documents during the class.)
14.9 Exam Guidance Summary
14.9.1 Scope and Coverage
Exam note: The exam covers everything — all topics from the entire course, including EC3 content. Policy gradient methods (REINFORCE, REINFORCE with baseline, Actor-Critic, A2C) are all examinable.
14.9.2 Student Questions and Answers
Q: What will be the syllabus for the examination? Will it also contain the portion of EC3 or only the portion of the course?
A: It is everything. You do not need to read two separate documents — everything discussed across all lectures is included.
14.9.3 Problem Types and Preparation
Exam note — What to prepare:
- Numerical problems: Expect numerical problems involving policy gradient updates. The lane-keeping assistant with continuous actions is the canonical example — be prepared to compute parameter updates given initial parameters, states, actions, and rewards.
- Continuous actions: The numerical will involve continuous action spaces with Gaussian policy parameterization. Know how to compute \(\mu_\theta(s)\), sample actions, compute the log-probability gradient, and perform the parameter update.
- Key algorithms to know:
- REINFORCE: Update rule, Monte Carlo nature, learning rate sensitivity
- REINFORCE with baseline: Why baseline does not change gradient direction (proof), the advantage function, dual-network algorithm
- Actor-Critic: TD error as quality signal, bootstrap vs. Monte Carlo, one-step algorithm
- A2C: Same as one-step actor-critic, n-step extensions
- Study advice: Go through the companion documents and numerical PPTs. The professor emphasizes: "Go through this document. If you are good at putting these expressions right and then putting these values, there is nothing much that you should do."
- Imitation learning: This topic will be covered by another instructor and is also on the exam.
- Office hours: The professor is available for discussions and clarifications any time except the last week before the exam (during which paper-setting is happening).
14.10 Key Connections and Summary
14.10.1 The Policy Gradient Progression
The lecture builds a clear progression from value-based methods to modern policy gradient:
| # | Method | Quality Signal | Update Timing | Bias/Variance |
|---|---|---|---|---|
| 1 | DQN | \(Q(s,a)\) derived | After batch | N/A (value-based) |
| 2 | Policy Gradient (theorem) | \(\sum_s \mu(s) \sum_a Q_\pi \nabla \pi\) | N/A (theory) | N/A |
| 3 | REINFORCE | \(G_t\) (full return) | End of episode | Unbiased, high variance |
| 4 | REINFORCE + baseline | \(G_t - V(s)\) | End of episode | Unbiased, lower variance |
| 5 | Actor-Critic | \(R + \gamma V(s')\) (bootstrap) | Each step | Biased, low variance |
| 6 | A2C | \(\delta = R + \gamma V(s') - V(s)\) | Each step | Biased, low variance |
| 7 | Continuous actions | Same, with Gaussian \(\nabla_\theta \ln \pi\) | Same | Same |
The progression in one sentence: Value-based → policy gradient theorem → REINFORCE (sample-based) → REINFORCE with baseline (variance reduction) → Actor-Critic (bootstrapping) → A2C (advantage-based) → Continuous actions (Gaussian policy).
14.10.2 Closing Remarks
The professor's closing summary: "In many serious problems, it is always good to learn the policy directly. We began with an estimate of the policy gradient theorem. And we have reasons outlined for what is policy gradient theorem. And then we come to how to use policy gradient theorem with REINFORCE, with REINFORCE with baseline, and with actor-critic."
What comes next: The next lecture will cover advanced policy gradient methods including PPO (Proximal Policy Optimization) and other modern algorithms. PPO builds on the ideas from this lecture — it uses the policy gradient theorem, advantage estimates, and clipping to ensure stable updates.
DRL Lecture 14 notes · Policy Gradient Methods
Sections Breakdown
Contrasts value-based methods (learn Q(s,a) then pick the best action) with policy-based methods (learn the policy directly), covering continuous action spaces, stochastic policies, the performance metric J(theta), and how policy gradient differs from supervised learning.
States and derives the policy gradient theorem from first principles, showing the gradient scope lies entirely within the policy network and why direct implementation is still impractical.
Converts the theorem into a practical sample-based Monte Carlo update, with a worked two-step episode, the crazy corridor learning-rate sensitivity study, and complexity considerations.
Subtracts a state-dependent baseline to reduce variance without changing gradient direction, introduces the advantage function, and presents the dual-network algorithm with a worked example.
Replaces Monte Carlo returns with bootstrapped TD estimates, clarifies why REINFORCE with baseline is not actor-critic, and presents the one-step actor-critic algorithm and A2C.
Gaussian policy parameterization for continuous actions, with the full derivation of the log-probability gradient and a numerical spot-check.
A full numerical worked example of continuous-action policy gradient updates in a three-state lane-keeping assistant, the canonical exam numerical.
Student Q&A on REINFORCE's Monte Carlo nature, why V(s) alone cannot determine a policy, and exam logistics.
Exam scope and coverage, problem types, and preparation guidance for policy gradient topics.
The progression from value-based methods through the policy gradient theorem, REINFORCE, baselines, actor-critic, A2C, and continuous actions.
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.
Policy-Based vs. Value-Based Methods
Must-know: Policy gradient learns \(\pi(a|s;\theta)\) directly. Three advantages: continuous actions, stochastic policies, complex structures. \(J(\theta)\) maximized via gradient ascent (+ sign), differs from supervised learning in objective, data correlation, and non-stationarity.
\[ \theta_{\text{new}} = \theta_{\text{old}} + \alpha \, \nabla_\theta J(\theta) \]
⚠️ Top pitfall: Treating policy gradient like supervised learning — ignoring temporal correlation and non-stationarity
Self-check: Why can't DQN handle continuous action spaces directly?
Connects to: 14.2, 14.3
The Policy Gradient Theorem
Must-know: Policy gradient theorem: \(\nabla_\theta J(\theta) \propto \sum_s \mu(s) \sum_a Q_\pi(s,a) \nabla_\theta \pi(a|s;\theta)\). Gradient scope is entirely within the policy network. Environment dynamics cancel via the log-derivative trick.
\[ \nabla_\theta J(\theta) \propto \sum_{s} \mu(s) \sum_{a} Q_\pi(s, a) \, \nabla_\theta \pi(a \mid s; \theta) \]
⚠️ Top pitfall: Thinking you need to know the environment's transition dynamics to compute the gradient — you don't, they cancel out
Self-check: Why does the policy gradient theorem not require knowledge of the environment's dynamics?
Connects to: 14.1, 14.3
The REINFORCE Algorithm
Must-know: REINFORCE update: \(\theta \leftarrow \theta + \alpha G_t \nabla_\theta \ln \pi(A_t|S_t;\theta)\). Monte Carlo (full episodes), on-policy (can't reuse old data). Log-derivative trick: \(\nabla\pi/\pi = \nabla\ln\pi\). Learning rate sensitivity — no single formula works.
\[ \theta_{t+1} = \theta_t + \alpha \, G_t \, \nabla_\theta \ln \pi(A_t \mid S_t; \theta) \]
⚠️ Top pitfall: Trying to reuse old trajectories after updating \(\theta\) — REINFORCE is on-policy, old data is stale
Self-check: Why does REINFORCE require the full episode before updating? What is the quality signal?
Connects to: 14.2, 14.4
REINFORCE with Baseline
Must-know: Baseline doesn't change gradient direction (proof via \(\sum_a \nabla_\theta \pi = 0\)). Advantage function \(A^\pi(s,a) = Q_\pi(s,a) - V_\pi(s)\). Algorithm learns two networks: policy (\(\theta\)) and value (\(w\)). Unbiased estimate, still Monte Carlo, still on-policy.
\[ \theta_{t+1} = \theta_t + \alpha \, (G_t - V(S_t; w)) \, \nabla_\theta \ln \pi(A_t \mid S_t; \theta) \]
⚠️ Top pitfall: Confusing \(V(s)\) with \(Q(s,a)\) — \(V(s)\) alone cannot determine the policy without model dynamics
Self-check: Why doesn't subtracting a baseline change the expected gradient direction? What is the advantage function?
Connects to: 14.3, 14.5
Actor-Critic Methods
Must-know: Actor-Critic: critic embedded in quality signal (not just baseline). TD error \(\delta = R + \gamma V(S';w) - V(S;w)\). Updates step-by-step (not end of episode). A2C = one-step actor-critic. Bias-variance tradeoff: lower variance but biased.
\[ \delta = R_{t+1} + \gamma \, V(S_{t+1}; w) - V(S_t; w) \]
⚠️ Top pitfall: Confusing REINFORCE with baseline (critic is passive normalizer) with actor-critic (critic is active in quality signal)
Self-check: How does actor-critic differ from REINFORCE with baseline? What is the TD error?
Connects to: 14.4, 14.6
Continuous Action Spaces
Must-know: Continuous actions: learn Gaussian mean \(\mu_\theta(s) = \theta^\top \mathbf{x}(s)\), sample \(A \sim \mathcal{N}(\mu, \sigma^2)\). Log-probability gradient: \(\nabla_\theta \ln \pi = \frac{A - \mu}{\sigma^2} \nabla_\theta \mu\). For the linear case: \(\nabla_\theta \ln \pi = \frac{A - \mu}{\sigma^2} \mathbf{x}(s)\).
\[ \nabla_\theta \ln \pi(A \mid s; \theta) = \frac{A - \mu_\theta(s)}{\sigma^2} \, \nabla_\theta \mu_\theta(s) \]
⚠️ Top pitfall: Assuming Gaussian policy works for multi-modal action distributions — it only captures unimodal distributions
Self-check: What does the policy learn for continuous actions? Derive the log-probability gradient for a Gaussian policy.
Connects to: 14.3, 14.7
Lane-Keeping Assistant: A Continuous-Action Worked Example
Must-know: Lane-keeping: 3 states one-hot, continuous actions, Gaussian policy. Compute \(\mu = \theta^\top \mathbf{x}\), sample \(A \sim \mathcal{N}(\mu, \sigma^2)\), compute \(\nabla_\theta \ln \pi = \frac{A-\mu}{\sigma^2} \mathbf{x}\), update \(\theta\). The professor indicates this is the canonical exam numerical.
\[ \mu_\theta(s) = \theta^\top \mathbf{x}(s), \quad \nabla_\theta \ln \pi = \frac{A - \mu}{\sigma^2} \, \mathbf{x}(s) \]
⚠️ Top pitfall: Forgetting to use the Gaussian log-probability gradient (not the softmax gradient) for continuous actions
Self-check: Given \(\theta = [-0.5, 0, 0.5]\), \(\mathbf{x} = [1,0,0]\), \(\sigma = 0.2\), compute \(\mu\). If \(A = -0.3\), compute the log-probability gradient.
Connects to: 14.6, 14.3
Student Questions and Answers
Must-know: REINFORCE = Monte Carlo (full episodes). \(V(s)\) alone can't determine policy without model dynamics. Exam covers everything.
⚠️ Top pitfall: Thinking \(V(s)\) is enough to derive a policy — you need \(Q(s,a)\) or the transition model
Self-check: Why can't you derive a policy from \(V(s)\) alone?
Connects to: 14.3, 14.4
Exam Guidance Summary
Must-know: Exam: everything. Numerical: lane-keeping continuous-action policy gradient. Know all algorithms. Imitation learning covered by another instructor.
⚠️ Top pitfall: Not preparing for continuous-action numerical problems
Self-check: List the 4 key algorithms covered in this lecture.
Connects to: 14.3, 14.4, 14.5, 14.6, 14.7
Key Connections and Summary
Must-know: Progression: value-based → policy gradient theorem → REINFORCE → baseline → actor-critic → A2C → continuous actions. Each step reduces variance or adds capability.
⚠️ Top pitfall: Not understanding how each method builds on the previous one
Self-check: What is the key difference between REINFORCE and actor-critic in terms of the quality signal?
Connects to: 14.1, 14.2, 14.3, 14.4, 14.5, 14.6