REINFORCE and RLOO

REINFORCE is the simplest policy-gradient algorithm: sample an output, score it, and raise the log-probability of the output in proportion to its score. RLOO (REINFORCE Leave-One-Out) adds one idea that makes it practical for language models: sample $k$ responses per prompt and use the average reward of the other $k-1$ responses as each one's baseline. The result is an unbiased, low-variance policy gradient with no value network, no GAE and, in its basic form, no clipping. In the post-training stack RLOO is a drop-in replacement for PPO in the RL stage after SFT and reward modeling, and it is the direct ancestor of the group baselines in GRPO. If you understand RLOO, GRPO is RLOO with two changes you can now evaluate on their merits.

Where it came from#

Ronald Williams published REINFORCE in 1992 in Machine Learning, as a family of algorithms that follow the gradient of expected reward without ever computing it in closed form. The trick is the score-function (log-derivative) identity, and Williams already noted that subtracting a "reinforcement baseline" leaves the gradient unbiased while reducing its variance. For two decades the baseline was usually a learned value function, which is what actor-critic methods and eventually PPO use.

Kool, van Hoof and Welling (2019) pointed out in a short ICLR workshop paper, Buy 4 REINFORCE Samples, Get a Baseline for Free!, that if you draw several samples per input anyway, the other samples provide a baseline at no extra cost, and that leaving the current sample out keeps it unbiased. Rennie et al. (2017) had earlier used a related idea for image captioning, with the greedy decode as the baseline, which is the route ReMax takes.

The LLM version is Ahmadian et al. (2024), Back to Basics: Revisiting REINFORCE Style Optimization for Learning from Human Feedback in LLMs. Their argument: PPO was designed for RL from scratch, where policies are unstable and variance is enormous. A pretrained, instruction-tuned language model is a very strong initial policy, so most of PPO's machinery (the critic, per-token credit assignment, clipping) is solving problems that barely exist. They treated each full completion as a single action, used the leave-one-out baseline, and reported RLOO matching or beating PPO, DPO and RAFT on summarisation and helpful-harmless dialogue while using less memory.

The math#

The REINFORCE gradient

Let ${\pi }_{\theta }(y\mid x)$ be the policy's probability of the full response $y$ to prompt $x$, and $R(x,y)$ a scalar reward. The objective and its gradient are

The second equation follows from $\nabla \pi =\pi \nabla \log \pi$: the gradient of an expectation becomes an expectation of a gradient you can estimate by sampling. For an autoregressive model $\log {\pi }_{\theta }(y\mid x)={\sum }_{t=1}^T\log {\pi }_{\theta }(y_t\mid x,y_{<t})$, so the sequence log-probability is a sum of token log-probabilities and backpropagation through it is the same as for SFT, just weighted by $R$.

Why a baseline is free of bias

For any $b(x)$ that does not depend on $y$,

so $(R-b)\nabla \log \pi$ has the same expectation as $R\nabla \log \pi$. Its variance can be far lower. If all rewards sit around 5 with a spread of 0.5, raw REINFORCE pushes up every sampled response by roughly 5 units and relies on tiny differences between those large pushes to carry the signal. Subtracting 5 leaves only the differences. The ideal baseline is close to $\mathbb{E}[R\mid x]$, the expected reward for this prompt.

The leave-one-out estimator

Sample $k$ responses $y_1,\dots ,y_k$ i.i.d. from ${\pi }_{\theta }(\cdot \mid x)$ with rewards $R_1,\dots ,R_k$. RLOO's gradient estimate for that prompt is

Because $b_i$ uses only the other samples, which are independent of $y_i$, it is a valid baseline and the estimate is unbiased. A little algebra gives a useful identity: with $\bar{R}=\frac{1}{k}{\sum }_j{R}_j$,

So the RLOO advantage is the group-mean-centred reward scaled up by $k/(k-1)$. Subtracting the mean including the sample itself, as GRPO does, gives the same direction but shrinks the expected gradient by $(k-1)/k$: by half at $k=2$, a quarter at $k=4$. Our toy run below measures exactly this shrinkage.

