PaperlayerView exact revision on arXiv

Source-linked AI summary

Maximum Likelihood Reinforcement Learning

Fahim Tajwar, Guanning Zeng, Yueer Zhou, Yuda Song, Daman Arora, Yiding Jiang, Jeff Schneider, Ruslan Salakhutdinov, Haiwen Feng, Andrea Zanette

arXiv:2602.02710v3cs.LG

TL;DR

Binary terminal-reward tasks induce an implicit likelihood over correctness, but standard expected-reward RL only provides its first-order approximation because direct likelihood optimization is difficult. MaxRL uses sampling compute to interpolate between expected reward and maximum likelihood, outperforming existing RL objectives across tested settings and scaling more effectively with compute and data.

  • Problem

    Binary terminal feedback induces an implicit likelihood over correctness, but direct maximum-likelihood optimization is difficult because success is observed after a non-differentiable stochastic generation process.

  • Method

    MaxRL is a compute-indexed family of sample-based objectives that interpolates between expected reward and exact maximum likelihood through a Maclaurin expansion in pass@k events.

  • Results

    MaxRL Pareto-dominates standard RL objectives across all tested settings, achieves up to 20× test-time scaling efficiency gains over GRPO on mathematical reasoning, and scales better with additional compute and data.

  • Takeaways & Limitations

    MaxRL offers a principled optimization framework for non-differentiable binary-reward settings and suggests that some RL limitations may arise from objective choice rather than optimization or sampling.

  • Takeaways & Limitations

    The finite-sample estimator can assign zero gradient when N samples contain no successes and is unbiased only for the truncated maximum-likelihood objective.

Abstract

from arXiv · show

Reinforcement learning (RL) is the method of choice for training models in setups where the objective function can only be evaluated by sampling from the model. Our key observation is that when the feedback is terminal and binary, models implicitly induce a likelihood over correct rollouts. Maximum likelihood would be the natural framework in such settings, but RL is used instead as a workaround to the non-differentiability. We prove that the standard, expected-reward RL formulation is only a first-order approximation of the likelihood. To remedy this mismatch, we introduce Maximum Likelihood Reinforcement Learning (MaxRL), a compute-indexed family of sample-based objectives that interpolate between expected-reward RL and maximum likelihood as sampling compute is scaled. The resulting objective is a one-line change to standard RL implementations. MaxRL Pareto-dominates existing methods in all tested models and tasks, achieves up to $20\times$ gains in test-time scaling efficiency over GRPO, and scales more favorably with additional training data and compute.

1 Introduction

The paper argues that correctness-based tasks induce an implicit likelihood over successful outputs, making maximum likelihood principled but difficult to optimize through non-differentiable stochastic generation. MaxRL addresses this mismatch by interpolating between expected-reward RL and maximum likelihood as sampling compute increases, with stronger empirical scaling than standard objectives.

  • Motivation: Correctness-based tasks use binary verifier feedback after stochastic generation, implicitly defining a likelihood over each input’s probability of success.This pattern appears in navigation, program synthesis, structured prediction, and multi-step reasoning.
  • Motivation: Maximum likelihood is principled for this implicit success likelihood, but direct optimization is difficult because intermediate generation is non-differentiable and success probabilities may be small.The computational challenge motivates using additional sampling compute to approximate likelihood-based training.
  • Core claim: Standard reinforcement learning optimizes only the first-order approximation of the maximum likelihood objective.The paper formalizes correctness-based RL as latent-generation maximum likelihood and identifies the objective mismatch.
  • MaxRL: MaxRL introduces a compute-indexed family of objectives that interpolates between expected reward and exact maximum likelihood through a Maclaurin expansion in pass@k events.The approach progressively incorporates higher-order correctness information as more sampling compute is used.
  • Results: MaxRL Pareto-dominates RLOO and GRPO in all tested settings, with up to 20× test-time scaling efficiency gains over GRPO on mathematical reasoning tasks.It also shows better scaling trends when additional compute and data are available.

2 Preliminaries

The preliminaries define correctness-based learning through model pass rates and distinguish expected-reward RL from maximum likelihood. RL maximizes expected pass rate, whereas ML maximizes the expectation of its logarithm.

  • Correctness-based tasks: The paper focuses on correctness-based problems where each input produces a binary success or failure outcome.RL commonly represents correctness with a binary reward function.
  • Notation: For input x, the model distribution pθ(· | x) assigns probabilities to outputs, with correctness defined relative to the task’s correct answer or label.Output equality may use a task-dependent semantic equivalence relation.
  • Latent generation: Latent generation models first sample a trajectory z and then deterministically decode it into the final output y, which is evaluated for correctness.Examples include chains of thought, generated programs, and extracted boxed answers.
  • Pass rates: Pass rate is the probability of producing the correct answer for a fixed input, while pass@k is the probability that at least one of k independent samples is correct.These quantities provide the success events used throughout the objectives.
  • Objective distinction: RL maximizes the expectation over pass rate, whereas ML maximizes the expectation over its logarithm.The ML objective is the log-likelihood of observing correctness and is analogous to cross-entropy training.

