PaperlayerView exact revision on arXiv

Source-linked AI summary

Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic

Hongyi Zhou, Kai Ye, Erhan Xu, Jin Zhu, Ying Yang, Shijin Gong, Chengchun Shi

arXiv:2603.01162v3cs.LGstat.ML

TL;DR

GRPO is widely used for LLM reasoning, but its theoretical properties and the basis for its group-mean critic approximation remain insufficiently understood. This paper analyzes GRPO through U-statistics and shows that its gradient estimator has oracle and asymptotically optimal properties, while deriving guidance for group-size selection. The analysis also includes finite-sample and asymptotic policy results, with empirical support for the theoretical findings.

  • Problem

    GRPO’s theoretical properties and the rationale for replacing its critic with a group mean remain insufficiently understood, despite its practical use in LLM reasoning.

  • Method

    The paper models GRPO’s policy gradient as a U-statistic and applies finite-sample analysis, Hoeffding decomposition, and asymptotic analysis to gradients and learned policies.

  • Results

    GRPO is asymptotically equivalent to an oracle policy-gradient algorithm and asymptotically optimal within a broad class of algorithms, with a scaling law for optimal group size.

  • Takeaways & Limitations

    The U-statistic framework provides a statistical basis for GRPO’s group-mean estimator and principled guidance for selecting its group size.

  • Takeaways & Limitations

    The simplified analysis omits reward normalization, importance sampling, and KL regularization, while the empirical group-size comparisons use only five independent runs because training is computationally costly.

Abstract

from arXiv · show

Group relative policy optimization (GRPO), a core methodological component of DeepSeekMath and DeepSeek-R1, has emerged as a cornerstone for scaling reasoning capabilities of large language models. Despite its widespread adoption and the proliferation of follow-up works, the theoretical properties of GRPO remain less studied. This paper provides a unified framework to understand GRPO through the lens of classical U-statistics. We demonstrate that the GRPO policy gradient is inherently a U-statistic, allowing us to characterize its mean squared error (MSE), derive the finite-sample error bound and asymptotic distribution of the suboptimality gap for its learned policy. Our findings reveal that GRPO is asymptotically equivalent to an oracle policy gradient algorithm -- one with access to a value function that quantifies the goodness of its learning policy at each training iteration -- and achieves asymptotically optimal performance within a broad class of policy gradient algorithms. Furthermore, we establish a universal scaling law that offers principled guidance for selecting the optimal group size. Empirical experiments further validate our theoretical findings, demonstrating that the optimal group size is universal, and verify the oracle property of GRPO.

1 Introduction

GRPO addresses practical challenges in reinforcement-learning post-training for LLM reasoning by replacing the expensive critic network with group-based estimates. This paper analyzes the approach through U-statistics, deriving finite-sample and asymptotic results, oracle and optimality properties, and a universal group-size scaling law.

  • Motivation: GRPO eliminates the critic network by sampling multiple outputs per prompt and using their group average as a proxy for the critic.This reduces the computational burden of maintaining and updating a separate critic model in reasoning tasks.
  • Open questions: The paper identifies a theoretical gap surrounding GRPO’s effectiveness, the rationale for its group mean, convergence, and the number of outputs to sample.These questions concern both the statistical basis of the estimator and practical group-size selection.
  • Theoretical framework: GRPO’s policy gradient is shown to be inherently a U-statistic, providing a classical-statistical explanation for using the group mean to approximate the critic.The paper uses this connection to analyze the algorithm and its variants.
  • Theoretical results: The paper derives finite-sample MSE and suboptimality-gap bounds, parameter consistency, and an asymptotic suboptimality-gap distribution without requiring parameter identifiability.The analysis addresses convergence questions while accounting for overparameterized LLMs.
  • Theoretical results: GRPO is asymptotically equivalent to an oracle algorithm and asymptotically optimal within a broad class of policy-gradient algorithms.The paper reports empirical evidence supporting these oracle and optimality properties.
  • Practical implication: The optimal group size depends only on training data and model architecture, rather than training budget or iteration count.This scaling-law result is presented as a universal guide for selecting the number of sampled outputs.

2 Related works