Where the KL goes

As in RLHF, RLOO keeps the policy near the SFT reference with a KL penalty. Ahmadian et al. fold it into the sequence-level reward:

with the log-ratio treated as a constant (no gradient through it) when forming the advantage. Every token in $y_i$ then gets the same advantage $A_i=R_i-b_i$. That is the "whole completion is one action" modelling choice: no per-token credit assignment, no value model to learn it.

Why sequence-level credit is enough

Giving every token the same advantage looks crude next to PPO's per-token GAE. It works for two reasons. First, the reward model only ever scores complete responses, so a critic has to invent intermediate values from a signal that arrives at the end; with $\gamma =1$ and $\lambda$ close to 1, which is what RLHF uses, GAE's advantages are already close to "final return minus a baseline" at every position. Second, a value model for a 7B policy is itself a 7B network trained on noisy targets from a moving policy. Early in training its predictions are poor, and a poor critic adds bias that RLOO avoids by construction. Ahmadian et al. reported that the partial-completion modelling PPO does brought no benefit in their RLHF experiments. Where per-token credit does matter, for long reasoning traces with a single early mistake, the better fix is usually a denser reward (a process reward model) rather than a learned critic.

Taking more than one step per batch

Plain RLOO uses each batch once, because after one update the samples no longer come from ${\pi }_{\theta }$. To reuse them, weight by the importance ratio against the sampling policy and clip it as PPO does:

Sequence-level ratios are products of many token ratios and swing widely, so implementations usually apply the ratio and clip per token while keeping the sequence-level advantage $A_i$. On the first step $\rho =1$ and the gradient is exactly the RLOO estimator; later steps are a trust-region approximation of it.

Side by side with its siblings

Worked example by hand#

One prompt, $k=4$ samples, rewards $R=(1.0,0.0,0.5,0.3)$. The leave-one-out baselines are the means of the other three: $b_1=(0+0.5+0.3)/3=0.267$, $b_2=(1+0.5+0.3)/3=0.600$, $b_3=(1+0+0.3)/3=0.433$, $b_4=(1+0+0.5)/3=0.500$. The advantages are $+0.733,-0.600,+0.067,-0.200$. They sum to zero, so the update moves probability between the samples rather than raising all of them. The group mean is 0.45, and $\frac{4}{3}(R_i-0.45)$ reproduces the same four numbers, confirming the identity above. GRPO's mean-centred advantages for the same rewards are $+0.55,-0.45,+0.05,-0.15$, three quarters of RLOO's, and dividing by the standard deviation (0.364) inflates them to $+1.51,-1.24,+0.14,-0.41$.

The algorithm#

inputs: SFT policy π_sft, reward model (or verifier) r, prompts D, k, β
π_θ ← π_sft;  π_ref ← π_sft (frozen)
repeat:
    sample B prompts
    for each prompt x: sample y_1..y_k ~ π_θ(·|x)         # k = 2 to 8
    logp     = Σ_t log π_θ(y_t | ...)    per sample (keep graph)
    logp_ref = Σ_t log π_ref(y_t | ...)  per sample (no grad)
    R_i = r(x, y_i) - β (logp_i - logp_ref_i).detach()
    A_i = R_i - (Σ_j R_j - R_i)/(k - 1)                   # leave-one-out
    loss = - mean_i( A_i · logp_i )                       # optionally normalise by tokens
    one optimizer step (or a few, with PPO-style ratio clipping)

Data. Prompts only, as for PPO: typically 10k to a few hundred thousand from the target distribution. Per step you generate $B\times k$ responses; a common configuration is 64 to 256 prompts with $k=4$. A Bradley-Terry reward model, an LLM judge or a programmatic verifier can provide $R$; RLOO does not care which.

What the loop actually does. Generation dominates wall-clock, exactly as in PPO. The training step is one forward and backward pass through the policy over the generated tokens plus one forward pass through the reference, with no critic to update. Basic RLOO is fully on-policy: each batch is used for one gradient step and discarded. Many implementations add PPO's importance ratio and clipping so they can take two to four steps per batch; that reintroduces the clip hyperparameter but not the critic.

