The Evolution of Policy Gradient Algorithms: The Complete Lineage from REINFORCE to PPO to GRPO

From Algorithm Checklists to an Evolutionary Narrative

For newcomers to reinforcement learning (RL), policy gradient algorithms often feel like a bewildering checklist: REINFORCE, Actor-Critic, TRPO, PPO, GRPO… They're listed side by side, yet rarely does anyone explain the causal relationships between them.

The core idea behind policy gradient methods is to transform RL into an optimization problem: directly parameterize the policy function π(a|s;θ), then maximize the expected cumulative return J(θ) through gradient ascent. The mathematical foundation for this approach is the Policy Gradient Theorem, formally introduced by Sutton et al. in 1999. The theorem proves that the gradient of expected return with respect to policy parameters can be expressed as an expectation, which can then be estimated through Monte Carlo sampling. Unlike value-based methods (such as Q-learning), policy gradient methods can naturally handle continuous action spaces and learn stochastic policies—particularly important in game theory and exploration problems.

A researcher with a PhD background in reinforcement learning shared his thoughts on Reddit, hitting this pain point directly: "Online tutorials mostly present these algorithms as a list. The evolutionary story—where each algorithm patches the most painful failure of the previous one—does exist, but it's scattered across a full-semester course like CS285, or buried in the original papers."

CS285 is UC Berkeley's deep reinforcement learning course taught by Professor Sergey Levine, widely regarded as one of the most authoritative graduate-level public courses in the field. The course comprehensively covers everything from fundamental MDP theory to cutting-edge model training methods, including policy gradients, Actor-Critic, model-predictive control, and offline RL. Since the course recordings and materials are freely available, it has become an essential resource for RL self-learners worldwide—though its semester-long scope and high mathematical prerequisites can be daunting for many beginners.

He invested considerable effort in writing a "compressed" narrative: a single-page, semi-technical walkthrough that goes from the most primitive RL objective function all the way to GRPO. The mathematics is intentionally simplified, targeting readers who entered RL through the "reasoning model wave" rather than researchers needing complete derivations.

The Core Narrative: Each Policy Gradient Algorithm Patches the Previous One's Pain Point

The most valuable aspect of this material is how it reorganizes the development of policy gradients into a causal chain of "problem → fix." Understanding this chain matters far more than memorizing each algorithm's formulas in isolation.

REINFORCE: The Starting Point of Policy Gradients and the Curse of High Variance

It all begins with the most straightforward policy gradient estimator: REINFORCE. It directly computes the gradient of expected return—an elegant approach—but suffers from a fatal flaw: extremely high estimator variance. Because the total return of complete trajectories fluctuates enormously, the gradient signal gets drowned in noise, making training slow and unstable. The author even designed an interactive chart so readers can viscerally feel just how absurd REINFORCE's estimator variance can be.

REINFORCE was proposed by Ronald Williams in 1992 and is one of the earliest policy gradient algorithms. Its core formula is: ∇J(θ) ≈ (1/N)Σ[Σ∇log π(aₜ|sₜ;θ) · R(τ)], where R(τ) is the cumulative return of the entire trajectory. The high variance stems from the fundamental nature of Monte Carlo estimation: every action in a trajectory is multiplied by the total return of the entire trajectory, and total returns are influenced by multiple sources of randomness—environmental stochasticity, policy stochasticity, and more—potentially fluctuating across an enormous range. In practice, this means millions of trajectory samples may be needed to obtain reliable gradient estimates, resulting in extremely low training efficiency.

Introducing the Baseline: The First Variance Reduction Attempt

The most natural fix for high variance is introducing a "baseline." By subtracting a reference value from the return, we can dramatically reduce variance without introducing bias. The "baseline slider" in the material lets readers manually adjust the baseline value and observe how variance changes accordingly—this is exactly the key intuition for understanding Actor-Critic methods.

