ProAS: A Progress-Aware Advantage Shaping Framework for Multi-Turn Agentic Reinforcement Learning

Bowen Ding; Mingda Wan; Yuhan Chen; Jiyao Yuan; Qi Zhu; Futing Wang; Heyuan Deng; Fei Mi

cs.LGOct 13, 2026

ProAS: A Progress-Aware Advantage Shaping Framework for Multi-Turn Agentic Reinforcement Learning

Authors: Bowen Ding, Mingda Wan, Yuhan Chen, Jiyao Yuan, Qi Zhu, Futing Wang, Heyuan Deng, Fei Mi,

Organizations: Zhejiang University · School of Engineering, Westlake University · Huawei Noah’s Ark Lab · Institute of Advanced Technology, Westlake Institute for Advanced Study

Abstract

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\times$ 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 $\{c_{i}\}_{i=1}^{50}$ . (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
Method	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 $\pm$ 0.0	25.0 $\pm$ 0.0	4.0 $\pm$ 0.0	8.3 $\pm$ 0.0	0.0 $\pm$ 0.0	4.5 $\pm$ 0.0	10.9 $\pm$ 0.0	–	25.3 $\pm$ 0.0	4.7 $\pm$ 0.0	–
SFT	99.0 $\pm$ 1.4 *	91.7 $\pm$ 6.8	94.7 $\pm$ 1.9	100.0 $\pm$ 0.0 *	93.1 $\pm$ 1.9 *	1.5 $\pm$ 2.1	79.7 $\pm$ 0.7	–	78.2 $\pm$ 1.4	64.3 $\pm$ 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
Method	Pick	Look	Clean	Heat	Cool	Pick2	ALL	TS	SR
GRPO	80.8 $\pm$ 4.6	69.4 $\pm$ 4.8	70.7 $\pm$ 6.1	75.0 $\pm$ 8.3	63.9 $\pm$ 9.6	59.1 $\pm$ 9.1	70.3 $\pm$ 2.8	82.4 $\pm$ 1.3	57.0 $\pm$ 3.1
GRPO + ProAS	90.9 $\pm$ 5.2 *	86.1 $\pm$ 4.8 *	90.7 $\pm$ 2.3	91.7 $\pm$ 8.3 *	83.3 $\pm$ 4.2 *	78.8 $\pm$ 5.2	87.0 $\pm$ 2.3 *	85.3 $\pm$ 2.4 *	64.6 $\pm$ 1.2
(a) Advantage Shaping Ablation
GRPO + ProAS -	83.8 $\pm$ 9.7	52.8 $\pm$ 19.2	78.7 $\pm$ 8.3	77.8 $\pm$ 9.6	63.9 $\pm$ 19.2	60.6 $\pm$ 5.2	71.6 $\pm$ 10.4	83.6 $\pm$ 0.5	63.3 $\pm$ 7.7
GRPO + ProAS +	86.9 $\pm$ 1.7	83.3 $\pm$ 8.3	85.3 $\pm$ 6.1	88.9 $\pm$ 12.7	76.4 $\pm$ 2.4	80.3 $\pm$ 2.6 *	83.3 $\pm$ 1.8	84.1 $\pm$ 2.1	64.6 $\pm$ 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	$\text{Rea}_{t}=1$ denotes an ARG-supported transition, and $\text{PA}_{t}=1$ denotes advancement to a previously unvisited ARG state.
Task ARG
ARG	$\textbf{g}_{1}$ sidetable reached $\xrightarrow{\ \texttt{take keychain 2}\ }$ $\textbf{g}_{2}$ keychain held $\xrightarrow{\ \texttt{go to desk 1}\ }$ $\textbf{g}_{3}$ desk reached while holding the keychain $\xrightarrow{\ \texttt{move keychain 2 to desk 1}\ }$ $\textbf{g}_{4}$ success.
Initial edge	The initial transition go to sidetable 1 enters $\textbf{g}_{1}$ .
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	$\text{Rea}_{t}=1$ denotes an ARG-supported transition, and $\text{PA}_{t}=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 $\xrightarrow{\ \texttt{go to desk 1}\ }$ $\textbf{g}_{1}$ desk reached $\xrightarrow{\ \texttt{take bowl 1/2}\ }$ $\textbf{g}_{2}$ target bowl held $\xrightarrow{\ \texttt{use desklamp 1}\ }$ $\textbf{g}_{3}$ 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$ .
$\mathcal{G}^{(17)}$	Existing expert path: initial state $\xrightarrow{\ \texttt{go to desk 1}\ }$ $\textbf{g}_{1}$ desk reached $\xrightarrow{\ \texttt{use desklamp 1}\ }$ $\textbf{g}_{2}$ desk lamp activated $\xrightarrow{\ \texttt{take pencil 2 from desk 1}\ }$ $\textbf{g}_{3}$ success.
Labels	$\text{Rea}_{t}=1$ denotes a transition supported by $\mathcal{G}^{(17)}$ , and $\text{PA}_{t}=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 $a_{t}$	Annotation under $\mathcal{G}^{(17)}$	$\text{Rea}_{t}$	$\text{PA}_{t}$	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

\mathcal{G}^{(17)}

. After the rollout succeeds, only its valid, non-self-loop transitions are extracted as a new reference path and merged into

\mathcal{G}^{(18)}

Case setup
Task	Find women’s activewear with nylon spandex, color=green , size=x-large , and price below $30.
Target	B08G8DXR5N
ARG	$\textbf{g}_{1}$ target visible $\rightarrow$ $\textbf{g}_{2}$ target opened $\rightarrow$ $\textbf{g}_{3}$ options { green , x-large } $\rightarrow$ $\textbf{g}_{4}$ price verified $\rightarrow$ $\textbf{g}_{5}$ attributes verified $\rightarrow$ $\textbf{g}_{6}$ purchase.
Labels	$\text{Rea}_{t}=1$ denotes an ARG-supported transition, and $\text{PA}_{t}=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 $a_{t}$	ARG annotation	$\text{Rea}_{t}$	$\text{PA}_{t}$

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.

Panel of Table 11 — Table 11: A turn-level SFT example from ALFWorld. Underlined text denotes instance-specific fields populated from the task, environment state, and interaction history.

Panel of Table 12 — Table 12: A turn-level SFT example from WebShop. Underlined text denotes instance-specific fields populated from the task, environment state, and interaction history.

Agentic RL

Agentic reinforcement learning trains AI agents to plan, use tools, and adapt through feedback from multi-step interactions.

See all 231 papers

Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents
Jun 24, 2026Changdae Oh, Wendi Li, Seongheon Park +3Process Reward Models RL Post-Training
University of Wisconsin–Madison · Argonne National Laboratory
Targeting Pivotal Decisions for Credit Assignment in Agentic Reinforcement Learning
Sep 28, 2026Dongwon Jung, Hemanth Neelgund Ramesh, Yifan Wang +7Agentic RL Group Relative Policy Optimization
University of California, Davis · Microsoft · University of Washington
Progress- and Reliability-Oriented Group Policy Optimization for Agentic Reinforcement Learning
Jul 5, 2026Mingxuan Fan, Peiyang LiuAgentic RL Group Relative Policy Optimization
Baidu Inc., China · Peking University, China

Jun 24, 2026J/K move · Enter open · S save

Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents

Changdae Oh, Wendi Li, Seongheon Park, Samuel Yeh+2

University of Wisconsin–Madison · Argonne National Laboratory

Process Reward Models RL Post-Training RL for LLM Agents

Open paper AskPDF arXiv

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.

Abstract

Agentic RL

Explore similar work

Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents

Targeting Pivotal Decisions for Credit Assignment in Agentic Reinforcement Learning

Progress- and Reliability-Oriented Group Policy Optimization for Agentic Reinforcement Learning