Hyperparameters that matter#

For a fixed budget of generated responses, $k$ trades prompt coverage against baseline quality. With dense rewards from a reward model, $k=2$ to 4 is usually enough. With binary rewards, the probability that all $k$ samples agree, $p^k+(1-p{)}^k$, is high for very easy or very hard prompts, and those groups contribute nothing.

Compute and memory#

RLOO holds three networks: the trained policy and two frozen inference models (reference and reward model). Using about 16 bytes per trained parameter (bf16 weights and gradients plus fp32 Adam state and master weights) and 2 bytes per frozen parameter:

For a 7B policy with a 7B reward model that is about 140 GB of model state for RLOO against about 252 GB for PPO with a 7B critic. Dropping the critic also removes its forward and backward passes and the engineering burden of keeping it calibrated. Generation cost is the same as PPO for the same number of responses: RLOO does not need more samples, it just organises them in groups. Relative to DPO, RLOO still pays for online generation and a reward model, typically several times DPO's compute for a comparable number of training examples.

A toy experiment: measuring the variance#

To measure what the baseline buys, we used a softmax "policy" over 32 responses with random logits, where response $a$ succeeds with probability $q_a\sim \text{Beta}(1,3)$ and the reward is success plus a constant offset of 2 (the offset mimics a reward model whose scores are not centred). We computed the exact policy gradient, then drew 20,000 independent gradient estimates per method and measured each estimator's bias, total variance and the ratio of its mean to the true gradient (seed 0; true gradient norm 0.052).

At $k=4$, the leave-one-out baseline cuts gradient variance by a factor of about 20 compared with no baseline, and comes within 35% of the oracle baseline that knows the true expected reward; at $k=8$ it is within 15%. The group-mean estimator has lower variance, but the column on the right shows why: its expected gradient is shrunk by 0.50, 0.76 and 0.89, matching the predicted $(k-1)/k$ of 0.50, 0.75 and 0.875. It is not a better estimator, just a smaller one, and a learning-rate change would undo the difference. The REINFORCE row also makes the signal-to-noise problem concrete: a true gradient of norm 0.052 under noise with standard deviation $\sqrt{1.297}\approx 1.14$.

We then trained each method for 300 steps of 64 samples (learning rate 2.0 on the logits, 10 seeds). All runs started at an expected success rate of 0.304; the best response has $q=0.693$. REINFORCE without a baseline reached 0.608 with a standard deviation of 0.088 across seeds. RLOO with $k=4$ and a moving-average baseline both reached 0.665 with seed-to-seed spread below 0.001. In a single-prompt problem a moving average is nearly as good as RLOO because there is only one prompt difficulty to track. With many prompts of different difficulty, a global moving average cannot track per-prompt expected reward, and that is where the per-prompt RLOO baseline earns its keep.

Failure modes and how to detect them#

Zero-signal groups. With binary or coarse rewards, groups where all $k$ rewards are equal produce zero advantage. Log the fraction of such groups; above 50%, increase $k$, filter prompts by current pass rate, or move to a curriculum. DAPO's dynamic sampling is a systematic fix.

KL drift without a critic to slow it. RLOO steps can be larger than PPO's because nothing clips them. Watch per-sequence KL to the reference; a steady climb past your target without matching gains in evaluation means $\beta$ is too low or the learning rate too high. Adding ratio clipping or lowering the learning rate are both reasonable responses.

Length bias from loss normalisation. If you average the loss over tokens across the batch, long responses with positive advantage get more total gradient than short ones; if you sum per sequence and average over sequences, the reverse can hold for negative advantages. Watch mean response length; a monotonic climb with flat quality usually points here or at the reward model.

Reward hacking. Identical to PPO: proxy reward climbs, independent judge win rate flattens. RLOO removes nothing that protects against it, so the same KL-versus-win-rate plot applies.

