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

Thank you for the review. Below, we address the concerns raised in the review.

---

We don't need to annotate or learn a dense reward model, but sparse reward trajectories could solve all problems. The main weakness is that it is difficult to imagine how this result can be useful. Could you provide any tangible procedure that could replace the PRM with ORM? In practice, what will be the difficulty of applying this idea?

Thanks for the feedback. We suspect that there might be some misunderstanding regarding the terminology and our focus. In this paper, we focus on statistical complexity by using an information-theoretic perspective to distinguish outcome/process supervision—that is—whether the external supervision signals are trajectory-wise or step-wise (see Section 2.2 for detailed explanation). Under our formulation, approaches that learn PRMs from outcome labels are considered outcome supervision, because these algorithmic interventions do not improve the statistical limits.

Our primary focus is on statistical complexity rather than algorithmic design. The central takeaway is a theoretical result: RL from sparse trajectory rewards is not, information-theoretically, significantly harder than RL from dense step-level rewards, despite the ostensible gap in information.

In terms of tangible procedures, many recent empirical studies that train PRMs using outcome labels [1,2,3] are, in our terminology, outcome-supervised (again, because the algorithmic aspects do not improve the statistical limits), which supports rather than contradicts our theoretical results. Our theory also aligns with the recent successes of outcome-based RL in the LLM industry (e.g., DeepSeek-R1, Kimi-K1.5), which further exemplify a tangible outcome-supervision procedure.

---

What assumption is not realistic?

Note that our paper follows the most general assumptions of RL theory with general function approximation. In fact, perhaps surprisingly, our core technical contribution—the Change of Trajectory Measure Lemma (Lemma 3)—only requires the Markov property and does not rely on any structural assumption regarding the environment’s dynamics or function class. This means that Lemma 3 is widely applicable to any Markov decision process, beyond the problem in this paper.

We suspect that this question from the reviewer arises because our key message (that outcome supervision is not much harder than process supervision) seems to contradict existing empirical results. However, this is just a matter of terminology, as we discussed above. Again, empirical successes in learning PRMs from outcome labels should be considered outcome supervision in our terminology, which supports rather than contradicts our theoretical results.

---

References:
[1] Luo, Liangchen, et al. "Improve mathematical reasoning in language models by automated process supervision." arXiv preprint arXiv:2406.06592 2 (2024).
[2] Wang, Peiyi, et al. "Math-shepherd: Verify and reinforce llms step-by-step without human annotations." arXiv preprint arXiv:2312.08935 (2023).
[3] Setlur, Amrith, et al. "Rewarding progress: Scaling automated process verifiers for llm reasoning." arXiv preprint arXiv:2410.08146 (2024).

Thank you very much for your support.

---

Relevant Citations in L416

We will add the citations accordingly.

---

Assumption on finiteness of $|R|$

Thanks for pointing this out. Even though the current theorems are stated for finite reward models, the change-of-trajectory-measure lemma does not require the size of the reward class to be finite. We believe it is easy to generalize our results to an infinite-size parametric reward class, or even to a nonparametric reward class, with the help of classical tools for analyzing the ERM performance in parametric or nonparametric model classes. We will add an explicit discussion regarding the assumption on the finiteness of $|R|$ in our future version.

---

Typos

Thanks for pointing out the typos. We will fix these in the revision.

Thank you for the review. Below, we address the concerns raised in the review.

---

I think some of the claims in the introduction and general framing of the paper are too strong … I think the applicability is probably lower because the reward signals in LLMs are often provided by human overseers. The analysis neglects practically important aspects such as where do the process and outcome rewards come from … overall I'm not drawing any strong conclusions from the results in this paper.

If our understanding is correct, the main concern of the reviewer is that the outcome reward and process reward in practice often come from different sources with varying quality, so it is not practical to directly compare their sample complexity without considering these potential differences in quality.

We appreciate this feedback; however, we would like to clarify that our paper primarily focuses on RL from outcome reward, because RL from process reward is already extensively studied in theory. This paper only considers the case where the outcome reward has the same quality as the process reward (i.e., outcome reward = sum of process reward), so that learning from process reward is always easier. We then investigate how much more difficult RL from outcome reward can be compared with process reward. This is well motivated by recent LLM reasoning problems, as checking the correctness of the entire solution is not more difficult than verifying each step.

Our major result is both simple and somewhat counterintuitive: we prove that RL from outcome reward is not much harder than RL from process reward, information-theoretically, even though process reward seems to provide far more information for credit assignment. We believe this theoretical conclusion is significant, because it coincides with and explains recent surprising successes of outcome-based RL in the LLM industry (e.g., DeepSeek-R1, Kimi-K1.5).

