Policy Gradient Methods: From REINFORCE to Natural Policy Gradient

TL;DR

Policy gradient methods optimize a policy directly by gradient ascent on expected return, rather than learning a value function and acting greedily on it. REINFORCE is the original Monte Carlo estimator but has punishing variance; subtracting a baseline (usually a learned value function) cuts that variance without introducing bias; and Natural Policy Gradient fixes a subtler problem — that a fixed-size step in raw parameter space is not a fixed-size step in policy-behavior space — by rescaling the gradient with the Fisher information matrix. This family is the direct ancestor of every actor-critic method covered in the companion article on this site. Used in robotics control, dialogue policy optimization, neural architecture search controllers, and any continuous or stochastic-policy setting where value-based max doesn’t apply.

Problem Statement

Value-based methods like Q-learning learn Q(s, a) and derive a policy from it implicitly. That’s awkward in two situations: continuous action spaces, where you can’t enumerate every action to take a max, and settings where the optimal policy is genuinely stochastic (e.g., rock-paper-scissors, or partially observable environments where randomization prevents exploitation). Policy gradient methods sidestep both by parameterizing the policy π(a|s; θ) directly and climbing the gradient of expected return with respect to θ.

REINFORCE: The Original Monte Carlo Estimator

The policy gradient theorem gives a remarkably clean estimator: run a full episode, then push up the log-probability of every action taken, scaled by the total return that followed.

def reinforce_loss(log_probs: list[torch.Tensor], rewards: list[float], gamma: float = 0.99):
    returns = []
    G = 0.0
    for r in reversed(rewards):
        G = r + gamma * G
        returns.insert(0, G)
    returns = torch.tensor(returns)

    loss = -sum(lp * G for lp, G in zip(log_probs, returns))
    return loss

This is unbiased — in expectation it points exactly toward higher-return policies — but the variance is enormous. A single lucky or unlucky episode can swing the entire return G used to scale every action in that episode, even actions that had nothing to do with the outcome.

Baseline Subtraction: Cutting Variance for Free

Subtracting any state-dependent baseline b(s) from the return leaves the gradient estimator unbiased (this falls directly out of the policy gradient theorem) while sharply reducing its variance, because what matters isn’t the raw return but how much better it was than expected:

def reinforce_with_baseline_loss(log_probs, rewards, values, gamma=0.99):
    returns = compute_returns(rewards, gamma)
    advantages = returns - values.detach()   # baseline: a learned V(s)

    policy_loss = -sum(lp * a for lp, a in zip(log_probs, advantages))
    value_loss = F.mse_loss(values, returns)
    return policy_loss + value_loss

The moment the baseline is a learned value function trained alongside the policy, this is no longer pure REINFORCE — it’s the seed of actor-critic. The companion article on this site picks up from exactly this point and carries it through A2C, A3C, DDPG, TD3, SAC, and PPO.

Natural Policy Gradient

Ordinary gradient ascent takes equal-sized steps in parameter space, but the same-sized step can correspond to a tiny change in policy behavior in one direction and a catastrophic change in another — softmax probabilities near 0 or 1 are far more sensitive to a parameter nudge than probabilities near 0.5. Natural Policy Gradient (Kakade, 2002) corrects for this by rescaling the gradient with the inverse Fisher information matrix, which measures curvature in terms of KL-divergence between policies rather than raw parameter distance:

θ_new = θ_old + α · F(θ)⁻¹ · ∇_θ J(θ)

def natural_gradient_step(fisher_matrix, vanilla_grad, learning_rate=0.01):
    natural_grad = torch.linalg.solve(fisher_matrix, vanilla_grad)  # F^-1 * grad
    return learning_rate * natural_grad

In practice, computing and inverting the full Fisher matrix is too expensive for large networks — this is precisely the problem TRPO (covered in the actor-critic article) solves approximately with conjugate gradients, and that PPO later sidesteps entirely with a clipped surrogate objective. Natural Policy Gradient is best understood as the theoretical ancestor both of those methods reference explicitly.

Comparison Table

Applications

• Robotics control — early policy gradient methods were among the first successful approaches to continuous-torque control before actor-critic variants took over.
• Dialogue and recommendation policies — sequential decision problems with large or structured discrete action spaces where enumerating a max over Q-values is impractical.
• Neural architecture search — REINFORCE was used to train a controller network that outputs architecture decisions, treating validation accuracy as the reward.
• Any genuinely stochastic-optimal-policy setting — game-theoretic and adversarial environments where a deterministic policy is exploitable.

Key Learnings

1. The baseline is the single highest-leverage idea in this family. It’s a free variance reduction with zero bias cost, and it’s the conceptual seed that turns pure policy gradient into actor-critic.
2. Raw gradient steps and “natural” steps are not the same thing, and the gap between them is exactly what motivated the trust-region line of methods (TRPO, PPO) that dominate practical use today.
3. This family exists because value-based methods can’t take a max over continuous actions. Understanding policy gradients is what makes the actor-critic family’s design choices — why an explicit actor network is needed at all — make sense.