← All AI/ML open problems

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

Learning from Steps or Outcomes?

Dense feedback can improve credit assignment but may consume more compute or reward a misleading intermediate notion of correctness.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

Take tasks that compose HH maps from a finite alphabet on SS states; inputs specify the map sequence and initial state, and a shared softmax policy generates a state trace. A terminal verifier checks the final state, while a queried intermediate check reports prefix correctness with independent error ν<1/2\nu<1/2. Determine the minimum total generation/checking cost to reach final success 1−ε1-\varepsilon, comparing terminal-only learning with adaptive intermediate queries as H,S,νH,S,\nu and the relative check costs vary.

Assumptions and scope

  • Define the compositional task class, base-policy quality and information revealed by an intermediate check; a correct final answer need not uniquely determine all valid intermediate routes.
  • Charge generation, outcome verification and intermediate checks separately, and preserve the same final correctness objective.
  • State whether intermediate rewards are unbiased information, potential-based shaping or a changed objective; include verifier error when applicable.

What would settle it?

Matching sample/cost comparisons for a specified task family and an adaptive placement rule for intermediate checks, including a regime where the extra supervision provably does not pay.

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

Compositional RLVR learnability, relative-budget theory and empirically effective process rewards already exist. The target is the costed, noisy, selectively observed comparison rather than a blanket claim that dense rewards help. 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. Barzilai, Wolf and Basri — When Is Compositional Reasoning Learnable from Verifiable Rewards? ↗partial theory · source checked 2026-11-19

    Primary abstract checked: task-advantage-ratio characterization, positive learnability cases and suboptimal-composition obstructions. The remaining target must go beyond this specified autoregressive model.

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

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

  4. He et al. — How Data Scales in Agentic Reinforcement Learning ↗empirical motivation · source checked 2026-11-19

    Full-text Sections 3–6 checked: distinguish worlds, environment structures, tasks, trajectories and reward density. Exponents and synthesis discounts are empirical, regime-specific fits; allocation assumes a stated cost model.