Policy Gradients and Deep RL

Every algorithm in the previous lessons stores one number per state (or state-action pair). For Atari, the raw pixel state space has roughly $10^{56{,}000}$ distinct frames — storing a table is physically impossible. For continuous control (robot joints, financial portfolios), the state space isn't even countable.

Function approximation replaces the table with a parameterised function $\hat{V}(s;\theta)$ or $\hat{Q}(s,a;\theta)$, where $\theta$ are the weights of a neural network. The network generalises from visited states to nearby unseen ones.

The shift introduces new failure modes: the value function is no longer guaranteed to converge, updates can destabilise each other, and the "deadly triad" can cause divergence. Understanding these risks is as important as understanding the algorithms.

Deep Q-Network (DQN) — Mnih et al., 2015 — brought Q-learning to Atari using two stabilising tricks:

1. Experience replay. Transitions $(s,a,r,s')$ are stored in a replay buffer of size $10^6$. Mini-batches are sampled uniformly at training time. This breaks temporal correlations that make online updates diverge and allows each transition to be reused many times.

2. Target network. A separate copy of the Q-network $\theta^-$ is frozen for $C$ steps and used to compute TD targets: $y_t = r + \gamma \max_{a'} Q(s', a'; \theta^-)$ Without freezing, the target $y_t$ moves every update step, chasing a moving target — a major source of instability. Every $C$ steps, $\theta^- \leftarrow \theta$.

Experience flows through the replay buffer; the target network provides stable TD targets.

Value-based methods derive a policy by taking the argmax of $Q$. But argmax is not differentiable, and it collapses to deterministic policies — bad for games requiring mixed strategies or continuous action spaces.

Policy gradient methods directly parameterise the policy $\pi_\theta(a \mid s)$ and optimise the objective $J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[G_0]$.

The policy gradient theorem (Sutton et al., 1999) gives the exact gradient:

$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta}\!\left[\sum_t \nabla_\theta \log \pi_\theta(a_t \mid s_t) \cdot Q^{\pi_\theta}(s_t, a_t)\right]$

The $\log \pi_\theta$ term is the score function — tractable even when the reward function is non-differentiable. This is the REINFORCE estimator at its core.

REINFORCE replaces $Q^{\pi_\theta}(s_t, a_t)$ with the sampled return $G_t$:

$\nabla_\theta J \approx \frac{1}{T} \sum_t \nabla_\theta \log \pi_\theta(a_t \mid s_t) \cdot G_t.$

This is unbiased but extremely high variance. The standard fix: subtract a baseline $b(s)$, typically $V^\pi(s)$:

$\nabla_\theta J \approx \frac{1}{T} \sum_t \nabla_\theta \log \pi_\theta(a_t \mid s_t) \cdot \underbrace{(G_t - V(s_t))}_{\text{advantage } A_t}.$

Subtracting any function of $s$ alone doesn't bias the gradient (the expectation of the subtracted term is zero), but it can massively reduce variance. The quantity $A_t = G_t - V(s_t)$ is the advantage — how much better action $a_t$ was than the average.

# Minimal REINFORCE with baseline
for ep_states, ep_actions, ep_rewards in episodes:
    returns = compute_discounted_returns(ep_rewards, gamma)
    baselines = value_net(ep_states)          # V(s)
    advantages = returns - baselines.detach() # A_t
    log_probs = policy_net.log_prob(ep_states, ep_actions)
    policy_loss = -(log_probs * advantages).mean()
    value_loss = F.mse_loss(baselines, returns)
    (policy_loss + value_loss).backward()
    optimizer.step(); optimizer.zero_grad()

Actor-critic replaces the Monte Carlo return $G_t$ with a bootstrapped estimate, combining the low-variance benefit of TD with the policy gradient framework:

$\nabla_\theta J \approx \sum_t \nabla_\theta \log \pi_\theta(a_t \mid s_t) \cdot \underbrace{\left(r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)\right)}_{\text{TD error} = \hat{A}_t}$

Two networks: the actor $\pi_\theta$ chooses actions; the critic $V_\phi$ estimates value and provides the advantage signal. They share a common feature extractor in many implementations.

Actor-critic methods sit at the intersection of policy gradient (for the actor) and value-based methods (for the critic). A2C (synchronous), A3C (asynchronous), and PPO are all actor-critic variants. The main hyperparameter tension: a critic that is too noisy introduces bias; a critic that is too old introduces staleness.

Proximal Policy Optimization (PPO) — Schulman et al., 2017 — is the de-facto standard for continuous control and the algorithm behind most instruction-tuned LLMs (RLHF).

The core idea: after collecting a batch of experience with $\pi_{\theta_{old}}$, update $\theta$ multiple times on that batch, but clip the probability ratio $r_t(\theta) = \pi_\theta(a_t|s_t) / \pi_{\theta_{old}}(a_t|s_t)$ to stay within $[1-\epsilon, 1+\epsilon]$:

$L^{\text{CLIP}}(\theta) = \mathbb{E}_t\!\left[\min\left(r_t(\theta)\hat{A}_t, \text{clip}(r_t(\theta), 1\!-\!\epsilon, 1\!+\!\epsilon)\hat{A}_t\right)\right].$

The clip prevents destructively large policy updates without the complexity of a KL-constrained trust region (TRPO). PPO is stable, parallelises trivially over CPU workers, and achieves near-TRPO sample efficiency at a fraction of the implementation cost.

Sutton and Barto name three ingredients that, combined, can cause Q-learning with function approximation to diverge:

Each alone is fine. Pairs are usually fine. All three together can produce runaway updates: the value function spirals to infinity even as the policy appears to be improving.

DQN succeeds despite using all three because the target network partially breaks the bootstrapping feedback loop, and uniform replay partially compensates for distributional shift. Rainbow, C51, and IQN add further stabilisers. This is why RL engineering feels fragile — you're navigating the deadly triad by luck and engineering discipline, not by theoretical guarantees.

Neither family dominates across all tasks:

Practical guidance: for discrete action Atari-style games, DQN/Rainbow; for continuous control (MuJoCo, robotics), PPO or SAC; for LLM alignment, PPO or GRPO.

Four active frontiers:

• Offline RL (CQL, IQL): learn from a fixed dataset with no online interaction — closes the gap between RL and supervised learning pipelines.
• Model-based RL (DreamerV3, MuZero): learn a world model and plan inside it, dramatically improving sample efficiency.
• Multi-agent RL (MARL): multiple agents share an environment; equilibria replace optimal policies.
• RLHF and RLAIF: reward models trained from human or AI feedback drive policy optimization for language models. PPO's clipping trick scales surprisingly well to billion-parameter actors.

The Bellman equation you learned in lesson 1 is still the core of every frontier above. The innovations sit in the approximate infrastructure built around it — function approximators, replay, exploration, and credit assignment.