Research map / Reinforcement learning / RL from feedback

Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective

ICML 2025 · Reinforcement learning › RL from feedback · approach: Scaling RL with verifiable rewards · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows theoretically that outcome supervision is statistically no harder than process supervision in offline RL (up to horizon polynomials) via a Change of Trajectory Measure Lemma relying on state-action concentrability, and that the advantage function of any policy is an optimal process reward model.

Problem

Whether outcome supervision (trajectory-level reward) is statistically harder than process supervision (step-level reward) in RL for complex reasoning in LLMs.

Approach

A Change of Trajectory Measure Lemma bounds trajectory-return distribution shift using only state-action concentrability (not trajectory concentrability), enabling least-squares reward imputation from outcome data with polynomial-in-H overhead; additionally the advantage function of any policy, estimated via rollouts, is shown to be an optimal process reward model while the Q-function is not.

Key results

• Least-squares reward imputation from outcome data yields suboptimality bounds scaling as H^{3/2} sqrt(C_sa log|R| / |D_O|), so outcome supervision matches process supervision up to horizon polynomials.
• Change of Trajectory Measure Lemma: E_pi[f(tau)^2] <= O(H^3 C_sa(pi, pi_off)) E_pi_off[f(tau)^2].
• The advantage function of any policy serves as an optimal process reward model, whereas a hard MDP shows the Q-function can yield suboptimality of at least 1/3.

Surprising findings

• State-action concentrability suffices for outcome supervision, not only for process supervision.
• Using the Q-function as a reward model can produce a policy with suboptimality at least 1/3, while the advantage function is provably valid.

Limitations

• Results carry polynomial-in-horizon factors that may not be removable.
• Guarantees require outcome data collected offline; online settings are left for future work.
• DPO analysis assumes deterministic transitions and bounded log-ratio of trajectory probabilities.

Experimental setup

Metrics: sample complexity bounds

Baselines: Q-function reward model

Builds on: offline RL with concentrability DPO performance difference lemma

Closest papers by meaning

• Let's Verify Step by Step (ICLR 2024 · similarity 0.89)
• StepORLM: A Self-Evolving Framework With Generative Process Supervision For Operations Research Language Models (ICLR 2026 · similarity 0.88)
• Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning (ICLR 2025 · similarity 0.88)
• Learning Process Rewards via Visitation Matching for Efficient RL (NeurIPS 2026 · similarity 0.87)
• Training Large Language Models for Reasoning through Reverse Curriculum Reinforcement Learning (ICML 2024 · similarity 0.86)
• Discriminative Policy Optimization for Token-Level Reward Models (ICML 2025 · similarity 0.86)