3 Maximum Likelihood Reinforcement Learning (MaxRL)

MaxRL derives a compute-indexed approximation to maximum likelihood by expanding it in pass@k events and truncating the expansion at a chosen order. The truncation recovers RL at order one, approaches ML at infinite order, and can be estimated under fixed sampling budgets.

  • Objective expansion: Maximum likelihood admits a population-level expansion in pass@k events, while standard RL retains only the first-order term.Higher-order terms capture rare-success information that matters when pass rates are small.
  • Motivation: MaxRL is motivated by the difficulty of estimating large-k pass@k gradients when sampling budgets are fixed and pass rates are small.The method explicitly targets the maximum likelihood objective while remaining compatible with sampled, non-differentiable generation.
  • MaxRL objective: Truncating the expansion at order T defines a family in which T = 1 recovers RL, T →∞ recovers maximum likelihood, and intermediate T values interpolate between them.The truncation level controls which orders of correctness events contribute to learning.
  • Compute scaling: MaxRL provides a principled way to trade additional rollout compute for higher-fidelity approximations to the maximum likelihood objective.The compute level determines how many higher-order correctness terms can be incorporated.
  • Estimation: The remaining construction question is whether truncated objectives have simple unbiased estimators under a fixed sampling budget, which the paper answers affirmatively.The estimator is designed for the truncated objective rather than requiring direct estimation of the infinite ML series.

4 Gradient Estimators for MaxRL

The section develops a conditional, success-filtered gradient estimator for MaxRL and establishes its equivalence to a truncated maximum-likelihood objective. Unlike REINFORCE, additional rollouts improve the objective approximation itself, while variance reduction and zero-success cases impose practical considerations.

  • Conditional estimator: A success-conditioned maximum-likelihood gradient equals the average score function over successful trajectories.The estimator can approximate this conditional expectation by averaging gradients from successful rollouts sampled from the unconditional policy.
  • Estimator construction: REINFORCE and MaxRL differ only in normalization—total samples N versus successful samples K—but are unbiased for different objectives.The normalization choice determines whether the estimator targets the standard pass@1 objective or a truncated maximum-likelihood objective.
  • Estimator–objective equivalence: The MaxRL estimator is unbiased for the gradient of the truncated maximum-likelihood objective with truncation level T = N.The result aligns the estimator with the gradient of the truncated Maclaurin expansion rather than the full infinite-series maximum-likelihood objective.
  • Compute scaling: Increasing rollout count N improves MaxRL’s approximation to the maximum-likelihood gradient, whereas REINFORCE mainly reduces variance for a fixed pass@1 objective.Thus, additional sampling compute changes the optimized objective for MaxRL rather than only improving estimation quality.
  • Variance reduction: The estimator can have high variance when successful samples K are few, and standard policy-gradient baseline arguments do not directly apply because K is random and rollout-dependent.The method instead uses an unconditional average-score control variate; practical implementation drops gradient terms when K = 0.
  • Implementation: The practical algorithm samples N trajectories per input, evaluates binary success and score functions, and applies a one-line modification to standard policy-gradient advantages.Its practical estimator is unbiased for MaxRL of order T = N − 1 because of the control-variate formulation.

5 A Unifying Weight-Function View

The weight-function view characterizes each objective by how it allocates learning signal across inputs with different pass rates. MaxRL approaches maximum-likelihood weighting for difficult inputs as sampling compute increases, unlike GRPO’s distinct objective.

  • Weight-function formulation: Population-level gradients for ML, MaxRL, classical RL, and GRPO share a pass-rate-dependent weight function w(p) that determines learning emphasis.The weight function fully characterizes how each objective allocates signal across inputs of varying difficulty.
  • MaxRL interpolation: As T increases, MaxRL uniquely approaches maximum-likelihood weighting in the low-pass-rate regime.The truncated MaxRL objectives therefore interpolate between REINFORCE and maximum likelihood as sampling compute grows.
  • GRPO interpretation: GRPO’s empirical standard-deviation normalization induces a population-level objective fundamentally different from REINFORCE.The weight-function perspective reframes this difference as a distinct allocation of learning signal across pass rates.
  • GRPO comparison: For small p, GRPO upweights low-pass-rate inputs approximately as 1/√p, placing it between classical reinforcement learning and maximum likelihood.This weighting differs from standard expected-reward optimization while remaining distinct from likelihood weighting.
  • GRPO comparison: Additional GRPO sampling does not improve its approximation to maximum likelihood because its induced population loss is fundamentally distinct.At sufficiently large pass rates, GRPO’s weighting increases as p → 1, unlike likelihood-based weighting.

