← All AI/ML open problems

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.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

Consider NN contextual tasks, a finite answer alphabet, horizon HH, binary terminal rewards and policies πθ(a∣h,x)∝exp⁡(θ⊤ϕ(x,h,a))\pi_\theta(a\mid h,x)\propto\exp(\theta^\top\phi(x,h,a)) with ∥ϕ∥2≤1\|\phi\|_2\leq1 and ∥θ∥2≤B\|\theta\|_2\leq B. Under C=Crollout+Cupdate+CverifyC=C_{\mathrm{rollout}}+C_{\mathrm{update}}+C_{\mathrm{verify}}, 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 N,H,BN,H,B 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

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

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

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

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