Organizations: Zhejiang University · School of Engineering, Westlake University · Huawei Noah’s Ark Lab · Institute of Advanced Technology, Westlake Institute for Advanced Study
Reinforcement learning (RL) has emerged as the primary paradigm for optimizing Large Language Model (LLM) agents, yet efficient critic-free algorithms (e.g., GRPO) suffer from a fundamental uniform credit assignment dilemma that broadcasts trajectory-level advantages equally to all actions. Our analysis reveals that this uniformity inherently reinforces structurally invalid actions in preferred trajectories and ignores the downstream cascading influence of early pivotal deviations in unpreferred ones. To resolve this without introducing critic overhead, we propose Progress-Aware Advantage Shaping (ProAS), a plug-and-play framework that leverages a dynamically evolving Agentic Reference Graph (ARG) to achieve fine-grained credit assignment via Masking Unreasonable Incentives (MUI) and Asymmetric Penalty Redistribution (APR). Extensive experiments across Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct demonstrate that ProAS universally elevates mainstream group-based baselines to new state-of-the-art performance, achieving peak success rates of 91.9% and 94.3% on ALFWorld, alongside 66.7% and 70.8% on WebShop, respectively. Furthermore, it accelerates training convergence by up to 2.44× while maintaining strong robustness against imperfect or distilled ARGs. Codes: https://github.com/LINs-lab/ProAS.
Figures & tables
Figure 1: (a) The demonstration of ARG. Diverse successful trajectories are unified into a DAG that serves as a progress reference. (b) Probing unreasonable actions. From an identical state, the counterpart injected with unreasonable actions yields a lower Expected Success Rate (ESR) on 50 sampled continuations {ci}i=150 . (c) Suppressing by Future-Drift (FD). Forcibly suppressing the original action at different trajectory points and resampling 50 continuations shows recovered ESR rises with the suppressed action’s FD.
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
ALL
Spd.@70
TS
SR
Spd.@50
Proprietary Model
GPT-5.6-Sol (ReAct)
90.9
83.3
68.0
83.3
79.2
68.2
78.9
–
27.6
21.9
–
Qwen2.5-1.5B-Instruct
Direct Prompt
24.2 ± 0.0
25.0 ± 0.0
4.0 ± 0.0
8.3 ± 0.0
0.0 ± 0.0
4.5 ± 0.0
10.9 ± 0.0
–
25.3 ± 0.0
4.7 ± 0.0
–
SFT
99.0 ± 1.4 *
91.7 ± 6.8
94.7 ± 1.9
100.0 ± 0.0 *
93.1 ± 1.9 *
1.5 ± 2.1
79.7 ± 0.7
–
78.2 ± 1.4
64.3 ± 2.4
–
Table 1: Main results on ALFWorld and WebShop. ALFWorld reports success rates (%) for six task types and all tasks; WebShop reports task score and success rate (%). Boldface indicates that the ProAS framework improves over its corresponding base RL algorithm, while a superscript ∗ marks the best value within the corresponding model-size block.
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
ALL
TS
SR
GRPO
80.8 ± 4.6
69.4 ± 4.8
70.7 ± 6.1
75.0 ± 8.3
63.9 ± 9.6
59.1 ± 9.1
70.3 ± 2.8
82.4 ± 1.3
57.0 ± 3.1
GRPO + ProAS
90.9 ± 5.2 *
86.1 ± 4.8 *
90.7 ± 2.3
91.7 ± 8.3 *
83.3 ± 4.2 *
78.8 ± 5.2
87.0 ± 2.3 *
85.3 ± 2.4 *
64.6 ± 1.2
(a) Advantage Shaping Ablation
GRPO + ProAS -
83.8 ± 9.7
52.8 ± 19.2
78.7 ± 8.3
77.8 ± 9.6
63.9 ± 19.2
60.6 ± 5.2
71.6 ± 10.4
83.6 ± 0.5
63.3 ± 7.7
GRPO + ProAS +
86.9 ± 1.7
83.3 ± 8.3
85.3 ± 6.1
88.9 ± 12.7
76.4 ± 2.4
80.3 ± 2.6 *
83.3 ± 1.8
84.1 ± 2.1
64.6 ± 1.8
Table 2: Ablation study with Qwen2.5-1.5B-Instruct. ALFWorld reports success rates (SR, %) for six task types and all tasks; WebShop reports task score (TS, %) and success rate (SR, %). Training results are the mean and sample standard deviation over three seeds. Values higher than the GRPO baseline are shown in bold; a superscript ∗ marks the best mean in each column.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Task family
Training seed 0
Training seed 1
Training seed 2
Validation
Pick
391
392
399
33
Look
161
162
162
12
Clean
315
311
310
25
Heat
249
241
239
12
Cool
262
268
266
24
Pick2
399
393
408
22
Appendix
Table 5: ALFWorld task-family counts in the frozen training sets and validation set. Each training column counts unique game instances within one seed. Validation contains 128 distinct tasks shared across seeds.
Task category
Training seed 0
Training seed 1
Training seed 2
Validation
Fashion
1570
1568
1577
95
Garden
294
291
283
23
Electronics
57
53
57
6
Grocery
37
37
39
2
Beauty
57
62
80
2
Total
2015
2011
2036
128
Appendix
Table 6: WebShop task-category counts in the frozen training sets and validation set. Each training column counts unique base tasks within one seed. Validation contains 128 distinct tasks shared across seeds.
Figure 2: Validation success rate curves on ALFWorld and WebShop within 150 RL steps. Dashed horizontal lines mark the fixed success rate targets used for computing training speedup: 70 points for ALFWorld and 50 points for WebShop. Black double arrows indicate the speedup of each base algorithm after adding ProAS.
Case setup
Task
Put a keychain on a desk.
Labels
Reat=1 denotes an ARG-supported transition, and PAt=1 denotes advancement to a previously unvisited ARG state.
Task ARG
ARG
g1 sidetable reached take keychain 2g2 keychain held go to desk 1g3 desk reached while holding the keychain move keychain 2 to desk 1g4 success.
Initial edge
The initial transition go to sidetable 1 enters g1 .
Clean condition
Appendix
Table 7: An ALFWorld case illustrating the effect of unreasonable actions in the context. The clean and noise-injected conditions reach the same continuation state. Each condition contains 50 independently sampled continuations. Only the injected unreasonable actions are highlighted in pink.
Case setup
Task
Look at a bowl under the desk lamp.
Labels
Reat=1 denotes an ARG-supported transition, and PAt=1 denotes advancement to a previously unvisited ARG state. FD counts the current non-advancing action and all subsequent non-advancing actions in the original trajectory.
Intervention
At the selected decision, an exact match to the original action is rejected and that decision is resampled; all other candidate actions remain eligible.
Task ARG
ARG
Initial state go to desk 1g1 desk reached take bowl 1/2g2 target bowl held use desklamp 1g3 success.
Raw trajectory
Appendix
Table 8: An ALFWorld case comparing exact-action suppression at four positions in the same failed rollout. Action indices are 1-based and Future-Drift (FD) is the inclusive suffix count of non-advancing actions. Repeated non-advancing spans are compressed. Each intervention preserves the original prefix, suppresses only the exact original action at the selected position, and independently samples 50 continuations.
Case setup
Task
Look at a pencil under the desk lamp.
Source
Qwen2.5-1.5B-Instruct rollout at training iteration 17; success; reward =10 .
G(17)
Existing expert path: initial state go to desk 1g1 desk reached use desklamp 1g2 desk lamp activated take pencil 2 from desk 1g3 success.
Labels
Reat=1 denotes a transition supported by G(17) , and PAt=1 denotes advancement to a previously unvisited ARG state. The update decision is applied only after environment-verified success.
Raw successful rollout and ARG annotations
t
Action at
Annotation under G(17)
Reat
PAt
Purification
Appendix
Table 9: An ALFWorld case illustrating strict ARG purification and online graph evolution. The action-level annotations are computed against the pre-update graph G(17) . After the rollout succeeds, only its valid, non-self-loop transitions are extracted as a new reference path and merged into G(18) .
Case setup
Task
Find women’s activewear with nylon spandex, color=green , size=x-large , and price below $30.
Reat=1 denotes an ARG-supported transition, and PAt=1 denotes entry into a previously unvisited valid ARG state. Thus, (1,1) is productive, (1,0) is reasonable but non-advancing, and (0,0) is unsupported.
Rollout comparison
Trajectory
t
Action at
ARG annotation
Reat
PAt
Appendix
Table 10: A WebShop case illustrating order-invariant option completion and action-level ProAS annotations. Trajectories A and B complete the option sub-goal in different orders and both succeed; Trajectory C shows a failed rollout with unreasonable or non-advancing actions.
Table 11: A turn-level SFT example from ALFWorld. Underlined text denotes instance-specific fields populated from the task, environment state, and interaction history.
Table 12: A turn-level SFT example from WebShop. Underlined text denotes instance-specific fields populated from the task, environment state, and interaction history.
Process reward models enable fine-grained, step-level evaluation of LLMs, yet building them for agentic settings remains prohibitively difficult: long-horizon interactions, irreversible actions, and stochastic environment feedback make both human annotation and Monte Carlo estimation infeasible at scale. In this work, we show that reinforcement learning (RL) post-training already provides the ingredients for effective step-level scoring, eliminating the need for dedicated reward model training altogether. Concretely, we derive an implicit advantage under a general stochastic Markov decision process, which we term progress advantage -- log-probability ratio between the RL-trained policy and its reference policy exactly recovers the optimal advantage function. This formulation makes the resulting signal annotation-free, domain-agnostic, and available as a byproduct of the standard RL post-training pipeline. We validate the effectiveness of the progress advantage across three different applications: test-time scaling, uncertainty quantification, and failure attribution on five benchmarks and four model families. Across all settings, it consistently outperforms confidence-based baselines and, despite requiring no task-specific training, surpasses dedicated trained reward models. We complement these results with deeper analyses on characteristics of progress advantage, offering practical guidance for adoption in real-world agentic systems.
Changdae Oh, Wendi Li, Seongheon Park +3
University of Wisconsin–Madison · Argonne National Laboratory
Group Relative Policy Optimization (GRPO) has become a promising approach for training large language model agents. However, its uniform assignment of trajectory-level advantages to all policy tokens fails to distinguish consequential decisions from less relevant ones, obscuring which intermediate decisions contributed to success. We introduce ProVer, a framework that targets potentially pivotal decisions for fine-grained credit assignment in agentic reinforcement learning. Given a rollout group, an agentic judge contrasts successful and failed trajectories to propose a segment potentially responsible for their divergent outcomes. Rather than directly trusting the judge's assessment, ProVer verifies the proposed segment by estimating its advantage from the difference in terminal success rates between current-policy continuations sampled before and after the segment. Positive estimates are then incorporated into the GRPO advantages of policy tokens within the proposed segment. By using model judgment only to select where to verify, ProVer grounds local credit in observed outcomes without exhaustively evaluating every intermediate state. Across ALFWorld, WebShop, and SearchQA, ProVer achieves the strongest average performance at both model scales, with relative improvements over GRPO of 9.91% and 7.12% for Qwen3.5-2B and Qwen3.5-4B, respectively. Further analyses demonstrate that informed segment selection improves policy training with modest additional generation overhead, even without a frontier-scale judge model, highlighting the effectiveness and efficiency of selectively targeting pivotal decisions for fine-grained credit assignment in agentic reinforcement learning.
Dongwon Jung, Hemanth Neelgund Ramesh, Yifan Wang +7
University of California, Davis · Microsoft · University of Washington
Group-based reinforcement learning (RL) has become an effective paradigm for improving large language model agents on long-horizon interactive tasks. To obtain finer-grained policy updates than trajectory-level optimization, recent work has moved toward step-level group-based RL, where intermediate steps are grouped and compared within a rollout batch. However, step-level advantage estimation is sensitive to how groups are formed: grouping by broad state keys improves coverage but may compare actions taken under different histories, while enforcing historical consistency yields fairer comparisons at the cost of fragmented groups and missing peer-comparison signal. In this paper, we propose ProGPO (Progress- and Reliability-Oriented Group Policy Optimization), a learned-critic-free method for context-consistent step-level learning. ProGPO keeps exact-prefix action comparison, and complements sparse peer comparisons with transition credit derived from rollout-based state potentials. To estimate these potentials reliably, ProGPO combines semantic expansion with inverse-variance fusion across history depths. We evaluate ProGPO on two challenging agentic tasks, ALFWorld and WebShop, with Qwen2.5-1.5B-Instruct. Results show that ProGPO improves over matched agentic RL baselines under comparable computational overhead, and additional Qwen2.5-3B-Instruct experiments further test the scalability of the proposed method.