The related work connects GRPO’s role in LLM reasoning with reinforcement learning, RLVR, and classical U-statistics. It also situates the paper among practical GRPO variants and the limited existing theoretical analyses of their foundations.

  • Reinforcement learning: Reinforcement learning research spans planning and learning, with model-free learning divided into value-based and policy-based approaches.The paper places GRPO close to policy-based methods such as REINFORCE and actor-critic.
  • Reinforcement learning: RL research has progressed through classical RL, deep RL, offline RL, and RLHF, with different settings emphasizing function approximation, exploration, safety, or preference alignment.These phases provide the broader methodological context for GRPO.
  • LLM reasoning and RLVR: RLVR post-trains LLMs using objective verifiers, such as matching mathematical solutions or executing generated code, rather than subjective human preferences.GRPO is presented as a major RLVR algorithm for scaling LLM reasoning.
  • GRPO extensions: Follow-up GRPO research modifies the baseline, importance-sampling ratio, reward normalization, optimization objective, or training-efficiency strategy.These works include methods for exploration, length or difficulty awareness, risk sensitivity, and trajectory reuse.
  • Theoretical gap: Existing theoretical work on GRPO has studied gradient and advantage biases, gradient norms, and objective functions, but the broader theoretical foundations remain largely unexplored.The paper addresses this gap using U-statistics.
  • U-statistics: The decomposition makes U-statistics asymptotically equivalent to averages of i.i.d. variables, enabling classical limit theorems for analyzing GRPO’s gradient and learned policy.This provides the statistical foundation for the paper’s analysis.

3 Preliminaries

The paper formulates LLM reasoning as sequential decision-making and introduces a meta-algorithm that unifies policy-gradient methods, including REINFORCE, actor-critic, and GRPO variants. It explains how sparse terminal rewards, baselines, minibatches, and grouped outputs support these algorithms.

  • 3.1 Problem setup: LLM reasoning is modeled as sequential decision-making, with prompts as observations, generated tokens as actions, and a terminal reward for the completed response.The policy generates tokens autoregressively, while the reward evaluates the completed output.
  • 3.1 Problem setup: The framework can alternatively treat each complete output as one action, reducing the sequence problem to a bandit over context-action-reward tuples.This collapses the time horizon to T = 1.
  • 3.2 A meta-algorithm: Baseline subtraction reduces gradient-estimator variance without changing its expectation when the baseline depends only on the prompt and is conditionally independent of the output and reward.This preserves unbiasedness under the stated condition.
  • 3.2 A meta-algorithm: GRPO eliminates a separate critic by using sampled group outputs to construct a group-mean baseline, whereas A2C uses a learned critic network.Sampling from the policy is presented as more computationally efficient than training a critic model.
  • 3.2 A meta-algorithm: The meta-algorithm samples B prompts and G outputs per prompt, obtains rewards, applies a baseline, and uses the resulting estimates for gradient-based policy updates.Its inputs include the prompt distribution, initial parameters, learning rates, batch size, group size, and baseline functions.
  • 3.2 A meta-algorithm: The unified framework recovers REINFORCE, A2C, and GRPO-type methods through different choices of batch size, group size, and baseline.REINFORCE uses B = 1, G = 1, and a zero baseline; A2C uses a critic; GRPO-type methods use leave-one-out group means.
  • 3.2 A meta-algorithm: The analyzed algorithm simplifies production GRPO by omitting reward normalization, importance sampling, and the KL-divergence penalty.The paper states that these gaps are addressed in analyses of related variants and supplementary material.

4 Main results

The paper analyzes GRPO through U-statistics, deriving finite-sample and asymptotic results for its gradient estimator and learned-policy suboptimality. These results establish oracle and optimality properties, a universal group-size scaling law, and supporting extensions for practical variants.

  • Gradient evaluation: GRPO’s policy gradient is a second-order U-statistic, enabling classical U-statistical analysis of its group-mean critic approximation.This connection is formalized in Lemma 1.
  • Gradient evaluation: The gradient estimator’s MSE decomposes into first- and second-order projection terms, with rates G^-1 and G^-2, respectively.The leading first-order term matches the oracle estimator’s MSE, while the second-order term is a higher-order residual.
  • Policy optimization: The universal optimal group size G* balances sampling-budget terms and depends on the data-generating process and policy-space geometry, not budget, iteration count, or learning-rate schedule.The scaling law applies under fixed per-iteration or total sampling budgets.
  • Gradient evaluation: As G →∞, GRPO’s estimator MSE becomes equivalent to the oracle estimator’s MSE, establishing the gradient estimator’s oracle property.The result holds in both prompt-conditional and overall forms.
  • Gradient evaluation: GRPO asymptotically minimizes MSE among gradient estimators with prompt-only baselines and has strictly smaller asymptotic MSE than vanilla.The optimality result requires Assumptions 1 and 2, including conditional uncorrelation.
  • Policy optimization: Finite-sample suboptimality bounds depend on gradient-estimator MSE, while Theorem 8 establishes consistency and a weighted sum of independent χ2 variables for the asymptotic gap.The asymptotic result applies in the overparameterized regime without parameter identifiability.
  • Policy optimization: Sharper suboptimality upper bounds alone do not prove a strictly smaller actual gap, motivating the asymptotic-distribution analysis.This limitation concerns conclusions based only on upper bounds.
  • Policy optimization: The policy-level oracle and optimality properties follow from the estimator results, making GRPO asymptotically equivalent to the oracle policy as G →∞.The paper also extends its analyses to reward standardization, importance sampling, and KL penalties.

