PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ming Ma, Yi Zhu, Yiran Zhong, Feida Zhu, Chonghan Liu, Pengkun Jiao, Qichao Wang, Yanhao Jia, Tianming Yang, Steven Hoi

arXiv:2609.27532v2cs.LGcs.CL

TL;DR

Outcome-only rewards lose information about failed attempts’ progress and about which turns advance a task. ProCredit uses acceptance checks on intermediate states to assign progress-based credit across attempts and turns. It achieves the highest task completion rate at every tested scale on both AppWorld test sets, and the reported ablations attribute the gain to crediting progress where it occurs.

  • Problem

    Outcome-only rewards provide no advantage in all-fail groups, do not distinguish failed attempts by progress, and give advancing turns the same credit as queries.

    Source: §1 · pp. 1–2

  • Method

    ProCredit reruns acceptance checks after each turn, rewards changes in the fraction passed, and uses those rewards for trajectory-level and turn-level credit.

    Source: §1 · p. 2

  • Results

    ProCredit achieves the highest TGC at all three model sizes on both AppWorld test sets; at 4B, its margin over the strongest outcome-only method is 4.1 TGC points on test-normal.

    Source: §1 · p. 3, §4.2 · p. 8

  • Takeaways & Limitations

    Adding progress only to trajectory scores does not improve performance; the reported gain comes from crediting progress at the turn where it occurs.

    Source: §1 · p. 3, §4.2 · p. 8

    The current progress measure treats checks as equally weighted and unordered.

    Source: §5 · p. 11

Abstract

from arXiv · show

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.

1. Introduction

Outcome-only rewards discard how much progress failed attempts make and when turns make it. ProCredit verifies intermediate progress using acceptance checks and assigns credit across attempts and turns; it achieves the highest task completion rate at every tested scale on both AppWorld test sets.

1. Introduction

  • Outcome-only rewards give all-fail groups zero advantage, treat failed attempts with different progress alike, and give advancing turns the same advantage as querying turns.This loses information about both how much progress was made and when it occurred.Source: §1 · pp. 1–2
  • Step-level comparisons still rely on final success, while learned intermediate rewards are estimates; executable acceptance checks can instead verify progress on intermediate states.This avoids requiring a separate model to supply the progress signal.Source: §1 · p. 2
  • ProCredit reruns task acceptance checks after each turn, rewards changes in the fraction passed, and uses the rewards to assign credit across attempts and within trajectories.The checks are used during training; a turn that advances the task receives more credit than turns after it.Source: §1 · p. 2
  • ProCredit achieves the highest task completion rate at every tested scale on both AppWorld test sets, including one with applications unseen in training.The direction also holds on ToolSandbox, and function calling on BFCL does not decline.Source: §1 · pp. 2–3

2. Related work

Related work supplies intermediate training signals through learned models, policy-derived signals, checklists, reference trajectories, or verifiers, and refines credit assignment through turn rewards, value functions, or comparisons across states. ProCredit derives its signal from the task’s acceptance checks and uses it to compare progress without requiring matching states across trajectories.

Reinforcement learning for long-horizon agentic tasks

  • Prior group-based reinforcement-learning methods compare trajectories sampled for the same task using rewards provided mainly at the end.ProCredit retains the environment setting and optimization objective while changing where reward is read.Source: §2 · p. 3

Sources of intermediate signals

  • Intermediate signals may come from learned reward models or critics, policy belief updates, language-model checklists, reference trajectories, or verifiers.ProCredit reruns full acceptance checks after each turn and derives rewards from observed progress changes, without annotations, reward models, or reference trajectories.Source: §2 · p. 3

Credit assignment in group-based reinforcement learning

  • Group-based methods often share one trajectory advantage across all turns, while state-grouping approaches redistribute outcome rewards and rely on recurring states across trajectories.Hand-designed turn rewards require environment-specific redesign, and value functions provide learned estimates.Source: §2 · p. 3

3. Method: ProCredit

ProCredit keeps task-level outcome rewards but adds progress-based rewards and two levels of credit. It measures progress using acceptance checks on environment states, compares trajectory scores across attempts, and uses onward returns to distinguish turns within trajectories.

3. Method: ProCredit

  • ProCredit checks the environment after each tool-execution turn and combines a trajectory-level advantage with a turn-level advantage in the policy update.The trajectory term compares attempts at the same task; the turn-level term uses returns from individual turns onward.Source: §3 · pp. 3–4

