Policy Gradient Methods for Reinforcement Learning with Function Approximation

Before this paper, the dominant paradigm in reinforcement learning was simple: estimate a value function $Q(s, a)$ — how good is action $a$ in state $s$ — then act greedily, always picking the action with the highest estimated value. This works perfectly with lookup tables where each state-action pair has its own entry. But real problems have enormous or continuous state spaces, so you need function approximation — a neural network, a linear model, or any parametric function that generalizes across states.

The moment you introduce function approximation, the greedy approach develops a dangerous discontinuity. The policy is $\arg\max_a Q(s, a)$: a tiny change in parameters can shift which action has the highest value, causing the policy to jump discontinuously. These jumps cascade — a different policy visits different states, changing the training distribution, which changes the value estimates, which causes more jumps. Q-learning, SARSA, and dynamic programming methods had all been proven to diverge with simple function approximators on simple problems.

Instead of building a value function and extracting a policy from it, parameterize the policy directly. Let $\pi(s, a, \theta)$ be the probability of taking action $a$ in state $s$ given parameters $\theta$. The policy might be a neural network, a softmax over linear features, or any differentiable function that outputs action probabilities.

Define a performance measure $\rho(\pi)$ — the expected long-term reward under policy $\pi$. The idea is breathtakingly simple: compute $\frac{\partial \rho}{\partial \theta}$ and update parameters in that direction. Small changes in $\theta$ produce small changes in action probabilities, which produce small changes in the state distribution — no discontinuities anywhere.

The question is: can you actually compute this gradient? The performance $\rho$ depends on the policy, which determines which states are visited, which affects the reward. Differentiating through the entire state distribution seems intractable. This is where the Policy Gradient Theorem delivers its surprise.

The theorem says something remarkable: to compute the gradient of performance, you do not need to differentiate through the state distribution $d^\pi(s)$. The gradient can be expressed purely in terms of quantities you can sample from experience. Before seeing the formula, let's set up the pieces.

Consider an agent interacting with a Markov decision process. At each time step, the agent is in state $s$, takes action $a$ according to policy $\pi(s, a, \theta)$, receives reward $r$, and transitions to the next state. The action-value function $Q^\pi(s, a)$ measures how good it is to take action $a$ in state $s$ and then follow $\pi$ forever after. The state distribution $d^\pi(s)$ tells us how often the agent visits each state under policy $\pi$.

Read that formula in plain words: visit states by following your policy, and for each state, ask "how much does adjusting $\theta$ increase the probability of good actions?" The answer — summed over all states and actions, weighted by how often you visit each state and how good each action is — gives you the exact direction to improve.

The magic is what's missing. Changing $\theta$ changes the policy, which changes which states the agent visits. Naively, you'd need $\frac{\partial d^\pi(s)}{\partial \theta}$, which involves differentiating through the entire dynamics of the environment. The theorem shows this term cancels out — the state distribution acts only as a weighting, and you get that weighting for free just by running the policy.

The simplest use of the Policy Gradient Theorem is Williams's REINFORCE algorithm. Instead of knowing $Q^\pi(s, a)$ exactly, use the actual return $R_t$ — the total reward from time $t$ onward — as an unbiased sample. This gives the update rule:

$\Delta \theta_t \propto \frac{\partial \ln \pi(s_t, a_t)}{\partial \theta} R_t$

The term $\frac{\partial \ln \pi}{\partial \theta}$ is called the score function. It points in the direction that increases the probability of the action taken. Multiplying by $R_t$ makes the update larger when the action led to high reward and smaller (or reversed) when it led to low reward. Run a full episode, compute returns, and update — that's REINFORCE.

The problem? Variance. $R_t$ is a single noisy sample of $Q^\pi$. One lucky episode might update parameters dramatically in a direction that isn't actually good on average. Learning is slow because the signal-to-noise ratio is low.

REINFORCE uses full episode returns — a Monte Carlo method. This is unbiased but has high variance and requires waiting for the episode to end. What if we could use a learned value function to estimate $Q^\pi$ instead?

This is the actor-critic architecture. The actor is the policy $\pi(s, a, \theta)$ — it decides what to do. The critic is a learned value function $f_w(s, a)$ — it evaluates how good the actor's choices are. The actor uses the critic's evaluation to compute policy gradients; the critic learns from the actor's experience using temporal-difference methods.

But here's the danger: if the critic's approximation is wrong, the gradient estimate is biased, and the whole thing might converge to the wrong answer. The paper's Theorem 2 resolves this by identifying a compatibility condition — a specific relationship between the critic and the policy parameterization that guarantees the gradient estimate is exact despite the approximation.

Theorem 2 provides the conditions under which a learned critic $f_w$ can replace the true $Q^\pi$ in the Policy Gradient Theorem without introducing bias. Two conditions must hold:

Condition 1 — Compatible features. The critic's gradient must equal the policy's score function: $\frac{\partial f_w(s,a)}{\partial w} = \frac{\partial \ln \pi(s,a)}{\partial \theta}$. This means the critic is linear in the same features that characterize how the policy responds to parameter changes.

Condition 2 — Minimized error. The critic's parameters $w$ must minimize the mean squared error weighted by the state-action distribution under $\pi$. In other words, the critic has been trained to convergence.

When both conditions hold, the approximation error in $f_w$ is orthogonal to the policy gradient direction, so it doesn't corrupt the gradient at all. This is not an "approximately correct" result — it is exact.

Theorem 3 ties everything together. It states that if the actor and critic satisfy the compatibility condition, the policy's second derivatives are bounded, and the learning rate decreases appropriately, then the sequence of policies converges to a local optimum — $\lim_{k \to \infty} \frac{\partial \rho(\pi_k)}{\partial \theta} = 0$.

This was the first proof that policy iteration with general differentiable function approximation converges at all. Previous value-function methods had been proven to diverge with function approximation. This theorem opened the door to scaling RL with neural networks — exactly what would happen a decade and a half later with deep reinforcement learning.

The proof of Theorem 1 reveals why the state distribution disappears from the gradient. The key insight comes from unrolling the value function recursively.

Start from $\frac{\partial V^\pi(s)}{\partial \theta}$ and apply the product rule to $\sum_a \pi(s,a) Q^\pi(s,a)$. You get two terms: (1) the gradient of the policy times $Q^\pi$ — the direct effect — and (2) the policy times the gradient of $Q^\pi$ — the indirect effect through future states. Expanding $Q^\pi$ using the Bellman equation and unrolling recursively, the indirect terms telescope into a sum over future state visitations. When you sum over the stationary distribution $d^\pi$, the future-state terms cancel with the current-state terms (because $d^\pi$ is stationary), leaving only the direct effect.

In the discounted start-state formulation, the cancellation works differently but achieves the same result: the probability of reaching each future state from $s_0$ in $k$ steps, summed over all $k$ with discount $\gamma^k$, defines $d^\pi(s)$ directly.

Every time a language model is fine-tuned with human feedback, every time a robot learns to walk, every time a game agent discovers a new strategy — the Policy Gradient Theorem is running underneath. Sutton et al. did not just solve a convergence problem; they gave reinforcement learning its computational engine.