Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective
Authors: Zeyu Jia
Alexander Rakhlin
Tengyang Xie
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning Theory
Process Supervision
Outcome Supervision
Reward Modeling
Markov Decision Process
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Under standard data coverage assumptions, reinforcement learning through outcome supervision is no more statistically difficult than through process supervision.

Abstract: Process and outcome supervision represent two fundamental approaches to   reinforcement learning, especially for complex reasoning tasks in large language models. While process supervision offers intuitive advantages for long-term credit assignment, the precise relationship between these paradigms has remained an open question. Conventional wisdom suggests that outcome supervision is fundamentally more challenging due to the trajectory-level coverage problem, leading to significant investment in collecting fine-grained process supervision data.

In this paper, we provide a possible theoretical resolution to this debate. Perhaps surprisingly, our main theorem shows that: *under standard data coverage assumptions, reinforcement learning through outcome supervision is no more statistically difficult than through process supervision*. At the core of this result lies the novel *Change of Trajectory Measure Lemma*---a powerful technical tool that bridges return-based trajectory measure and step-level distribution shift. Furthermore, for settings with access to a verifier or a rollout capability, we prove that any policy's advantage function can serve as an optimal process reward model, providing a simple yet powerful connection between outcome and process supervision. These findings suggest that the empirically observed performance gap between outcome and process supervision likely stems from algorithmic limitations rather than inherent statistical difficulties, potentially transforming how we approach data and algorithm design for reinforcement learning.