6 Experiments

Across controlled, data-rich, data-scarce, and large-model experiments, MaxRL improves more effectively with training compute and preserves coverage better than standard RL objectives. Its optimization dynamics also emphasize difficult prompts and maintain broader learning progress.

  • 6.1 Comparisons with Exact Maximum Likelihood: MaxRL closely tracks exact maximum likelihood as rollout compute increases, whereas REINFORCE can fail from low initial pass rates.The controlled ImageNet comparison uses cross-entropy as the exact maximum-likelihood objective.
  • 6.2 Infinite Data Regime: In the data-rich maze setting, MaxRL scales more favorably with compute than GRPO and RLOO.At 128 rollouts per prompt, RLOO and GRPO still trail MaxRL trained with 4 and 16 rollouts, respectively, across pass@k metrics.
  • 6.3 Data-Scarce Regime: In the data-scarce GSM8K setting, MaxRL eventually surpasses faster-starting baselines while sustaining healthier pass@k performance over extended training.RLOO and GRPO peak earlier but show substantial pass@k degradation, whereas MaxRL continues improving and reaches a higher peak.
  • 6.4 Large Reasoning Model Training: Across four mathematical reasoning benchmarks and two Qwen3 model sizes, MaxRL Pareto-dominates GRPO and achieves up to 20× test-time scaling efficiency gains.MaxRL improves pass@k relative to both the pretrained base and GRPO checkpoint in 7 of 8 evaluation settings.
  • 6.5 Behavior Analysis of MaxRL: MaxRL produces stronger gradients on harder prompts and maintains a larger fraction of prompts with at least one correct rollout during training.These dynamics distinguish MaxRL from GRPO and RLOO beyond aggregate performance metrics.

7 Related Work

MaxRL is positioned against reinforcement-learning methods that address binary, verifier-based outcomes despite an implicit likelihood over successful outputs. Unlike adaptive sampling approaches, it uses a fixed-budget on-policy estimator designed to approach maximum likelihood as rollout compute increases.

  • Binary-verifier tasks induce an implicit likelihood over successful outputs, motivating likelihood-based alternatives to expected-reward reinforcement learning.
  • Prior work studies nonlinear pass-rate weighting through adaptive rollout allocation and sampling strategies.
  • MaxRL instead derives a fixed-budget on-policy estimator that approaches maximum likelihood as rollout compute increases.
  • The paper focuses empirically on improved data and compute scaling, whereas related adaptive-sampling work compares alternative sampling frameworks.

8 Conclusion

The paper presents MaxRL as a principled framework for binary-reward, non-differentiable settings, showing improved scaling over traditional RL while identifying binary rewards and several training settings as current boundaries. It situates the approach among supervised learning, reinforcement learning, exploration, and related inference-based views.

  • MaxRL is presented as a principled framework for non-differentiable binary-reward settings that scales more effectively with additional compute and data.
  • The method does not directly extend to continuous or arbitrarily valued rewards, multi-turn reinforcement learning, or off-policy PPO-style training.
  • The work relates to supervised and reinforcement learning because supervised methods are stable and sample-efficient, whereas RL can optimize non-differentiable objectives and improve beyond demonstrations.
  • MaxRL uses a fixed rollout budget to define compute-indexed objectives, unlike MCEM-style procedures that use samples to approximate a fixed maximum-likelihood objective.
  • The paper distinguishes its focus on recovering a cross-entropy-based classification objective in an RL pipeline from prior reasoning post-training approaches.
  • A noted limitation is that tasks with no correct rollout receive no gradient, motivating methods that assign non-zero rewards to incorrect generations.

C Theoretical Results

