Source-linked AI summary
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, Lifeng Shang, Tao Lin
TL;DR
Critic-free RL assigns trajectory-level advantages uniformly, despite differences among actions and their downstream influence. ProAS uses a dynamically evolving Agentic Reference Graph to shape action-level advantages without critic overhead. Experiments report improved performance across mainstream group-based baselines, with faster convergence and new state-of-the-art results.
Problem
Critic-free methods such as GRPO efficiently broadcast trajectory-level advantages uniformly, leaving differences in action validity and downstream influence unaccounted for.
Source: §1 · p. 1Method
ProAS uses a dynamically evolving Agentic Reference Graph to guide fine-grained, critic-free advantage shaping through MUI and APR.
Source: §1 · p. 2Results
Across ALFWorld and WebShop, ProAS elevates mainstream group-based baselines to new SOTA and accelerates convergence by 1.12× to 2.44×.
Source: §1 · p. 2Takeaways & Limitations
ProAS is a plug-and-play enhancer that improves group-based RL baselines across model scales and environments and remains robust to imperfect or distilled ARGs.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Critic-free GRPO assigns a shared trajectory advantage to every action despite differences in validity and downstream influence. ProAS uses a dynamically evolving ARG to reshape action-level incentives without critic overhead.
1 INTRODUCTION
- Uniform credit assignment treats all actions alike, reinforcing structurally invalid actions in preferred trajectories while ignoring how early deviations affect later actions.This dilemma arises because critic-free methods broadcast trajectory-level advantages uniformly, while actor-critic methods add computational overhead and optimization instability in long-horizon settings.Source: §1 · pp. 1–2
- The paper identifies two failure modes: unreasonable actions can pollute preferred-trajectory context, while early deviations in unpreferred trajectories can drive cascading failures.Uniform penalization consequently suppresses all actions in a failed trajectory equally, irrespective of their downstream influence.Source: §1 · p. 2
- ProAS uses a dynamically evolving Agentic Reference Graph to annotate action progress and reshape advantages through MUI and APR without adding critic overhead.MUI zeros local advantages for unreasonable actions in preferred trajectories; APR assigns heavier penalties to actions followed by more downstream non-advancing actions.Source: §1 · p. 2
- Across ALFWorld and WebShop, ProAS elevates mainstream group-based baselines to new SOTA, boosts success rates by up to 16.7 points, and accelerates convergence by 1.12× to 2.44×.GiGPO+ProAS exceeds MiGPO by 13.1 points on 1.5B WebShop and reaches 94.3% on 7B ALFWorld.Source: §1 · p. 2
2 RELATED WORKS
The paper focuses on training paradigms for existing multi-turn agentic tasks rather than constructing new environments. It positions ProAS as a plug-and-play response to the coarse credit assignment of critic-free RL.
2 RELATED WORKS
- Rather than creating environments, this work develops more efficient and effective training paradigms for existing multi-turn agentic tasks.Examples of these tasks include ALFWorld for embodied household tasks and WebShop for web navigation.Source: §2 · pp. 2–3
- Critic-free methods such as GRPO retain trajectory-bound credit assignment, while GiGPO and MiGPO differentiate actions by matching anchor states or milestones across rollouts.DAPO and dense-reward methods address sparse-reward advantage vanishment but leave credit assignment trajectory-bound.Source: §2 · p. 3
- ProAS addresses uniform credit assignment in preferred and unpreferred trajectories through advantage shaping that plugs into existing critic-free RL algorithms.Source: §2 · p. 3
3 PRELIMINARY
The preliminary section describes sequential agent decisions and GRPO's group-normalized trajectory advantages. It identifies GRPO's uniform credit assignment as the limitation motivating action-level differentiation.
3.1 DECISION PROCESS OF LLM AGENTS
- At each step, an LLM agent samples an admissible action conditioned on task context, interaction history, and the current state.Harnessing wrappers may provide partial observations or summarized historical information before the current state.Source: §3.1 · p. 3
3.2 GRPO
- GRPO estimates trajectory advantages by normalizing verifiable outcome rewards within a group of rollouts.Its objective uses a clipped surrogate; the importance ratio is bounded to limit improvements from favorable ratio changes.Source: §3.2 · p. 3
- The figure depicts successful trajectories unified as an ARG DAG and probes how unreasonable actions and Future-Drift relate to expected success or recovery.The caption reports lower Expected Success Rate after injecting unreasonable actions; suppressing actions with greater Future-Drift is associated with rising recovered ESR.Source: Figure 1 · p. 4, §3.2 · p. 4
- Under the on-policy setting, every step in a trajectory receives the same trajectory-level advantage, regardless of its individual differences.The paper terms this limitation the dilemma of uniform credit assignment.Source: §3.2 · p. 4
4 METHODOLOGY
The methodology replaces uniform trajectory-level credit assignment with step-wise, progress-aware shaping. It builds on an evolving Agentic Reference Graph and intervention evidence to motivate asymmetric treatment of actions.
4.1 AGENTIC REFERENCE GRAPH
- The Agentic Reference Graph is a DAG of ordered sub-goals whose states capture permutation-invariant valid executions; verified successful trajectories add novel states and actions over time.Invalid transitions and self-loops are pruned, and graph updates adhere to these purity rules.Source: §4.1 · pp. 4–5
4.2 ACTION-INTERVENTION ANALYSIS
- With identical underlying environment states, prepending a four-step unreasonable segment to the clean history degraded Expected Success Rate (ESR) from 82% to 58%.Source: §4.2 · p. 5
- 24%, 16%, 10%, and 0% ESR followed suppression of actions with Future-Drift values 47, 23, 11, and 4, respectively, in one failed ALFWorld trajectory.In this case, suppressing the higher-Future-Drift action was more likely to allow recovery and task completion.Source: §4.2 · p. 6
4.3 PROGRESS-AWARE ADVANTAGE SHAPING
- ProAS reshapes trajectory-level advantages into step-wise signals: MUI zeros advantages for unreasonable actions in preferred trajectories, while APR weights negative advantages by normalized Future-Drift.MUI prevents reinforcement of invalid actions; APR assigns heavier penalties to early pivotal actions in unpreferred trajectories.Source: §4.3 · p. 6
5 EXPERIMENTAL SETUP
The experimental setup evaluates ProAS across two model scales and two long-horizon environments, using multiple group-based RL baselines. It specifies task, efficiency, training, and robustness evaluations.
5 EXPERIMENTAL SETUP
- Four research questions cover task success and convergence across scales, baseline compatibility, MUI/APR design, and robustness to altered or distilled ARGs.The design asks whether the shaping mechanisms are individually necessary and synergistic, and whether Future-Drift redistribution outperforms simpler masking.Source: §5 · p. 6
5.1 MODELS AND DATA
- Experiments use Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct on ALFWorld and WebShop, with 128 validation tasks per environment and seed-specific training sets.ALFWorld training sets contain 1777, 1767, and 1784 tasks across seeds; WebShop sets contain 2015, 2011, and 2036.Source: §5.1 · p. 6
5.1.1 EVALUATION METRICS
- ALFWorld uses overall and per-category Success Rate (SR), while WebShop uses overall SR and Task Score (TS), a 0–100 checklist metric.Training speedup compares baseline and ProAS environment steps to reach 70% SR on ALFWorld and 50% on WebShop.Source: §5.1.1 · p. 7
5.1.2 IMPLEMENTATION DETAILS
- Models train for 150 RL steps, with validation every 10 steps and reporting from the highest-SR checkpoint; runs use three seeds unless specified, and ARGs start from official annotations.ALFWorld annotations represent sequential steps as sub-goals; WebShop uses annotated sub-goals with corresponding states and actions.Source: §5.1.2 · p. 7
5.1.3 BASELINES
- Baselines include GPT-5.6-Sol, prompted and SFT Qwen models, PPO, GRPO, DAPO, GiGPO, and MiGPO.MiGPO is described as an agentic RL method with segment-level credit assignment.Source: §5.1.3 · p. 7
6 RESULTS AND ANALYSIS
ProAS improves benchmark performance across the reported settings, accelerates convergence, and remains effective with imperfect or distilled ARGs. Ablations support the roles of both shaping mechanisms and dynamic ARG evolution.
6.1 MAIN RESULTS
- 94.3% SR on 7B ALFWorld and 70.8% SR on 7B WebShop are ProAS peaks, while 1.5B ProAS variants reach 66.7% SR on WebShop.The reported comparisons establish new SOTA records; Table 1 summarizes ALFWorld and WebShop results.Source: §6.1 · pp. 7–8, Table 1 · p. 8
- GRPO+ProAS improves ALFWorld SR by 16.7 points at 1.5B and 8.4 points at 7B; WebShop gains include 9.4 points for 1.5B DAPO and 3.1 for 7B GRPO.The passage reports gains across all tested configurations.Source: §6.1 · p. 8
- ProAS speeds convergence by an average of 1.5× for 1.5B models, and by 2.2× on ALFWorld and 1.7× on WebShop for 7B models.These are average speedups to target success rates.Source: §6.1 · p. 8
6.2.1 ADVANTAGE SHAPING ABLATION
- Disabling MUI drops SR by 15.4 points on ALFWorld and 1.3 on WebShop; disabling APR drops ALFWorld SR by 3.7 points and WebShop TS by 1.2.The authors report that both mechanisms are indispensable and synergistic.Source: §6.2.1 · p. 9, Table 2 · p. 9
- Replacing APR with masking non-advancing actions underperforms GRPO+ProAS by 14.1 SR points on ALFWorld and 0.8 on WebShop.The comparison supports APR’s Future-Drift weighting over the masking heuristic; all three tested variants still outperform native GRPO on aggregate metrics.Source: §6.2.1 · p. 9
6.2.2 ARG ABLATION
- Random ARG labels lower SR relative to ProAS by 39.3 points on ALFWorld and 15.4 on WebShop; pruning 40% of action-state pairs still leaves ProAS 7.0 points above GRPO on ALFWorld.Disabling ARG evolution further lowers SR by 5.2 points on ALFWorld and 5.4 on WebShop with an incomplete graph; with a clean graph, ALFWorld SR falls from 87.0% to 82.8%, while Static records 65.9% WebShop SR, best among variants.Source: §6.2.2 · p. 9
- With a distilled ARG covering 2,566 tasks, the 1.5B model reaches 83.6% SR on ALFWorld and 64.8% on WebShop, respectively 13.3 and 7.8 points above GRPO.The results are reported as comparable to GRPO+ProAS and demonstrate applicability with teacher-distilled trajectories.Source: §6.2.2 · p. 9
7 CONCLUSION
The conclusion presents ProAS as a critic-free approach to fine-grained credit assignment and reports improved performance, faster convergence, and robustness across the evaluated settings.
7 CONCLUSION
- ProAS combines a dynamically evolving ARG with MUI and APR to reshape trajectory advantages without critic overhead.The conclusion reports that experiments across multiple model scales and environments show faster convergence, new SOTA performance, and robustness to incomplete or distilled ARGs.Source: §7 · p. 10
A DERIVATION OF THE GRPO POLICY GRADIENT
The appendix derives the GRPO policy gradient from its clipped surrogate and documents the training framework and algorithm-specific configurations.
A DERIVATION OF THE GRPO POLICY GRADIENT
- At the old policy, each token shares its trajectory’s advantage multiplier and normalization, although token score-function gradients can differ.The derivation holds the sampling policy, trajectories, and group-normalized advantages fixed during the update.Source: A DERIVATION OF THE GRPO POLICY GRADIENT · p. 13
B.1 TRAINING FRAMEWORK
- RL and SFT use the same turn-level prompt format, but SFT responses are curated offline while RL responses are generated online.Prompts include the instruction, current observation, admissible actions, and visible history from the two most recent turns.Source: §B.1 · p. 14
B.2 RL CONFIGURATION
- GiGPO+ProAS applies MUI to excessively positive step advantages and rescales clustered negative-advantage actions using future-miss normalization.Configuration details vary by base algorithm and environment; the shared RL setup uses one policy-update epoch per rollout batch.Source: §B.2 · p. 14
B.3.1 DATA CURATION.
The paper curates seed-specific supervised demonstrations to match RL task exposure, then describes the ALFWorld and WebShop environments and their frozen training and validation sets.
B.3.1 DATA CURATION.
- For each environment seed, the authors curate supervised data from frozen training tasks, using expert ALFWorld trajectories and an ARG-based WebShop oracle.The WebShop oracle follows the ARG’s sub-goal progression; each demonstration is represented as a turn-level example with the task, observation, admissible actions, and two recent interaction turns.Source: §B.3.1 · pp. 14–15
- SFT full-parameter fine-tunes both Qwen2.5 models for three epochs and selects the checkpoint with the highest success rate on the shared 128-task validation set.Training minimizes token-level negative log-likelihood of oracle responses, with AdamW and a cosine learning-rate schedule.Source: §B.3.1 · p. 15, Table 5 · p. 15, Table 6 · p. 16
C ENVIRONMENT DETAILS
- ALFWorld spans six household task families, while WebShop requires product search, page navigation, option selection, and purchase across five product categories.Both environments permit one action per interaction turn; WebShop includes ordered milestones and options selectable in either order.Source: C ENVIRONMENT DETAILS · pp. 15–16
- WebShop’s frozen training sets contain 2,015, 2,011, and 2,036 tasks for seeds 0, 1, and 2, respectively, with 128 shared validation tasks.The task-category table reports counts for each training seed and the shared validation set.Source: C ENVIRONMENT DETAILS · p. 16, Table 6 · p. 16
D.1 UNREASONABLE ACTION PROBING ANALYSIS IN ALFWORLD
A controlled ALFWorld intervention compares continuations from the same state with clean or noise-injected visible histories. The noise-injected condition has a lower observed expected success rate.
D.1 UNREASONABLE ACTION PROBING ANALYSIS IN ALFWORLD
- The two conditions replay the same three-action clean prefix and reach the same continuation point, with 47 steps remaining.From this point, the authors sample 50 continuations per condition.Source: §D.1 · p. 17
- Table 7 highlights only the four unreasonable actions added to the policy-visible history.It presents the task ARG and separates the clean and noise-injected conditions before summarizing sampled suffixes and Expected Success Rates.Source: §D.1 · p. 17
- Expected Success Rate falls from 82% to 58% with unreasonable actions prepended to the visible history, despite identical continuation state and rollout budget.Each condition independently samples 50 continuations; the injected actions affect policy-visible history but are not executed in the continuation environment.Source: §D.1 · p. 17
D.2 VARYING FUTURE-DRIFT ACTIONS SUPPRESSION ANALYSIS IN ALFWORLD
The section examines how suppressing actions at different positions relates to continuation success, then illustrates dynamic ARG expansion and order-agnostic option progress in WebShop.
D.2 VARYING FUTURE-DRIFT ACTIONS SUPPRESSION ANALYSIS IN ALFWORLD
- ESR is 24%, 16%, 10%, and 0% when suppressing actions with FD 47, 23, 11, and 4, respectively, in one failed ALFWorld rollout.The authors present this as intervention evidence for a diagnostic trend, not a universal causal-effect estimate.Source: §D.2 · p. 17
D.3 THE ARG DYNAMIC EVOLUTION IN ALFWORLD
- Successful ALFWorld rollouts are purified by removing invalid and inadmissible steps, then merged into the ARG to expand its coverage of viable paths.The example concerns a task with multiple valid solutions that a single static ARG does not cover.Source: §D.3 · p. 17
D.4 THE ORDER-AGNOSTIC OF ACTIONS IN WEBSHOP
- WebShop’s ARG treats different option-selection orders as progress-advancing while preserving high-level sub-goal order.A repeated click can be reasonable but non-advancing; a wrong option or premature purchase is unsupported by the ARG.Source: §D.4 · p. 17
E TRAINING SPEEDUP CURVES
Figure 2 displays validation success-rate curves for ALFWorld and WebShop over 150 RL steps. Fixed success-rate targets define the training-speedup comparison before and after adding ProAS.
E TRAINING SPEEDUP CURVES
- Training speedup is measured by the RL steps required to reach each fixed target before and after adding ProAS.The learning curves in Figure 2 are used to compute the training-speedup results in Table 1.Source: E TRAINING SPEEDUP CURVES · p. 18, Figure 2 · p. 18
- Figure 2 compares validation success-rate curves for ALFWorld and WebShop within 150 RL steps.The figure’s arrows indicate the speedup of each base algorithm after adding ProAS.Source: Figure 2 · p. 18
- The speedup targets are 70 points for ALFWorld and 50 points for WebShop.Dashed horizontal lines mark these fixed success-rate targets.Source: Figure 2 · p. 18