Selective Rollout: Mid-Trajectory Termination for Multi-Sample Agent RL

• URL: http://arxiv.org/abs/2605.05802v1
• Date: Thu, 07 May 2026 07:41:09 GMT
• Title: Selective Rollout: Mid-Trajectory Termination for Multi-Sample Agent RL
• Abstract summary: Group-relative RL training (GRPO) samples a small group of parallel rollouts for every training prompt.<n>Uses their within-group reward spread to compute per-trajectory advantages.<n>When every rollout of a prompt ends with the same reward, the group has zero reward variance and contributes no gradient.
• Score: 6.435733307123974
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Group-relative RL training (GRPO) samples a small group of parallel rollouts for every training prompt and uses their within-group reward spread to compute per-trajectory advantages. In agentic environments each rollout is a long multi-turn dialogue with one LLM call per step, so this multi-sample multiplier dominates the total training cost. When every rollout of a prompt ends with the same reward, the group has zero reward variance and contributes no gradient, so the extra rollouts add no information; such groups are common in practice (typically around 40% of all groups), so the wasted-compute fraction is substantial rather than marginal. Existing methods filter such groups at the prompt level, either after their rollouts are paid for or before any rollout begins, but both decide without using information that becomes available during the rollout itself. We instead ask whether the in-group divergence between the partial trajectories at an intermediate step can already predict that the group will be zero-variance: when the parallel rollouts have already converged on the same action prefix, the group is on track to produce a single reward, and we can stop early. We propose a one-parameter gate that stops a group when the mean pairwise prefix edit distance between its partial action sequences falls below a threshold. On a 60-iteration on-policy GRPO run on ALFWorld with Qwen2.5-7B, averaged over four random seeds, the gated arm finishes 10.7% faster in wall-clock (bootstrap 95% CI excludes 0) and shifts held-out success rate on 50 unseen tasks by +2.5 pp, with the held-out gain tracing to a measurable reduction in zero-advantage gradient-batch dilution. Code is available at https://github.com/zhiyuanZhai20/selective-rollout.

Related papers

• Why Sample What You Can Enumerate? Exact Policy Optimization for Genomic Tool Selection [23.92446384027772]
  Reinforcement learning over a frozen reasoner has become a common recipe for teaching a policy which external tools invoke.<n>We show that this recipe becomes structurally mismatched in specialist scientific settings where the complete tool-subset space is enumerable.<n>We introduce FGPO, which scores every tool subset and optimize the exact action expectation, so each update sees the complete action space.
  arXiv  Detail & Related papers  (2026-09-09T14:20:47Z)
• ThinkPrior: Zero-Rollout Difficulty Priors for Cold-Start Prompt Selection in RLVR [0.38452047300097886]
  Group-relative advantages are identically zero if all rollouts in a group are correct or all are wrong.<n>History-based prompt selection must first spend target-policy rollouts to estimate difficulty.<n>ThinkPrior selects by expected learnability and then updates from training outcomes, changing neither the loss nor the gradient.<n>The measured ThinkPrior+DAPO composition reduces generated rollouts by 10.6% while both arms retain the same 3840-rollout update budget.
  arXiv  Detail & Related papers  (2026-09-08T17:30:12Z)
• Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR [0.0]
  We show that a group's effectiveness is usually decided early, within the first few of its rollouts, so spending a full group on an already-decided prompt is wasteful.<n>We apply a two-threshold, SPRT-style rule that commits effective groups, abandons saturated ones after a short probe, and reallocates the freed budget to fresh prompts.<n>We prove abandonment reliability, expected rollout savings, fixed-budget yield dominance, and a link between effective-group yield and the GRPO norm.
  arXiv  Detail & Related papers  (2026-07-28T20:43:23Z)
• Process Reward Informed Tree Rollout for Effective Multi-Turn RL [58.392997761968566]
  In long-horizon agentic tasks, a uniform rollout strategy can waste budget on uninformative dead-end attempts.<n>We propose Process-Scorer Guided Adaptive Tree Rollout (PATR), a quality-aware rollout framework for multi-turn agent RL.<n>PATR uses task-appropriate process feedback to score partial trajectories, selectively branches from promising states, reuses shared prefixes, and conservatively stops paths to reduce wasted sampling.
  arXiv  Detail & Related papers  (2026-07-17T04:16:58Z)
• GD$^2$PO: Mitigating Multi-Reward Conflicts via Group-Dynamic reward-Decoupled Policy Optimization [54.596224644751565]
  Post-training reinforcement learning (RL) increasingly relies on multi-dimensional rewards to cultivate comprehensive capabilities.<n>To address this, existing methods such as Group reward-Decoupled Policy Optimization (GDPO) decompose the overall score into independent reward groups, then compute the RL loss separately within each group.<n>We propose Group-Dynamic reward-Decoupled Policy Optimization (GD$2$PO), which employs a conflict-aware filtering mechanism to mask out rollouts suffering from severe reward-wise disagreement.
  arXiv  Detail & Related papers  (2026-06-15T14:19:28Z)
• Effective Reinforcement Learning for Agentic Search by Recycling Zero-Variance Queries During Training [28.12666966542811]
  We propose query recycling, which returns zero-variance groups to a mutable pool for future resampling.<n>We show that recycled queries supply roughly three quarters of the effective batch by the end of training.
  arXiv  Detail & Related papers  (2026-06-09T11:12:58Z)