5 Experiments

Experiments validate GRPO’s oracle-like gradient behavior and investigate how group size affects optimization under fixed sampling budgets. Results support a universal, intermediate optimal group size, while limited runs constrain statistical conclusions.

  • 5.1 Oracle property in gradient evaluation: GRPO-type gradients have lower MSE than vanilla gradients across group sizes and target policies.
  • 5.1 Oracle property in gradient evaluation: At G = 8, GRPO-type MSE is already close to the oracle estimator, becoming nearly indistinguishable at G = 32 or 64.
  • 5.1 Oracle property in gradient evaluation: All estimators’ MSE decreases as group size increases and as model reasoning capability improves.
  • 5.2 Optimal group size for policy optimization: Under a fixed sampling budget, increasing group size reduces estimator MSE but increases computational cost, producing an intermediate optimum dependent on data and the policy model.
  • 5.2 Optimal group size for policy optimization: Except at n = 200, GSM8K accuracy generally rises with G and then falls, matching the predicted scaling-law trade-off.
  • 5.2 Optimal group size for policy optimization: G = 32 is consistently optimal across the other GSM8K training steps, supporting universality with respect to training iteration.
  • 5.2 Optimal group size for policy optimization: Only five GSM8K runs per setting were conducted, leaving most group-size accuracy differences statistically insignificant because additional runs were computationally infeasible.
  • 5.2 Optimal group size for policy optimization: On MATH, the optimal group size is mostly 64 and increases to 128 as the sampling budget grows.

6 Conclusion

The paper develops a rigorous statistical account of GRPO through U-statistics, covering estimator error, policy suboptimality, oracle behavior, optimality, and group-size scaling. Theory and experiments support GRPO’s oracle and optimality properties and the universality of its group-size scaling law.

  • GRPO’s policy-gradient estimator is a U-statistic, enabling MSE analysis through Hoeffding’s decomposition.
  • The analysis derives finite-sample suboptimality bounds, an asymptotic suboptimality distribution, and oracle and optimality properties for policy learning.
  • A scaling law guides the optimal group-size choice, with empirical validation across training iterations supporting its universality.
  • The framework also extends to reward normalization, importance sampling, and KL-divergence penalties.

A Practical considerations

The practical GRPO formulation differs from the original implementation through normalization, importance sampling, and KL regularization, while its estimator admits asymptotic U-statistic analysis. These choices create bias-variance trade-offs and establish oracle-like variance behavior as group size grows.

  • Importance sampling: Token-level importance sampling reduces variance relative to sequential ratios but introduces bias because outputs come from the old policy.Sequential ratios provide unbiased correction but suffer exponentially growing variance with the horizon.
  • Estimator structure: Reward normalization makes the gradient estimator only asymptotically equivalent to a U-statistic because its kernel depends on data-dependent reward dispersion.The equivalence holds as G →∞ under coverage and related assumptions.
  • KL regularization: The practical KL term omits importance sampling and therefore contributes another source of bias in the gradient estimator.Theorem 12 upper-bounds both squared bias and variance from these sources.
  • Estimator accuracy: The bias terms scale with the next learning rate η_i+1 and vanish as η_i+1 approaches zero.This is part of the MSE bias-variance decomposition for the practical gradient estimator.
  • Estimator accuracy: The leading variance term equals the variance of an oracle estimator that knows the value function, while the remaining U-statistic error is O(G^-2).As G grows, the estimator reaches the oracle estimator’s asymptotic variance.
  • Scope: The analysis leaves two practical gaps: original GRPO’s length normalization and the sophisticated optimizers used instead of simple stochastic gradient descent.These differences are left for future research.

B.1 Group relative gradient evaluation

The group-relative gradient can be analyzed through Hoeffding’s decomposition: its first-order component is the oracle gradient, while its second-order component determines additional sampling error. This yields an explicit MSE decomposition and oracle comparisons.

  • U-statistic decomposition: Hoeffding decomposition separates the U-statistic into orthogonal first- and second-order components with zero means.The orthogonality relations produce the MSE decomposition.
  • Oracle comparison: The first-order component of the GRPO gradient estimator is exactly the oracle gradient estimator.The oracle estimator corresponds to knowing the relevant value function in advance.
  • MSE: Under the stated conditional-independence assumption, the interaction term vanishes, simplifying the comparison with the oracle estimator.The resulting relation gives the GRPO estimator’s MSE in terms of oracle variance.

