acceptodds
Under review as a conference paper at ICLR 2027

ProCredit: From Outcome Rewards to Progress Credit in Agentic Reinforcement Learning

10 views

Abstract

Long-horizon agentic tasks require an agent to modify an environment through a sequence of tool calls, with success determined by the final state. The standard recipe assigns a single outcome reward at the end and compares trajectories sampled for the same task. As a result, a group with no successful trajectory yields no training signal, failed attempts cannot be told apart by how close they came to completion, and turns that advance the task receive the same credit as turns that only query the environment. Prior work refines the unit of comparison from the trajectory to the step, or trains a reward model to supply intermediate signal: the former still derives its signal from final success alone, and the latter estimates it with a model. We observe that the acceptance checks that decide success can also be run on intermediate states, so progress is as verifiable as the outcome. We propose ProCredit, which turns this verified progress into credit: it reruns the acceptance checks after each turn, rewards the turn by its change in progress, and uses these rewards to assign credit both across attempts at the same task and across the turns within a trajectory. Starting from Qwen3.5 base models at three scales on AppWorld, ProCredit outperforms outcome-reward baselines and progress-based baselines in task completion rate at every scale on both test sets, exceeding the strongest outcome-reward baseline by 4.1 percentage points at 4B, and results in a second environment show the same direction of improvement. Ablations show that adding the final progress to the trajectory score alone does not improve performance: the gain comes from crediting progress to the turn where it occurs.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, large language model, credit assignment, verifiable rewards

Reviews

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

This paper considers a special class of long-horizon agentic tasks in which an agent modifies an environment through multiple tool-use turns and final success is determined by a collection of executable acceptance checks. Let the terminal outcome be R∈{0,1}R\in\{0,1\}. The checks can also be executed on intermediate environment states, although their results are used only during training.

For task gg, the paper uses a set of binary checks Cg={Cg,m}m=1KgC_g=\{C_{g,m}\}_{m=1}^{K_g} and defines progress as the fraction currently passed:

Φg(s)=1Kg∑m=1KgCg,m(s).\Phi_g(s)=\frac{1}{K_g}\sum_{m=1}^{K_g} C_{g,m}(s).

In the experiments, only checks that fail in the initial state are included in the progress calculation, so Φ0=0\Phi_0=0. Consequently, CgC_g can be a subset of the complete acceptance conditions: final success implies ΦT=1\Phi_T=1, but ΦT=1\Phi_T=1 need not imply success. A turn receives the progress-difference reward

rt=c(Φt−Φt−1),r_t=c(\Phi_t-\Phi_{t-1}),

and a trajectory receives the score

=R+c(\Phi_T-\Phi_0).$$ ProCredit uses this signal at two levels. It standardizes $S$ among trajectories sampled for the same task to obtain a trajectory-level advantage. It also computes an undiscounted onward return for each turn, $$G_{i,t}=R_i+c(\Phi_{i,T_i}-\Phi_{i,t-1}),$$ centers these returns over all sampled turns for the task, and adds the resulting turn-level advantage to the trajectory-level advantage. All tokens within a turn receive the same combined advantage. The paper evaluates ProCredit using Qwen3.5 base models at 4B, 9B, and 35B-A3B scales. ProCredit has the highest reported mean task-goal completion rate among the included methods in all six AppWorld model-size/test-split combinations. The largest gains occur at 4B and become smaller at larger scales. A smaller ToolSandbox study also favors ProCredit over GRPO, and BFCL evaluation suggests that the measured function-calling capabilities are retained. The ablations report that adding final progress only to the trajectory score does not consistently help, whereas the complete turn-level construction does, and that undiscounted returns outperform $\gamma=0.95$ in this setup.
Critical strengths

1. The method exploits a useful source of objective intermediate supervision

