RL & post-training · Statistical learning theory / Open question
Learning More from Every Rollout
A fixed group size wastes samples as individual tasks move from rare success to reliable success. An allocation theorem could guide verifier-backed LLM and proof-agent training.
Seed catalog · Showing the bundled record.
Problem statement
For horizon- tasks with binary reward , use , , , and a fixed prompt law . Define success . Determine excess rollout cost for choosing group sizes online to reach an attainable target , against a moment-informed allocator using the same updates. Include policy-dependent gradient covariance and bias from empirical group normalization.
Assumptions and scope
- Use bounded features/scores, binary terminal rewards, finite output horizon and explicit smoothness/coverage constants; expose dependence on small success probabilities.
- Specify empirical centering, variance smoothing, clipping and KL terms. A homogeneous group has zero centered reward advantage; auxiliary regularizers may still produce an update.
- The comparison oracle knows allocation statistics, not free correct answers or exact gradients. It must pay for samples and use the same permitted policy-update mechanism.
What would settle it?
An adaptive allocation algorithm with explicit excess-compute upper bounds and matching lower bounds for the declared task/policy class, or an obstruction showing which additional assumptions or normalization corrections are necessary.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
The mixed-group probability and inverse-success heuristic are elementary/existing. sGPO profiles the initial policy; VSR gives a fixed-policy variance optimum. The residual target is allocation regret and learning progress under coupled, changing policies. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Sudalairaj et al. — sGPO: Trading Inference FLOPs for Training Efficiency in RLVR ↗related algorithm · source checked 2026-11-19
Abstract checked: initial-policy profiling already motivates inverse-success group sizes, filtering and curricula. The simple inverse-success rule is not listed here as new.
- Wang et al. — Variance-Optimal State Resampling for RLVR ↗partial theory · source checked 2026-11-19
Abstract checked: a fixed-policy variance-minimizing Neyman allocation is already derived. Online multi-step allocation and the cost of learning its changing inputs are separate targets.
- Mroueh — RLVR: GRPO's Effective Loss, Dynamics, and Success Amplification ↗partial theory · source checked 2026-11-19
Full-text formulation and theorem statements checked: stabilized population/no-clipping policy-space updates and KL-dependent recurrences. Finite empirical groups and shared-parameter optimization require additional analysis.
- Wachi et al. — A Relative-Budget Theory for RLVR in LLM Reasoning ↗partial theory · source checked 2026-11-19
Abstract checked: relative horizon versus first-success time and finite-sample online guarantees already exist under the paper's assumptions.