Finally, we emphasize that our submission is a theoretical paper, submitted to the theory category. Besides our main message, we present the novel Change of Trajectory Measure Lemma, which is the first result addressing trajectory-level change of measure with only step-level distribution shift. This lemma has broader applicability in RL theory beyond this paper. Hence, our theoretical results, rather than the outcome-to-process transformation itself, represent our core contribution and substantially deepen the theoretical understanding of reinforcement learning.

---

Pre-LLM RL discussion

We do include substantial discussion of pre-LLM RL throughout the paper. For instance, Section 2 addresses coverage assumptions in the classic RL literature, and Section 3 discusses offline RL and preference-based RL. We also provide a Related Work section in the appendix, which includes references to pre-LLM RL research that is not covered in detail in the main text. Furthermore, we will add a discussion of RL with trajectory feedback and reward shaping to the Related Work section in our revision.

Thank you for your review. Below, we address the concerns raised in the review.

---

more thoroughly discuss recent works on automated process supervision [1-3]

Thanks for pointing these out, we will add more detailed discussion in the updated version.

---

Coverage Assumptions

We would like to clarify that coverage assumptions are essential and widely used in the theory of offline RL (see discussion in Section 2.3). Our paper provides results on two kinds of coverage assumptions: in addition to $C_{\sf s,a}(\Pi,\pi_{\sf off})$ (coverage of all $\pi$ in $\Pi$) used in Section 3., we also have results in Appendix C that rely solely on $C_{\sf s,a}(\pi^*,\pi_{\sf off})$ (coverage for a single good policy $\pi^*$).

We believe the latter notion should be considered practical even in the LLM regime, because it only requires the data distribution to cover a single good policy. For example, $\pi^*$ could be the best-of-N policy. In this case, $C_{\sf s,a}(\pi^*,\pi_{\sf off})$ is bounded by N.

---

Lack of Empirical Validation / Disconnect from Practice

Thanks for pointing this out. We suspect that there might be some misunderstanding regarding the terminology. In this paper, we focus on statistical complexity by using an information-theoretic perspective to distinguish outcome/process supervision—that is—whether the external supervision signals are trajectory-wise or step-wise (see Section 2.2 for detailed explanation).

Therefore, recent empirical results that learn PRMs from outcome labels [1,2] are actually outcome supervised in our language (because these algorithmic interventions do not benefit the statistical limits), which supports rather than contradicts our theoretical results. Our theory also coincides with the recent findings from DeepSeek-R1 and indicates that outcome annotation only induces a poly(H) additional cost of statistical complexity compared to step-by-step annotation (which can be easily bypassed if we have an “almost-free” rule-based outcome reward).

---

Limited Intuitive Explanations

We agree the proof of Lemma 3 can be complicated and counterintuitive. We have re-written the proof sketch and will update it in our future version. Due to space constraints, we only include the most important intuition below:

The key difficulty of implementing a trajectory-level change of measure is that small values of $|f(\tau)|$ do not necessarily ensure small values on every prefix $\tau_{1:h}$ or suffix $\tau_{h+1:H}$ (since cancellations could occur; for example, $a + b = 0$ does not imply $a = b = 0$). However, the Markov property ensures that if $f$ has a small second moment under $\pi_{\sf off}$ and state $s_h$ is frequently visited, then $f$ cannot have high variance on either the prefix or the suffix through $s_h$. This is because high variance on any component would imply high variance for the entire trajectory.

From that, we can apply the change of measure over these frequently encountered states from the offline policy to the objective policy, only paying the state-action concentrability. Afterward, we show that if all states along a trajectory satisfy the prefix/suffix trajectory low-variance property mentioned above, then the absolute value of the total rewards can be upper bounded as well.

---

about advantage function result (Section 4)

There has been some work that explicitly validates the idea of using the advantage function in reward models [3], demonstrating an advantage over using the Q-function as a reward. However, it is still unclear which approach is theoretically correct, as using the Q-function as a reward also shows strong empirical potential [1,2]. In Section 4, our motivation is to clarify this A vs. Q debates: we formally prove that using the advantage function of any policy as a reward is correct in principle, whereas using the Q-function can fail in certain cases.

---

Decision making with partial observability

Thank you for bringing this to our attention. This is an interesting research direction, and we plan to explore it in our future work.

---

References:
[1] Luo, Liangchen, et al. "Improve mathematical reasoning in language models by automated process supervision." arXiv preprint arXiv:2406.06592 2 (2024).
[2] Wang, Peiyi, et al. "Math-shepherd: Verify and reinforce llms step-by-step without human annotations." arXiv preprint arXiv:2312.08935 (2023).
[3] Setlur, Amrith, et al. "Rewarding progress: Scaling automated process verifiers for llm reasoning." arXiv preprint arXiv:2410.08146 (2024).