Do We Need to Verify Step by Step?
Rethinking Process Supervision from a Theoretical Perspective
Zeyu Jia Alexander Rakhlin Tengyang Xie
Abstract
1. Introduction
Reward signals play a central role in reinforcement learn- ing, and has been hypothesized that intelligence and its associated abilities could emerge naturally from the simple principle of reward maximization (Silver et al., 2021). Over the past decade, this idea has been powerfully demonstrated across diverse AI systems. In specialized domains like Al- phaGo Zero (Silver et al., 2017), superhuman performance has been achieved by maximizing simple, well-defined en- vironmental reward signals. The paradigm has also proven transformative for general-purpose AI systems, particularly in training large language models (LLMs) using reinforce- ment learning (Ouyang et al., 2022; Bai et al., 2022; Jaech et al., 2024). However, for these more open-ended sys- tems, the challenge of reward specification significantly more complex, requiring reward signals to be learned from human-annotated data through reward modeling rather than being manually specified.
As large language models have evolved, it has become crucial to distinguish between process supervision and outcome supervision-two key reinforcement learning approaches to complex reasoning tasks. While process supervision of- fers intuitive advantages for long-ferm credit as- signment, the precise relationship between these paradigms has remained an open question. Con- ventional wisdom suggests that outcome super- vision is fundamentally more challenging due to the trajectory-leve coverage problem, leading to significant investment in collecting fine-grained process supervision data. In this paper, we take steps towards resolving this debate. Our main theorem shows that, under standard data cover- age assumptions, reinforcement leurning through outcome supervision is no more statistically diffi- cult than through process supervision, up to poly- nomial factors horizon. At the core of this result lies the novel Change of Trajectory Mea- sure Lemma-a technical tool that bridges return- based trajectory measure and step-level distribu- tion shift. Furthermore, for settings with access to a verifier or a rollout capability, we prove that any policy's s advantage function can serve as an optimal process reward model, providing a direct connection between outcome and process supervi- sion. These findings suggest that the empirically observed performance gap if any between out- come and process supervision likely stems from algorithmic limitations rather than inherent statis- tical difficulties, potentially transforming how we approach data and algorithm design for reinforce- ment learning.
This challenge of reward specification has led the emer- gence of two fundamental supervision paradigms in rein- forcement learning (e.g., Uesato et al., 2022; Lightman et al., 2023):
Outcome supervision: Reward feedback is provided only after the final output, based on the final out- comes or-in the case of LLMs-overall quality of the model's chain-of of-thought (CoT).
Process supervision: Fine- fine-grained reward feedback is provided based on the quality of each intermediate step (c.g., correctness of each step in the CoT in the case of L.MMs).
The choice between these paradigms represents a fundamen- tal trade-off in reinforcement learning system design. Pro- cess supervision offers several intuitive advantages: it pro- vides more granular feedback, enables better interpretability of model decisions, and potentially allows for more efficient credit assignment in long reasoning chains. These benefits have led significant investment in collecting step-by-ster feedback data, despite the substantial human effort required (Lightman et al., 2023). The granular nature of process supervision also aligns with how humans often learn and teach through step- by- guidance rather than just final outcomes.
"Massachusetts Institute of Technology, Cambridge MA, USA Univeessity of Misconsin-Madisonn Madison WI. USA. Corre- spondence to: Zeyu Jia <zyjia@m mit.edus, Alexander Rakhlin <rakhlin mit, Tengyang Xie <tx wid....d...
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Process vs. Outcome Supervision
However, the high cost of collecting process supervision data raises important questions about its necessity. Outcome supervision, while providing less detailed feedback, offers practical advantages in terms of data collection efficiency and scalability. It also reflects various natural settings of human learning where detailed step-by-step feedback may not be available (e.g., game-playing). Recent empirical advances in automated process supervision derived from outcome supervision (Wang al., 2024; Luo et al., 2024; Zhong et al., 2024; Yuan et al., 2024; Setlur et al., 2024) or in directly learning from outcome supervision (Guo et al., 2025) suggest that the statistical benefits of process supervi- sion might not be as fundamental as previously thought.
(1) Our key technical contribution- of Trajec- tory Measure Lemma (Lemma 3) applicable be- yond our main results. The change of measure is a fundamental operation in analyzing off-policy evalua- tion (e.g.. Uehara et al., 2020), offline reinforcement learning (e.g.. Xie et al., 2021a), and out-of-domain generalization (Dong and Ma, 2022). To our knowl- edge, Lemma 3 presents the first result concerning trajectory-lever change of measure via step-level distri- bution shift.
(2) We also extend our main results to the setting of preference-basee reinforcement learning (Section 3.4), Namely, we transform preference-based trajectory data, generated according to the Bradley-Tene model, into a dataset of trajectories with per-step reward. In partic- ular, for direct preference optimization (Rafailov et al., 2023), we improve the previous analyses and show that its sample complexity only scales with the state-action concentrability coefficients instead of trajectory con- centrability peeficients-pooeeniiii an exponential improvement.
This tension between process and outcome supervision touches on deeper questions in machine learning and cog- nitive science: How much explicit supervision is truly nec- essary for effective learning? Can systems learn optimal behavior from sparse reward signals, or is step-by-step guid- ance fundamentally necessary? Understanding these ques- tions has important implications not just for practical system design, but also for our broader understanding of learning and intelligence.
1.2. Notation
We use an S b, or an (bx,) whenever there exists some universal positive constant e such that a, bn- We use : R - [0, 1] to denote the sigmoid function
1.1. Our Results
This paper examines the statistical performance of reinforce- ment learning under outcome supervision- emerging paradigm that has garnered significant attention in large lan- guage model research. Our findings challenge conventional wisdom that outcome supervision is inherently more diffi- cult than process supervision due to its coarser feedback.
- ==x)= = =xp((r/(11 + exp(x)).
2. Background
In this section, we introduce key prerequisite concepts. We begin with the basics of Markov Decision Processes (Sec- tion 2.1). We then discuss the two aforementioned super- vision paradigms in reinforcement learning (Section 2.2). Finally, we review the concepts of state-action and trajectory concentrability (Section 2.3).
(1) Our main results (Section 3) demonstrate that given dataset of trajectories with only cumulative rewards (as in outcome supervision), we can transform the data into trajectories with per-step rewards, while only pay- ing an additive eтrоr that scales with the state-action concentrability. As a result, we can transform any al- gorithm that takes trajectories with per-step rewards as input into an algorithm that takes trajectories with total rewards as input, with essentially no loss in statistical performance up polynomial factors of the horizon.
2.1. Markoy Decision Processes
An MDP M consists of a tuple (S,A, P,rr H). Here H e E denotes the horizon, S = , S, denotes the layered state space, A denotes the action space, P == (PI..... PH) with Pa Sr A + ((Sp+1) denoting the transition model, and r" S x A - [0, 1] is the deterministic ground truth reward model. For simplicity, we let 81 E S be a fixed initial state.
(2)
We also provide (Section 4) theoretical analysis of using Q-functions or advantage functions as reward functions, a popular approach in practice for mimick- ing process supervision from outcome supervision data (e.g., Wang et al., 2024: Luo et al., 2024; Setlur al., 2024). We prove that the advantage function of any policy can serve as an optimal process reward model: in contradistinction, using Q-functions could lead to sub-optimal results.
For a trajectory - (81, (11, 82, 022 8H, a.)), we write r(r) = Σ" r(s,, ) denote the total reward accumu- lated along the trajectory under deterministic reward model S x A - IR (which can be the ground truth reward model r" or any learned reward model f). A (Markov) policy π S - SSA((A A(A) is a mapping from the state space S to a distribution on the action space A. The notation P Pran and Erar stands for the probability and expectation
Beyond these two main messages, we make the following contributions:
2

---

Process vs. Outcome Supervision
with respect to trajectories r sampled according to policy π within the transition model given by P. starting from fixed state 51. For any given policy n, the occupancy measure of any state Sh E Sp, in layer h and any state-action pair (sh; an) E Sp x A are defined, respectively, as d² (sh) == Pronn (9h, E 7) and d= (sn. an) == (P
human feedback (e.g.. Ouyang et al., 2022) typically falls under this paradigm, where only the trajectory- level supervision signal is available.
Our analysis reveals the temporal resolution distinction de- scrihed above does not inherently create statistical complex- ity gaps when proper coverage conditions hold. Our results formalize this insight in the following two settings: (1) Of- fline RL with different reward signal resolutions (Section 3), and (2) Online RL with verifier/rollout access (Section 4).
E 7). Additionally, we define the trajectory occupancy measure for any trajectory T, (T) = Pr'no (T = r²), as well as (T) (.))r Taa sh) (note that d''l (r) and (()) are different when transitions is stochastic). For any policy t,, we use ((r to denote the expected total reward of trajec- tories collected by π under the ground truth reward r", i.e., [TT) == (e>=<("(TT], For a specific reward model r, we use (T) to denote the expected total reward of trajectories collected by π under reward r, i... (T) = E [r])] We assume that r (7) [0, 1] for any trajectory T.
Settcome-Superviedd and Process-Supervised Reward Models. Two other commonly used terms related to this paper are outcome-supervised reward models (ORMs) and process-supervised reward models (PRMs). ORMs are learned to evaluate the final outcomes of whole trajecto- ries, corresponding to the value R in Eq. (2). PRMs are learned to evaluate the intermediate rewards of each state- action pair, corresponding the values r (Sh, an) in Eq. (I) for all h E [H].
2.2. Outcome Supervision and Process Supervision
This paper focuses on two basic supervision paradigms in reinforcement learning: process supervision and outcome supervision. We analyze these approaches through the lens of statistical complexity rather than algorithmic implemen- tation details.
In this paper, we use ORMs and PRMs to refer specifically to different algorithmic approaches for learning reward models, rather than the underlying supervision paradigms discussed earlier, as learning ORMs or PRMs does not necessarily require the underlying data to be collected under the same supervision paradigm.
The distinction lies in the temporal resolution of available reward signals:
Process supervision provides step-wise rewards during trajectory collection. More precisely, the offline data has the form
2.3. State-Action Coverage and Trajectory Coverage
The coverage concentrability coefficient (Munos, 2003; Antos et al., 2008; Farahmand et al., 2010; Chen and Jiang. 2019; Jin et al., 2021; Xie and Jiang, 2021: Xie et al., 2021a; Bhardwaj et al., 2023) played a central role in the theory of offline (or, batch) reinforcement learning, and has recently gained growing attention online reinforcement learning through related concept of a coverability coefficient (Xie et al., 2022b; Liu et al., 2023; Amortila et al., 2024a;b).
referred to as a bounded
Dp = ((s1, T1, #2, d2, 72, ................................ 88 CH. TH)h.
(I)
where rh = r" (s),, (n)) denotes the ground truth re- ward value at step h. This setting is compelling com- pared to outcome supervision, especially for complex multi-step reasoning problems, as it provides more precise feedback that can pinpoint the location of sub- optimal actions and allows to correct for cases where the agent makes mistakes in the middle of the reason- ing path but reaches the correct final answer (Uesato et al., 2022; Lightman et al., 2023).
In this paper, we use coverage conditions to capture the statistical complexity of different supervision paradigms. To motivate the importance of coverage notions, consider the following approach for imputing the missing rewards in outcome supervision. Suppose we minimize the trajectory- level regression objective over a class of reward functions R (r S x A R},
Outcome supervision reveals only the cumulative re- wards for complete trajectories. The data for this set- ting has the form
Do = {(51, 41, 42, ... .8, 88, R)},
(2)
where R = Dth Σカ= 1= r* (sh; un) denotes the total reward along the trajectory (31, 01, sH, ax).
f arg min EII.REEDO (r(T) - R)²
(3)
where the outcome supervision data Do are collected by some reference policy Tofl. With the learned reward model F, we can now employ an offline RL method of our choice. However, we have a (standard in the literature) mismatch: while Σ F(sh, az)) - Σh r" r"*(p, 4z)] is small for trajectories collected by ooff. we care about the error [J(r) - J=(m)) for some policy a that differs from
We also consider preference learning, where the learner only has access to trajectory-level pairwise preferences, as an extension of outcome supervision. Our main results are applicable to both cases, and are discussed in Section 3. The problem of reinforcement learning from human preferences (e.g., Christiano et al., 2017)
3

---

Process vs. Outcome Supervision
Tolt, where (T) and Ję(T)) are defined in Section 2.1. A naive approach for capturing such change of trajectory measure is to use the trajectory concentrability coefficient,
In the following sections, we will present results using all- policy coverage conditions for simplicity, and defer the single-policy case to the appendix.
Ciraj(T,, (T, Toft) == sup dhoff (T)
(4)
3. Outcome and Process Supervision: Similar Statistical Guarantees
where the supremum is over all possible trajectories.
3.1. Learning Reward Model from Total Reward
This trajectory concentrability coefficient is usually consid- ered to be prohibitively large, and its limitation has been widely studied in the literature on off off-p evaluation (e.g., Liu et al., 2018; Xie et al., 2019; Nachum et al., 2019; Ue- hara et al., 2020). An alterative approach is to express upper bounds (if possible) in terms of the state-action concentra- bility coefficient, commonly used in offline policy learning literature (e.g., Munos, 2003; Antos al., 2008; Farahmand et al., 2010; Chen and Jiang, 2019) and defined as follows:
We present simple approach to estimate rewards in an outcome supervision dataset of the form Eq. (2) using least squares regression, assuming that the learner has access to a class of reward models R. This transformation allows the learner to use outcome supervision data with methods designed for process reward data, as detailed below. We have the following theorem for the least squares estimate of the rewards:
Theorem 1. Suppose the dataset Do is collected i.i.d. ac- cording to policy Toff in the MDP M = (S,A.P,r* H)) with the ground truth reward model r* E R. Then, with probability at least 1 - 6, for any policy и, the PRM reward model f computed by Eq. (3) satisfies
d=s (Sh, 01))
(TT, Toff) = max he(M]
sup sr, ES d (8h, ax)
(5)
The state-action concentrability coefficient is always smaller than the trajectory concentrability coefficient, and the dif- ference can be exponential. This is because d (s), as) ag- gregates over all trajectories that pass through (Sk, an), and thus
CSa Tort) log (RR/0)
[J*(T) J(T) S 3
[Dol
where Cza (T, Toft) is the state-action concentrability coeffi- cient defined in Eq. (5).
d= an))
EnronaaWEr de (T)
d= (T)
Endemaaeer dooer( (T) S sup door (T)
@Tor(ssh an)
The proof of Theorem I is deferred to Appendix B.2. Theo- rem 1 yields an approach for transforming any offline RL algorithm which takes trajectories with per-step reward into an offline RI. algorithm which takes trajectories with to- tal reward as input. More precisely, we split the outcome supervised data, use the first part to estimate the reward function via least squares, and then this estimate to impute the missing rewards the second part of the data. We summarize this basic transformation in the following algorithm.
for all h E [H] and (n) E S x A.
straightforward to see that using the state-action con- centrability coefficient is usually sufficient for the process supervision paradigm, the setting prevalent in the offline RL literature. The intuition is that process supervision allows us to achieve small estimation error at the state-action level, which only poses a state-action level change of measure during the subsequent policy learning step. Perhaps sur- prisingly, we show that state-action concentrability is also sufficient for the outcome supervision case.
Algorithm Offline Outcome-to- Process Transformation
Input: Offline dataset with total rewards Do : ag, R)), Reward model class R, Of- fline RL Algorithm Ω
Single-Policy and All-Policy Coverage. Another impor-
[(s1,a1...- .H.
tant concept in the offline RL literature is the distinction between single-policy and all-policy concentrability. Using the state-action concentrability coefficient as an example, single-policy concentrability refers to the coverage of a spe- cific target policy (such as the optimal policy r",, defined as Css (TT", ). In contrast, all all-policy concentrability consid- ers the coverage of all policies in a policy class II, defined as C.a (II, Toft)= := sup C=,(T, Toff).
2: Split Do into two datasets Db and Dÿ of equal size.
3: Compute f by solving Eq. (3) with dataset D' and the reward class R.
4: Construct dataset Dp = [($1,, (1,1,01,77 01, ri, .8 aH, TH) from Dy. where V(81, V(si,a1," ". , an, Rt) E Dg.
T = f(sh. ax),
vh E [H]
Single-policy versus all-policy coverage is one of the central questions in the offline RL literature. For more details, we refer the reader to Chen and Jiang (2019); Xie et al. (2021a); Jiang and Xie (2024), but this not the focus of this paper.
5: Call algorithm 2 with dataset Dp and output learned policy f.
Output: Learned policy म.
4

---

Process vs. Outcome Supervision
Corollary 2. Fix a policy set II which contains the op- timal policy x². Suppose the offline RL algorithm M al- ways outputs policy & E 11 with error at most Ealg, i.e., [(x)) - (() S Ealg, with probability at least 1 - 6. Then the policy output by Algorithm/ satisfies with probability
d1 and dg. and r(a1) r(,)(a)) 0, and policy π Unif((a1;a)) In the meantime, many classical offline RL algorithms, such as Fitted Q-Iteration (Antos et al., 2008; Munos and Szepesvári, 2008), the theoretical backbone of Deep Q-Network (DQN), require sample complexity that scales with C₂2 T //e/ for obtaining an s-optimal policy (Chen and Jiang, 2019; Xie and Jiang, 2020). Hence Corollary provides transformation with the same sample complexity in these works (up polynomial in horizon factors), when encountering outcome supervision reward data.
at least 1 26,
max J(T) (TT
Ca, Tott log((o)/// (R11/))
Eag + 11312.
iDol
As for the instance destance-dependent case (corresponding to the single-policy coverage discussed in Section 2.3), the lower bound result in Xie al. (2021b) shows that any algorithm requires at least Csa (T",, /s number of samples to out- put an e-optimal policy, which only depends the coverage of optimal policy x². Recent offline RL algorithms (Xie et al., 2021a; Cheng et al., 2022; Uehara and Sun, 2021; Bhardwaj et al., 2023) indeed reach that sample complexity in terms of the single-policy concentrability Csa (T", Toy). Our results presented in Appendix C match the upper bound of these offline RL algorithms for the process supervision case and also enjoy the same sample complexity depending the single-policy concentrability Csa (IT", Toft).
where C2 Toa) == sup CSa(T, ToR))
Notice that the bound in the above theorem suffers from all-policy concentrability, regardless of which algorithm 2 is used with the transformed data. This occurs because the transformation fixes the learned reward model, requiring us to account for the distribution shift between Toff and the data-dependent policy स which can be any policy in the policy class II. This is a common issue in classical offline RL without specific methods like pessimism, par- ticularly for the case of partial coverage. However, the concept of pessimism can also be applied to the outcome supervision setting in our paper, where we learn specific reward model for each policy, as commonly done in the (proces--superissin)) offline RL literature (e.g., Xie et al., 2022a; Cheng et al., 2022; Uehara and Sun, 2021; Bhardwaj et al., 2023). Following this approach, we can transform model-based offline RL algorithms that use pessimism (Xie et al., 2022a; Bhardwaj et al., 2023) into algorithms that em- ploy outcome supervision data. The sample complexity of these transformed algorithms scales with the single-policy concentrability (sa(m", Toff), which depends only the optimal policy n-" We defer further details to Appendix C.
3.2. Change of Trajectory Measure
The proof of Theorem I relies on the following key change of trajectory measure lemma, which states that changing the measure of trajectory returns can be done at the price of state- action concentrability, up to logarithmic and polynomial- in-horizon factors. This lemma will be used for bounding the error between the true reward model r" and the learned reward model F. Thus, by setting f = r" - P, we only need to show that the expectation of the absolute value of ((T) = E(snee)ur [(h, an) is small for T when controlling under Toff-
Statistical Efficiency. We now argue that there is no sig- nificant statistical edge for process supervision paradigm compared the outcome supervision paradigm in the of- fline setting. The latter corresponds to standard offline RL problems (Levine et al., 2020; Jiang and Xie, 2024), for which a rich body of work exists analyzing sample com- plexity. Our "equivalence" argument primarily focus on coverage conditions, since different coverage notions (e.g., state-action-level vs. trajectory-level) can lead exponen- tial differences, as discussed in Section 2.3. While our results establish equivalence with respect to coverage condi- tions, we ack acknowledge they may still be subject to polyno- mial factors of H; removing such factors is an avenue for further research.
Lemma 3. (Change of Trajectory Measure Lemma) For
MDP M = (S,A,T,J f, H) with any function SS x A +
[-1, 1], for any two policies π. and Teft we have
E [[TT) By [[ S (T,
where Csa(T, Toft) is defined in Eq. (5). Additionally, the following holds without the extraneous log factors:
ErT [lf(+)) S VI13Csa (TT, Toft) Erowod (T)]].
This lemma reveals perhaps surprising insight: when the squared sum of some state-action value functions (n f(sh, )² is small under the off-policy tra- jectory distribution 7 ~ Toff, we only need to account for sute-action-lers distribution shifts between Ro and i to bound the same squared sum under 7 ~ a. This holds true
If we consider the worst-case scenario, it is easy to see that any algorithm which outputs an c-optimal policy requires at least sup, Csa (T, Toa) number of samples. To see this, we may consider the two-armed bandit with action
5

---

Process vs. Outcome Supervision
even though controlling such trajectory sums theoretically cannot prevent cases where individual terms have equal and large magnitude but opposite signs (i.e., where la| = [6] > 0 but a a-+b bb = 0). We provide proof sketch of Lemma 3 in the following. The detailed proof is deferred to Appendix B.1.
than for entire trajectories: P. Pr (bad)
S Css (T, Foft)
P Promon (bad).
Hence, with high probability, π visits only "good" states throughout its trajectory, ensuring that each layer h "locks in" a small partial sum (as both its prefix and suffix have low variance). When we stitch these layers from h = 1 to h = H. the entire sum [(() is guaranteed to have small absolute values.
3.3. Proof Sketch of Lemma 3
In this section, we outline the key insights behind the proof of Lemma 3. The central observation is that controlling the trajectory-level variance of f under a reference policy ooff implies an automatic control of variance on prefixes and suffixes over the entire trajectory, with only polynomial overhead in the horizon length H. This seemingly simple fact leads to perhaps surprisingly strong guarantees.
3.4. Extension to Preference- Reinforcement Learning
In the previous section, we studied the statistical complexity of outcome supervision under the data format of Eq. (2), where the outcome reward is provided at the end of each trajectory. Preference-basee reinforcement learning (e.g.. Knox and Stone, 2008; Akrour et al., 2012; Wirth et al., 2017) represents another well-established paradigm that extends outcome supervision and is commonly employed for learning from human preferences (e.g.. Griffith et al., 2013; Christiano et al., 2017; Stiennon et al., 2020; Ouyang et al., 2022).
Insight I: Trajectory-level bound controls the second moment on prefixes and suffixes. At first glance, small value [f]] over the entire trajectory T does not obviously guarantee that the value of f on either (i) every prefix Tish or (ii) every suffix 1:H1 is small. In principle, large posi- tive and large negative portions of single trajectory could "cancel" each other out, resulting in small overall sum [f(r)] = (frs) + [(++1:=))-
Recent work on implicit reward modeling through single- step contrastive learning approaches (DPO; Rafailov et al., 2023) aims to eliminate the need for explicit reward model- ing. While extensive prior work (e.g.. Zhan et al., 2023; Liu et al., 2024; Song et al., 2024; Zhang et al., 2024) has focused on the sample complexity of these implicit reward modeling approaches, most existing bounds rely on trajectory-Ievel change of measure. These results are also considered to depend on the trajectory concentrability under naive simplifications, which can grow exponentially with the horizon length (see detailed discussion in Section 2.3 and Section 3.2 of Xie et al. 2024).
Crucially, however, thanks to the Markov property, we can argue that if f has small second moment (under Toft) and if state 8n is visited sufficiently often by Toff. J' cannot have high variance on the prefix (leading up to s;) and suffix (fol- lowing s,). Indeed, if the value of f on the prefix (or suflix) has large variance, then conditioned on passing through $a that visited sufficiently often by Toff, the value of f on the entire trajectory also has large variance, which directly implies the large variance (hence, large second moment) of f(r). Hence, even though the trajectory-level bound looks coarse, it forces each state 8) to have relatively stable partial sums in both the prefix and suffix directions under Toff-
In this section, we extend our main results to the preference- based reinforcement learning setting. As a direct application of our Change of Trajectory Measure Lemma (Lemma 3), we first provide a sample complexity bound of preference based RL which only scales with state-action concentrability instead of trajectory concentrability, a result applicable to standard explicit reward modeling approaches as well as implicit reward modeling approaches (i.e., DPO).
Insight II: Layer-by-layer "locking" with only state- action coverage. Next, we want to argue that if all states in trajectory satisfy the above low-variance property (we call such states "good" states), then the reward of the entire trajectory cannot have large absolute value. We call this the "locking in" property here for brevity. In the following, we argue that "locking in" happens with high probability, even under policy π.
In preference- based RL, we suppose that for any trajectory
T, the total reward along satisfies r(7) E [0. Vmux)- To form the dataset D of preferences, the learner collects two reward-free trajectories т = (81: a1 82, a2. ,H an) and 7' = af $/2, dz. S' d'y) according to policy Tref, and receives the information about the order (T+, r-) of T, 7', based on the preference y ~ P(r > r'). We adopt
According to the earlier argument, "bad" states (opposite of "good" states) cannot have large visitation probability under Toft- Then, by the definition of C.a (TT, For), which upper bounds the probability ratio between л and Toff at any state, we conclude that such bad states also have low probability under म, up to a factor of Ca,(T, R. Thus, we avoid exponential blow-up over the horizon because we only "pay" for distribution shift at each individual (s, a), rather
OOur formal proof also needs to consider the "good" state- action-state tuples, which are similar to "good" states but involve the (sh, ahe 8h+1) tuple. We omit the details here for brevity, and readers can refer to the full proof in Appendix B.I.
6

---

Process vs. Outcome Supervision
the Bradley-Terry model (Bradley and Terry, 1952):
Therefore, as acquire enough samples, J(x') J converges
with high probability, implying that म is a near-optimal policy. This convergence requires the same condition of bounded state-action concentrability as in Corollary
exp(r(r)) P(T - r') exp(r(r)) + exp(r(r"))
The labeled preference dataset consists of ordered sam- ples (T+, T-), where both trajectories are collected accord- ing to policy Tref and labeled according to the Bradley- Terry model Eq. (6).
3.4.2. IMPROVED ANALYSIS OF DPO ALGORITHM We now extend our main results the implicit reward mod- eling setting and analyze the sample complexity of the DPO algorithm (Rafailov et al., 2023). DPO is popular implicit reward algorithm that converts the two-step process of re- ward modeling and policy optimization into single-step contrastive learning problem. DPO is commonly used in the token-level setup of L.MMs, where actions (tokens) are directly appended to states (contexts) (Rafailov et al., 2023; 2024). In this case, the state-action concentrability coeffi- cient essentially reduces trajectory-level concentrability, as the last state is contains the trajectory. However, recent work indicates that DPO-style algorithms are applicable beyond the token-level setup, e.g., in environments with deterministic transition dynamics but still Markovian states, e.g., in robotics (Hejna et al., 2023; Xie et al., 2024). In these settings, our bounds with only state-action concentrability can be substantially tighter than existing trajectory-level ones.
3.4.1. IMPROVED ANALYSIS OF PREFERENCE-BANE RL WITH EXPLICIT REWARD MODELING
We first provide the analysis for the case where an explicit reward modeling procedure is used for preference-basee RI.. Suppose the learner given the preference-basee dataset Preef and reward class R, where for every reward model E RR. and any trajectory r(r) E [0, V- In the fol- lowing result, an analogue of Theorem 1, we transform the preference- based dataset into the reward model via maxi- mum likelihood rather than the method of least squares. Theorem 4. Suppose Prref [(T+,TTT) T-)3 contains i.i.d. pairs of sequences collected according to Teet and ordered according Eq. (6) with r* RR. Let
F arg min
Σ loga(r(T4)- -((())))(r)))) r(T-))
rER
(TtsT-JEDpss
be the maximum likelihood estimate. With probability at least 1 - for any two policies n, n² E 11, it holds that
Following Xie et al. (2024), we assume deterministic ground-truth transition dynamics and consider the following KL-regularized objective (Xiong et al., 2023; Ye et al., 2024; Xie et al., 2024): for some positive number |3,
E EN [Ir (r) -()) +(7')l
$ H3/2 Viaxee 2mma
JT(TT) = J,(T) -D(r,(((T)) || Tree(T))
(Cs((T, Trer) V Csa(T', (re() log (18
((T)
(8)
= EE
(((T) Blog Teee
The policy nz which maximizes (T(T) in Eq. (8) satisfies Tā(T)) xx (Ter(T) exp (T)/B) for any trajectory It is easy to verify that z3 is a Markov policy. We assume the learner has access aims to find policy से that is nearly optimal with respect to the policy class 11, i.e.
The proof of Theorem 4 is deferred to Appendix B.3. Notice that with Eq. (7), if we could obtain से as the optimal policy under reward model F (otherwise we can just pay for the sub-optimality as in Corollary 2), then with high probability â is near-optimal policy. To see this, we choose म arg max, Jz( and n' = . arg max, J(F). then with probability at least 1- - 5,
Markov policy class IT 8-A, and
max
JT(T) Jp( Se. HEll
J(m²) J(7) S J(((²) ( - JT(TT) + (+( E' 10" (T') (T) - -((r'+
The DPO algorithm (Rafailov et al., 2023) takes the dataset
D = {(++, T-)} input, and outputs the policy क II hooi which maximizes the log likelihood, i.c., â is obtained by solving
S En ||r (T') - (T( - -f(r') f(7)
& 33/21 V 2V
mmxx
arg min
Σ (T.
log [ Blog T(T+) mTa((T))
B log
(T-
CCa (Tt, Tref) V (Ta ; Teas) log (188
sen
(
IED
[D]
(9)
In the following, we provide a refined analysis of the sample complexity of this algorithm. We first make the following assumptions.
Csa (II, off log (og([I//)) /0)
< H V e
D
7

---

Process vs. Outcome Supervision
Assumption 1 (Policy Realizability). The optimal policy is in the policy class II, i.e., "3 IT.
Although these methods have demonstrated empirical promise, their theoretical properties remain relatively unex- plored. Establishing a theoretical foundation could reveal the assumptions and conditions under which these methods are effective and enable principled comparisons to alter- native reward modeling approaches. In what follows, we present (to our knowledge) the first theoretical study of advantage-based reward learning with online rollouts. We show that the advantage function of any policy can serve as valid process-based reward model, recovering the same optimal policy as the original environment. By contrast, we also prove a lower bound indicating that simply using the Q-function can fail: in certain cases, the Q-function-bane -based reward model produces suboptimal or undesired policies.
Policy realizability is a minimal assumption for sample- efficient reinforcement learning and is necessary for estab- lishing many standard results (Agarwal et al., 2019; Latti- more and Szepesvári, 2020; Foster and Rakhlin, 2023).
In addition, we make the following assumptions of bounded trajectory concentrability.
Assumption 2. For any policy E II and trajectory T, Vmax
log
This assumption is commonly used in the literature on im- plicit reward modeling approaches for preference-basee reinforcement learning (e.g., Rosset et al., 2024; Xie et al., 2024). The intuition behind this assumption is that we treat implicit value function, so that this as- sumption essentially plays the same role as bounded value
4.1. Algorithm and Upper Bounds For MDP is M = =S. P.r, H), suppose the transition model P is known to the learner, but the reward model unknown. For any given policy μ4, we define the advantage function A : S x A + R as
log (e
xx()
functions in the analysis.
If the above assumptions hold, we have the following upper bound on the sample complexity of the DPO algorithm in terms of the state-action concentrability.
A" = Q% a) V7 (s), Ah E [H), s Sh a A, (10)
where 0% and V/2 denote the Q-function and value func- tion of policy μc
Theorem 5. Suppose Assumptions and hold, with prob- ability at least - 8, the output ăt of the DPO algorithm in
Eq. (9) satisfies
Setlur al. (2024) find an approximation f to A" and then invoke policy gradient algorithm for the MDP with tran- sition model P and reward function F. yielding policy î.. We provide a theoretical guarantee for this approach by showing that the performance gap of π to the optimal policy can be upper bounded in terms of the error stat of approximating the advantage function and the error Ealg of optimizing the policy. Before stating the result, we define the concentrability coefficient with respect to distribution v/
[T(TT)) - (T)
suPren Csa Roft) log( (11
< H3/2V e 2iaax.
[D]
The proof of Theorem 5 is deferred to Appendix B.3. Note that, the exponential dependence on the reward range Vmax is a fundamental characteristic of the Bradley-Tenee model, not an artifact of our analysis. Indeed, this exponential dependence appears consistently across the thcoretical lit- erature on RLHF (e.g.. Zhu et al., 2023; Zhan et al., 2023; Rosset et al., 2024: Xie al., 2024; Das et al., 2024).
d" a)
Csa (V) sup sup sES,aEAA
(1I)
where the outer supremum is over all possible policies. Theorem 6. Suppose there exists some policy a and distri- bution E A(S x A) such that
4. Advantage Function Learning with Rollouts
In this section, we analyze common empirical strategy for converting outcome-superrvised data into process supervi- sion by leveraging online rollouts. The central observation that, given access to an environment that returns final out- comes, one can initiate rollouts from individual state-action pairs and use the resulting outcomes to approximate their "quality." Multiple works have adopted variations of this idea, relying on Q-functions (e.g., Wang et al., 2024), advan- tage functions (e.g., Setlur et al., 2024), or other specialized value estimators (e.g., Luo et al., 2024).
E(s,ay~ [F(ss - (s, S Estat
(12)
If policy it satisfies
maxx)(M) J=((T) S Ealg:
(13)
n
then it also satisfies
max [(x) - J(T) 2H22H/ (Ca(V)) Estat + Ealg-
In fact, log (T)) corresponds to a more complex combi- nation of value functions and rewards. We refer readers to Watson al. (2023); Rafailov al. (2024); Xie al. (2024) for further details.
The proof of Theorem 6 is deferred to Appendix D. In- tuitively. the proof follows from the performance differ- ence lemma (Kakade and Langford, 2002), which states
8

---

Process vs. Outcome Supervision
that for any policies and μ. ((x) - J() H (x) [A* (sh, [n]]. This implies that maximizing AA (treating A the reward function) is equivalent to maximizing J, since they differ only by the constant term J(... Therefore, both optimization problems yield the same optimal policy.
While our transformation scheme works for most of the offline algorithms, the theoretical guarantees require that the outcome supervision data are collected offline. How to construct similar transformation for online data or online algorithms is left for future work.
A Acknowledgements
There are several ways of obtaining an estimate F of the ad- vantage function A that satisfies Eq. (12). One commonly used approach is Monte-Carlo sampling, for instance as in Setlur et al. (2024). In detail, this approach first collects a dataset D of data (s, a, A), where (s, a) E S x A and Á is calculated via rollout from (s, a) under policy Jr, serving as an approximation to the advantage function of policy j at (s, a). Next, we fit a reward function F in a reward class to the dataset D. Then, as long as the reward class realizes the ground truth advantage function A", the reward function f satisfies Eq. (12) with high probability.
ZJ and AR acknowledge support of the Simons Founda- tion and the NSF through awards DMS-203188 and PHY- 2019786, as well from the ARO through award W911NF 21-1-0328.
Impact Statement
This work contributes to advancing the field of Machine Learning through theoretical analysis and insights. While our research focuses on foundational understanding rather than direct applications, we acknowledge that theoretical advancements in machine learning can have broad societal implications. However, given the theoretical nature of this work, we believe these potential impacts do not warrant specific discussion in this context.
4.2. Lower Bound Failure of Using Q-Functions Theorem 6 indicates that the MDP with reward function set to be the advantage function of any policy μ has the same best policy as the original MDPs. One may wonder whether the same holds for the Q-function as well. In this section, we disprove this by providing a hard MDP with best policy n². and a policy μl so that the best policy of the MDP with reward function Q" is not x².
References
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32:96. 2019.
Theorem 7. There exists an MDP M (S,A,P,r, and a policy μ E AS, such that
1
Riad Akrour, Marc Schoenauer, and Michèle Sebag. April: Active preference learning-base based reinforcement learn- ing. In Muchine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II 23, pages 1 116-131. Springer, 2012.
max J. -.
3'
for = =arg max, Jom(T) Here Q S x A - R is the Q-function of MDP M.
The proof of Theorem 7 is deferred to Appendix D.
Philip Amortila, Dylan Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie. Harnessing density ratios for online reinforcement learning, arXiv preprint arXiv:2401.0968) 2024a.
Theorem 7 indicates that the widely used approach in large language model training, whereby an approximate Q- function is learned in place of the reward model, is theoreti- cally incorrect and possibly outputs undesired policies. In contrast, using the advantage function as the reward model theoretically justified.
Philip Amortila, Dylan J Foster, and Akshay Krishna- murthy. Scalable online exploration via coverability. arXiv preprint urXiv:2403.0657/ 2024b.
5. Conclusion
András Antos, Csaba Szepesvári, and Rémi Munos. Learn- ing near-optimal policies with aallman-residun minimiza- tion based fitted policy iteration and a single sample path.
In this paper, we present a way of transforming data in the setting of outcome supervision into the data in the setting of process supervision. This transformation enables us to design offline algorithms in the outcome supervision model from the large pool of algorithms that use process super- vision. This transformation extends to preference-basee algorithms such as DPO. Beyond this transformation, we also provide theoretical guarantees for algorithms using an approximate advantage function as the reward function.
Machine Learning, 71:89-129, 2008
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.0 05862, 2022.

---

Process vs. Outcome Supervision
Mohak Bhardwaj, Tengyang Xie, Byron Boots, Nan Jiang, and Ching-An Cheng. Adversarial model for offline re- inforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Rein- forcement learning with trajectory feedback. In Proceed- ings of the AAAI conference artificial intelligence, volume 35, pages 7288-7295, 2021.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-35,, 1952.
Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. Advances in neural information process- ing systems, 23, 2010.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprini 1rXX:::810./28000 2018.
Dylan J Foster and Alexander Rakhlin. Foundations of reinforcement learning and interactive decision making. arXiv preprint arXiv:2312. 2023.
Asaf Cassel, Haipeng Luo, Aviv Rosenberg. and Dmitry Sotnikov. Near-optimal regret in linear mdps with aggre- gate bandit feedback. arXiv preprint arXiv:2405.0700 076677, 2024.
Dylan J Foster, Sham Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making, arXiv preprint arXiv:21 2021.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learn- ing with pece-per-episode feedback. Advances in Neural Information Processing Systems, 34:3401-3412, 2021.
Shane Griffith, Kaushik Subramanian, Jonathan Scholz, Charles L Isbell, and Andrea L Thomaz. Policy shaping: Integrating human feedback with reinforcement learning. Advances neural information processing systems, 26, 2013.
Jinglin Chen and Nan Jiang. Information-theoretic con- siderations in batch reinforcement learning. In Interna- tional Conference on Machine Learning, pages 1042- 1051. PMLR, 2019.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseck-rl: Incentivizing reason- ing capability in llms via reinforcement learning. arXiv preprint 25X1::2501.1244: 2025.
Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation. In International Conference Machine Learning, pages 3773-3793, PMLR, 2022.
Abhishek Gupta, Aldo Pacchiano, Yuexiang Zhai Sham Kakade, and Sergey Levine. Unpacking reward shap- ing: Understanding the benefits of reward engineering sample complexity. Advances in Neural Information Processing Systems, 35: 35:15281 2022.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning, pages 3852-3878. PMLR, 2022.
Joey Hejna, Rafael Rafailov, Harshit Sikchi, Chelsea Finn, Scott Niekum, W Bradley Knox, and Dorsa Sadigh. Con- trastive prefence learning: Learning from human feed- back without rl. arXiv preprint arXiv:2310. 13639,,,,,, 2023,
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30. 2017.
Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Cameyy, al. Openai ol system card. arXiv preprint arXiv:2412.16720 2024.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 10. 10.14688 2021.
Nan Jiang and Tengyang Xie. Offline reinforcement learn- ing in large state spaces: Algorithms and guarantees. Statistical Science, 2024.
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Provably sample efficient rlhf via active preference optimization. arXiv preprint arXiv:2402. 105500 2024.
Ying Jin, Zhuoran Yang. and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Con- ference on Machine Learning, pages 5084-5096 PMLR, 2021.
Kefan Dong and Tengyu Ma. First steps toward under- standing the extrapolation of nonlinear models to unseen domains. arXiv preprint arXiv:2211.117/1 2022.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, volume 2, pages 267-274, 2002.
10

---

Process vs. Outcome Supervision
W Bradley Knox and Peter Stone. Tamer: Training an agent manually via evaluative reinforcement. In 2008 7th IEEF international conference development and learning, pages 292-297. IEEE, 2008.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in neural information processing systems, 32, 2019.
Nathan Lambert, Valentina Pyatkin, Jacob Morrison, LJ Mi- randa, Bill Yuchen Lin, Khyathi Chandu, Nouha Dziri, Sachin Kumar, Tom Zick, Yejin Choi, et al. Rewardbench: Evaluating reward models for language modeling. arXiv preprint arXiv:2403.13777 2024.
Gergely Neu and Gábor Bartók. An efficient algorithm for learning with semi bandit feedback. In International Conference on Algorithmic Learning Theory, pages 234- 248. Springer, 2013.
Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and ap- plication to reward shaping. In International Conference on Machine Learning, volume 99, pages 278-287, 1999.
Tal Lancewicki and Yishay Mansour. Near-optimal regret using policy optimization in online mdps with aggregate bandit feedback. arXiv preprint arXiv:2502.04004, 2025.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Car- roll Wainwright, Pamela Mishkin, Chong Zhang, Sand- hini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feed- back. Advances in neural information processing systems, 35:27730-27744, 2022.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04835 2021.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Ed- wards, Bowen Baker, Teddy Lee, Jan Leike, John Schul- man, llya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint arXiv:2305.20033 200500 2023.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference on machine learn- ing, pages 2778-2787 PMLR, 2017.
Fanghui Liu, Luca Viano, and Volkan Cevher. What can on-
line reinforcement learning with function approximation benefit from general coverage conditions? In Interna- tional Conference on Machine Learning, pages 22063- 22091. PMLR, 2023.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christo- pher D Manning, Stefano Ermon, and Chelsea Finn. Di- rect preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36, 2023.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. Advances in neural information processing systems, 31, 2018.
Rafael Rafailov, Joey Hejna, Ryan Park, and Chelsea Finn. From to q": Your language model is secretly a q- function. arXiv preprint wrXiv:2404.12355 2024.
Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang, Jose Blanchet, and Zhaoran Wang. Provably mitigating overoptimization in rlhf: Your sft loss is implicitly adversarial regularizer. arXiv preprint arXiv:2405. 164466, 2024.
Corby Rosset, Ching-An Cheng, Arindam Mitra, Michael Santacroce, Ahmed Awadallah, and Tengyang Xie. Di- rect nash optimization: Teaching language models to self-improve with general preferences. arXiv preprint arXiv:2404.03715 2024.
Liangchen Luo, Yinxiao Liu, Rosanne Liu, Samrat Phatale, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, Jiao Sun, et al. Improve mathematical reasoning in lan- guage models by automated process supervision. arXiv preprint ar XXiv:2406.06592. 2024.
Amrith Setlur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Eisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar. Rewarding progress: Scaling automated process verifiers for 11m reasoning. arXiv preprint arXiv:2410.088145 2024.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560-567. Citeseer, 2003.
David Silver, Julian Schrittwieser, Karen Simonyan, Joannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Master- ing the game of go without human knowledge. nature, 550(7676):354-559 2017.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008

---

Process vs. Outcome Supervision
David Silver, Satinder Singh, Doina Precup, and Richard S Sutton. Reward is enough. Artificial Intelligence, 299: 103535, 2021.
Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical compar- ison. In Conference on Uncertainty in Artificial Intelli- gence, pages 550-559. PMLR, 2020.
Yuda Song, Gokul Swamy, Aarti Singh, Drew Bagnell, and Wen Sun. The importance of online data: Understanding preference fine-tuning via coverage. In The Thirth-eigtth Annual Conference on Neural Information Processing Systems, 2024.
Tengyang Xie and Nan Jiang. Batch value-function approx- imation with only realizability. In International Confer- ence on Machine Learning, pages 1 11404-11413. PMLR, 2021.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with hu- man feedback. Advances in Neural Information Process- ing Systems, 33:3008-300 2020.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in neural information processing systems, 32, 2019.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Belliman-consiseent pessimism for offline reinforcement learning. Advances in neural infor- mation processing systems, 34:6683-6694 2021a.
Alexander Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Keeping your distance: Solving sparse reward tasks using self-balancing shaped rewards. Ad- vances in Neural Information Processing Systems, 32, 2019.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34:27395- 2021b.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint urXiv:2107.062266 2021.
Masatoshi Uchara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off- aff-po evaluation. In International Conference Machine Learning, pages 9659-9668. PMLR, 2020.
Tengyang Xie, Mohak Bhardwaj, Nan Jiang, and Ching-An Cheng. Armor: A model-based framework for improv- ing arbitrary baseline policies with offline data. arXiv preprint arXiv:2211.0453 2022a.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geof- frey Irving, and Irina Higgins. Solving math word prob- lems with pnocess-and outcome-based feedback. arXiv preprint ar X1v:22/11.142 14275, 2022.
Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online rein- forcement learning. arXiv preprint urXiv:2210.04157 2022b.
Tengyang Xie, Dylan Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit af-approximation for sample-efficient rlhf. arXiv preprint arXiv:2405.21046 2024.
Peiyi Wang, Lei Li, Zhihong Shao, Runxin Xu, Damai Dai, Yifei Li. Deli Chen, Yu Wu, and Zhifang Sui. Math- shepherd: Verify and reinforce I1ms step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 9426-9439, 2024.
Wei Xiong, Hanze Dong, Chenlu Ye, Han Zhong, Nan Jiang, and Tong Zhang. Gibbs sampling from human feedback: A provable kl-constrained framework for rlhf. arXiv preprint arXiv:2312.11456 2023.
Joe Watson, Sandy Huang, and Nicolas Heess. Coherent soft imitation learning. Advances in Neural Information Processing Systems, 36, 2023.
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314 2024.
Christian Wirth, Riad Akrour, Gerhard Neumann, and Jo- hannes Fümkranz. A survey of meference-based rein- forcement learning methods. Journal of Machine Learn- ing Research, 18(136):1-46, 2017.
Lifan Yuan, Wendi Li, Huayu Chen, Ganqu Cui, Ning Ding, Kaiyan Zhang, Bowen Zhou, Zhiyuan Liu, and Hao Peng. Free process rewards without process labels. arXiv preprint arXiv:2412.0198) 2024.
Runzhe Wu and Wen Sun. Making rl with preference-bare based feedback efficient via randomization. arXiv preprint arXiv:2310. 14554, 2023.
12

---

Process vs. Outcome Supervision
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason D Lee, and Wen Sun. Provable offiine preference-based reinforcement learning, arXiv preprint arXiv:2305.14816, 2023.
Shenao Zhang, Donghan Yu, Hiteshi Sharma, Han Zhong, Zhihan Liu, Ziyi Yang. Shuohang Wang, Hany Hassan, and Zhaoran Wang. Self-exploring language models: Active preference elicitation for online alignment. arXiv preprint arXiv:2405. 19332, 2024.
Han Zhong, Guhao Feng, Wei Xiong, Xinle Cheng, Li Zhao, Di He, Jiang Bian, and Liwei Wang. Dpo meets ppo: Reinforced token optimization for rlhf. arXiv preprint arXiv:2404. 18922, 2024.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pair- wise or k-wise comparisons. In International Conference on Machine Learning, pages 43037-43067. PMLR, 2023.
13

---

Process vs. Outcome Supervision
Appendix
A. Related Work
Process vs. Outcome Supervision. Our work motivated by the empirical effectiveness of process supervision over outcome supervision, particularly in language model reasoning tasks (Cobbe al., 2021; Uesato al., 2022: Lightman et al., 2023). To address the challenges of cost and scalability in obtaining (Wang et al., 2024; Luo et al., 2024; Setlur et al., 2024) have developed automated methods to generate process supervision from outcome-based signals, leveraging Q-functions and advantage functions under specific policies. When data is provided in the form of preferences, outcome supervision is sometimes conducted with implicit rewards, as seen in works such as Direct Preference Optimization (Rafailov et al., 2023; Lambert et al., 2024; Zhong et al., 2024; Yuan et al., 2024).
process labels, recent approaches
RL with Trajectory Feedback. A closely related line of theoretical work reinforcement learning with trajectory feedback or aggregate bandit feedback (or, bandit and semi-bandit feedback) (Neu and Bartók, 2013; Efroni al., 2021; Chatterji et al., 2021; Chen al., 2022; Cassel et al., 2024; Lancewicki and Mansour, 2025), where the learner only receives trajectory-level feedback at the end of each episode. This line of work also includes preference-based RL (Pacchiano et al., 2021; Zhu et al., 2023; Wu and Sun, 2023; Zhan et al., 2023), which operates on trajectory-level pair preferences. While most existing works in this area focus on online exploration settings, our paper investigates offline learning and analyzes the statistical relationship between process (step-level) and outcome (trajectory-leve) feedback.
Offline Reinforcement Learning. Our work is most closely related to offline (batch) reinforcement learning in the classical reinforcement learning literature. The paradigm of reinforcement learning with process- supervisd data is essentially an offline RL problem, where rich body of existing theoretical results (e.g., Munos, 2003; Antos al., 2008; Farahmand et al., 2010; Chen and Jiang, 2019; Xie and Jiang, 2020; Jin et al., 2021; Xie and Jiang, 2021; Xie et al., 2021a; la; Uchara and Sun, 2021; Cheng et al., 2022; Xie et al., 2022a; Bhardwaj et al., 2023) can be applied to our paper, either directly for the process supervision case, or serving as subroutines in our Algorithm 1 for the outcome supervision case. Within these results, Chen and Jiang (2019); Xie and Jiang (2020) develop model-free algorithms under all-policy coverage conditions, while Xie and Jiang (2021) proposes model-free approach requiring only realizability assumptions but with stronger coverage requirements. Xie al. (2021a); Cheng al. (2022) investigate model-free offline RL under partial coverage settings, and Uehara and Sun (2021); Xie et al. (2022a); Bhardwaj et al. (2023) address model-based offline RL with partial coverage.
Off-Policy Evaluation. Our work also connects to the rich literature off-policy evaluation (OPE) in reinforcement learning. A central challenge in OPE is the change of measure problem, where extensive research (Liu et al., 2018; Xie et al., 2019; Nachum et al., 2019; Uehara et al., 2020) has investigated the significant distinction between state-action coverage and trajectory coverage conditions. These findings highlight the significance of our main results, particularly our change of trajectory measure lemma.
Reward Shaping and Internal Rewards. related but distinct line of research focuses on augmenting sparse reward functions to improve learning efficiency. Reward shaping techniques have been extensively employed as a method for providing denser learning signals while preserving optimal policies (e.g.. Ng et al., 1999; Trott et al., 2019; Gupta et al., 2022). Similarly, intrinsic rewards based on prediction errors of environment dynamics (Pathak et al., 2017) or random networks (Burda et al., 2018) have been proposed to tackle sparse reward settings. However, these approaches differ fundamentally from our work in their objectives- - while reward shaping and intrinsic rewards aim to improve exploration in online RL by modifying the reward landscape, our analysis focuses on the statistical properties of learning in the offline setting where the data distribution is fixed.
B. Missing Proofs in Section
B.1. Proof of Change of Trajectory Measure Lemma
Proof of Lemma 3. In the following proof, for any trajectory (s1, a1, 82, 02, SH. OH) and 1 S u uSSS H, we use Twa to denote the partial trajectory (8n, tue Sut1 (utt1, ,8,, a.). We use s(Tw:e) == Σhev [sh, an) to denote the cumulative reward in this segment. Without loss of generality we assume for any trajectory T. f(T) E [-,, Since the state space of the MDP is layered, we write {sp E T for Sn E Sr to denote the event that 8n is the time-h element of the trajectory F. We let
(nn) P Towtor [[((T)] 2 r7]
14

---

Process vs. Outcome Supervision
for every yj 0. For every real number E IR and 1/. O, we define the following sets:
(h) = E ES Promoa (Ir ((T-((T)))))))) Sn 8h ET) 2 1 21-pj. 1)
and (r, = {sn E Sh Prweaae (r- f(T1sh-1) S ET) 2 1 PJ
Intuitively, (r, p) denotes subset of states in S₁, where, conditionally arriving at that state under policy Roff with probability least - p, the total reward collected in the first (h - 1) steps is 17-looe to r. Similarly, S 7) p) denotes subset of states in Sn where, conditionally on arriving at that state under policy Toff, the probability that the total reward collected in the last (H h + steps is 17-close is at least p.
We further define sets
() p) Uren Sr, (t, = Ur.
We can now upper bound the occupancy measure of those states outside the set (n) St p). This property is summarized in the following claim:
Claim 1. We have the following upper bounds on the occupancy measure outside S ().))) and (n,
Prostett (T of (m.P)) & L(n) and P Primar (T of () -
L(n) p
(14)
Proof. We only prove the first inequality, as the proof of the second inequality is similar. Notice that for any state 8h E Sr (n.P). according to the definition of S p) we have for any E TR,
P PINNTIIT (Ir - f(Tca)) s 7 8n TT) < <1-p.
According to the Markov property, when sampling T Toff. Tish-1 1L Th. conditioned on which implies
( sn ET)
PrNNTI
ETTaTat Pronoct [I((TaN)) - (-S(Tin-))) Sn Th ET] 8n ET S p.
Hence we have
(T.))) P. which implies the first inequality of Eq. (14). The second inequality of Eq. (14) follows similarly. Next, for every real number R and 7) > O, define the set
I(1) Pootan [lf(T)) 2 n| P P
(TN (T &
(T = {sh E Sn P PT- (1- f( 1) )1 S 77 and + f(T..))))
Sn S 8n E 2 21 21- P).
This set denotes subset of states in S₁, where conditioned on arriving at that state under policy Toff the probability that the first (h- 1) steps' total reward is y--close to r and also the last (!1 - h + 1) steps" total reward is r--cose to -r is less than We further define the set
Sx(n.p) Ur Sn (r. n.p),
Then we have the following claim, which shows that the occupancy measure of states outside Sj, (77, p) is also upper bounded:
Claim 2.
We have the following upper bounds on the occupancy measure outside Sn (1.
P P ST & Sn(n p)) < L(2n/3) +
4L(n/3)
(15)
p
15

---

Process vs. Outcome Supervision
Proof. For state 8/ (5,()()))))) but on (1/3,, S there exists some rt (5h) E IR and (+ E R
such that
P PrINTAIe (1F(5))+ -(rss--) - 3 sh E ET)
p and P PriNTTIr (15(s)) -((m))()))))))) - 1
Sh E 2 p
2
By union bound we have that for any such S/+
P Printaer (Ir((s)) - f( - 3
and |r* - [(TNAt)) 1 3 sn E 2 pp
If for some sn (h..p)) we have (sh) (sn)l - 4n then by letting (( we obtain
(r- (I- f(T:h---- 1 and + f(Thh(()ll S 17 sn ET)
P Pritei
2 PINNTI (Ir((s) - f(T s and (st - [(TaA))) ET)
21 -1
This contradiets the definition of Sn (,,((()))) p). Hence for any 8h E (Sh (6133 always have (sA) rl (sn))
ig 3 which implies that
[((T)
27 2
(Ir((s)) - (()
! and (sx) - f(T(H))) S 7
PriNTotf
8h
E
2 PoNTTtt
3h E
3
3
2 1 -1-p.
Further notice that
L(2n/3) ProNTa (I[(T)) 2n/3)
2 P P (T n& c cc5.:5kk..)nnn100/////////233.10 (1 p)-
Hence we obtain
I(2n/3) 1-p
P P (T C (tsss:/c.ccknnnnls/////////////s
Additionally, according to our previous claim, have
P Primai (T Sn C S/.n333p/22) & 2L(1/3) and P PAiTER (T Sn c S/(n33.p/2) p/2)) v 2L(1/3)
p
p
Combining the above three inequalities, we obtain that
P PrINeT ST & Sa(n.))) < L(2n/3) + 4L(n/3)
p
and Eq. (15) is verified.
We next define the following sets of "good" state-action-state tuples:
Un (*h, Gh: 8h+1) 8%. E Sn, ab E An, 8h+1 E Shtt1,
3r, r' E IR such that E (r. sht1 Sh+1(r',, (r', p) and If(s), an) +r-r( r'1 s 3n)
and also "bad" state-action-state tuples:
uh = {(s,, ah. Sh+1) 8h Sn, an E Ab, Sh41 E Sht1,
Vr,r' E IR such that sn Sn(r, n. (), sh+1 E Sh+1 (r', m, p) and [f(sh, an) +r r'1 3n).
16

---

Process vs. Outcome Supervision
We will show that under policy Toff. the encountered state-action-state pairs 'good', i.e., belong Un with high probability. Notice that the complement of set Uh, satisfies
(vh) C 26 U {(8ps On, 8h+1): 8p E S. (n..)) U [(Sp, Ob, 8h+1) 8h+1 Sh+1 (1.+1(1).))
(16)
and according to the last claim we have
P P P & Sn(n,))) - T(2n/3) 4T(n/3)
+
1-p P
and P P (T & Sh+1 ()) v L(2n/3) 4L(n/3)
1-p +
(17)
p
We next upper bound P Powmen (T 0 Un + 0), which is summarized into the following claim.
Claim 3. We have the following upper bounds on the occupancy measure of Un
L(n)
P PIINTR (T * 0) - 2p
(18)
Proof. According to the Markov property, we have
(51, a1. 5h-1, on- IL (an, Sh+1) and Ph+11,9411 sH ag) IL (sh, an)
conditioned on 8h
conditioned on 8h+1-
Hence for any (sh; Oh, Sh+1) E Uh there exists and r' such that 8h SS(rr (r,:))))) and 8ht1 E Sh+1 (r', (bp)), which implies
Prinra (1((Tsh-1) - S (sh, Oh, 8h41) ET) = P Pronsua -r Sn 8h (T) -
and
P Pronto (1((TuH)) +r'l sn (sh, au. sht1) ET) =P P (I(TTNH))
sh+1 2 21-p +rl (1(T))))
By union bound, we obtain
Pronuue (1((Tan1)) - S and (T(T)))) + +r'l Sn n (on, an, 8n+1) ET) 2p.
Additionally (sh, ah, sh+1) Uh implies (s an) + r/ - 37. Therefore, for any (sh, ahs sh+1) Un
P Protoer (1((T) 2 1/ (sh,an, ET) 2 2pp
This leads to
L(n) = PrNNO (lf(T)) 2 2 P PrixOt (Tn + #) (1 2p).
and Eq. (18) follows.
Combining Eq. (18) and the two inequalities in Eq. (17), and in view of Eq. (16), we obtain
P PONTO (r nud = 9) 2L(2n/3) 1-p + 8L(n/3)
+ L(n)
1 - 2p
Next notice from the definition of state-action concentrability, we have for any policy and layer h [H],
d= (8h, Oh, 88+1)
sup D.ES E. ES d (8h, ah, Sh+1)
8hy ap. Jorl an) . T(
dd (Sh, an)) T(sh+1
sup 8y Es, 11
17

---

Process vs. Outcome Supervision
d" (s, S Csa(T,
sup o ES EA drorr (s.
which implies that for any policy and layer h E [H].
P P nuh = 0)
Σ
d' (sh: 0h. 8h++1
(9) x
S (T,
Σ
d (8h, ahs 8h+1)
(9 11) x 1Ax
= (T, Noft)
PTINTOI (T nl = 0)
(2L(2)/3)
8L(n/3)
L(m)
+
+
p
p
2p/
Hence by union bound, we have for any policy IT,
(2L(2n/3)
8L(n/3)
L(n)
PT # 0, wh E [H] 2 1 (T,
1
2p
Finally, we have the last claim showing that if for all [H], (sh, ah. Sh41) E Uh, then the total reward of the trajectory be upper bounded.
Claim 4. For any trajectory T ($1, 01. ,8, ag) where (sh, an sh+1) E Un for every h, we have
Proof. We define tuple un = (shs an 9h+1) for [H]. According to the definition of Un there exist real numbers r(un) E I and r' 11) E R such that for any [H].
91+1 E ((n'(un),, n.p), and [f an) + r(())) - r' (un)) $ 3n. Sy E (((r(un)mmp)))
Compare the condition on 8n E (r(n))) with on E Sh Sn (un- P), we have
P Printatt (Ir(un) - f(TTA- <n ET) 2 1- and Prntu (I'(un-1)) - f(rrA-1) sn E 2 21-p
When < 1/2, by union bound we obtain
Prosuc (I((u)) [(TIa) and (r'(wn1)) [(Ti S ET) 2 - -22 2p>00 0,
which implies that there exists trajectory such that Ir(un) f(1in-1)) I 1 and (r((u-1) f( both hold. Hence we obtain
(r(w)) ('(un-1) S (r(u)) f(Trm-1)) + ('nnn))) S $n+
2m.
Therefore, obtain that
1(())= Σ f(nn an)
< 3Hn + (('((un-r(uul))) 55H + (r(()) r(uz) = 5Hn,
where the last equality uses the fact that 81+1 is the notational terminal state and 81 is in the first layer. According to the previous proofs, we obtain that
(2
8L(n/3)
L(n)
Pr~ (1f(T)) 2 5Hn) s HC,
+ 2p
1
18

---

Process vs. Outcome Supervision
By choosing p= 1/3 and replacing 7) by n/HH), have
P (1((T) n) < (T,((, Toft) (67.(2n/(15H)) + 24T(0/ + (L(nn(5H))
(2 2 33H (T, Tan) L(n/ (15H)) = 33HCsa Toa) Promon (If(r)) 2 // (15H),,
where (1) uses the fact that L(n) is monotonically decreasing with 7). Hence obtain
ETax [f(T) (
2n P (lf(T)) 7) dn
<
2n 33H (T, Toft) Preuu (If(T)) m/(1HH) dn
15H
2n 33H TOHH)
Procou (IS(7)) (15H)) dn
7425 Caa (T. Toft) [ 2(1/(15H) P PriTRT (1f(T)) (15H)) (6/((15H)
7425H Csa( Noft) By (f())))
where (z) uses integration by parts and also the assumption that for any trajectory T, f(r) E [-1, Additionally, we upper bound the expected total reward under policy æ with Mauchy-Schware inequality:
E Erww [[((T)]] S V B [(T)) v 113Csa Toft) . ETwNTS [f(T)²]
B.2. Missing Proofs in Section 3.1
Proof of Theorem I. For any reward model r, we use r*[r] = T y* to denote the difference between reward model r and r*. Then we have
(T) (T(T) (
For any reward E R. also have
Σ (r(()-r(()))
Σ (r*(1(7))²
TEDon
TEDomm
We notice that according to our assumption on the MDPs, for any trajectory 7 and reward model r, r(r) E [o, 1], hence (T(()(T) E [-1, 1]. According to Foster et (2021, Lemma A.3) and union bound over R, with probability P we have for any r E R,
Σ (r*(]((7))
Eynase [(*))
< 2 Eynaot [(*b))()]]] +
4 (lg((2
(19)
Porm
Dorml
rEDomm
When Eq. (19) holds for all r E R, since F is the solution of optimization problem Eq. (3), we have
Σ (r)))(7))) + (log(2
Eraxou ((+((((T))) <
Dorm
DDrmm
rEDorm
8 12 /pp Porm
(r*(r*((7))
D Dorm
TEDomm
16 log Rl/p)
< 33E.natt
(()))) +
[D Drrm
16 1olg((211//))
(Domll
19

---

Process vs. Outcome Supervision
where the last equation uses (*(r)) r* r* 0. Therefore, according Lemma 3, with probability at least p have for any policy n,
(Ta Toff)
log( (og((Rl/p) [Doml]
(+((T) -1=) V H3 Cs, Toft) Bywwoor (M(())) & H882
Proof of Corollary 2. Suppose x² to be the best policy of the true MDP M By Theorem 1, with probability at least 1 6, for any policy æ we have
HC Tof) log( [R|/6)
[J()) 5
[D
Especially since n", क E II, have
H1C Tott) (og((R)/0)
H sup Csa(T Roft) log (R]()))/))
-
1D1l
[D1]
and also
c (T. Toft) log( (og((R)/))
H supren Csa( Roft) log( [R|/5)
(J(T) - J+(
[Dil
D
Next, by calling algorithm 2. with probability at least 1 - 8 we have
max Jz(x) -+( S (1)g(1))2,)),
Hence with probability at least 25,
max (TT) - ( = ((T*) - ((t)
S J+('') - J=((T) + +0 (1 (0()))))())))
H3 (II, Toft) log(l-M1/8)
Dil
H3CCsa (11, Toft)
log (gg())))8)
< max J+(T)) - Jz( +0
7
[Di
H3 Cza (II, Toft) log([MM/
S (1)2))))) +
[D,
B.3. Missing Proofs in Section 3.4
In the following, will prove Theorem and Theorem 5. Before the proofs, first present several useful lemmas. Lemma 8 (Lemma A.1 in Song al. 2024). Suppose Assumption holds, and के satisfies
$ = arg max ETAN F(T) -log (T))
(20)
(T)
Tell
then we have
Jo(TT) Jo( < IE E Fna --))
Proof of Lemma 8. We calculate
[B(TT) Js( ErNNy (r(r) - -lo T5(T)
Eraa r²(r) - -ogg [(()
Traf (T)
20

---

Process vs. Outcome Supervision
Trer Bnna ((T) - -log a(T) rreef (T)
=b(T))
E Erwnz f(T) log
B (r'(()) [(T)] - (+) -f(7)]
E B [rr (r) - f(T)] - B |r f()))
E 3 t~ (T) - r (F) -(7) + [(F),
where in (1) we uses Eq. (20) and the realizability assumption Assumption
Lemma 9 (Lemma C.5 in Xie et al. 2024). We define reward model f:
(T)
f(T) log Traf (T)
where R is given in Eq. (9). Then with probability at least 1 6, we have
sn² 2 2log(I
Reat (r())) F(T)
[D]
where K= = 16V mmxmxxe V
Lemma 10. For MDP M = (S, A,T, H) with eeaattfunction f A [-1, 11, then for any policy and ū, we have
V (Ca Toft) V Csa (ft Rof))
E
(((()-
lid Naatt
where (n, Toft) is defined in Eq. (5).
Proof of Lemma 10. Suppose the layered state space representation is S = = Sy. We construct a new MDP M' with horizon 2H. The state spaces of M' among layer 1 to H, and among layer H + 1 to 2H, are both S,, Sn- The action space of M' is A. The transition model of M' follows transition model in the first H layers, and then transits to the initial state 81 of M and follows transition model again in the last H layers as well. The reward model g in the first H layers are set to be f and in the last H layers are set to be ff.
We define the policy n' of MDP M', which follows policy ı in the first H layers, and follows policy स in the last H layers. We further define the policy T' of MDP M', which follows policy woff in the first H layers, and in the last H layers as well. Then it is easy to see that
- f(+)ll = Er [l((T
where the right hand side is the expected rewards in the new MDP M'. We also have
E
[((+)) ( (())))
Ey [9(T')
Ril
Next, according to the construction of M', we have
d (s, a) he(2H] REA d= (s,a)
Caa (I, Tott) Cza(i,, Tott)
sup
sup
Hence according to Lemma 3, we have
d= (s,a) NEIH aEA d'a (s, a)
Ey'wa' (19(7))1
H3. sup sup
Er' ET'N [9(T')2]
/
(3(Csa Toff) V Cza (i, Toft)) Eri [T(T()
which implies that
E (1)f) - & // (T,(CsaTT, ToR) V Caa Toa))
1, Hid
-
21

---

Process vs. Outcome Supervision
Now are ready to prove Theorem 4 and Theorem 5.
Proof of Theorem 4. According to Lemmas 9 and 10, for any policy n, with probability at least 1 - 8,
By (1) (T') -(7) F(r')1)
2 V H². (T, Traf) V , B
T ((*((T) - -(t)
(C, aret) V Csa(T', &ref)) (og((R)/6)
2 max e Vuna
[D]
where the second line uses Lemma 9 with the class of policies ( : ((T) (T) exp((rr)) Vr E R).
Proof of Theorem 5. Let क to be the policy given in Eq. (9). We define the reward model f as
((T)
F(r) log
(T)
Then it is easy to see that ā is the solution of Eq. (20) according to the above reward model. Since â E Il and Tá E II according to Assumption 1, with probability least 1 - ö we have
(1)
JT(TT)) (T)
Toaa g twa (r (+) - F(T) + F(F)]
2V
H Csa (I1, Tret)
E
To (T+(()) -ft + +(F))²
((i)
CIa(II, Trer) log( [11/8)
V 2
[D]
where (i) uses Lemma 8, (it) uses Lemma 10 with the reward model to be F, and (mii uses Lemma 9.
C. Analysis of ARMOR with Total Reward
ARMOR is an offline RL algorithm introduced by Xie et al. (2022a). Given n trajectories of data in the form of (81, (8, 01; T1, 8H, (HH,T)) Toff, they proved that for the optimal policy n², the output policy ß of their algorithm satisfies
H (2-C((T, Foll log( (M/6)
(21)
Notably, this error bound scales with the best-policy concentrability C(^*, Toll) rather than the all-policy concentrability sup, C(T,, Roft) shown in Corollary 2. natural question arises: can we develop variant of ARMOR that takes data in the form of trajectory plus total reward, i.e., (51, (1,, d1,'.. SH az; R), while maintaining the sample complexity that scales with best-policy concentrability instead of all-policy concentrability? In this section, we answer this question affirmatively by presenting and analyzing such a variant of the ARMOR algorithm.
Suppose the learner is given a model class M. which realizes the ground truth model M*. The learner also have access to some offline batched data D, which is collected from policy कof.. Specifically, D consists of i.i.d. sampled trajectories = ($1, a1. sz an) together with its total reward R r(7). Each of the trajectories is collected by executing Toff under the ground truth MDP M
We consider Algorithm 2, which is variant of the ARMOR algorithm introduced in Xie et al. (2022a) after specifically taylored for data of trajectories with total reward. We have the following guarantee on its sample complexity, which only relies on the single policy concentrability ; Toft).
Theorem 11. Suppose the model class M realizes the ground truth model M*. Then there exists some positive constant c such that for any 8 > 0, by letting a = e log()M)/5), with probability least - 8, the output of Algorithm 2 satisfies
H3. H Css Toff) log (og(//6))
JM-(TT) - Jas (7) S
n
22

---

Process vs. Outcome Supervision
Algorithm 2 ARMOR with Total Rewards
1: Input: Batch data D, model class M, parameter
2:
Construct version space
Ma = MEM:
max - M'EM
LD(M) - sa
sa)
where for MDP model M with transition model Pas and reward function TM,
H
27
(D(M): =
Σ
log (sh+1
Sh: an) -
Σ
TM an) - R
(81
RJED
h=1
3: Output the best policy with pessimism:
arg max min JM (T), MEMa
where (T) denotes the value function of policy æ under MDP M
Proof of Theorem 11. Adopting the similar way as Xie et al. (2022a), we let
H-1
{D(M) = II
II
(9 8hs an)
(er (1 R)DD hml
Then according Xie (2022a, Lemma 8), with probability at least
we have
[M
max log (M)) s log MEM
where M denotes the ground truth model. Additionally, according Xie et al. (2021a, Theorem A.I) (by letting 0 and merge states or actions across the entire horizon into one state or action), we have
[M| 8
Σ (rD
(rar- (7) R2² min Σ (FM(T) - RR)² S log MEM
(r,R)ED
Combining the above incqualities together, obtain that
[M 8
CD(M) (D(M*) S log
MEM
Hence with our choice of a, with probability at least 1 - 5 we have M E M. Next, by Xie et al. (2022a, Lemma 7), with probability at least 1 - 6, for any M E M,
H
H
27
(s mn 88 an Toott
Σ
Drv (Pr((P 8h, on), PMS- (su+1 sh an)) -
Σ
ras (sh, an) - -ras- (sh, and
h=1
maxM'M LD(M')
(D(M)) log(
log(IM]/8)
(22)
n
n
Finally, according the optimality of R, if letting M arg min MeM JM (7), have
Jas- (x*) Jas. (7) < Jas (T*)
min MEM
JM(
JM (TT*) max min JMr MEM
< max {JM- (T')
MEM
23

---

Process vs. Outcome Supervision
where (i) uses the definition of स in Algorithm According simulation lemma (e.g., Uehara and Sun, 2021, Lemma 7), have
H
Jass (xt) -=a((="))) )1
B on (Drv (PM 8h: an); Par- (8h+1 Sb, 04))]
h=1
+ Br [|r (T) (FM(
H-1
I H2/2 , Tolt)
Σ
E (on (Dv Sh. an), Par ($h+1 Sh, an))
+ E By [| (7) -rM(T)]l
where the last inequality uses the Cauchy- Sauwhy-Schwarz inequality and the definition of state-action concentrability. Additionally, according to Lemma 3, we have
E [| (T) (M((T]] 3// VC Toft) Erwao (Fra- (T) - (T))7))
Therefore, with probability least 8,
Jas (ar (T)
max (1Jar [T)(T')] S V H3Caa (T* Fofff) MEM
E (1e,00.---00000))))
Drv(PMr(SHt) 8h, sh, Pas- (8h+1 sh, sh) + Erwaon (rx(()) PM- (T))
h=1
CaCsa Foot log() (Ig()118))
24
n
where the last inequality is due Eq. (22).
We observe that similar to the ARMOR algorithm, the sample complexity of Algorithm 2 scales with the single-policy concentrability (Tr Toff) rather than the all-policy concentrability sup, CSa Toff) shown in Theorem 11. However, unlike ARMOR, Theorem I requires the assumption that the total reward is bounded by [0, 1]. Without this assumption, we include the scale of total reward in the proof of Theorem 11, we would directly obtain a sample complexity of
Cr. (Fr. log( Comparing this with ARMOR's sample complexity (Eq. (21)), we observe gap of 3 (when obtaining an e-sub-optimality bound) in terms of the horizon dependency.
We suspect this gap arises fundamentally from the extra horizon dependency in the Change of Trajectory Measure Lemma (Lemma 3). To illustrate this, consider how changing measures affects complexity (ignoring log terms):
Change of state-action measure: For any function g: S x A R.
h- (( )1
E( [g(s ) hE(H] Es (g 2n)
d (Sh, an)
max
max sup
Σ/ 11 Fo [g( (8h, )3
he[H] an R EA Jom (sh, an)
Change of trajectory measure (Lemma 3): For any function S A-R
Eyan [f(T)2]
d (sh. ah)
H max he(f
sup E. nell (Sh, a%)
E Eyazan [f(T)2]
While this gap in horizon dependency raises an interesting theoretical question, the precise polynomial dependence on horizon is not the main focus our paper. We leave a more thorough investigation of this horizon dependency gap between outcome and process supervision as an interesting direction for future work.
24

---

Process vs. Outcome Supervision
D. Missing Proofs in Section 4
D.1. Proof of Theorem
First we present lemma.
Lemma 12. For any MDP M (S, and policy μ. if we let A :S A - IR to be the advantage function of
policy μ (defined in Eq. (10)), then for any policy n, we have
JA = J.( - J,(H).
Proof of Lemma 12. In view of the performance difference lemma (Kakade and Langford, 2002), we have
(T) (n) = -H (s,a)rd (Q" a) (s, mi]
H. (s)aa)) (s) (*())
B(eaa)dd (8,(8,))
= (T)
Next present the proof of Theorem 6.
Proof of Theorem 6. For any policy π. we decompose
- - = - -()
J+ (,
-4() ((()
(23)
where in (i) use Lemma 12. Next, notice that for any policy म. can write down the value of policy æ as the inner product between the occupancy measures of policy and the reward function, which implies that
- -
H
Σ
Σ
d' (s) (s) F(s,a))
sESaEA
(8)
$ H
Σ Σ
(s, (Ar(s, (()
sESaEA
(4))
< (Calv) B(a,a)o [AA((s) - -(s,a))
((0)
< ll Csa()) Estat:
where (i) uses Cauchy-Schwarz inequality, (ii) adopts the definition of (sa(v) in Eq. (11), and finally in (iit)
Eq. (12). Additionally, according to Eq. (13) we have
J+(T) Jx( S 1ax (+( < Salg
Bringing these inequalities back to Eq. (23), we obtain that
Jn(T) (F) S 2H CCalu) East + Ealg-
D.2. Proof of Theorem
Proof of Theorem 7. We construct M as follows: We let H 2, {0, 1}. and S Si U.S where S {a} and
S. = cb. We further define the transition model P
P(b a, 0) = and P(c a, 1) =
25

---

Process vs. Outcome Supervision
and the reward function R as
2 R(c,,
R(a,0) 0) R[(a, 1) and R(b,0) 1, R(6, = =0, and R(c, 3
The best policy x² of this MDP M satisfies
(a)) x² (b) (c)
hence (x(T*) We choose policy μ u(a) p(b) puc) 1. Then can calculate that
(b R(b, 0) 1, Q" 1) RR6, 1)
2 3 Q"(c1) R(e, 1) = 2
(' 0) = R(c 0)
(a, = R(a, 0) + (²(b,)(b)) 0, Q"(a, 1) - R(a, + (c(c 2
Therefore, the greedy policy Ω with respect to the MDP with reward function to be Q* is
a(a) 1, {(b) = 0, [(c) 0.
which satisfies
max J/( - (R( = 2
3
Remark 1. With the same choice of MDP M and policy in the above proof. can calculate the advantage function A"
as
1 6' 1c, = and (a, =0, A 1 2
(b, 1, (b, =0 and (²
And it is easy to verify that the greedy policy with respect to the MDP with reward function to be A coincides with T²"
26


Reviews:
[{"review_id": "kosruEt4DO", "reviewer": "Reviewer_5vLh", "summary": "This paper challenges the conventional belief that process supervision (step-wise rewards) is statistically superior to outcome supervision (cumulative rewards) in reinforcement learning, particularly for complex tasks like LLM reasoning. The main contributions are:\n\n1. **Theoretical Equivalence**: Under standard data coverage assumptions, outcome supervision is shown to have comparable statistical complexity to process supervision via a novel *Change of Trajectory Measure Lemma*. This lemma bounds trajectory-level distribution shifts using state-action concentrability, avoiding exponential dependence on horizon length.\n\n2. **Advantage Functions as Optimal Process Rewards**: Theoretically, advantage functions of any policy can serve as optimal process reward models, while Q-functions may lead to sub-optimal results.\n\n3. **Extensions to Preference-Based RL**: Improved sample complexity bounds for Direct Preference Optimization (DPO), replacing trajectory-level concentrability with state-action terms.\n\n4. **Practical Algorithm**: A transformation method (Algorithm 1) that enables the use of process supervision algorithms with outcome supervision data.\n\n## update after rebuttal\nMaintain original score. See reasons in rebuttal comments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Below, we address the concerns raised in the review.\n\n***\n\n> more thoroughly discuss recent works on automated process supervision [1-3]\n\nThanks for pointing these out, we will add more detailed discussion in the updated version.\n\n***\n\n> Coverage Assumptions\n\nWe 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^*$). \n\nWe 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.\n\n***\n\n> Lack of Empirical Validation / Disconnect from Practice\n\nThanks 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). \n\nTherefore, 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).\n\n***\n\n> Limited Intuitive Explanations\n\nWe 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:\n\nThe 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.\n\nFrom 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.\n\n***\n\n> about advantage function result (Section 4)\n\nThere 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.\n\n***\n\n> Decision making with partial observability\n\nThank you for bringing this to our attention. This is an interesting research direction, and we plan to explore it in our future work.\n\n***\n\nReferences:  \n[1] Luo, Liangchen, et al. \"Improve mathematical reasoning in language models by automated process supervision.\" arXiv preprint arXiv:2406.06592 2 (2024).  \n[2] Wang, Peiyi, et al. \"Math-shepherd: Verify and reinforce llms step-by-step without human annotations.\" arXiv preprint arXiv:2312.08935 (2023).  \n[3] Setlur, Amrith, et al. \"Rewarding progress: Scaling automated process verifiers for llm reasoning.\" arXiv preprint arXiv:2410.08146 (2024).", "claims_and_evidence": "The paper's claims are generally well-supported by theoretical analysis and proofs:\n\n- **Supported Claims**:\n  - The equivalence between outcome/process supervision under coverage (Theorems 1, 4) is rigorously proven using concentration inequalities and the Change of Trajectory Measure Lemma.\n  - The optimality of advantage functions as reward models (Theorem 6) and the sub-optimality of Q-functions (Theorem 7) is validated via a constructed MDP counterexample.\n  - The improved sample complexity for preference-based RL (Theorems 4, 5) is mathematically derived.\n\n- **Unsupported Claims**:\n  - Practical implications (e.g., reduced need for process annotations) remain speculative due to the lack of empirical validation.\n\nThe mathematical derivations are sound, though some proofs (particularly for Lemma 3) are quite technical and would benefit from more intuitive explanations.", "methods_and_evaluation_criteria": "The theoretical framework is appropriate, leveraging established concepts (state-action concentrability, offline RL theory) to analyze the statistical complexity of different supervision paradigms. The paper focuses on theoretical analysis rather than empirical evaluation, which is reasonable given the nature of the contributions.\n\nThe evaluation criteria, based on statistical complexity and sample efficiency, are appropriate for comparing the two supervision paradigms. However, the absence of experiments limits assessment of real-world applicability, especially given that the theoretical results contradict some empirical observations where process supervision often outperforms outcome supervision.", "theoretical_claims": "I checked the correctness of several key proofs:\n\n1. **Change of Trajectory Measure Lemma (Lemma 3)**: The proof in Section B.1 is logically sound, using a careful decomposition of states into \"good\" and \"bad\" states and analyzing their probabilities under different policies. The technical approach effectively bounds trajectory-level distribution shifts using state-action concentrability.\n\n2. **Theorem 1 (Learning a Reward Model from Total Reward)**: The proof correctly applies the Change of Trajectory Measure Lemma to bound the error between the true reward model and the learned reward model.\n\n3. **Theorems 4 and 5 (Preference-Based RL)**: The proofs extend the main results to preference-based settings, correctly applying the Change of Trajectory Measure Lemma to derive improved sample complexity bounds.\n\n4. **Theorem 6 (Advantage Function Learning)**: The proof correctly uses the performance difference lemma to show that the advantage function can serve as an optimal process reward model.\n\n5. **Theorem 7 (Lower Bound on Failure of Using Q-Functions)**: The proof provides a valid counterexample showing that using Q-functions as reward models can lead to sub-optimal policies.\n\nNo apparent errors were detected in the proofs, though some sections could benefit from more intuitive explanations.", "experimental_designs_or_analyses": "The paper is primarily theoretical and does not include empirical experiments. While the focus is theoretical, experiments on synthetic MDPs or LLM tasks would strengthen the practical relevance of the findings, especially given that they challenge conventional wisdom.\n\nThe absence of empirical validation is a limitation, particularly since the theoretical results suggest a different conclusion than what is often observed in practice, where process supervision frequently outperforms outcome supervision.", "relation_to_broader_scientific_literature": "The paper effectively connects to several areas of reinforcement learning literature:\n\n- **Offline RL**: Builds on work by Chen & Jiang (2019), Xie et al. (2021a), and others on concentrability coefficients and offline policy learning.\n\n- **Off-Policy Evaluation**: Relates to work by Uehara et al. (2020) on the change of measure problem and the distinction between state-action and trajectory coverage.\n\n- **Preference-Based RL**: Extends results to DPO (Rafailov et al., 2023) and provides improved sample complexity bounds.\n\n- **Process vs. Outcome Supervision**: References empirical work showing the effectiveness of process supervision (Uesato et al., 2022; Lightman et al., 2023).\n\nThe paper's novelty lies in bridging outcome and process supervision via concentrability concepts and providing a theoretical foundation for understanding their relationship.", "essential_references_not_discussed": "The paper mentions but could more thoroughly discuss recent works on automated process supervision that generate step-wise rewards from outcomes, such as:\n\n1. Wang et al. (2024) \"Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations\"\n2. Luo et al. (2024) \"Improve mathematical reasoning in language models by automated process supervision\"\n3. Setlur et al. (2024) \"Rewarding progress: Scaling automated process verifiers for LLM reasoning\"\n\nThese works are briefly cited but not deeply analyzed, despite being highly relevant to the paper's claim that outcome supervision can be transformed into process supervision. A more detailed discussion would better contextualize the practical need for manual process labels and the empirical approaches already being used to address this issue.", "other_strengths_and_weaknesses": "### Strengths:\n\n1. **Novel Theoretical Insight**: The Change of Trajectory Measure Lemma is a significant technical contribution that challenges a widely held assumption about the statistical complexity of outcome vs. process supervision.\n\n2. **Non-trivial Connections**: The paper establishes important connections between advantage functions and process rewards, providing theoretical justification for certain empirical approaches.\n\n3. **Comprehensive Analysis**: The theoretical analysis covers various aspects of the problem, including extensions to preference-based learning and the role of advantage functions.\n\n4. **Practical Algorithm**: Algorithm 1 provides a concrete way to transform outcome supervision data into process supervision data, making the theoretical insights actionable.\n\n### Weaknesses:\n\n1. **Heavy Reliance on Coverage Assumptions**: The results depend on state-action concentrability coefficients (Csa), which may not hold in practice, especially in complex environments like those encountered in LLM training.\n\n2. **Lack of Empirical Validation**: The absence of experiments weakens the impact of the theoretical results, especially since they contradict some empirical observations.\n\n3. **Limited Intuitive Explanations**: Some of the proofs, particularly for Lemma 3, are quite technical and would benefit from more intuitive explanations.\n\n4. **Disconnect from Practice**: The paper could more explicitly address why, if outcome and process supervision are statistically equivalent, empirical results often show process supervision outperforming outcome supervision.", "other_comments_or_suggestions": "1. Section 4 on advantage function analysis could be better motivated and connected to the main thesis of the paper.\n\n2. There are a few typos in the paper, including \"contradistinction\" (line 100) and \"alterative\" instead of \"alternative\" (line 171).\n\n3. The paper would benefit from a discussion of limitations, particularly regarding the assumptions made in the theoretical analysis and how they might not hold in certain practical settings.\n\n4. A simple illustrative example demonstrating the key insight of the paper would help readers grasp the main idea more intuitively.", "questions_for_authors": "1. How do your theoretical assumptions (e.g., Csa) align with real-world scenarios like LLM training, where state-action coverage is often poor? This would help clarify the practical applicability of your results.\n\n2. Could the advantage function result (Section 4) be empirically validated on a simple MDP or LLM reasoning task? This would strengthen the connection between theory and practice.\n\n3. Have you considered extending the analysis to settings with partial observability, which are common in sequential decision-making for LLMs? This would address a significant aspect of real-world applications.\n\nResponses to these questions would clarify the applicability of the theoretical results and guide future empirical work in this area.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TLfedZ3mtB", "reviewer": "Reviewer_F65b", "summary": "The paper compares process and outcome supervision in reinforcement learning from a theoretical perspective. The central result is showing that RL outcome rewards is no more statistically difficult than RL with step-level rewards, which is shown via a result that states that an offline RL dataset with outcome rewards can be transformed into a dataset with process rewards with minimal loss in statistical efficiency.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. Below, we address the concerns raised in the review.\n\n***\n\n> 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.\n> 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.\n\nIf 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. \n\nWe 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. \n\nOur 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). \n\nFinally, 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.\n\n\n***\n\n> Pre-LLM RL discussion\n\nWe 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.", "claims_and_evidence": "The theoretical claims all seem plausible, although I did not check the proofs in detail.\n\nHowever, I think some of the claims in the introduction and general framing of the paper are too strong. In general, the results in the paper are about RL with goal-based reward and step-level reward. I don't think there is anything specific to RL with LLMs. Still the introduction heavily discusses work with LLMs suggesting particular applicability to that context. In fact, I think the applicability is probably lower because the reward signals in LLMs are often provided by human overseers.\n\nThe main claim of the paper is that we can draw conclusions about which of the two methods should work better in practice based on statistical difficult metrics of the learning problems. While I think the results are interesting and provide some evidence about this question, I think the introduction is vastly overclaiming the applicability to practical choices.", "methods_and_evaluation_criteria": "The proposed theoretical analysis is a valid way to gain insight about the comparison between process and outcome supervision.\n\nHowever, the analysis neglects practically important aspects such as where do the process and outcome rewards come from. The paper shows a way of transforming process into outcome rewards and vice-versa but it is unclear what this implies in practice. For example, the quality of outcome and process rewards can vary widely if the rewards are given by humans. In some domains it is easier for humans to provide outcome rewards and in other domains it's easier to provide a process reward signal. So, overall I'm not drawing any strong conclusions from the results in this paper.", "theoretical_claims": "I did not check any of the proofs in detail and I do not have the relevant background to evaluate whether the proofs are correct.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "The paper provides a theoretical perspective to compare outcome and process supervision which in this form is novel.", "essential_references_not_discussed": "I was surprised to not see essentially any discussion of pre-LLM RL. In particular work on goal-conditioned RL and step-level feedback seems relevant. For example potential-based reward shaping is a way to transform a sparse (\"outcome\") reward into a shaped (\"process\") reward.", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "Overall I'm very unsure about this paper because I don't have the necessary expertise to evaluate the validity and importance of the theoretical claims. From a practical perspective I'm skeptical that the results are particularly useful. But I would support accepting the paper if other reviewers find the results interesting from a theoretical perspective.", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JRPQRTgcr6", "reviewer": "Reviewer_yWDQ", "summary": "This paper shows a theoretical analysis of the statistical equivalence between dense reward trajectories and sparse reward trajectories, which returns the total reward at the end of the episode in offline RL.\n\n**Post-rebuttal**\nI read the responses from the authors and other reviewers.\nI think this is a theory paper, as mentioned in the rebuttals, and it shows new findings.\nThere is a weak connection to practical algorithm designs, but this paper offers valuable insights;\ndifficulty in obtaining PRMs in practice, and several approaches are using outcome rewards to translate into process rewards.\nadvantage function is better considered than the q-function.\n\nThis paper will be more appreciated by people who are interested in theory.\nExtracting more valuable insights would be even more appreciated, and providing intuition about the assumptions would also increase the impact of this work. Finally, I increased the score, reflecting the significance of the work.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. Below, we address the concerns raised in the review.\n\n***\n\n> 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.\n> Could you provide any tangible procedure that could replace the PRM with ORM?\n> In practice, what will be the difficulty of applying this idea?\n\nThanks 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.\n\nOur 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.\n\nIn 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.\n\n***\n\n> What assumption is not realistic?\n\n\nNote 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.\n\nWe 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.\n\n***\n\nReferences:   \n[1] Luo, Liangchen, et al. \"Improve mathematical reasoning in language models by automated process supervision.\" arXiv preprint arXiv:2406.06592 2 (2024).  \n[2] Wang, Peiyi, et al. \"Math-shepherd: Verify and reinforce llms step-by-step without human annotations.\" arXiv preprint arXiv:2312.08935 (2023).  \n[3] Setlur, Amrith, et al. \"Rewarding progress: Scaling automated process verifiers for llm reasoning.\" arXiv preprint arXiv:2410.08146 (2024).", "claims_and_evidence": "The main claims are given in the form of concentration inequalities.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "No", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "This is a mathematical theory paper analyzing the error bounds in offline reinforcement learning, and I am not sure how much of the theoretical claims can actually be transferred to scientific literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The strength is that the claim is very nice, if it is possible in practice. We don't need to annotate or learn a dense reward model, but sparse reward trajectories could solve all problems.\nThe main weakness is that it is difficult to imagine how this result can be useful.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Could you provide any tangible procedure that could replace the PRM with ORM?\n\nIn practice, what will be the difficulty of applying this idea? \n\nWhat assumption is not realistic?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xuhztU8gs6", "reviewer": "Reviewer_jQ9F", "summary": "The paper’s central takeaway is that offline RL under trajectory-wide sparse rewards (for LLMs, outcome supervision) and dense rewards (process supervision) are statistically equivalent (up to polynomial factors in the horizon).\n\nThe main contribution is the Change of Trajectory Measure Lemma, a powerful result that asymptotically bounds the quotient of the second moments for trajectory distributions from two different policies of a function on (s, a) added across the trajectory. Crucially, the bound is based on the horizon and the state-action-level distribution shift between the policies.\n\nThis Lemma is then used to show the aforementioned statistical equivalence (up to polynomial factors in the horizon) between outcome and process supervision, as well as tighter results for Preference-based RL with explicit reward modeling and DPO. Finally, the paper analyzes two common approaches to learning a process reward from outcome supervision, showing rewards that approximate the advantage function are theoretically coherent. In contrast, rewards that approximate the Q function are not consistent.\n\n## Post–Rebuttal\nI have read the concerns from other reviewers and the responses from the authors, and I maintain my original assessment.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your support.\n\n***\n\n> Relevant Citations in L416\n\nWe will add the citations accordingly.\n\n***\n> Assumption on finiteness of $|R|$\n\nThanks 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.\n\n***\n\n> Typos\n\nThanks for pointing out the typos. We will fix these in the revision.", "claims_and_evidence": "Most of the claims made are supported by a complete and novel theoretical analysis. Nonetheless, I believe the abstract and introduction do not state clearly enough that some of the provided results (Thm 1, Cor 2, Thm 4, and Thm 5) require the assumption of a finite hypothesis set, which impacts practical applicability. Similarly, the results provided (Thm 1, Cor 2) are limited to offline RL settings, which should also be clarified more explicitly in the introduction.", "methods_and_evaluation_criteria": "Yes, claims are theoretical and accompanied by corresponding proof. Consequently, there are no empirical results, but none appear required for the paper’s soundness.", "theoretical_claims": "I carefully verified the proofs for the core Lemma 3 and Theorems 1 and 7. I also reviewed the proofs of the remaining results but did not reproduce them with the same level of detail. Everything seems correct.", "experimental_designs_or_analyses": "There are no empirical results.", "relation_to_broader_scientific_literature": "To the best of my knowledge, the results presented in this paper are novel and very valuable. Although their positioning focuses on the timely and active field of outcome and process supervision, their result seems to extend naturally to any offline RL method with trajectory-wide sparse rewards, making the analysis broadly impactful.\n\nMore importantly, their main result, Lemma 3, is powerful and widely applicable even beyond offline RL. Their paper already shows its flexibility through the various results they derive from it, ranging from offline RL in general and outcome supervision to preference-based learning. Future works will likely benefit from and build on these results.\n\nMore specifically, position-wise, this paper is tightly relevant to recent works in LLMs where either (1) only rewards for the outcome (outcome supervision) or (2) step-by-step rewards (process supervision) are available. The community has recently been unable to reach a consensus on which of these approaches is most compelling overall, as adequately discussed in the paper. On the one hand, process supervision provides a richer signal that aids learning, while outcome supervision facilitates data collection. This paper examines the situation from a theoretical perspective, proving that outcome supervision is statistically no harder than process supervision (up to poly(H) factors), providing a solid argument to challenge what’s considered the main limitation of outcome supervision with respect to process supervision.\n\nRegarding the framework adopted for the theory, this paper works on the “state-action coverage” assumption, which, as cited correctly in the paper, is a widely used measure of statistical difficulty in the offline setting. While this magnitude is natural for process supervision, the equivalent for outcome supervision would be the much looser trajectory coverage. Through lemma 3, this paper not only tightens results that naturally depend on trajectory-level coverage, such as therein cited reward-modeling methods (e.g., DPO), but more generally bridges an important gap in OPE (as properly cited).\n\nFinally, the paper also provides compelling theoretical grounding for advantage-function-based “process” rewards, as done in some recent works, while shining a light on the limitations of Q-function-based rewards, as done in others. Indeed, the paper shows that the former preserves optimal policies while the latter doesn’t.\n\nOverall, this paper significantly advances offline RL theory, with direct impact and insight on LLM post-training.", "essential_references_not_discussed": "I don’t have a specific set of missing works that should be cited, but I would propose some parts of the paper that would benefit from appropriate citations.\n\nProofs such as the one of Lemma 3 seem to use relatively standard ideas from the literature. I don’t want to push any specific work that inspired some of these ideas, but I believe it would be good if the authors would acknowledge the works that most influenced their approach to the proofs.\n\nI would also appreciate relevant citations in the second column in L416 after “widely used.”", "other_strengths_and_weaknesses": "I believe the above conveys the strengths I find in the paper pretty comprehensively, as well as the main weaknesses (not stating adequately in the abstract and intro the offline setting and finite hypothesis set).\n\nIn terms of weaknesses, as usual, proofs could contain more text to ensure they are pleasant and amenable to the reader.\n\nAlso:\n* L179, C2. To use the union bound, and of course, as is apparent from the result, a big assumption is the finiteness of |R|. This can probably be relaxed in the future, but as it currently stands, this is a big assumption that should be more clearly stated.", "other_comments_or_suggestions": "* L074, C2. The notation probably belongs more to the background than an introduction, and given that both the O notation and sigmoid are reasonably common, I would remove this section and introduce the notation the first time it appears.\n* L075, C2. I would encourage using only the O notation (or the other), not both.\n* L111, C2. RL is used without relating it to “Reinforcement Learning,” and “Reinforcement Learning” is probably fully spelled too many times, as well as “Large Language Model.”\n* L168, C2. Here, it would be nice to clarify that you are referring to state-action rewards more explicitly, maybe through using the r notation to distinguish from R. I think this paragraph could be clearer.\n* L259, C1. This paragraph could be made clearer by saying: “Indeed, many classical offline RL algorithms ... are known to achieve exactly this sample complexity under standard coverage assumptions”. Otherwise, the two sentences might seem to make different points while trying to get to the same point.\n* L268, C1. Maybe it would be clearer to explicitly refer to “the single-policy concentration bound in Appendix C, ...” instead of \"the data-dependent case.”\n* L270, C2. \"till\" -> \"until\"\n* L300, C1, and L863, among others. I would encourage using max and min instead of ∨ and ∧.\n* L694, I believe there is a typo here and f(s_h) should be r(s_h).", "questions_for_authors": "I have no specific questions, but I welcome the author’s pointing out anything in my review that might suggest I have misunderstood anything.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work provides a comprehensive theoretical examination of process supervision in reinforcement learning. It establishes the statistical equivalence between outcome and process reward models, while demonstrating that process rewards approximating the advantage function is theoretically coherent. The theoretical insights presented in this work, in particular the Lemma 3, are highly valued by reviewers (5vLH, yWDQ, jQ9F). Despite some concerns in the practical algorithm design (Fb56, yWDQ), the paper's strength as a theoretical contribution with broad applicability (jQ9F) substantially outweighs these concerns, which is acknowledged by reviewers during the discussion period.

As a suggestion, this work may benefit from more discussion about relevant literature (5vLH). Besides [1-3], I also note [4] is related to the results in transforming outcome rewards for process rewards. Nonetheless, I think this work offers valuable insights that will benefit the broader research community, and recommend the acceptance of this work.

[1] Wang et al. Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations. ACL 2024

[2] Luo et al. Improve mathematical reasoning in language models by automated process supervision. arXiv preprint arXiv:2406.06592 2 (2024).

[3] Setlur et al. Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning. ICLR 2025.

[4] Feng et al. Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlo. ICLR 2025.
Decision: Accept (poster)