3.1. Preliminaries

  • Each attempt consists of action generation, tool execution, and observation, and ends when completion is declared or the turn limit is reached.The environment then assigns an outcome reward of 0 or 1; GRPO uses the same advantage for every turn in a trajectory.Source: §3.1 · pp. 4–5

3.2. Verifiable task progress

  • Task progress is the fraction of executable acceptance checks passed in the current environment state.Progress depends on state changes: queries leave it unchanged, modifications can raise it, and incorrect modifications can reduce it by invalidating passed checks.Source: §3.2 · p. 5

3.3. Progress rewards and two levels of credit

  • Turns receive positive, negative, or zero rewards when they advance, undo, or leave progress unchanged; the trajectory score combines outcome reward with summed progress rewards.Turn-level credit uses the return from that turn onward; ProCredit uses undiscounted returns and centers them across all turns sampled for the task.Source: §3.3 · pp. 5–6

4. Experiments

Across AppWorld test sets, ProCredit leads in task completion at every model scale, and its turn-level credit outperforms alternatives that use the same progress signal. Analysis and ablations also examine credit granularity, discounting, failed-attempt progress, and responses to tool feedback.

4.1. Experimental setup

  • AppWorld trains on 90 tasks and evaluates test-normal (168 tasks) and test-challenge (417 tasks), using Qwen3.5 4B, 9B, and 35B models from base checkpoints.Comparisons are within model size; results are means and standard deviations over three independent runs.Source: §4.1 · pp. 6–8

4.2. Main results

  • ProCredit achieves the highest TGC at all three sizes on both AppWorld test sets, with a 4.1-point test-normal margin over the strongest outcome-only method at 4B.Its SGC is highest in every column except 35B test-normal, where DAPO is slightly higher.Source: Table 1 · p. 7, §4.2 · p. 8
  • Against GRPO-Φ, ProCredit's test-normal TGC gains are 6.1, 3.4, and 2.2 points at 4B, 9B, and 35B, respectively.The methods assign the same score to a given trajectory and differ only in the turn-level term.Source: Table 1 · p. 7, §4.2 · p. 8
  • ProCredit outperforms GRPO at each model size on ToolSandbox, while its BFCL function-calling scores remain close to the base models.ToolSandbox results are success rates; BFCL evaluates single-turn and multi-turn function calling.Source: Table 2 · p. 8, §4.2 · p. 8

4.3.1. Rewards and credit assignment

  • ProCredit (turn) exceeds ProCredit (token) in TGC by 8.3 points at 4B and 3.6 points at 9B, with larger gaps in SGC.The token variant spreads the same turn progress reward across token positions without token-level environmental feedback.Source: Table 3 · p. 9, §4.3.1 · p. 9

4.3.2. Discount factor

  • Moving ProCredit from γ = 0.95 to γ = 1 raises TGC by approximately 3, 10, and 13 points at 4B, 9B, and 35B, respectively.The reported gap grows with model size; GiGPO also scores higher without discounting at 9B and 35B but remains below ProCredit.Source: Table 3 · p. 9, §4.3.2 · p. 9

4.4. Analysis

  • 54.9% and 38.6% of all-fail groups at 4B and 9B contain distinguishable progress differences, providing ProCredit signals unavailable to outcome-only rewards.In mixed groups, progress-based methods produce more-complete failed trajectories than GRPO early in training; ProCredit remains higher later.Source: Figure 3 · p. 10, §4.4 · p. 10
  • Compared with GRPO, trained models have lower output entropy after task-advancing turns while preserving the entropy increase after errors.The paper reports entropy curves and results at all three model sizes in Appendix A.Source: §4.4 · p. 10

5. Discussion

ProCredit depends on verifiable progress at intermediate states, and its turn-level signal is most useful when checks distinguish progress across turns. Its scope is bounded by the available checks and by the information progress can recover.

