From REINFORCE to Trust Regions

The policy-gradient promise — and its noise

Volume I introduced policy gradients as a way to optimize a policy directly: parameterize π(a|s;θ), then push θ uphill along the gradient of expected return. The policy-gradient theorem gives that gradient as an expectation of (∇ log π) weighted by how good the action turned out to be — so we can estimate it from sampled trajectories without ever differentiating the environment. That is the whole reason policy gradients work in worlds we cannot model.

The catch is variance. The vanilla estimator multiplies the score function by the raw return, which lumps together the effect of the action we are crediting with the effect of every other random choice in the episode. The result is an unbiased but extremely high-variance signal: gradients that point in wildly different directions from one batch to the next. Most of graduate-level policy-gradient theory is a campaign to reduce that variance without introducing bias — and to take steps in the right geometry once the direction is trustworthy.

\nabla_\theta J(\theta) = \mathbb{E}_{\tau\sim\pi_\theta}\!\left[\sum_{t}\nabla_\theta \log \pi_\theta(a_t\mid s_t)\, G_t\right]

The REINFORCE score-function estimator: unbiased, but every action is credited with the whole noisy return G_t.

Advantage estimation: the bias–variance dial

The first move is to subtract a state-dependent baseline — typically the value function V(s) — turning the raw return into an advantage A(s,a) = Q(s,a) − V(s): how much better this action was than the policy's average. Subtracting V is provably unbiased (it does not depend on the action) yet cuts variance dramatically. But how do we estimate A? A one-step temporal-difference target is low-variance but biased by a wrong value estimate; a full Monte Carlo return is unbiased but high-variance.

Generalized advantage estimation (GAE) gives you a continuous knob between those extremes. It forms an exponentially weighted average of n-step TD residuals with a decay λ ∈ [0,1]: λ→0 collapses to the low-variance, high-bias one-step estimate; λ→1 recovers the high-variance, unbiased Monte Carlo estimate. In practice λ≈0.95 with γ≈0.99 is a sweet spot, and the recursion below makes it a single backward pass over a trajectory.

delta_t = r_t + gamma * V(s_{t+1}) - V(s_t)   # one-step TD residual
A_t = delta_t + (gamma * lam) * A_{t+1}        # backward recursion over the episode

GAE as a single backward sweep; λ trades bias against variance.

Why the Euclidean step is the wrong step

Even with a clean advantage estimate, ordinary gradient ascent treats θ-space as flat Euclidean space — it moves a fixed distance in parameters. But what we care about is distance in policy space: a tiny change to a sensitive parameter can swing the action distribution violently, while a large change to an inert one does nothing. Steepest descent in the wrong metric produces erratic, scale-dependent updates.

The natural policy gradient fixes this by preconditioning the gradient with the inverse Fisher information matrix — the natural Riemannian metric on the manifold of probability distributions. Equivalently, it measures step size as the KL divergence between the old and new policies rather than as Euclidean parameter distance. This is exactly natural gradient descent specialized to RL, and it makes the update invariant to how you happen to parameterize the policy.

\tilde{\nabla}_\theta J = F(\theta)^{-1}\,\nabla_\theta J,\qquad F(\theta)=\mathbb{E}\!\left[\nabla_\theta \log \pi_\theta\,\nabla_\theta \log \pi_\theta^{\top}\right]

The natural gradient preconditions by the inverse Fisher matrix F, measuring distance in policy space rather than parameter space.

Trust regions and monotonic improvement

Trust-region policy optimization (TRPO) turns the natural-gradient intuition into a principled algorithm with a guarantee. It maximizes a surrogate objective — the advantage of the new policy estimated under the old policy's samples via importance weighting — subject to a hard constraint that the average KL divergence from the old policy stays below a small δ. The theory shows this surrogate is a lower bound on true performance, so optimizing it inside the trust region yields approximately monotonic improvement: each update is guaranteed not to make things much worse.

Collect a batch of trajectories under the current policy and compute GAE advantages.
Estimate the surrogate objective and the policy gradient g, plus the Fisher matrix F implicitly.
Solve for the natural-gradient direction F⁻¹g using conjugate gradient (no explicit matrix needed).
Line-search the step length so the KL constraint holds and the surrogate actually improves.

PPO — the pragmatic clip

TRPO is principled but heavy: the conjugate-gradient solve and line search make it awkward to scale. Proximal policy optimization (PPO) keeps the trust-region spirit with first-order machinery. It clips the importance-sampling ratio r(θ) = π_new/π_old to the interval [1−ε, 1+ε], so once the new policy has moved far enough on a sample, the objective flattens and the gradient stops pushing. There is no hard constraint and no second-order solve — just a clipped surrogate you optimize with ordinary SGD over several epochs per batch.

L^{\mathrm{CLIP}}(\theta)=\mathbb{E}_t\!\left[\min\!\left(r_t(\theta)\,\hat{A}_t,\ \mathrm{clip}\!\left(r_t(\theta),\,1-\epsilon,\,1+\epsilon\right)\hat{A}_t\right)\right],\quad r_t(\theta)=\frac{\pi_\theta(a_t\mid s_t)}{\pi_{\theta_{\text{old}}}(a_t\mid s_t)}

PPO's clipped surrogate: clamping the probability ratio r_t enforces the trust region with only first-order updates.

ratio = exp(logp_new - logp_old)
unclipped = ratio * A
clipped   = clip(ratio, 1 - eps, 1 + eps) * A
loss = -mean(min(unclipped, clipped))   # pessimistic: take the worse of the two

PPO's clipped surrogate — a first-order stand-in for the trust region.