acceptodds
Under review as a conference paper at ICLR 2027

The Price of Imperfect Process Rewards: Bias Floors and Finite-Budget Reversals

Abstract

A learned process reward model (PRM) provides feedback at each step, whereas its reward estimates may be inaccurate, which can lead to suboptimal policies. We compare policy learning from a fixed PRM with learning from unbiased outcome feedback under the same downstream rollout budget. On task families where the PRM preserves most preferences, we establish a reversal through matching bounds: process feedback has lower minimax regret at small positive budgets, while outcome feedback has lower minimax regret at large budgets. With an unknown transition model, the minimax regret of the process learner decreases toward an exact bias floor. Our lower bound accounts for the transition estimation error, establishing the reversal even when actions have an arbitrarily small effect on transition probabilities. In the known-transition family, for trajectories of steps, the crossover budget scales as for the largest process regret over a range of per-stage reward gap. For finite tabular MDPs with compact convex occupancy sets, we give exact bounds on the loss in cumulative true reward under policy comparisons with a specified tolerance in PRM value. These bounds account for potential shaping and reward scale, and policy constraints can make these class-specific certificates arbitrarily smaller than the corresponding global STARC guarantees. For a weighted combination of process and outcome rewards, the bias term in the regret bound is proportional to the PRM weight. Our tabular experiments vary PRM accuracy at a fixed true reward, examining how horizon length and transition estimation affect policy regret.

Primary area:
reinforcement learning
Keywords:
Process Reward Models, Outcome Rewards, Reward Misspecification, Sample Complexity

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_wJyiOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies an interesting problem for RL, and from the writing, in particular to RL post training of LLMs where we either provide process rewards to weight each individual choice but sometimes can be wrongly rewarded, or using a terminal reward that only judge the outcome. The author found out that, under a particular problem setting, inaccurate process reward can still be useful in a small data regime but outcome reward wins (smaller minimax regret) when compute budget is larger.

Critical strengths
  1. The paper carefully distinguishes known and unknown dynamics and provides consistent results for its claim. I find the analysis under different scenarios helpful and comprehensive.

  2. Theorem 4 provides a clean characterization of the loss.

  3. The synthetic experiments are consistent with the analytical predictions.

Critical weaknesses
  1. In the known-dynamics family, the process learner can therefore select its minimax policy before collecting any downstream trajectories. The outcome learner receives fresh information about the true reward and can eventually correct its uncertainty. This is a valid comparison but I am not sure how important this is as the outcome learner eventually winning seems obvious. The construction can thus be restated as a stochastic linear bandit.
  2. Much of the theory applies to generic objectives. Theorem 3 follows by adding and subtracting proxy values and bounding the span of the errors. Corollary 5 then scales this error by the hybrid weight without characterization. Theorem 4 is more substantive, but its characterization follows from convex duality over occupancy differences.
  3. Finally I do not understand the comparison with STARC and fail to understand its significance as the paper is too cryptic on such concepts.
Questions for authors
  1. Which conclusion genuinely depends on stepwise PRM? In particular, would replacing the supplied PRM in Theorem 1 with the complete terminal predictor in a stochastic bandit setting change either the minimax risks?
  2. How should the conditional Bernoulli noise assumption be interpreted in the motivating RLVR setting? Can the authors give detailed characterizations of such assumptions?
Reviewer_dCvdOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper compares two ways to train a policy under the same rollout budget: a process learner that optimizes a fixed, imperfect PRM without observing terminal rewards, and an outcome learner that observes unbiased terminal rewards but has no PRM. On constructed tabular task families where the PRM misranks a few stages at unknown locations, the authors derive the exact minimax risk of the process learner and matching-scale bounds for the outcome learner, showing that process feedback is preferable at small budgets and outcome feedback at large budgets, with the crossover at Θ(α−2log⁡(H/k))\Theta(\alpha^{-2} \log(H/k)). With unknown transitions, the process risk decays to a nonzero bias floor and the reversal persists. They relate this floor to a policy-relevant error span that is invariant to potential shaping, and give a scale-optimized certificate that exactly characterizes the worst true-return loss among policy comparisons satisfying a PRM tolerance; this certificate can be much smaller than global STARC guarantees under policy constraints. A hybrid objective has bias proportional to the PRM weight, and tabular experiments confirm the predicted learning curves.

Critical strengths
  1. The finite-budget comparison is rigorous: the process learner’s minimax risk is computed exactly at every budget, and the outcome bounds match it in scale. In the unknown-transition case, the analysis separates transition and reward uncertainty so that the dynamics-estimation cost cancels exactly, showing the reversal persists even under weak action effects.

  2. The scale-optimized certificate exactly characterizes the worst true-return loss among policy comparisons that satisfy a PRM tolerance, for finite tabular MDPs with compact convex occupancy sets. It is invariant to potential shaping and to joint rescaling of the PRM and its tolerance, and it can be computed by a linear program.