• ARBOR: Online Process Rewards via a Reusable Rubric Buffer for Search Agents [48.80766702702854]
  LLM-based search agents are trained predominantly with outcome-only reward, leaving the search process itself unsupervised.<n>This signal degenerates on outcome-homogeneous groups where all sampled trajectories share the same correctness, yielding zero within-group advantage and no gradient.<n>We propose ARBOR (Adaptive Buffer for Online Reward), a reusable process-reward framework that maintains a rubric memory shared across queries.
  arXiv  Detail & Related papers  (2026-06-02T06:58:54Z)
• Breaking $\ extit{Winner-Takes-All}$: Cooperative Policy Optimization Improves Diverse LLM Reasoning [53.42577591449649]
  Group Cooperative Policy Optimization shifts the training paradigm from rollout competition to team cooperation.<n>GCPO replaces independent rollout scoring with team-level credit assignment.<n>It redistributes the collective team reward to each single rollout according to its average marginal contribution to the team.
  arXiv  Detail & Related papers  (2026-05-12T03:20:24Z)
• MARBLE: Multi-Aspect Reward Balance for Diffusion RL [71.6241143519038]
  Reinforcement learning has become the dominant approach for aligning diffusion models with human preferences.<n>Existing practice deal with multiple rewards by training one specialist model per reward.<n>We propose MARBLE, a gradient-space optimization framework that maintains independent advantage estimators for each reward.
  arXiv  Detail & Related papers  (2026-05-07T16:20:42Z)
• Improving Search Agent with One Line of Code [68.58667107354253]
  Tool-based Agentic Reinforcement Learning (TARL) has emerged as a promising paradigm for training search agents to interact with external tools.<n>We propose textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO), which stabilizes training via a conditional token-level KL constraint.
  arXiv  Detail & Related papers  (2026-03-10T04:07:39Z)
• Train Less, Learn More: Adaptive Efficient Rollout Optimization for Group-Based Reinforcement Learning [37.10958874118462]
  Reinforcement learning (RL) plays a central role in large language model (LLM) post-training.<n>In GRPO, each query prompts the LLM to generate a group of rollouts with a fixed group size $N$.<n>When all rollouts in a group share the same outcome, either all correct or all incorrect, the group-normalized advantages become zero.<n>We introduce Adaptive Efficient Rollout Optimization (AERO), an enhancement of GRPO.
  arXiv  Detail & Related papers  (2026-02-15T23:14:05Z)
• RC-GRPO: Reward-Conditioned Group Relative Policy Optimization for Multi-Turn Tool Calling Agents [40.88916135445381]
  Multi-turn tool calling is challenging for Large Language Models because rewards are sparse and exploration is expensive.<n>A common recipe, SFT followed by GRPO, can stall when within-group reward variation is low.<n>We propose RC- GRPO, which treats exploration as a controllable steering problem via discrete reward tokens.
  arXiv  Detail & Related papers  (2026-02-03T02:47:32Z)
• MC-GRPO: Median-Centered Group Relative Policy Optimization for Small-Rollout Reinforcement Learning [11.456510890703994]
  Group-relative policy optimization methods train language models by generating multiple rollouts per prompt.<n>In resource-constrained settings where the rollout budget is small, accuracy often degrades.<n>We propose Median-Centered Group Relative Policy Optimization (MC-GRPO), a simple and effective solution for small-rollout training.
  arXiv  Detail & Related papers  (2026-01-30T05:24:51Z)
• Generalized Parallel Scaling with Interdependent Generations [58.43994876504917]
  We propose Bridge to generate interdependent responses in parallel.<n>With only a small amount of new parameters, Bridge improves the relative mean accuracy gains from reinforcement learning.
  arXiv  Detail & Related papers  (2025-10-01T17:33:35Z)
• BranchGRPO: Stable and Efficient GRPO with Structured Branching in Diffusion Models [57.304411396229035]
  We present BranchGRPO, a method that restructures the rollout process into a branching tree.<n>On HPDv2.1 image alignment, BranchGRPO improves alignment scores by up to textbf16% over DanceGRPO.<n>A hybrid variant, BranchGRPO-Mix, further accelerates training to 4.7x faster than DanceGRPO without degrading alignment.
  arXiv  Detail & Related papers  (2025-09-07T12:53:06Z)
• MALT: Improving Reasoning with Multi-Agent LLM Training [67.76186488361685]
  MALT (Multi-Agent LLM Training) is a novel post-training strategy that divides the reasoning process into generation, verification, and refinement steps.<n>On MATH, GSM8K, and CSQA, MALT surpasses the same baseline LLM with a relative improvement of 15.66%, 7.42%, and 9.40% respectively.
  arXiv  Detail & Related papers  (2024-12-02T19:30:36Z)
• Improved Group Robustness via Classifier Retraining on Independent Splits [6.930560177764658]
  Group distributionally robust optimization is a widely used baseline for learning models with strong worst-group performance. This paper designs a simple method based on the idea of retraining on independent splits of the training data. We find that using a novel sample-splitting procedure achieves robust worst-group performance in the fine-tuning step.
  arXiv  Detail & Related papers  (2022-04-20T16:22:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.