The theoretical results express likelihood and reinforcement-learning gradients through pass-rate-dependent weighting, showing that standard RL captures only the first-order term while MaxRL incorporates higher-order terms under finite sampling. The resulting estimators and practical variants are analyzed under fixed rollout budgets.

  • Maximum-likelihood gradients can be represented as conditional expectations over successful trajectories.
  • The practical estimator for MaxRL with order T=N is unbiased for the corresponding MaxRL gradient.
  • The practical dropped-baseline estimator is unbiased for the (N−1)-truncated MaxRL gradient.
  • All considered population-level objectives can be written using a pass-rate-dependent weighting function over input gradients.
  • Maximum likelihood uses inverse pass-rate weighting, whereas classical RL uses constant weighting and GRPO uses a distinct pass-rate-dependent weighting.
  • In ImageNet, cross-entropy, GRPO, REINFORCE, and MaxRL differ through their rollout-based binary-reward objectives and advantage calculations.
  • Validation top-1 accuracy equals majority-voting accuracy after averaging the per-example correctness indicator over validation examples.

H.4 Gradient Norm Analysis

The gradient-norm analysis compares sampling-based objectives with cross-entropy and evaluates their scaling behavior in didactic ImageNet experiments. MaxRL aligns more closely with cross-entropy, while GRPO improves with compute but remains below MaxRL and supervised training in the reported comparisons.

  • MaxRL and cross-entropy assign larger gradient norms to hard inputs and smaller norms to easy inputs.
  • GRPO concentrates its highest gradient norms on medium-difficulty inputs rather than inputs with pass rates near zero.
  • REINFORCE remains below 0.003 pass rate after 1500 steps and is reported to show no signs of learning in this setting.
  • MaxRL outperforms and scales better than GRPO with additional compute, while GRPO remains suboptimal relative to MaxRL and supervised cross-entropy training.
  • The maze experiments use procedurally generated symbolic grids whose difficulty is controlled by grid size and whose outputs are navigation-action sequences.
  • The maze evaluation uses 1 million distinct 17 × 17 training mazes and 256 non-overlapping test samples.
  • Training comparisons vary rollout count, batch size, and RL steps, including settings with 4 to 128 training rollouts and 128 rollouts per task.

I.4 Training Dynamics in Our Highest Compute Budget Setting

At the highest compute budget, MaxRL outperforms GRPO and REINFORCE across pass@k metrics in maze training and outperforms broader baselines in both average accuracy and coverage. In the data-scarce GSM8K setting, MaxRL achieves the strongest reported performance across metrics.

  • Highest compute budget: MaxRL significantly outperforms GRPO and REINFORCE at pass@1, pass@32, pass@128, and pass@256 in the highest-budget maze experiment.The experiment uses a 3M model, 17x17 mazes, batch size 256, and 128 training rollouts per task.
  • Baseline comparison: MaxRL outperforms entropy bonus, PKPO, Differential Smoothing, and SELF across metrics while maintaining both pass@1 accuracy and pass@k coverage.The broader comparison uses batch size 32 and 128 training rollouts.
  • Baseline comparison: MaxRL reaches 84.4 pass@1 and 94.3 pass@256 in the maze setting, improving over standard GRPO by more than 44 points on pass@1.PKPO reaches 74.5 pass@1, while SELF reaches 87.5 pass@256 but only 46.1 pass@1.
  • Data-scarce GSM8K: The GSM8K experiment studies data-scarce but compute-rich reinforcement fine-tuning of SmolLM2-360M-Instruct for 1500 steps.The training set is GSM8K, with evaluation on GSM8K-Platinum and 128 generations per prompt.

J.3 Effect of Additional Compute

Increasing rollout compute improves MaxRL’s approximation to maximum likelihood and improves final performance, with the largest gains appearing at higher pass@k values. MaxRL also avoids the extreme pass-rate concentration observed for GRPO and RLOO.

  • Compute scaling: Increasing the number of MaxRL training rollouts increases the approximation order T of its maximum-likelihood objective.The comparison varies T while keeping the remaining GSM8K training setup fixed.
  • Compute scaling: T = 128 outperforms T = 1 (REINFORCE) by almost 30% at pass@2048 as rollout compute increases.The largest gains occur at higher values of pass@k.
  • Performance with additional compute: MaxRL reaches 33.2 pass@1 and 83.4 pass@1024 on GSM8K, with the performance gap widening as k grows.MaxRL is 7.5 points above PKPO at pass@1024 and more than 30 points above GRPO and several other baselines.
  • Distribution dynamics: GRPO and RLOO concentrate per-prompt pass rates near 0 or 1, whereas MaxRL maintains a broad pass-rate distribution throughout training.The figure tracks pass-rate bins across epochs 0, 10, 20, 30, 40, and 50.
  • Distribution dynamics: MaxRL is more robust to distribution sharpening and extracts more learning signal from a fixed GSM8K training dataset.This conclusion follows the observed contrast between MaxRL and GRPO/RLOO pass-rate distributions.

