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

AI summary

Overview

Research area: Machine learning — reinforcement learning (RL) for large language model (LLM) agents operating in multi-turn, tool-using environments; specifically credit assignment in critic-free policy optimization.

Technical level: Advanced. The paper assumes familiarity with policy-gradient methods, group-relative advantage normalization (GRPO/DAPO), and PPO-style clipped surrogates.

Scope (one sentence): The paper diagnoses a structural flaw in critic-free agentic RL — trajectory-level advantages applied uniformly to every action — and proposes a plug-and-play advantage-shaping wrapper, ProAS, that uses a dynamically evolving Agentic Reference Graph to annotate individual actions as reasonable or progress-advancing.

What This Paper Is About

Critic-free RL algorithms such as GRPO score an entire multi-turn trajectory with a single number and then apply that same advantage to every action the agent took, regardless of whether an individual step was sensible or actually moved the task forward. The authors show this "uniform credit assignment dilemma" causes two failures: in successful trajectories it reinforces structurally invalid actions that pollute the context, and in failed trajectories it penalizes late steps as harshly as the early decisions that caused the failure. ProAS addresses both by reshaping the trajectory-level advantage per step using annotations from a reference graph, without adding a learned critic.

Key Contributions

1. Problem identification. The paper formalizes the uniform credit assignment dilemma in critic-free agentic RL, showing through a derivation of the GRPO gradient that the per-step credit multiplier reduces to the trajectory-level advantage under on-policy sampling, and demonstrating empirically that this both reinforces noise in preferred trajectories and ignores downstream influence in unpreferred ones.

2. Algorithmic innovation. It introduces Progress-Aware Advantage Shaping (ProAS), a plug-and-play framework driven by an Agentic Reference Graph (ARG) — a directed acyclic graph of sub-goal states and valid transitions that evolves online by absorbing verified new successful trajectories. ProAS applies two mechanisms: Masking Unreasonable Incentives (MUI) and Asymmetric Penalty Redistribution (APR).1. Empirical superiority. Across Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct, ProAS lifts GRPO, DAPO and GiGPO to new best results on ALFWorld and WebShop, accelerates convergence by 1.12× to 2.44×, and remains effective when the ARG is incomplete, static, or distilled from a 7B teacher rather than crowdsourced.

3. Supporting intervention study. A controlled action-intervention analysis (50 sampled continuations per condition) supplies the causal evidence behind each mechanism, including the definition of Future-Drift as the count of downstream non-advancing actions.

Main Findings

• Uniform credit reinforces bad actions in winning trajectories. Unreasonable actions make up 41.6% of successful GRPO trajectories on ALFWorld and 39.6% on WebShop for Qwen2.5-1.5B-Instruct. Injecting a four-step unreasonable segment into an otherwise clean ALFWorld context dropped the Expected Success Rate over 50 continuations from 82% to 58%.

• Later failures are often inherited, not independent. Non-advancing actions are concentrated in failed GRPO trajectories (93.1% on ALFWorld, 76.1% on WebShop). Suppressing the original action at points with Future-Drift values of 47, 23, 11 and 4 and resampling 50 continuations recovered Expected Success Rates of 24%, 16%, 10% and 0% respectively — higher Future-Drift actions are the ones worth penalizing hardest.

• Peak success rates. The best ALFWorld results were 91.9% (1.5B, GiGPO+ProAS) and 94.3% (7B, GiGPO+ProAS); the best WebShop success rates were 66.7% (1.5B, reached by both DAPO+ProAS and GiGPO+ProAS) and 70.8% (7B, GRPO+ProAS).

• ProAS beats the strongest segment-level baseline. GiGPO+ProAS exceeds MiGPO by 13.1 points on WebShop with the 1.5B model (66.7% vs 53.6%). On 7B ALFWorld, 94.3% exceeds MiGPO's 91.9% and GPT-5.6-Sol's 78.9% by 15.4 points.

• It outperforms SFT and PPO. GiGPO+ProAS surpasses SFT by 12.2 points (1.5B) and 14.4 points (7B) on ALFWorld, despite both using expert annotations. ProAS variants outpace PPO by 5.5 to 18.7 points in ALFWorld success rate, 4.1 to 12.2 points in WebShop task score, and 3.4 to 11.5 points in WebShop success rate.

• Largest single-algorithm gain. Equipping GRPO with ProAS raises ALFWorld success from 70.3% to 87.0% on 1.5B (+16.7 points) and from 80.7% to 89.1% on 7B (+8.4 points).

• Faster convergence. Speedups range from 1.12× (GiGPO+ProAS, 1.5B WebShop) to 2.44× (GiGPO+ProAS, 7B ALFWorld), with 1.59×/1.27×/1.61× for GRPO/DAPO/GiGPO+ProAS on 1.5B ALFWorld and 2.20×/2.05×/2.44× on 7B ALFWorld. The paper reports an average of roughly 1.5× for the 1.5B model, 2.2× on 7B ALFWorld and 1.7× on 7B WebShop.

• Both mechanisms matter, and they are complementary. Removing MUI (ProAS⁻) costs 15.4 success-rate points on ALFWorld and 0.8 on WebShop; removing APR (ProAS⁺) costs 3.7 success-rate points on ALFWorld and 1.2 task-score points on WebShop.

• Shaping advantages beats shaping rewards and simpler heuristics. A progress-aware auxiliary reward variant (PR) trails ProAS by 14.1 and 3.4 success-rate points on ALFWorld and WebShop; masking all reasonable actions instead of redistributing penalties (ProAS_msk±) trails by 14.1 and 0.8 points; substituting raw suffix length for Future-Drift (ProAS_suffix) trails by 5.5 and 1.6 points.