High variance at $k=2$. With two samples each baseline is a single other reward, and in our toy run variance at $k=2$ was three times that at $k=4$. If curves are noisy, raise $k$ before raising batch size.

Sampling mismatch. Top-p, top-k or a temperature other than 1 during training make the samples come from a different distribution than the one whose log-probabilities you differentiate. The estimator is then biased in ways that are hard to see. Sample with plain temperature 1.0.

What healthy curves look like. Mean reward rises quickly over the first few hundred steps and then bends into a slow climb. KL to the reference grows roughly in step with it, sublinearly in steps. The fraction of zero-advantage groups falls early (the policy finds prompts it can now sometimes solve) and then rises again late (it solves them every time). Response length moves slowly or not at all. A reward curve that keeps rising linearly while KL accelerates is the signature of the policy finding a reward-model exploit, and it is the moment to compare checkpoints with an independent judge before training further.

When to use it#

Minimal implementation in PyTorch#

The full RLOO loss fits in a few lines once you have per-sequence log-probabilities. TRL ships an RLOOTrainer that wraps the same computation with generation and logging.

import torch

def seq_logprob(model, input_ids, attn, resp_mask):
    # resp_mask: 1 on response tokens; returns sum of log-probs per sequence
    logits = model(input_ids=input_ids, attention_mask=attn).logits[:, :-1]
    tgt = input_ids[:, 1:]
    lp = torch.log_softmax(logits.float(), -1).gather(-1, tgt.unsqueeze(-1)).squeeze(-1)
    return (lp * resp_mask[:, 1:]).sum(-1)

def rloo_loss(logp, logp_ref, scores, k, beta=0.05):
    # logp, logp_ref, scores: [B*k], grouped so rows i*k .. i*k+k-1 share a prompt
    R = scores - beta * (logp - logp_ref).detach()          # sequence-level KL-shaped reward
    R = R.view(-1, k)
    baseline = (R.sum(1, keepdim=True) - R) / (k - 1)        # leave-one-out
    adv = (R - baseline).view(-1)
    loss = -(adv * logp).mean()
    stats = {"reward": scores.mean().item(),
             "kl": (logp - logp_ref).mean().item(),
             "zero_adv_groups": (R.std(1) == 0).float().mean().item()}
    return loss, stats

# per step: generate k samples per prompt at temperature 1.0, score them,
# compute logp with grad and logp_ref without, then:
# loss, stats = rloo_loss(logp, logp_ref, scores, k); loss.backward(); opt.step()

The three logged statistics, together with response length and an independent evaluation, are enough to run RLOO responsibly. In POFE, RLOO is available as an RL recipe with the same evaluation panels as PPO, so switching between them is a configuration change rather than a new pipeline.

Further reading#

Williams (1992) for REINFORCE and baselines. Kool, van Hoof and Welling (2019) for the leave-one-out baseline. Ahmadian et al. (2024) for the case that REINFORCE-style methods suffice for RLHF. Rennie et al. (2017) for the self-critical greedy baseline. Shao et al. (2024) for GRPO, whose group baseline is the mean-including-self variant analysed above.

Frequently asked questions#

References#

1. Ronald J. Williams (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. doi.org/10.1007/BF00992696
2. Wouter Kool, Herke van Hoof, Max Welling (2019). Buy 4 REINFORCE Samples, Get a Baseline for Free!. mlanthology.org/iclrw/2019/kool2019iclrw-buy/
3. Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadaee, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, Sara Hooker (2024). Back to Basics: Revisiting REINFORCE Style Optimization for Learning from Human Feedback in LLMs. arxiv.org/abs/2402.14740
4. Steven J. Rennie, Etienne Marcheret, Youssef Mroueh, Jarret Ross, Vaibhava Goel (2017). Self-critical Sequence Training for Image Captioning. arxiv.org/abs/1612.00563
5. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, et al. (2024). DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. arxiv.org/abs/2402.03300
6. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, Oleg Klimov (2017). Proximal Policy Optimization Algorithms. arxiv.org/abs/1707.06347

Related reading