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

What it claims

Critic-free group RL (GRPO and relatives) gives every step in a trajectory the same advantage. The authors say this does two kinds of damage. In successful rollouts it rewards invalid actions, which make up 41.6% of steps in successful GRPO trajectories on ALFWorld and 39.6% on WebShop (Qwen2.5-1.5B-Instruct). In failed rollouts it penalises late actions as heavily as the early mistake that caused the failure.

ProAS reshapes the per-step advantage using a graph of known-good progress. It is a wrapper around an existing algorithm, not a new optimiser. It was tested on top of GRPO, DAPO and GiGPO, where it gave gains of up to +16.7 success points (GRPO, 1.5B, ALFWorld) and 1.12×–2.44× faster convergence.

How it works

Agentic Reference Graph (ARG). The graph is a DAG built from pre-collected successful trajectories:

• Vertices are M ordered sub-goals. Each sub-goal is a set of valid states, with order-insensitive internal steps merged into one equivalence class.
• Edges are deterministic (s, a, s') transitions between consecutive sub-goals.
• Error states and self-loops are pruned.
• During training, every newly verified successful rollout is added to the graph by strict union.

Per-step labels, computed against the current graph:

• Rea_t = 1 if the transition (s_t, a_t, s_{t+1}) is an ARG edge.
• PA_t = 1 if s_{t+1} is an ARG state the trajectory has not already visited. Every progress-advancing step is also reasonable.
• Future-Drift D_{i,t} is the number of non-advancing steps from t to the end of the trajectory, counting t itself.

Advantage shaping (Eq. 7) branches on the sign of the GRPO advantage A_i:

flowchart TD
  A[Trajectory advantage A_i] --> B{sign}
  B -->|A_i > 0| C[MUI: A_i × Rea_t<br/>invalid steps get 0]
  B -->|A_i < 0| D[APR: A_i × D_t / mean D<br/>early drift-causing steps penalised more]
  B -->|otherwise| E[A_i unchanged]

APR normalises by the trajectory's mean Future-Drift. This redistributes the penalty within the trajectory rather than increasing it overall.

Evidence

Headline results. Peak success rates are 91.9% / 94.3% on ALFWorld and 66.7% / 70.8% on WebShop, for 1.5B / 7B. The 94.3% figure is GiGPO+ProAS on 7B ALFWorld.

Comparison with MiGPO. The paper compares against MiGPO, a segment-level milestone-matching method. GiGPO+ProAS beats MiGPO by 13.1 points on WebShop at 1.5B.

Motivating interventions (Qwen2.5-1.5B, ALFWorld, single trajectories, 50 continuations each):

• Prepending a 4-step invalid segment to a clean history dropped expected success from 82% to 58%, with the environment state unchanged.
• In a failed trajectory, the authors forbade the original action at points with Future-Drift 47, 23, 11 and 4. Recovered success was 24%, 16%, 10% and 0% respectively.

The fetched text stops before the results tables and ablations. Per-baseline numbers, compute cost and the imperfect/distilled-ARG experiments could not be checked.

How to use it

Code is at https://github.com/LINs-lab/ProAS. The fetched text gives no install commands, licence or hardware figures.

What you need:

• A set of successful trajectories to seed the ARG.
• An environment where you can detect states and transitions well enough to test whether something is an ARG edge or state.
• A group-based RL trainer whose per-step advantage you can override.

Limits

• Environment assumptions. The ARG assumes deterministic transitions and a fixed sub-goal sequence. Both fit text environments like ALFWorld and WebShop. The paper does not show how to build it for open-ended tool use or for environments with stochastic or continuous states.
• Narrow evaluation. Only two benchmarks and only Qwen2.5 at 1.5B and 7B were tested.
• Thin motivating evidence. Both interventions in §4.2 are single hand-picked trajectories.
• Unverified robustness claim. Robustness to "imperfect or distilled" ARGs is asserted in the abstract, but the evidence was not in the fetched text. The authors also say the online-evolution step is necessary, so a static graph may underperform.
• Zero-advantage groups. Steps with A_i = 0 (all-success or all-fail groups) are left unshaped. ProAS does not address advantage vanishing.