Policy gradient methods

WHY do we even want policy gradients?

Value methods (Q-learning) learn $Q(s,a)$ and pick $\arg\max_a Q$. This breaks when:

• Actions are continuous — you can't argmax over an infinite set easily.
• The optimal policy is stochastic — e.g. rock-paper-scissors, or partially observed states where the best move is genuinely random. A greedy value policy is deterministic.
• You want smooth improvement — small $\theta$ changes give small policy changes, which is stable.

WHAT are we optimizing?

Define the objective as expected return of a trajectory $\tau = (s_0,a_0,s_1,a_1,\dots)$:

$J(\theta) = \mathbb{E}_{\tau\sim\pi_\theta}\big[R(\tau)\big], \qquad R(\tau)=\sum_{t=0}^{T}\gamma^t r_t$

We do gradient ascent: $\theta \leftarrow \theta + \alpha\,\nabla_\theta J(\theta)$.

The whole game is: how do we compute $\nabla_\theta J$ when the reward doesn't obviously depend on $\theta$? Reward comes from the environment; $\theta$ only shapes which trajectories we sample. This is the trick.

HOW: deriving the Policy Gradient Theorem from scratch

Write the objective as an integral over trajectories, with $P_\theta(\tau)$ the trajectory probability:

$J(\theta) = \int P_\theta(\tau)\,R(\tau)\,d\tau$

Step 1 — differentiate. $\nabla_\theta J = \int \nabla_\theta P_\theta(\tau)\,R(\tau)\,d\tau$ Why this step? $R(\tau)$ has no $\theta$ in it (reward is environment's), so only $P_\theta$ is differentiated.

Step 2 — the log-derivative trick. Multiply and divide by $P_\theta(\tau)$: $\nabla_\theta P_\theta = P_\theta \frac{\nabla_\theta P_\theta}{P_\theta} = P_\theta\,\nabla_\theta \log P_\theta(\tau)$ Why? Because $\nabla \log f = \frac{\nabla f}{f}$. This is the crucial identity — it turns the gradient of a probability into an expectation we can sample.

$\nabla_\theta J = \int P_\theta(\tau)\,\nabla_\theta\log P_\theta(\tau)\,R(\tau)\,d\tau = \mathbb{E}_{\tau}\!\big[\nabla_\theta\log P_\theta(\tau)\,R(\tau)\big]$

Step 3 — expand $\log P_\theta(\tau)$. The trajectory probability factorizes: $P_\theta(\tau) = \underbrace{\rho(s_0)}_{\text{init}} \prod_{t}\underbrace{P(s_{t+1}\mid s_t,a_t)}_{\text{dynamics}}\,\underbrace{\pi_\theta(a_t\mid s_t)}_{\text{policy}}$ Take log → sum. The init and dynamics terms have no $\theta$, so they vanish under $\nabla_\theta$: $\nabla_\theta\log P_\theta(\tau) = \sum_{t=0}^{T}\nabla_\theta\log\pi_\theta(a_t\mid s_t)$ Why this matters: we never need the environment's dynamics model! This is model-free.

Reducing variance: causality + baseline

REINFORCE works but has huge variance. Two principled fixes:

1. Causality (reward-to-go). An action at time $t$ can't affect rewards before $t$. So replace the full $R(\tau)$ multiplying the $t$-th term with only future reward: $\nabla_\theta J = \mathbb{E}\!\left[\sum_t \nabla_\theta\log\pi_\theta(a_t\mid s_t)\;\underbrace{\sum_{t'\ge t}\gamma^{t'-t}r_{t'}}_{G_t\ \text{(reward-to-go)}}\right]$

2. Baseline subtraction. Subtract any function $b(s_t)$ that doesn't depend on the action: $\nabla_\theta J = \mathbb{E}\!\left[\sum_t \nabla_\theta\log\pi_\theta(a_t\mid s_t)\,\big(G_t - b(s_t)\big)\right]$ Why is this allowed (unbiased)? Because $\mathbb{E}_{a\sim\pi}[\nabla_\theta\log\pi_\theta(a\mid s)\,b(s)] = b(s)\,\nabla_\theta\!\sum_a\pi_\theta(a\mid s)=b(s)\,\nabla_\theta 1 = 0$. Subtracting zero changes nothing in expectation but slashes variance.

The best baseline is $b(s)=V(s)$, giving the advantage $A(s,a)=G_t-V(s)\approx Q(s,a)-V(s)$. This is the seed of Actor-Critic.

Steel-manned mistakes

Flashcards

Connections

• Actor-Critic methods — baseline becomes a learned critic $V_\phi$.
• REINFORCE algorithm — the direct Monte-Carlo estimator.
• Advantage function and Generalized Advantage Estimation.
• Trust Region and PPO — control step size for stability.
• Value-based methods (Q-learning) — the alternative family PG contrasts with.
• Log-derivative trick / Score function estimator — same idea across ML.
• Variance reduction in Monte Carlo.

Concept Map

Hinglish (regional understanding)