Introducing a baseline exploits an important mathematical property: subtracting any function b(s) that doesn't depend on the action from the return won't change the expected value of the gradient estimate (i.e., unbiasedness is preserved), but can significantly reduce variance. The optimal baseline choice turns out to be exactly the state value function V(s)—which is the core idea behind Actor-Critic methods. In the Actor-Critic architecture, the Actor is the policy network π(a|s;θ) responsible for decisions, while the Critic is the value network V(s;w) responsible for evaluation. The advantage function A(s,a) = Q(s,a) - V(s) measures how good a particular action is relative to the average, and using it instead of raw returns dramatically reduces variance. GAE (Generalized Advantage Estimation) further introduces a λ parameter to smoothly trade off between bias and variance.

The Risk of On-Policy Collapse

Policy gradient methods are inherently on-policy: you must use data collected by the current policy to update that same policy. If an update step is too large, the policy can "collapse" into a terrible region from which it never recovers. The author uses an "on-policy collapse simulator" to demonstrate this phenomenon—which also explains why subsequent algorithms are so careful about controlling update magnitude.

On-policy methods require that the data used to update the policy must be generated by the current policy, meaning that after each parameter update, all previously collected data becomes "stale" and must be re-sampled. This results in extremely low sample efficiency—vast computational resources are spent on data collection rather than learning. Off-policy methods (such as DQN, SAC) can reuse historical data, improving sample utilization through Experience Replay Buffers. Policy gradient methods are naturally on-policy because the expectation in the gradient estimate is taken over the current policy's distribution; using data from an old policy introduces distribution shift. Importance Sampling can partially mitigate this issue but introduces its own variance problems—especially when the new and old policies differ significantly, causing importance weights to explode in variance.

From TRPO to PPO: The Art of Constrained Policy Updates

To solve the collapse problem caused by large update steps, TRPO (Trust Region Policy Optimization) introduced the idea of a "trust region": each update is constrained to stay within a range where the new and old policy distributions don't differ too much. However, TRPO's implementation is quite complex, involving second-order optimization and KL divergence constraints.

TRPO was proposed by John Schulman et al. in 2015, drawing its core idea from trust region methods in optimization theory. The algorithm formalizes policy updates as a constrained optimization problem: maximize a surrogate objective while constraining the KL divergence between old and new policies to not exceed a threshold δ. The KL divergence D_KL(π_old || π_new) measures the difference between two probability distributions, used here to quantify the "step size" of a policy update. TRPO uses conjugate gradient methods and line search to approximately solve this constrained optimization problem, involving computation of the Fisher information matrix—a second-order method with significantly higher computational overhead than standard gradient descent. It was precisely this implementation complexity that motivated PPO's creation.

The author acknowledges simplifying the explanation of TRPO's surrogate objective to maintain narrative flow. This is also one of the areas where he actively solicited community criticism: "I simplified in a few places to keep the narrative moving, most notably around GAE and the TRPO surrogate objective. I genuinely want corrections, or pointers to where you think simplifications crossed the line into errors."

PPO (Proximal Policy Optimization) is the "engineering-friendly, democratized version" of TRPO. It replaces the complex trust region constraint with a clever clipped objective function, preserving the core idea of limiting update magnitude while vastly simplifying implementation. Specifically, PPO's objective function is: L(θ) = E[min(r(θ)·A, clip(r(θ), 1-ε, 1+ε)·A)], where r(θ) = π_new(a|s)/π_old(a|s) is the probability ratio and ε is typically set to 0.1 or 0.2. The min operation ensures that: when the update direction is correct (A>0), the probability ratio won't exceed 1+ε; when the update direction is wrong (A<0), the probability ratio won't drop below 1-ε. This "pessimistic" objective function automatically limits update magnitude without explicitly computing KL divergence or solving constrained optimization.

The material provides an interactive PPO clipping objective chart with adjustable epsilon, helping readers understand how the clipping mechanism constrains policy updates in practice—this is also the workhorse algorithm behind today's large model RLHF training.