When executable checks can be evaluated on intermediate environment states, their changes provide more information than a single binary outcome: they can distinguish partially completed failures, supply signal in some all-fail groups, and differentiate state-changing turns from pure queries. This is practically useful and avoids training a separate reward model. The method is also simple to implement in environments that already expose suitable checks.

2. The paper provides substantial empirical evidence that its complete training rule can help

The AppWorld experiments cover three model scales and two test splits, and the paper includes outcome-only and progress-based alternatives, three independent runs, several credit granularities, and analyses of all-fail groups and discounting. In particular, the consistent ordering between ProCredit and GRPO-Φ\Phi is meaningful evidence that the complete turn-level estimator contributes beyond using the paper's trajectory score alone. The second environment and retention evaluation are also useful, even though they do not establish broad generality.

Critical weaknesses

1. The paper does not clearly establish the research problem, its importance, or its status in prior work

The method applies not to general reinforcement learning with verifiable rewards, but to a narrower problem class: the terminal objective must be decomposable into multiple binary criteria, the criteria must be executable on intermediate environment states. This problem class should be defined explicitly before introducing ProCredit. The paper currently moves directly from examples such as AppWorld to the claim that acceptance checks can be reused as progress, without establishing how common this structure is and which important applications possess it.

More importantly, the paper does not explain whether identifying this problem class is itself new. Binary executable checks are a special case of a broader decomposed-evaluation setting in which a task is assessed by multiple checklist or rubric items, potentially with graded rather than binary scores. The paper briefly mentions CM2, VPR, GiGPO, and other related approaches, but it does not organize this literature around the underlying problem class or state what was already known about checklist-, rubric-, milestone-, and verifier-based intermediate supervision. Thus, it remains unclear whether the scientific contribution is (i) recognizing a new problem class, or (ii) proposing a new mathematical model for a known class. Without this positioning, the novelty and importance of the work cannot be assessed.

The paper should define the problem class independently of its proposed solution, explain its practical scope, review prior formulations of decomposable verifiers and rubric/checklist rewards, and identify the precise unresolved problem that ProCredit addresses.

2. The paper's reward construction is one particular modeling choice, but the most direct alternative is neither discussed nor evaluated

A more direct formulation would define progress as the fraction of all acceptance checks currently passed and redistribute the final all-check score across turns without changing the trajectory objective. The first turn would receive reward Φ1\Phi_1, the second would receive Φ2−Φ1\Phi_2-\Phi_1, and, in general, turn tt would receive Φt−Φt−1\Phi_t-\Phi_{t-1}. These rewards telescope exactly:

Φ1+(Φ2−Φ1)+⋯+(ΦT−ΦT−1)=ΦT.\Phi_1+(\Phi_2-\Phi_1)+\cdots+(\Phi_T-\Phi_{T-1})=\Phi_T.

Thus, maximizing the total intermediate reward is exactly the same optimization problem as evaluating the fraction of all acceptance checks passed once at the end of the trajectory. Success is simply the event ΦT=1\Phi_T=1, and no separate score of the form R+cΦTR+c\Phi_T is needed to recover the terminal all-check objective. This construction also retains checks that already pass initially, so damaging a required preservation condition reduces the score rather than being invisible to the progress signal.

ProCredit instead removes initially passing checks, separately retains the binary outcome, and optimizes a score of the form R+cΦTR+c\Phi_T. These choices have substantive consequences. Removing initially passing checks can make damage to required conditions invisible to the progress signal. Adding RR creates a separate completion bonus, and cc determines how success probability is traded against partial completion.

The paper lacks discussing why choosing its current formulation instead of the more direct one.

3. The GRPO-Φ\Phi ablation does not isolate which component of the turn-level estimator causes the gain

The paper explicitly concludes that “the gain comes from crediting progress to the turn where it occurs.” Its main evidence is the comparison between ProCredit and GRPO-Φ\Phi, an ablation introduced by this paper. The two methods use the same filtered checks and the same trajectory score, while ProCredit additionally uses

