Learning with a Single Rollout via Monte Carlo Pass@k Critic

Researchers propose SR-PPO, a reinforcement learning method that trains language models using single rollouts and Monte Carlo Pass@k critics for token-level credit assignment. The approach reduces computational costs while improving reasoning performance on mathematical benchmarks like HMMT26 and AIME24 by using reachability-based advantage estimation instead of repeated sampling.

This research addresses a fundamental efficiency problem in reinforcement learning for language models: training typically requires expensive repeated sampling to generate multiple trajectories for credit assignment. SR-PPO introduces an elegant solution by leveraging Pass@k probability estimates—the likelihood of success within k attempts—as a learning signal derived from single rollouts. This approach is computationally attractive because it eliminates the need for contrastive trajectory sampling while providing a more informative gradient signal than sparse outcome rewards.

The mathematical foundation is particularly noteworthy. As k increases, Pass@k converges to a reachability indicator showing whether a prefix can lead to any successful continuation. This theoretical insight connects to explicit state graphs where reachability can be computed efficiently in O(|V|+|E|) time, offering practitioners a principled way to estimate advantages without extensive sampling. The method directly addresses the credit assignment problem that limits algorithms like GRPO, which struggle to attribute outcomes to specific intermediate actions.

For the AI and machine learning community, this work demonstrates practical efficiency gains on meaningful benchmarks. Consistent improvements in Pass@128 success rates on HMMT26 and AIME24 suggest the approach generalizes across challenging mathematical reasoning tasks. The stable learning dynamics indicate the method avoids the instability often seen in RL for language models. However, broader adoption requires validation on diverse tasks beyond mathematical reasoning and comparison with other efficient credit assignment methods on standardized benchmarks.

• →SR-PPO reduces computational cost by using single rollouts with Monte Carlo Pass@k critics instead of repeated episodic sampling
• →Pass@k probability estimates provide more selective learning signals than sparse outcome rewards by prioritizing hard examples
• →Reachability indicators offer O(|V|+|E|) time computation for credit assignment without contrastive trace sampling
• →Mathematical reasoning benchmarks show consistent gains in Pass@128 success rates with stable learning dynamics
• →The method addresses a fundamental scalability bottleneck in reinforcement learning for language models