Technical Summary: Contextual Rollout Bandits for Reinforcement Learning with Verifiable Rewards

Problem Statement

Reinforcement Learning with Verifiable Rewards (RLVR) has emerged as a critical paradigm for enhancing the reasoning capabilities of Large Language Models (LLMs), particularly in domains like mathematics and code generation. However, existing RLVR methods suffer from two fundamental limitations that lead to noisy supervision, poor sample efficiency, and suboptimal policy updates:

1. Indiscriminate Intra-Group Utilization: Current approaches, such as Group Relative Policy Optimization (GRPO), generate multiple responses (rollouts) for a single prompt but treat them uniformly during gradient computation. This ignores the significant quality heterogeneity within a group, where many responses may be low-utility, noisy, or misleading (e.g., guessed-correct solutions or trajectories with redundant reasoning steps).
2. Restricted Data Horizons: Most methods rely exclusively on the latest batch of rollouts for optimization, discarding historical trajectories after a single use. This myopic training paradigm prevents the reuse of high-value historical data, limiting attainable policy performance and sample efficiency.

Existing attempts to address these issues often rely on static, hand-crafted heuristics that lack adaptivity to evolving training dynamics.

Methodology: Contextual Rollout Bandits (CBS)

The authors propose CBS, a unified neural scheduling framework that formulates rollout scheduling as a contextual bandit problem. In this formulation, each rollout is treated as an "arm," and the reward is defined by the induced performance gain between consecutive optimization steps.

Core Components

1. Neural Scheduler Architecture:

   • Arm Representation: Each rollout is encoded into a compact 10-dimensional vector capturing training dynamics. These features include:
     • Reward-related signals: Raw reward, advantage, mean group reward, and standard deviation of group reward.
     • Length-related signals: Normalized response length and truncation flags.
     • Policy perception metrics: Entropy and clip ratios.
     • Data interaction history: Usage count and sample age (freshness).
   • Scheduler Model: A Multi-Layer Perceptron (MLP) predicts the future utility of each rollout based on its representation and online feedback.
   • Selection Strategy: The scheduler employs an $\epsilon$-greedy strategy to balance exploration and exploitation, selecting top-scoring rollouts while occasionally sampling newer data.

2. Two Scheduling Regimes:

   • Intra-Group Scheduling (CBS):* Addresses response-quality heterogeneity by performing fine-grained selection within each rollout group. The scheduler selects a top-$p\%$ subset of high-value rollouts from each group, filtering out noisy or low-utility samples before policy optimization.
   • Global Adaptive Reuse (CBS): Addresses the limited-horizon constraint by maintaining a FIFO replay buffer of historical rollouts (from the last $L$ iterations). The scheduler performs global selection across this buffer to reuse high-value trajectories across training rounds, significantly improving sample efficiency.

3. Reward Definition and Update:

   • Performance Gain Reward: The reward function is defined as the metric gain between consecutive rollout data, incorporating average reward ($V$) and entropy ($E$) changes. An entropy penalty term prevents training collapse by penalizing entropy increases beyond a threshold.
   • Online Adaptation: The scheduler parameters are updated online using sample-level rewards derived from the group-level performance gain. To ensure stability, group rewards are normalized using an Exponential Moving Average (EMA) and scaled via a Sigmoid function.

Key Contributions

1. Unified Contextual-Rollout Bandit Framework: The paper formulates rollout scheduling in RLVR as a contextual bandit problem, providing a single principled framework that supports both noise-aware intra-group selection and adaptive global reuse of historical rollouts.
2. Theoretical Guarantees:
   • The authors establish a formal connection between RLVR data scheduling and contextual bandits.
   • They derive sublinear regret bounds ($\tilde{O}(\sqrt{T})$) for the proposed neural scheduler under a simplified single-sample selection setting, relying on the Neural Tangent Kernel (NTK) framework.
   • They prove that enlarging the replay buffer improves the achievable upper bound of policy performance, providing theoretical justification for global rollout reuse.
3. Empirical Effectiveness: Extensive experiments demonstrate that CBS consistently improves both final performance and training efficiency across multiple RLVR optimization methods (GRPO, DAPO, GSPO) and model sizes.

Experimental Results

The method was evaluated on six mathematical reasoning benchmarks (AIME24, AIME25, AMC23, MATH500, Minerva, Olympiad) using Qwen3 models (1.7B, 4B, 8B).

• Performance Gains: Integrating CBS resulted in consistent relative improvements across different policy optimization methods. For instance, on the Qwen3-1.7B model, CBS improved GRPO by 4.4% and DAPO by 15.7% on average.
• Training Efficiency: CBS significantly reduced the average policy optimization time (up to 50.4% reduction) by requiring fewer training trajectories per actor update.
• Computational Overhead: The scheduler's computational cost is negligible, accounting for less than 4% of total training time, and this ratio decreases as model size increases.
• Ablation Studies: Removing components such as the neural scheduler (replaced by random selection), EMA reward normalization, or the entropy penalty term led to performance degradation or training instability (e.g., uncontrolled entropy growth), validating the necessity of each component.

Significance and Claims

The paper claims that CBS offers a principled solution to the data inefficiency and noise issues inherent in current RLVR pipelines. By treating rollout selection as an adaptive learning problem rather than a static heuristic, CBS enables:

• Fine-grained supervision filtering: Automatically prioritizing informative responses while suppressing noisy ones.
• Long-horizon data reuse: Systematically leveraging historical high-value trajectories to refine policies over time.

The authors emphasize that their approach provides a scalable self-improvement paradigm that does not rely on manual, method-specific heuristics. While the current implementation uses a lightweight 10-dimensional representation for efficiency, the framework is designed to be extensible, potentially allowing for the integration of deeper semantic representations in future work. The work positions itself as a step toward more efficient and robust RLVR training for large reasoning models.