Critical weaknesses
  1. The constructed task families make the outcome learner’s job easy. Because the true return is additive in the actions, outcome learning reduces to parallel sign tests and avoids the sparse-reward credit assignment that motivates PRMs. The PRM is also an idealized, fixed oracle whose errors are not adaptive to the policy, so it is unclear whether the reversal is relevant in practice.

  2. The contributions that matter most in practice, or that go beyond prior work, are relatively thin. The hybrid bound follows directly from Theorem 3, the hybrid algorithm requires oracle knowledge of the PRM error rate, and the STARC separation mainly reflects restricting the policy class. The experiments mostly re-verify closed-form formulas on tabular tasks.

Questions for authors
  1. How do the results change when the outcome reward is non-additive? An example is a conjunctive reward, where success requires every step to be correct, so success under exploration is exponentially rare. Does the reversal still hold, and how does the crossover budget scale with H in that case?

  2. How does the hybrid learner perform without oracle knowledge of the PRM error rate k/m? For instance, it could estimate the error rate from outcomes or use a fixed weight schedule. Is there a lower bound for the joint protocol, with access to both the PRM and outcomes, showing whether Algorithm 1 is minimax optimal?

Minor:

Spelling mistake in line 74 - "ture" instead of "true".

Reviewer_m6YZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper compares learning from a fixed imperfect process reward model with learning from unbiased terminal outcomes under a common downstream rollout budget. On constructed task families, it establishes a budget reversal: process feedback is preferable at small budgets, while outcome feedback eventually achieves lower regret. The analysis includes unknown transitions and characterizes an exact process regret floor. The paper also develops reward error certificates that account for policy constraints, potential shaping, reward scale, and optimization tolerance. A hybrid estimator combines both signals, and synthetic tabular experiments illustrate the theoretical predictions.

Critical strengths
  1. The paper gives a precise quantitative characterization of the budget reversal on its task families. The results include exact process risks and matching crossover scales, with lower bounds that allow adaptive data collection. Theorem 2 is particularly useful because it retains the transition estimation contribution in the outcome lower bound. This permits a strict comparison when both learners must estimate the dynamics, including when actions have very weak effects on transition probabilities.

  2. The exact policy comparison certificate clearly identifies how policy constraints and optimization tolerance affect reward misspecification. Theorem 4 characterizes the largest true reward loss among policy pairs satisfying a specified PRM comparison, under compact convex occupancy sets. The treatment of positive scaling correctly rescales the comparison tolerance, and the paper distinguishes this pairwise certificate from the potentially smaller loss of an approximately PRM optimal output. The explicit constructions and numerical checks help clarify these distinctions.

Critical weaknesses
  1. The small budget advantage depends substantially on the information supplied to each learner and the outcome noise model. In Appendices B.1 and C.1, the process learner receives a complete pretrained PRM, while the outcome learner does not receive that model, and PRM training costs are excluded. If an outcome learner also receives the same PRM, it can emulate the process learner, so the strict process advantage disappears. The crossover therefore quantifies a tradeoff between informative prior reward knowledge and learning without that knowledge. Its interpretation as an advantage of process feedback requires this qualification. The noise assumption also matters: in the known transition chain, noiseless outcome observations allow all reward signs to be recovered using one baseline trajectory and one coordinate flip per stage, requiring only H+1H+1 trajectories independently of α\alpha. The stated crossover dependence therefore does not directly extend to that observation model.

  2. The certificate and hybrid results provide limited additional guidance beyond the specialized theoretical setting. At zero tolerance over the full policy class, the certificate is within a factor of two of the return span normalization associated with STARC. The unbounded separation uses a restricted class for the new certificate and the full class for the global guarantee. The distinctive contributions are consequently the exact characterization, explicit tolerance, and treatment of policy constraints. Theorem 3 and the linear dependence on the hybrid weight follow directly from the policy value difference identity. Meanwhile, Algorithm 1 requires the true error count kk and reward gap α\alpha to set its threshold. The experiments use the constructed families and small random MDPs, leaving the usefulness of this prescription under unknown PRM quality largely unresolved.

Questions for authors
  1. How should the main budget reversal be interpreted when the same pretrained PRM is available to every learner? Please distinguish the benefit of prior reward information from the effect of receiving feedback at intermediate steps, and clarify how the conclusion depends on noisy versus noiseless outcome observations.

  2. How sensitive is Algorithm 1 to misspecification of kk and α\alpha? Experiments using estimated or incorrect values would help establish whether the hybrid improvement remains useful when PRM accuracy and reward gaps are unknown.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.