K.3 Additional Results

Additional evaluations show that MaxRL matches or exceeds GRPO and the pretrained base model across benchmarks, including verifier-free majority voting. Its training dynamics and validation curves also generally favor MaxRL, while comparisons with PKPO show similar or better performance.

  • Extended benchmarks: MaxRL matches or outperforms the base model and GRPO on AIME 2024, both HMMT benchmarks, and JEEBENCH.It achieves up to 20.5× speedup over GRPO with multiple samples under a perfect verifier while maintaining similar or better pass@1.
  • Majority voting: MaxRL outperforms both the pretrained base model and GRPO on every benchmark under verifier-free majority voting.The method samples independently, groups responses by final answer, and selects the most frequent answer.
  • Training dynamics: Across Qwen3-4B-Base and Qwen3-1.7B-Base, MaxRL produces longer chains-of-thought, higher actor entropy, and larger gradient norms than GRPO.These trends are consistent across the two model sizes.
  • Validation accuracy: MaxRL consistently outperforms GRPO during Qwen3-4B-Base validation across three evaluation datasets.For Qwen3-1.7B-Base, MaxRL initially trails GRPO at pass@1 but catches up with extended training and ultimately converges higher.
  • Comparison with PKPO: MaxRL outperforms PKPO at all evaluated pass@k values in the maze and GSM8K settings and retains similar or better performance across four larger-scale evaluation datasets.The advantage over PKPO is more pronounced on BeyondAIME and AIME 2025.

L.2 ZPD

MaxRL outperforms ZPD and Power Function baselines across supervised, maze, GSM8K, and large-scale language-model settings. The comparisons also connect its performance to stronger learning signals on harder prompts and a larger fraction of prompts contributing useful gradients.

  • ZPD: MaxRL outperforms ZPD on ImageNet, where ZPD fails to improve significantly beyond the randomly initialized model.The ImageNet comparison uses identical training settings.
  • ZPD: MaxRL achieves significantly higher pass@k than ZPD in maze and GSM8K, including an approximately 30% improvement at pass@2048 on GSM8K.The comparisons use identical training settings and compute budgets.
  • ZPD: MaxRL outperforms ZPD on all evaluated Qwen3-4B-Base datasets, achieving 12.6× to 29.0× gains in test-time scaling efficiency under a perfect verifier.The models are trained on POLARIS-53K for 1000 RL steps.
  • Power Function: MaxRL outperforms the Power Function at both pass@1 and pass@128 on ImageNet despite using 128× less rollout compute.The performance gap is larger at pass@128.
  • Power Function: MaxRL outperforms the Power Function by approximately 20% at pass@2048 on GSM8K and achieves up to 12.4× test-time scaling efficiency gains on POLARIS-53K.On the larger-scale setting, MaxRL matches or outperforms the Power Function on all four evaluation datasets.
  • Non-zero gradient signal: MaxRL keeps a larger fraction of training prompts contributing useful gradient signal than GRPO and RLOO across maze and GSM8K.Prompts with no correct rollout contribute no gradient, while MaxRL produces at least one correct rollout for more prompts throughout training.

M.2 Policy Gradient Variance Analysis

The analysis finds that MaxRL’s variance-reduction baseline lowers gradient-estimator variance, while its gradient estimates become more stable as rollout counts increase. The broader evaluation also extends MaxRL to non-binary rewards, where it outperforms GRPO, though broader theoretical and empirical treatment remains future work.

  • Baseline variance: The variance-reduction baseline consistently lowers MaxRL gradient-estimator variance across rollout counts and tasks.This effect is reported for GSM8K, Polaris-53K, and Maze rollout pools.
  • Gradient stability: MaxRL becomes more stable as the rollout budget increases despite stronger amplification of very-low-success-rate problems.The inverse signal-to-noise analysis compares MaxRL with GRPO and RLOO using normalized gradient variance.
  • Evaluation context: MaxRL increases pass@k beyond the base model in a majority of scenarios, including large sampling budgets.On AIME 2025, MaxRL solves three problems exclusively compared with the base and GRPO-trained models when using 4096 samples per question.
  • Non-binary rewards: In the non-binary-reward maze setting, MaxRL outperforms GRPO on both Mean@32 and Best@32 validation reward.GRPO’s Best@32 reward collapses, while both MaxRL reward measures are still increasing at the end of training.
  • Scope: MaxRL’s non-binary extension is evaluated empirically, while full theoretical treatment and broader evaluation of non-binary rewards remain future work.The paper presents the extension under stated non-negative-reward assumptions.
Loading 2602.02710v3…