Ai,tturn=Gi,t−1∣Ug∣∑(j,v)∈UgGj,v.A_{i,t}^{\mathrm{turn}} =G_{i,t} -\frac{1}{|U_g|}\sum_{(j,v)\in U_g}G_{j,v}.

This comparison shows that adding the complete turn-level estimator is useful under the paper's configuration. It does not isolate temporal placement of progress as the cause.

It is also unclear from the paper why AturnA^{turn} helps in theory. Also, why use both AtrajA^{traj} and AturnA^{turn}? Why not use $A^{turn} $ alone?

Questions for authors

I don't have questions for authors.

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

This paper introduces ProCredit, which uses verifiable outcome rewards into per-turn progress credit by rerunning acceptance checks on intermediate states and rewarding each turn by its change in progress. The resulting progress rewards are used to assign credit across attempts at the same task and turns within each trajectory. Evaluations on Qwen3.5 at three different model scales (4B, 9B, 35B) on AppWorld, ToolSandbox, and BFCL show that ProCredit outperforms outcome-reward and progress-reward baselines.

Critical strengths

The proposed method is intuitive, and the presentation is generally well-written and easy to follow. The experiments demonstrate that ProCredit outperforms baselines on tool-use benchmarks where task completion requires multiple turns of tool use with verifiable task progress.

Critical weaknesses

ProCredit relies on verifiable acceptance checks for tasks that can be run after each turn given access to intermediate states of tasks, and the evaluations cover only tool use environments. The authors should consider discussing limitations of the proposed work, for instance on domains which may not have concrete progress or acceptance checks, such as formal math.

Questions for authors
  • What is the wall-clock cost of rerunning acceptance checks at every turn compared to final outcomes?

  • L215: What is the effect of not setting terminal potentials to zero like in PBRS? Would such a formulation also work for ProCredit?

  • L269: Is this criteria a valid reason for excluding the remaining 28 tasks? Are there difficult tasks with only 1 milestone that ProCredit is unable to solve, but outcome-based methods are?

  • Section 4.3.1: It would be helpful to provide some intuition for why turn progress outperforms token progress credit granularity?

Reviewer_nKatOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work pays attention to progress credit in reinforcement learning from the perspective of unsuccessful trajectories. The authors propose ProCredit, which uses executable task acceptance checks to measure progress at intermediate environment states. The central idea is that appropriately selected interventions can induce user behaviors that are more informative for distinguishing between competing preference hypotheses. The method combines two levels of advantage estimation: a trajectory-level advantage that compares different attempts at the same task and a turn-level advantage that assigns credit according to the remaining return from each turn. Experiments demonstrate improvements over several outcome-based and progress-based reinforcement learning baselines.

Critical strengths
  1. Simple and practical method. ProCredit reuses existing acceptance checks to provide intermediate rewards without training an additional reward model.

  2. Useful experimental analysis. The ablations help isolate the contribution of turn-level credit assignment, and the analysis of discount factors provides interesting insights into long-horizon RL.

Critical weaknesses
  1. Insufficient baselines. Although the paper compares several baselines, the comparison with existing progress-based reward and credit assignment methods is still limited. In particular, recent approaches such as SPA-RL, VPR, and MT-GRPO are not included. Comparisons with these methods would help better establish the effectiveness of ProCredit.

  2. Limited applicability of progress measurement. The method assumes that task progress can be measured by the fraction of satisfied acceptance checks. This may not reflect actual progress when subtasks have dependencies or different levels of importance.

  3. Unclear effectiveness of credit assignment. According to Eq. (11), turns without immediate progress receive the same advantage as the following turn. It is unclear whether the method can distinguish necessary preparatory actions from redundant ones.

  4. Modest improvements at larger scales. The gains over strong baselines become relatively small for larger models. For example, ProCredit improves TGC by only 0.2 points over RLOO on AppWorld Test-Normal at 35B, making the significance of some improvements unclear.

Questions for authors

Please see the Critical Weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.