← All AI/ML open problems

Verification & proof search · RL & post-training / Open question

Learning to Branch

Tree rollouts reuse expensive prefixes, but nominal leaf count can exaggerate the number of independent learning signals.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

In a depth-HH tree over an AA-symbol alphabet with terminal reward r(y)∈{0,1}r(y)\in\{0,1\}, estimate g(θ)=Ey∼πθ[r(y)∇θlog⁡πθ(y)]g(\theta)=\mathbb E_{y\sim\pi_\theta}[r(y)\nabla_\theta\log\pi_\theta(y)] by adaptively branching shared prefixes. At total generated-token and verification cost CC, determine the minimum attainable E∥g^−g(θ)∥22\mathbb E\|\hat g-g(\theta)\|_2^2 and a scheme attaining it, with bounded policy scores and explicit dependence on shared-prefix covariance. Correct branch-selection bias before using the estimator in policy updates.

Assumptions and scope

  • Specify the prefix sampling law and branch-selection rule, including any entropy or reward-dependent adaptation.
  • Charge a shared prefix once and every generated suffix/verification at its declared cost; keep the target policy gradient fixed within an estimation round.
  • State how selection is corrected so that adaptive branching does not silently change the estimated objective; then quantify error when that estimator drives successive updates.

What would settle it?

A covariance-aware estimator and adaptive branching rule with cost-normalized error bounds and a matching impossibility/comparison result for a stated tree class, followed by a justified policy-update consequence.

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

DATPO supplies an empirical tree-search design, while VSR addresses state resampling. The remaining target is joint prefix-sharing covariance, selection correction and allocation guarantees. 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. Yu et al. — Difficulty-Adaptive Tree-Structured Policy Optimization ↗related algorithm · source checked 2026-11-19

    Publisher abstract checked: sentence-entropy branching, adaptive difficulty and sibling-diversity advantages. Finite-budget empirical coverage gains do not imply independent-rollout statistics.

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