B.2 Group relative policy optimization

The policy-optimization analysis establishes convergence and asymptotic behavior under learning-rate schedules, while separating identifiable from non-identifiable parameter directions. The suboptimality gap converges to zero, and the identifiable component admits asymptotic normality.

  • Consistency: The analysis proves consistency of the learned policy parameter under the stated assumptions and learning-rate framework.The consistency result is established for θ_n as n increases.
  • Convergence rate: The parameter error satisfies E[d^2(θ_n, Θ*)] = O(n^-1) in the convergence-rate analysis.This rate appears as an intermediate step toward asymptotic distribution results.
  • Convergence: The suboptimality gap converges to zero almost surely under the diminishing learning-rate analysis.The proof establishes almost sure convergence of Δ(π_θn) and θ_n toward the optimal set.
  • Asymptotic normality: Because overparameterized models are not fully identifiable, asymptotic normality is established for the identifiable projection Q^Tθ_n rather than the full parameter vector.The matrix Q spans the identifiable subspace.
  • Asymptotic normality: The weak strong concavity condition allows the identifiable recursion to be approximated using H = −βH* despite dependence on non-identifiable components.The approximation isolates the asymptotically relevant dynamics.

B.3 Practical considerations

The practical estimator is asymptotically analyzed by replacing empirical reward dispersion with its population counterpart, yielding a U-statistic representation and a bias-variance characterization. The proof relies on boundedness, coverage, and nondegenerate reward variance assumptions.

  • Asymptotic representation: The empirical reward standard error converges in probability to the population standard deviation as group size G grows.This enables replacing the data-dependent normalization in the gradient estimator.
  • Asymptotic representation: After this replacement, the gradient estimator becomes asymptotically equivalent to a U-statistic with a fixed kernel.The result follows under bounded rewards, bounded scores, coverage, and reward standard deviation bounded away from zero.
  • MSE analysis: The MSE analysis decomposes the estimator error into squared bias and variance components.The bias is defined relative to the ground-truth gradient, and each component is bounded under the stated assumptions.
  • Policy objective: The ground-truth gradient is asymptotically equivalent to the derivative of the policy objective under the paper’s assumptions.This connection supports consistency analysis for the learned policy parameter.

B.4 Auxiliary lemmas and their proofs

The auxiliary lemmas establish geometric properties near maximizers, spectral bounds under the PL condition, and technical convergence results used in the analysis. Their proofs rely on Taylor expansions, induction, and standard stochastic-approximation theorems.

  • Lemma 14: Lemma 14 proves its sequence bound by choosing n0 and completing a base case plus induction step.The induction uses M = max{(1 + ε)C/(A −1), an0} to control the recurrence.
  • Lemma 15: Lemma 15 shows that Q^TΘ* is a singleton when the Hessian at the optimum has positive curvature in its r nonzero eigendirections.The proof converts equality of objective values into a sum of nonnegative squared coordinate differences.
  • Lemma 15: The proof of Lemma 15 concludes v1 = v2 by expanding the quadratic form in the eigenbasis.
  • Lemma 16: Every positive eigenvalue of −∇θg(θ*) is at least the PL constant µ, and L ≥ µ under smoothness.The argument applies Taylor’s theorem along an eigenvector and then lets the step size approach zero.
  • Stochastic tools: Lemma 17 states that a nonnegative adapted sequence converges almost surely when its cumulative error terms are summable.
  • Stochastic tools: Lemma 18 supplies a stochastic-recursion result for random matrices converging to a matrix whose eigenvalues exceed 1/2.The result is cited from Propositions B.1 and B.2 of Zhang (2016).

C Experiment Details

The experiment details specify the GRPO algorithm, prompt templates, reward generation, minibatch construction, and parameter updates used in Section 5. The setup generates grouped outputs for each prompt and returns a learned policy.

  • Prompt templates: The in-context learning prompt asks the model to solve an arithmetic problem and return only the final integer.
  • Prompt templates: The Base and Instruct prompt adds a calculator role before presenting the arithmetic problem template.
  • GRPO algorithm: Algorithm 2 takes a prompt distribution, initial parameter, learning rates, batch size, group size G, minibatch count, KL coefficient, and reference model.
  • GRPO algorithm: For each prompt, the procedure generates G outputs and obtains a reward for every output.The rewards are organized as Z(b,•), with the empirical group mean and its standard error used in the procedure.
  • GRPO algorithm: The experiments partition prompts into m equal-sized disjoint minibatches, update the parameter, and output policy πθ.
Loading 2603.01162v3…