5. Discussion

  • ProCredit requires accessible environment states and acceptance checks that can be rerun at intermediate states.AppWorld unit tests and ToolSandbox milestones are examples; coding tests and tasks evaluated by final database state may also fit.Source: §5 · p. 10
  • With only one or two checks, or checks passed only on the final turn, turn-level credit is constant within a trajectory and ProCredit reduces to GRPO-style trajectory comparison.The checks determine the granularity of progress that turn-level credit can distinguish.Source: §5 · p. 11
  • Progress must be determined from the environment state, since rewarding a model’s own dense predictions can improve those predictions without increasing task success.ProCredit reads progress from changes to the environment state.Source: §5 · p. 11
  • Gains narrow at larger model sizes, where fewer all-fail groups and failed attempts leave less missing information for progress to recover.The current measure is the equally weighted, unordered fraction of passed checks; future work targets larger models, harder environments, and environments with intermediate checks.Source: §5 · p. 11

6. Conclusion

ProCredit uses verified intermediate progress to assign both trajectory-level and turn-level credit. It achieves the highest task completion rate at three model sizes on both AppWorld test sets, and the reported ablations locate the benefit in crediting progress when it occurs.

6. Conclusion

  • ProCredit achieves the highest task completion rate at three model sizes on both AppWorld test sets, including applications unseen in training.The benefit comes from turn-level crediting: adding final progress only to trajectory scores or spreading it over tokens does not improve performance, while discounting early-turn credit reduces it.Source: §6 · p. 11
  • ProCredit reruns acceptance checks on intermediate states and uses environment-state progress changes to assign trajectory-level and turn-level credit.The same progress signal is used to compare attempts and to distinguish turns within an attempt.Source: §6 · p. 11
  • Adding progress only to trajectory scores or moving to token-level credit does not improve performance, while discounting credit for early turns reduces it.The conclusion attributes the benefit to crediting progress to the turn where it occurs.Source: §6 · p. 11

A. Output entropy after tool feedback

The appendix analyzes output entropy after tool feedback at 4B, 9B, and 35B, comparing feedback types and training conditions. The reported entropy differences vary by output position, model size, and training method.

A. Output entropy after tool feedback

  • Entropy is computed over the first 120 output tokens at temperature 1, and curves are averaged within trajectories, tasks, and three equally weighted seeds.The analysis classifies feedback as tool errors, progress without errors, or unchanged progress without errors; shading shows sample standard deviation across seeds.Source: A. Output entropy after tool feedback · p. 15
  • At 4B, the middle-segment progress-minus-ordinary entropy difference is −0.093 ± 0.014 for ProCredit and −0.025 ± 0.019 for GRPO.All three ProCredit seeds have lower values than all three GRPO seeds; Figure A1 compares entropy after tool feedback before training, after GRPO, and after ProCredit.Source: A. Output entropy after tool feedback · p. 15, Figure A1 · p. 15
  • At 9B, the middle-segment progress-minus-ordinary difference is −0.062 ± 0.011 for ProCredit and −0.037 ± 0.041 for GRPO.The entropy increase after errors is concentrated at earlier positions and approaches ordinary-turn levels toward the end; Figure A2 shows the feedback curves across training conditions.Source: A. Output entropy after tool feedback · p. 16, Figure A2 · p. 16
  • At 35B, the middle-segment progress-minus-ordinary difference changes from −0.029 ± 0.022 before training to −0.080 ± 0.019 under ProCredit.The end-segment error-minus-ordinary difference changes from +0.080 ± 0.021 to +0.017 ± 0.010; Figure A3 compares entropy after tool feedback across training conditions.Source: A. Output entropy after tool feedback · p. 16, Figure A3 · p. 17

B. A worked credit example for the alarm task

The alarm-task example illustrates how ProCredit scores trajectories and assigns credit to individual turns based on progress. Its turn-level credits decline after progress and distinguish trajectories by their completion.

B. A worked credit example for the alarm task

  • The trajectory scores for A, B, and C are 0, 0.333, and 1.5, with trajectory-level advantages −0.776, −0.353, and +1.129.A and B both fail, but their scores differ according to completion.Source: B. A worked credit example for the… · p. 17
  • Across trajectories, every turn in C has higher total credit than any turn in B, and every turn in B has credit at least as high as those in A.The example uses three checks: set the wake-up alarm to 06:00, disable Gym, and disable Work.Source: B. A worked credit example for the… · p. 17, Table B1 · p. 18
  • After each progress turn, the next turn’s credit decreases by exactly the progress reward just earned, 0.167.Reading the alarm list and the following progress turn receive equal credit because they have the same remaining progress to earn.Source: B. A worked credit example for the… · p. 17

C. How discounting penalizes long trajectories