RLHF (Reinforcement Learning from Human Feedback) is the mainstream paradigm for current large language model alignment, systematized by OpenAI in the InstructGPT paper. The process involves three steps: first, train a base model with supervised fine-tuning (SFT); then train a reward model using human preference data; finally, optimize the language model policy with RL algorithms like PPO to maximize the reward model's scores. In this framework, the language model is the policy network—generating each token is equivalent to selecting an action in sequential decision-making, with reward signals coming from the reward model's scoring of complete responses. PPO's role here is to ensure the model doesn't drift too far from the original SFT model while pursuing high rewards—a concrete embodiment of the trust region philosophy in large model training.

GRPO: A New Policy Gradient Solution for the Reasoning Model Era

The narrative culminates with GRPO (Group Relative Policy Optimization), a method receiving considerable attention in current reasoning model training. GRPO's core innovation is replacing traditional value function estimation with "group baselines": sample multiple answers to the same problem, compute gradients using relative advantages within the group, thereby eliminating the overhead of training a separate value network.

GRPO was first proposed and implemented by the DeepSeek^Ad team in their DeepSeek-R1 related work. Traditional PPO requires maintaining four models simultaneously: the policy model, reference model, reward model, and value model (Critic)—which brings enormous memory and computational overhead at large model scales. GRPO's key insight is: if you sample a group of answers (e.g., 16) for the same prompt, the group's average return serves as a natural baseline estimate requiring no additional network. Each answer's advantage value is computed through within-group normalization: A_i = (R_i - mean(R)) / std(R). This design completely eliminates Critic network training, nearly halving memory requirements—particularly suitable for reasoning-intensive tasks where answer correctness can be verified by rules (such as math problems and coding problems). DeepSeek-R1's success demonstrated GRPO's effectiveness in training large-scale reasoning models.

This design directly echoes the author's stated motivation—serving "newcomers who entered RL through the reasoning model wave." Since 2024, the AI industry has seen a shift from simply scaling model parameters (scaling laws) toward enhancing model reasoning capabilities. OpenAI's o1 series first demonstrated the enormous potential of training models to perform "slow thinking" (chain-of-thought reasoning) through reinforcement learning. Subsequently, open-source models like DeepSeek-R1 and Qwen-2.5 proved the reproducibility of this approach. The core training paradigm for these reasoning models is exactly RL based on policy gradients: models generate reasoning chains, receive rewards based on final answer correctness, then update their policies through algorithms like GRPO or PPO. This wave has made RL algorithms—previously active mainly in robotics control and game AI—suddenly required knowledge for NLP practitioners.

As models like DeepSeek have thrust GRPO into the spotlight, an increasing number of practitioners need to understand where it came from and what problems it solves. This material places GRPO back in its proper position along the entire evolutionary chain: it didn't appear from nowhere, but represents a natural continuation of all the preceding ideas about variance reduction and update control.

Why the "Chain" Approach Is More Effective for Learning Policy Gradient Algorithms

The value of this material lies not in mathematical depth, but in its narrative framework. Understanding algorithm evolution as a chain of "pain point → fix → new pain point" helps learners build genuine intuition rather than relying on mechanical memorization.

Notably, the author used Claude to build numerous interactive elements and visualizations—itself a nice case study in AI-assisted content creation. Interactive variance demonstrations, baseline sliders, collapse simulators, and more transform abstract mathematical concepts into manipulable, intuitive experiences—something static papers struggle to achieve.

The author also previewed his next planned piece: mapping out the value-based algorithm lineage (Q-learning → DQN → Rainbow). He specifically emphasized that criticism of this policy gradient article would also help improve the next one's quality—this open, iterative approach to knowledge sharing is itself worth emulating in learning communities.

Conclusion

For anyone seeking a systematic understanding of modern reinforcement learning—especially those wanting to grasp the PPO/GRPO logic behind large model training—this "evolutionary chain" approach provides a clear entry path. It reminds us that algorithms are never isolated collections of tricks, but crystallized wisdom built by generations of researchers facing concrete failures and gradually patching them. Once you understand this chain, reading original papers or taking complete courses yields a fundamentally different experience.