Source-linked AI summary
What is the objective of reasoning with reinforcement learning?
Damek Davis, Benjamin Recht
TL;DR
The paper addresses the difficulty of transparently comparing reinforcement-learning algorithms for large language models. It recasts these methods as stochastic-gradient optimization of monotone transforms of correct-answer probability, providing a unifying view while noting limits to the justification and practical guidance.
Problem
Different policy-gradient implementations can have enough degrees of freedom to make their behavior on particular optimization problems difficult to understand.
Source: §1 · p. 2Method
The paper presents a stochastic-gradient method for maximizing scaled correct-response probability and treats popular post-training algorithms as special cases.
Source: §1 · pp. 1–2Results
Takeaways & Limitations
The note aims to give language-model researchers more clarity and flexibility in designing fine-tuning methods, without making concrete recommendations.
Source: §7 · p. 8The paper says it is unclear whether logarithmic scaling has a rigorous justification in reinforcement learning when multiple answers can be correct.
Source: §5 · p. 7
Abstract
from arXiv · showhide
We show that several popular algorithms for reinforcement learning in large language models with binary rewards can be viewed as stochastic gradient ascent on a monotone transform of the probability of a correct answer given a prompt. In particular, the transformation associated with rejection sampling algorithms is the logarithm and that associated with the GRPO algorithm is the arcsine of the square root.
1 Introduction
The paper frames LLM reinforcement learning as stochastic-gradient ascent on a monotone transform of correct-answer probability, using this view to unify and compare algorithms.
1 Introduction
- The meta-algorithm samples prompts, generates responses, labels answers as good or bad, and fine-tunes on prompt-response-label triples.The paper names this underspecified procedure Meta-Algorithm 1.Source: §1 · p. 1
- The objective is a monotonically increasing function of the probability of a correct answer conditioned on the prompt.The proposed method aims to maximize scaled correct-response probability via stochastic gradient ascent.Source: §1 · p. 2
- Different implementations can be viewed as maximizing closely related objectives, offering a way to compare algorithms whose behavior is not always transparent.The paper says policy-gradient algorithms can have enough degrees of freedom to make their behavior on particular optimization problems unclear.Source: §1 · pp. 1–2
- Fine-tuning on correct answers alone requires the base model or engineer to generate correct answers; without them, the algorithms cannot progress.The paper states that no sophisticated policy-gradient implementation can circumvent this constraint.Source: §1 · p. 2
2 Background: Supervised Learning and Williams’ REINFORCE algorithm.
The section relates probabilistic supervised-learning updates to REINFORCE, then notes that binary-reward reinforcement learning can yield updates resembling supervised learning.
2 Background: Supervised Learning and Williams’ REINFORCE algorithm.
- A supervised-learning update fits a conditional distribution to input-output examples by maximizing a global objective motivated by maximum likelihood.The stochastic gradient is considered for an individual example.Source: §2 · p. 2
- REINFORCE uses unbiased estimates of the objective gradient to form a stochastic-gradient update.The gradient estimate concatenates unbiased partial-derivative estimates.Source: §2 · p. 3
- A calculus identity lets the analysis express stochastic gradients in terms proportional to gradients of log densities.The paper says it uses this analysis throughout.Source: §2 · p. 3
- For the described reinforcement-learning problem, binary rewards produce updates that look like supervised-learning updates.In LLM reinforcement learning, outputs are generated by the model being optimized.Source: §2 · pp. 2–3
3 Reinforcement Learning for Reasoning
For questions in a corpus, the goal is to fine-tune a probabilistic model to answer correctly; several methods can be viewed as stochastic gradient ascent on monotone transforms of correctness probability.
3 Reinforcement Learning for Reasoning
- The setup treats each prompt x as having a set C(x) of correct responses, which the model samples from its conditional distribution.A means of determining whether each response is correct is assumed.Source: §3 · p. 3
- Algorithm 1 samples a question and M answers, assigns per-answer weights from response evaluations, then applies a supervised learning update.The paper presents this as a concrete implementation of its meta-algorithm.Source: §3 · pp. 3–4
- The choice of advantage weights determines the optimized objective; vanilla REINFORCE uses correctness indicators and maximizes average correctness probability.Its weights are Zi = 1 when an answer is correct and 0 otherwise.Source: §3 · p. 4
- Rejection sampling corresponds to an objective close to log(t), while GRPO corresponds to one close to arcsin(sqrt(t)).Here t is the probability of a correct answer.Source: §3 · pp. 3–4
- Figure 1 compares the GRPO, REINFORCE, and log losses.Source: Figure 1 · p. 4
4 Which functions do the reweightings induce?
For weights conditionally linear in binary rewards, the induced objective transform is connected to a regularized incomplete beta function; the proof conditions on leave-one-out reward totals.
4 Which functions do the reweightings induce?
- The considered weights are conditionally linear in binary rewards, with their values determined by arbitrary measurable functions of the other samples’ total reward.The reward is an indicator of whether the sampled answer is correct.Source: §4 · p. 5
- The resulting transform is expressed using the regularized incomplete beta function.Source: §4 · p. 5
- The proof uses that the weighted score terms share a distribution, then conditions on the leave-one-out total to characterize each weight by answer correctness.Given that total, the weight takes one value for correct answers and another for incorrect answers.Source: §4 · p. 5
- The section establishes the transform identity before turning to the rejection-sampling and GRPO weight choices.Source: §4 · p. 5
5 Rejection sampling
Finite-sample rejection sampling induces an objective that approaches the logarithm of the correct-answer probability as the sample size grows. Sampling until a fixed number of correct responses yields an unbiased stochastic gradient of Jlog.
5 Rejection sampling
- With M sampled answers, the algorithm forms V from correct answers and uses weights Zi = RiM/(Si + 1).Source: §5 · pp. 5–6
- As M grows, the rejection-sampling function hM gets closer to log(t); Figure 2 shows hM, and H_M is the Mth harmonic number.Source: §5 · p. 6, Figure 2 · p. 6
- Sampling until B correct responses and applying a supervised update gives an unbiased stochastic gradient of Jlog.Source: §5 · pp. 6–7
- For a single observed target, rejection sampling can implement standard log-loss training, though the passage notes this is not very practical.Source: §5 · p. 7
- When C(x) contains multiple correct answers, Jlog has no natural maximum-likelihood interpretation, and its logarithmic scaling lacks a clear rigorous justification in reinforcement learning.Source: §5 · p. 7
6 GRPO
GRPO optimizes a monotone rescaling of the probability of a correct answer. Its induced function depends on sample size M and ε, with larger ε shifting its behavior toward h(t)=t.
6 GRPO
- GRPO normalizes sampled gradients by the square root of reward variance, amplifying each update’s impact.Source: §6 · p. 7
- Figure 3 tracks hM,ε/hM,ε(1); under the idealized setting, larger ε makes hM,ε behave more like h(t)=t.Source: Figure 3 · p. 8, §6 · p. 8
- GRPO, like rejection sampling, optimizes a monotone rescaling of the probability of a correct answer.Source: §6 · p. 8
7 What do we learn?
The note offers a recipe for constructing gradient estimators for chosen objective rescalings, but makes no concrete recommendations because their practical effects across multiple questions are hard to predict. With expressive enough models and global maximization, monotone rescalings share the same optimum, though they may affect optimization dynamics.
7 What do we learn?
- The note aims to give language-model researchers clarity and flexibility in designing fine-tuning methods, not concrete recommendations.Source: §7 · p. 8
- Replacing GRPO’s standard deviation with variance yields a function close to log-odds rescaling, and beta-density-based rescalings can also be derived.The beta-density-based loss functions approximate the corresponding beta-distribution CDFs.Source: §7 · p. 9
- The derivative of hM is a Bernstein polynomial, giving a basis for approximating h′ and constructing a gradient estimator for a chosen scaling h.For polynomial h of degree ≤M, the coefficients can make hM equal h plus a constant.Source: §7 · p. 9
- For any smooth h, a coefficient choice makes hM converge uniformly to h plus a constant; for h in C^p, p ≥ 3, the sup-norm convergence rate is 1/M.For polynomial h of degree ≤M, coefficients can instead make hM equal h plus a constant.Source: §7 · p. 9
- With expressive enough πθ and global maximization of Jh, the choice of monotone h is superfluous for the optimum, though it may affect optimization dynamics.For one question, each monotone h induces an identical problem.Source: §7 · p. 9
- The best rescaling for RL fine-tuning is context-dependent because the algorithms pursue closely related objectives.The note compares this choice to log loss versus hinge loss, whose best choice varies by task.Source: §7 · p. 9