University of Illinois Urbana-Champaign
RL with verifiable rewards learns from answers that can be checked. Policy staleness and training–inference mismatch mean those answers may come from a different policy. Can we still improve the learner without importance weights?
Fix one prompt. Each action is a complete response with reward . The learner , parameterized by , balances reward against KL divergence from the reference policy , with strength . Its adjusted reward and original objective are
Our responses come from the behavior policy . Importance sampling rewrites the objective as
This whole-response ratio can have high variance for long responses. We want a training objective computed directly from behavior samples, without importance weights.
Log-mean-exp minus mean.
Both expectations use behavior-policy samples, without importance weights.
For policies positive on a common finite action space, let be the best policy value and the coverage factor. Then
With coverage controlled, a small GGPO loss guarantees a small optimality gap. On policy, . The factor is used only in the guarantee.
Here we verify the bound from the resulting loss; Section 03 explains how to construct it. Define
Writing gives , since .
The Gibbs optimal-value identity gives
The second equality follows by substituting : the learner probability cancels. Thus, for any ,
At , the exponential term has learner mean , canceling the in the multiplier. The average is exactly the original gap, now decomposed into nonnegative action terms.
Multiply by the nonnegative and sum. This gives . Our choice of makes , so
Combining these facts,
On policy, and , so the bound is exact. This is a population bound; finite response groups have a separate guarantee in the paper.
The original optimality gap is nonnegative overall, but its individual action terms can be negative:
Primal–dual optimization gives us another decomposition: each action’s best possible contribution minus its current contribution.
Let be the probability assigned to response . The original, or primal, problem is
Introduce a multiplier for the normalization constraint. The standard Lagrangian is
The dual first maximizes this expression with normalization released, then minimizes over :
At fixed , the maximization separates into one problem per action:
Call these independent maximizers . They are unnormalized masses. Minimizing over restores normalization at :
Now the independent peaks form a valid policy. Since every action is at its peak and the constraint term vanishes for every valid policy, no other valid policy can do better.
For any fixed , compare the same action term at its maximizing mass and at the learner’s probability :
The best value cannot be smaller than the current value. This is why every action’s gap is nonnegative, before is optimized. Adding the gaps gives
To express this sum as a learner expectation, divide each action gap by its learner probability:
Nonnegativity lets the coverage condition transfer the guarantee:
Minimize this behavior average over the shared multiplier to obtain GGPO, without importance weights:
This behavior-optimal multiplier can differ from the normalizing multiplier . The zero-loss target is still the Gibbs policy:
Differentiating the action term in the dual with respect to gives
Its unique maximizer and the resulting dual value are
The dual is strictly convex. At its minimum, , so the independent maximizers are feasible and attain the dual upper bound. Hence and .
Substitution gives
For the paper’s shifted form, simply rename :
This is the same loss and the same minimization, expressed with a shifted multiplier. The shift is only an algebraic convenience; nonnegativity already follows from peak minus current.
Setting this derivative to zero gives the minimizing behavior multiplier and the loss
The condition here is , while the normalizing multiplier satisfies . On policy the two multipliers coincide.
Draw responses , with adjusted rewards . On this group, GGPO becomes
The exponential emphasizes the largest adjusted reward; the logarithm brings it back to the reward scale. More explicitly,
Best-of- takes the maximum; one uniform pick has the group average as its expected score. GGPO is a smooth, KL-adjusted version of this best-versus-average gap, with approximation error at most .
This explains the group loss. The paper’s finite-group bound connects its expectation to the reward gap between behavior best-of- and a single learner response, under coverage and reference-mismatch conditions.
Let . Factor out the largest exponential:
Every term inside the sum is at most one, and at least one equals one. The average is therefore between and , giving .
For fixed sampled responses and positive policies, as . Thus
This limit illustrates the loss value. Training uses and the policy-dependent adjusted rewards; its update contrasts all sampled responses, as shown in Section 04.
Averaging the limit over i.i.d. behavior groups compares behavior best-of- with behavior single-response reward. The learner guarantee is the separate finite-group result, with coverage and regularization terms.
AGRO’s off-policy objective minimizes the variance of adjusted rewards:
GGPO instead uses a log-mean-exp. When adjusted-reward deviations from their mean are small relative to , its second-order expansion gives
Thus, scaled AGRO is the local quadratic approximation to GGPO.
For binary rewards , MaxRL samples on-policy and uses the gradient estimate below. Let denote the average over sampled responses.
This is the mean score gradient over successful responses minus its mean over all responses. Groups with no successes give zero update.
For comparison, GGPO uses groups from . Holding the samples, reference and rewards fixed, its empirical loss gives the following descent update after dividing out the overall factor:
Write . For a group with both successes and failures, the weights connect as follows:
Reward + reference
Soft success weighting
Success-normalized
These two steps recover MaxRL’s update coefficients. The sampling differs: MaxRL is on-policy, while GGPO permits . Small alone retains GGPO’s reference weighting among equally rewarded responses.
We report response accuracy across five math benchmarks for default training and staleness, and on MATH-500 for offline learning. All results use Qwen3-1.7B-Base, except the 4B column.
To move beyond a fixed Gibbs target, GGPO and AGRO copy the learner into the reference every 160 optimizer updates, separately from rollout synchronization.
The rollout model is synchronized with the learner every optimizer updates.
| Method | 1.7B | 4B |
|---|---|---|
| GRPO | 42.64 | 55.51 |
| AGRO | 45.07 | 55.81 |
| GGPO | 46.58 | 56.98 |
All rollouts are generated by the initial model.