RL & post-training · Learning dynamics & scaling / Open question
Compute-Optimal Reinforcement Learning
Empirical allocation recipes are useful but do not yet provide an algorithm-independent guarantee for the full cost of post-training. Efficiency payoff: Reach a fixed reward target with less total generation, update and checking work.
Seed catalog · Showing the bundled record.
Problem statement
Consider contextual tasks, a finite answer alphabet, horizon , binary terminal rewards and policies with and . Under , jointly allocate groups, prompts, sample reuse and exact reward checks. Bound final expected-reward regret against the best allocation using the same policy-update rule, data access and budget; expose dependence on and the feature dimension.
Assumptions and scope
- Fix an evaluation distribution, algorithm family and a cost model accounting for sequence length, verification and policy updates; GPU-hours alone are not interchangeable across hardware.
- State realizability or optimization assumptions and the policy comparator explicitly; do not infer a global optimum from a nonconvex stationary-point bound.
- Distinguish allocation under a fixed problem distribution from acquiring new environments, and state whether verifier judgments are exact or noisy.
What would settle it?
A fully specified model with an achievable allocation bound and lower-bound comparison, including conditions for an interior optimum or saturation. A Lagrange multiplier calculation applied to an assumed fitted law is background, not the target theorem.
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
IsoCompute and BroRL already analyze sampling choices empirically and in restricted models. Their results motivate, but do not establish, the stated joint learning-and-verification guarantee. 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
- Cheng et al. — IsoCompute Playbook: Optimally Scaling Sampling Compute for LLM RL ↗empirical motivation · source checked 2026-11-19
ICML 2026 publisher abstract checked: allocation among rollouts, batch size and updates; optimal group size increases then saturates in the measured setups.
- Hu et al. — BroRL: Scaling Reinforcement Learning via Broadened Exploration ↗related result · source checked 2026-11-19
Publisher abstract checked: one-step mass-balance analysis, simulator results and empirical gains from hundreds of rollouts. This does not establish arbitrary multi-step shared-parameter guarantees.
- Khatri et al. — The Art of Scaling Reinforcement Learning Compute for LLMs ↗empirical motivation · source checked 2026-11-19
Abstract checked: empirical sigmoidal fits, recipe-dependent efficiency/ceilings and held-out-scale prediction; not a universal asymptotic theorem.
- Rahman et al. — ScalePRM: Scaling Verification Compute Without Ground Truth ↗empirical motivation · source checked 2026-11-19
EMNLP publisher abstract checked: synthetic step labels from self-consistency/meta-critique and observed reward exploitation. Learned process scores are not kernel certificates.