• Robustness to imperfect reference graphs. Randomizing ARG labels collapses performance (47.7% vs 87.0% on ALFWorld, 49.2% vs 64.6% on WebShop). Pruning 40% of action-state pairs still leaves ProAS 7.0 points above GRPO on ALFWorld, but also disabling evolution on top of that costs a further 5.2 points on ALFWorld and 5.4 on WebShop. A distilled ARG built from a 7B teacher over 2,566 tasks yields 83.6% on ALFWorld and 64.8% on WebShop for the 1.5B model, 13.3 and 7.8 points above GRPO.

Methodology in Plain English

The researchers start from a simple observation about how GRPO-style training works: every token the agent generates in a rollout is pushed up or down by one shared number, the trajectory's normalized reward. They then run controlled experiments to show why that is a problem.

First, they take a clean successful trajectory and ask a 1.5B model to continue from a fixed state 50 times, once with the original history and once with a deliberately broken four-step segment spliced in. The broken context lowers the success rate even though the underlying environment state is identical — so bad actions in the history genuinely hurt.

Second, they take a failed trajectory, force the model to abandon the original action at a chosen step, and resample 50 continuations. Abandoning early mistakes that are followed by many further mistakes (high Future-Drift) recovers far more successes than abandoning late, low-Future-Drift steps — so penalties should be concentrated on those early pivotal steps rather than spread evenly.

To know which actions are "reasonable" and which actually "advance progress," they build a reference graph from pre-collected successful trajectories. Sub-goals are nodes, valid state-action-state transitions are edges, and the graph is a DAG because sub-goals occur in a fixed order while the order of actions within a sub-goal can vary. The graph grows during training: whenever a newly sampled trajectory succeeds and is verified, its new states and edges are merged in.

Every action in every rollout is then checked against the graph on two binary criteria — is it a valid edge (reasonable), and does it reach a new graph state not already visited in this trajectory (progress-advancing)? Progress-advancing implies reasonable, so the two labels form a hierarchy.

The advantage reshaping itself has three branches. For positive advantages, actions that are not reasonable get zeroed out. For negative advantages, each step's penalty is scaled by its Future-Drift divided by the trajectory's average Future-Drift, so early steps responsible for cascading failure absorb more of the blame. Everything else keeps the original advantage. Because the method only rewrites the scalar advantage, it plugs into existing group-based algorithms without a critic.

Training used Verl-Agent for 150 RL steps, validated every 10 steps, and reported the best checkpoint averaged over seeds 0, 1 and 2.

Why This Matters

Impact on research. The paper reframes credit assignment in critic-free agentic RL as a shaping problem rather than a modeling problem: instead of learning a value function to get per-step signals, it derives structure from a graph of successful trajectories that costs far less than a critic. The negative result that a progress-aware auxiliary reward underperforms advantage shaping is a useful data point for anyone designing dense-reward variants. The finding that ARG evolution is necessary even when starting from a clean graph, and that 40% pruning is survivable, gives a practical picture of how much reference quality matters.

Real-world applications (drawn from environments and domains the paper discusses):

• Embodied household instruction-following agents, via the ALFWorld benchmark over Pick, Look, Clean, Heat, Cool and Pick2 task types.
• Web navigation and online shopping agents, via WebShop.
• Software engineering and personal-assistant agents, the application domains the introduction cites for sequential-decision LLM agents.
• GUI navigation agents and application-development agents (AppWorld) and dynamic conversational domains such as aviation and retail (τ²-Bench) are named as extensions of the same multi-turn paradigm.

Industry relevance. ProAS is a wrapper, not a replacement: teams already training with GRPO, DAPO or GiGPO can add it without adopting a critic or changing their infrastructure. The reported convergence acceleration of up to 2.44× translates directly into reduced compute per run, and the result that a distilled ARG from a 7B teacher works for a 1.5B student shows the method does not require hand-curated gold trajectories — a practical requirement in commercial settings where such annotations are unavailable.

Future Directions

• Extending beyond two environments. The paper validates only on ALFWorld and WebShop; whether ProAS transfers to AppWorld, τ²-Bench, GUI navigation or software-engineering agents — all cited in the related work but untested here — is an open question.

• Reducing reliance on reference-graph provenance. The distilled-ARG experiment shows synthetic references work, but only with a 7B teacher generating successful rollouts. How well ProAS holds up when successful rollouts are rarer, or when the teacher and student differ more, is not established.

• Richer action annotations. The current scheme is two binary labels (reasonable, progress-advancing) over sequential sub-goals. Whether finer-grained or learned annotations improve credit assignment beyond what MUI and APR extract is untested.

• Combining with segment-level methods. ProAS is presented as orthogonal and outperforms MiGPO in the reported comparisons, but a direct composition of ProAS with segment- or anchor-level credit assignment (GiGPO/MiGPO style) is not evaluated, leaving whether the gains stack an open question.

Target Audience

Researchers and engineers working on RL post-training for LLM agents — particularly those already using GRPO-family algorithms who want finer credit assignment without paying for a critic. It is also relevant to practitioners who have expert demonstrations or successful trajectory logs and want to convert them into a training signal rather than plain imitation. Readers without a background in policy-gradient methods will find Sections 3 and 4 heavy going; the intervention study in Section 4.2 and the results in Section 6 are accessible on their own.

Authors’ 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 unreasonable actions in preferred trajectories and ignores each action's downstream 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