Discounting reduces earlier turns’ credit when later rewards are delayed, creating a length tax. The section illustrates how this affects successful trajectories and their turn-level credit.

C. How discounting penalizes long trajectories

  • 5% per added turn at γ = 0.95, but no reduction at γ = 1, in earlier turns’ credit from rewards yet to arrive.The reduction depends on the number of turns, regardless of what an inserted turn does.Source: C. How discounting penalizes long… · p. 18
  • In an all-success group, trajectory scores tie, so the turn-level term supplies the only within-group signal.Each trajectory has R = 1 and ΦT = 1.Source: C. How discounting penalizes long… · p. 18
  • At γ = 0.95, the shortest trajectory has the highest average turn-level credit in 94.1%, 94.2%, and 91.9% of all-success groups at 4B, 9B, and 35B.Recomputing credit on the same trajectories with γ = 1 reduces those proportions to 5.0%, 6.3%, and 15.5%.Source: C. How discounting penalizes long… · p. 19
  • At γ = 1, the two illustrative trajectories have the same three-level return staircase; at γ = 0.95, the longer trajectory receives less return at each progress stage.The trajectories take 8 and 16 turns, with each progress event in the longer trajectory occurring at twice the turn index.Source: C. How discounting penalizes long… · p. 19, Figure C1 · p. 19

D. Complete comparisons of group-dependent variants

The variants alter discounting or turn-level credit for selected sampled groups while retaining the trajectory-level term. Their comparisons show that the main method’s turn-level credit and group-wide γ = 1 setting outperform or match the tested alternatives.

D. Complete comparisons of group-dependent variants

E. Learning dynamics

ProCredit’s development success exceeds GRPO-Φ at later training stages, with reported gains on held-out tasks and under a fixed training-time budget. BFCL scores remain close to base-model scores within the evaluated categories.

E. Learning dynamics

  • By later training stages, development success rises from 64.6% to 70.4% at 4B and from 77.1% to 80.1% at 9B versus GRPO-Φ.GRPO-Φ matches or exceeds ProCredit’s training success at some steps, but these gains do not carry over to development success.Source: E. Learning dynamics · p. 21, Figure E1 · p. 21
  • Under a six-hour budget, 4B ProCredit achieves 70.39% mean success, compared with 61.99% for GRPO and 64.55% for GRPO-Φ.The comparison uses each run’s latest evaluated checkpoint available within the budget.Source: E. Learning dynamics · p. 21, Figure E2 · p. 22

F. Retention of BFCL capabilities

  • BFCL single-turn AST scores differ from base models by less than 1 percentage point and multi-turn scores by less than 2 points after AppWorld training.The evaluation covers non-live single-turn AST and four multi-turn subcategories; other categories are excluded from aggregate scores.Source: F. Retention of BFCL capabilities · p. 22, Table F1 · p. 22

G. Two properties of the trajectory score

The trajectory score preserves a strict successful-over-failed ordering and, for solvable tasks, shares success-probability maximizers. The section also explains the pooled turn reference, contrasts state-based grouping, and lists training settings.

G. Two properties of the trajectory score

  • For any c > 0, every successful trajectory has a strictly higher score than every failed trajectory for the same task.The proof gives a score difference of at least 1, independently of c.Source: G. Two properties of the trajectory… · pp. 22–23
  • When a task is solvable with probability 1, policies maximizing expected trajectory score are exactly those maximizing success probability.For unsolvable tasks, expected score trades success probability against partial completion at a rate set by c.Source: G. Two properties of the trajectory… · p. 23

H. Why turns with different histories can share one reference value

  • The turn-level term subtracts the mean return across all turns for the task; turns from other trajectories provide a valid baseline because their actions are sampled independently.Using the pooled mean rather than a turn’s leave-one-trajectory-out baseline adds a bounded correction of order 1/N.Source: H. Why turns with different histories… · p. 23
  • State-based grouping uses the mean for turns at the same progress state, but does not outperform ProCredit at any model size.It can leave credit for reaching a good state to earlier turns, while passed-check anchors omit database contents and recent actions.Source: H. Why turns with different histories… · p. 24

I. Training settings

  • Training length limits and GPU counts grow with model size; ToolSandbox settings differ from AppWorld in tasks per step, training steps, and turn limit.Baselines use hyperparameters from their original papers.Source: §I · p. 24, Table I1 · p. 24
Loading 2609.27532v2…