← All AI/ML open problems

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.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

For NN horizon-HH tasks with binary reward r(x,y)r(x,y), use πθ(a∣h,x)∝eθ⊤ϕ(x,h,a)\pi_\theta(a\mid h,x)\propto e^{\theta^\top\phi(x,h,a)}, ∥ϕ∥2≤1\|\phi\|_2\leq1, ∥θ∥2≤B\|\theta\|_2\leq B, and a fixed prompt law DD. Define success pθ(x)=Ey∼πθr(x,y)p_\theta(x)=\mathbb E_{y\sim\pi_\theta}r(x,y). Determine excess rollout cost for choosing group sizes Gt(x)G_t(x) online to reach an attainable target Ex∼Dpθt(x)≥1−ε\mathbb E_{x\sim D}p_{\theta_t}(x)\geq1-\varepsilon, 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.