Paper deep dive
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
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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: this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2610.18683v1
- Canonical: https://arxiv.org/abs/2610.18683v1
Trouble viewing inline? Open PDF directly →
Full Text
72,773 characters extracted from source content.
Expand or collapse full text
Preprint PROAS: A PROGRESS-AWARE ADVANTAGE SHAPING FRAMEWORK FOR MULTI-TURN AGENTIC REINFORCE- MENT LEARNING Bowen Ding 1,2 , Mingda Wan 2 , Yuhan Chen 2,* , Jiyao Yuan 4,† , Qi Zhu 4,† , Futing Wang 1,2 , Heyuan Deng 4 , Fei Mi 4,‡ , Lifeng Shang 4 , Tao Lin 2,3,‡ , 1 Zhejiang University 2 School of Engineering, Westlake University 3 Institute of Advanced Technology, Westlake Institute for Advanced Study 4 Huawei Noah’s Ark Lab 2 dingbowen, wanmingda, wangfuting, lintao@westlake.edu.cn 4 dengheyuan, mifei2, Shang.Lifeng@huawei.com 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 broad- casts 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 to2.44×while maintaining strong robustness against imperfect or distilled ARGs. Codes: https://github.com/LINs-lab/ProAS. 1INTRODUCTION Large language models (LLMs) are increasingly deployed as autonomous agents that make sequential decisions through interactions with external environments. Their planning and reasoning capabilities have enabled applications in software engineering (Yang et al., 2024), personal assistance (Yoran et al., 2024), and graphical user interface navigation (Luo et al., 2025). Reinforcement Learning (RL) has emerged as the primary paradigm for elevating the agentic capacity of LLMs (GLM-5-Team et al., 2026; DeepSeek-AI, 2026). During RL rollouts, agents generate trajectories composed of interleaved environment states and actions, which introduces a fundamental credit assignment challenge: How should trajectory-level rewards and penalties be attributed to individual actions? Actor-critic algorithms (e.g., PPO (Schulman et al., 2017)) address this by learning a separate critic, which introduces substantial computational overhead and optimization instability in long-horizon settings (Wang et al., 2026a; Yue et al., 2025). Conversely, critic-free algorithms like Group Relative Policy Optimization (GRPO) (Shao et al., 2024) offer computational efficiency by broadcasting a trajectory-level advantage uniformly to every action (Ding et al., 2025). However, this inherently treats all intra-trajectory actions identically, completely overlooking their critical differences in local ∗ Work done at Westlake as an intern. † Work done at Huawei Noah’s Ark Lab. ‡ Corresponding authors. 1 arXiv:2610.18683v1 [cs.LG] 13 Oct 2026 Preprint validity, task contribution, and downstream inflence. As detailed in § 3.2, we term this structural limitation the uniform credit assignment dilemma. To systematically understand the uniform credit assignment dilemma, we conduct a fine-grained action-intervention analysis (§ 4.2). Our findings reveal a dual suboptimality. First, in preferred trajectories with positive advantages, uniform credit inadvertently reinforces structurally invalid actions (i.e., unreasonable actions) that pollute the context history and impede the agent from reaching success. Second, in unpreferred trajectories with negative advantages, uniform penalization ignores the autoregressive nature of LLMs, where early deviations drive cascading failures; consequently, they unfairly suppress all actions equally without considering their actual downstream influence. To resolve this dilemma without introducing critic overhead, we propose Progress-Aware Advantage Shaping (ProAS) in § 4.3. ProAS leverages an Agentic Reference Graph (ARG, mentioned in § 4.1), which abstracts task progression into dynamically evolving sub-goals to formally annotate whether an action is reasonable (structurally valid) or progress-advancing (driving task completion). Using these structural annotations, ProAS asymmetrically reshapes trajectory-level advantages in Eq. 7: (1) Masking Unreasonable Incentives (MUI) zeros out the local advantages of unreasonable actions in preferred trajectories to prevent their inadvertent reinforcement. (2) Asymmetric Penalty Redistribution (APR) utilizes Future-Drift (Eq. 6), the inclusive count of downstream non-advancing actions, to assign proportionally heavier penalties to actions triggering severe downstream stagnation. Extensive experiments in § 6 on ALFWorld (Shridhar et al., 2021) and WebShop (Yao et al., 2023) using Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct (Qwen Team, 2024) validate ProAS as a versatile, plug-and-play enhancer. It universally elevates mainstream group-based RL baselines (GRPO (Shao et al., 2024), DAPO (Yu et al., 2025), GiGPO (Feng et al., 2025)), boosting success rates by up to 16.7 points (e.g., GRPO on 1.5B ALFWorld) and accelerating training convergence by 1.12×to2.44×. On top of that, this orthogonal enhancement propels these standard algorithms to establish new state-of-the-art (SOTA) performance, consistently eclipsing the strong segment-level baseline, MiGPO (Wang et al., 2026b). Notably, GiGPO+ProAS outperforms MiGPO by a massive 13.1 points on WebShop with 1.5B model and secures the highest overall success rate of 94.3% on ALFWorld with 7B model. Furthermore, comprehensive ablations (§ 6.2) show that ProAS’s core mechanisms are both synergistic and superior to alternative advantage shaping variants, and confirm ProAS’s robust efficacy against incomplete or distilled ARGs, underscoring the necessity of ARG’s online evolution mechanism. In summary, our primary contributions are: •Problem Identification: We expose the uniform credit assignment dilemma in critic-free agentic RL, demonstrating how uniform advantages inadvertently reinforce contextual noise in preferred trajectories and ignore the downstream influence of actions in unpreferred ones. • Algorithmic Innovation: We propose Progress-Aware Advantage Shaping (ProAS), a plug-and- play framework. Guided by a dynamically evolving Agentic Reference Graph (ARG), ProAS achieves fine-grained, critic-free credit assignment via Masking Unreasonable Incentives (MUI) and Asymmetric Penalty Redistribution (APR). •Empirical Superiority: ProAS acts as a universal enhancer across multiple model scales and environments. It significantly accelerates training convergence, propels standard group-based algorithms to surpass strong SOTA baselines (e.g., MiGPO), and exhibits high robustness against imperfect and distilled reference guidance. 2RELATED WORKS Multi-Turn Agentic Tasks. Large Language Model (LLM) agents are increasingly deployed to solve complex real-world tasks (Xu et al., 2025). Given the intricacies of these environments, agents must engage in multi-turn interactions, continuously accumulating contextual knowledge and making sequential decisions to drive task completion. To facilitate the training and evaluation of such agents, the community has introduced various simulated environments. Examples include ALFWorld (Shridhar et al., 2021) for embodied household tasks, WebShop (Yao et al., 2023) for web navigation, AppWorld (Trivedi et al., 2024) for application development, andτ 2 -Bench (Barres et al., 2025) for evaluating dynamic conversational abilities in domains like aviation and retail. 2 Preprint Rather than constructing new environments, our work focuses on developing more efficient and effective training paradigms tailored for existing multi-turn agentic tasks. RL for LLM Agents. Critic-free RL like GRPO (Shao et al., 2024) is widely adopted for LLM agents (Qian et al., 2025; Jin et al., 2025; Wei et al., 2025), but suffers from sparse-reward advantage vanishment (Yu et al., 2025) and coarse trajectory-level credit assignment (Tan et al., 2026). While DAPO (Yu et al., 2025) and dense-reward methods (Qian et al., 2025; Lu et al., 2026; Zhao et al., 2026) mitigate this vanishment, their credit assignment remains trajectory-bound. To differentiate intra-trajectory actions, GiGPO (Feng et al., 2025) and MiGPO (Wang et al., 2026b) compute relative advantages by matching anchor states or milestones across rollouts. In this work, we systematically expose the flaws of uniform credit assignment in both preferred and unpreferred trajectories, addressing them through advantage shaping, which serves as a plug-and-play module for existing critic-free RL algorithms. 3PRELIMINARY 3.1DECISION PROCESS OF LLM AGENTS Given a task contextx∼ p(X), an LLM agent aims to solve the task within a maximum horizon of Tsteps. At each stept∈ [1,T ], the agent receives an immediate environment states t . Governed by a parameterized policyπ θ , the agent samples an actiona t from the admissible action spaceA(Sutton & Barto, 1998), conditioned on the task contextx, the interaction historyh t−1 =(s i ,a i ) t−1 i=1 , and the current state s t . Formally, this decision-making process is defined as: a t ∼ π θ (·|x,h t−1 ,s t ), a t ∈A, t∈ [1,T ](1) In practice, some harnessing wrappers (Feng et al., 2025) often provide partial observations or integrate summarized historical information (Li et al., 2026) (denoted as ˆ h t−1 ) into the context prior to the current state s t . 3.2GRPO GRPO (Shao et al., 2024) utilizes a group-level normalization strategy to estimate the advantage for assessing the action value. In GRPO, given a taskx, the old policyπ θ old generates a group ofG rollout trajectoriesτ i G i=1 , each evaluated by a verifiable outcome rewardR(τ i ). The trajectory-level advantage A i for τ i is computed by normalizing the rewards within the group: A i = R(τ i )− μ σ + ε (2) whereμandσdenote the mean and standard deviation of the group rewardsR(τ i ) G i=1 , andεis a small constant ensuring numerical stability. Excluding entropy and KL regularization terms for simplicity, GRPO optimizes the expected trajectory advantage as follows: J GRPO (θ) = E x,τ i G i=1 ∼π θ old 1 G G X i=1 1 |τ i | |τ i | X t=1 min ρ i,t (θ)A i , clip ρ i,t (θ), 1− ε, 1 + ε A i (3) where|τ i |is the trajectory length (in tokens), andy i,t denotes thet-th generated token withinτ i . The importance ratioρ i,t (θ) = π θ (y i,t |x,y i,<t ) π θ old (y i,t |x,y i,<t ) is used in a clipped surrogate with bounds[1−ε, 1 +ε]to limit improvements from favorable ratio changes. Differentiating this surrogate gives (see Appx. A): ∇ θ J GRPO (θ) = E x,τ i G i=1 ∼π θ old 1 G G X i=1 1 |τ i | |τ i | X t=1 1 clip i,t · A i · ρ i,t (θ)·∇ θ logπ θ (y i,t |x,y i,<t ) | z gradient at step (i,t) (4) where1 clip i,t indicates whether the surrogate’s gradient is active: it is zero whenA i > 0andρ i,t > 1+ε, or whenA i < 0andρ i,t < 1− ε, and one otherwise, with the boundary convention specified in Appx. A. 3 Preprint 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 continuationsc i 50 i=1 . (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. Credit Assignment of GRPO. As shown in Eq. 4, the per-step gradient is directly scaled by the credit multiplier1 clip i,t · A i · ρ i,t (θ). Under the on-policy setting (whereρ i,t (θ)≡ 1and thus1 clip i,t ≡ 1), this multiplier strictly reduces to the trajectory-level advantageA i . Consequently, all steps within the same trajectory are indiscriminately updated by the identical scalar, regardless of their individual difference. We term this systematic limitation the dilemma of uniform credit assignment. 4METHODOLOGY Since RL fundamentally optimizes policies by incentivizing or suppressing action likelihoods, tailored credit assignment requires understanding both the intrinsic properties of each step (e.g., reasonable- ness and progress advancement) and how modulating them dictates the final outcome. To quantify these step-level properties, § 4.1 constructs an Agentic Reference Graph (ARG). Guided by an intervention study probing these modulation effects (§ 4.2), § 4.3 introduces Progress-Aware Advan- tage Shaping (ProAS), a lightweight framework designed to resolve the uniform credit dilemma via asymmetric advantage shaping. 4.1AGENTIC REFERENCE GRAPH As illustrated in Fig. 1(a), ARG abstracts the task-solving progression intoMordered sub-goals using pre-collected successful trajectories. Below, we formalize its construction and online evolution, followed by a two-tier annotation scheme to categorize step-level actions. Construction and Formalization. To ensure reliable action assessment, we enforce strict graph purity by pruning invalid transitions and self-loops (example in Appx. D.3). Furthermore, while sub-goals follow a strict sequence, their internal atomic requirements are often permutation-invariant (example in Appx. D.4). By modeling each sub-goal’s completion as a state equivalence class, we seamlessly unify these diverse execution paths. Formally, the ARG is defined as a Directed Acyclic Graph (DAG)G = (V,E ): 4 Preprint Definition 4.1 (Sub-goals as Vertices). The vertex setV = S M m=1 g m comprisesMsub-goals in sequential order. Each sub-goalg m =s m,1 ,s m,2 ,...is an unordered set of permutation-invariant, valid states, strictly excluding error-induced states and redundant self-loops. Definition 4.2 (Actions as Edges). The edge setE ⊆ S M−1 m=1 (g m ×A m ×g m+1 )captures deterministic transitions (s,a,s ′ ) between consecutive sub-goals under admissible actions a∈A m . Dynamic Evolution. To capture the diverse spectrum of valid solutions, the ARG evolves dynamically. Upon verifying a novel successful trajectory at the rollout stage of training iterationk, we extract its new states (∆g m ) and actions (∆E ) to update the current graphG (k) via strict union: g (k+1) m = g (k) m ∪ ∆g m (1≤ m≤ M ),and E (k+1) =E (k) ∪ ∆E(5) These discrete updates strictly adhere to the purity principles, providing an increasingly comprehen- sive reference for action attribution over time (a raw-to-merged example is provided in Appx. D.3). Action Attribution. We evaluate any rollout trajectoryτ i =(s t ,a t ,s t+1 ) |τ i | t=1 generated at iteration k againstG (k) to formally annotate each step t using two binary criteria: (1) Reasonableness (Rea t ): Evaluates if an action forms a valid ARG transition:Rea t = I[(s t ,a t ,s t+1 )∈E (k) ]. While it filters explicit errors, it ignores valid but redundant loops. (2) Progress-Advancement (PA t ): Strictly quantifies task progression. An action is progress- advancing (PA t = 1) if it induces a valid ARG states t+1 ∈ V (k) while avoiding the historical trajectoryS ≤t =s 1 ,...,s t : PA t = I s t+1 ∈V (k) ≤t Thus, progress-advancing actions are a strict subset of reasonable ones (PA t = 1=⇒ Rea t = 1). Conversely, non-advancing actions (PA t = 0) encapsulate both explicit errors and structurally valid but stagnant steps. 4.2ACTION-INTERVENTION ANALYSIS By leveraging the reasonableness and progress-advancement annotations to assess fine-grained action quality, our pilot study reveals how individual steps dictate outcomes, motivating our solution to the uniform credit assignment dilemma. Probing Unreasonable Actions. Unreasonable actions hinder task progress by polluting the context history and disrupting subsequent decisions (Laban et al., 2026). Notably, they constitute a substantial proportion of successful GRPO trajectories (41.6% in ALFWorld, 39.6% in WebShop) of Qwen2.5- 1.5B-Instruct, where they are inadvertently reinforced by the uniform credit applied to preferred rollouts. To probe their impact, we select a clean ALFWorld trajectory (details in Appx. D.1) and sample 50 continuations,c i 50 i=1 , from a fixed state under two context conditions. As illustrated in Fig. 1(b), the clean control retains the original history, whereas the noise-injected condition prepends a four-step unreasonable segment. Despite sharing the identical underlying environment state, this visible context noise degrades the Expected Success Rate (ESR) from 82% to 58%. Insight 1: Unreasonable actions in the context actively impede the agent from reaching success. Suppressing Actions with Varying Future-Drift. Conversely, non-advancing (NA) actions are heavily concentrated in failed GRPO trajectories (93.1% in ALFWorld, 76.1% in WebShop), where they are suppressed uniformly. Given the autoregressive nature of LLMs, late-stage NA actions are often inevitable consequences of an already polluted context rather than making the mistake independently. Therefore, uniformly suppressing all actions within a failed trajectory is inherently unfair. To quantify the cascading effect, we define Future-Drift (D i,t , short as FD) as the inclusive count of downstream NA actions from step t: D i,t = |τ i | X t ′ =t 1− PA i,t ′ (6) To assess whether actions with higher Future-Drift warrant heavier penalization, we perform a targeted suppression intervention on a failed ALFWorld trajectory generated by Qwen2.5-1.5B-Instruct as 5 Preprint shown in Fig. 1(c). By preserving the trajectory prefix up to specific steps, forbidding the original action, and resampling 50 continuations, we measure the recovered ESR. Suppressing the actions with FD values of 47, 23, 11, and 4 yields ESRs of 24%, 16%, 10%, and 0%, respectively (case details in Appx. D.2). In this case, the higher the suppressed action’s Future-Drift, the more likely the agent is to recover and complete the task. Insight 2: Actions with higher FD should be prioritized for suppression. 4.3PROGRESS-AWARE ADVANTAGE SHAPING Building upon the empirical insights from § 4.2, we propose the Progress-Aware Advantage Shaping (ProAS) framework, aiming to resolve the uniform credit dilemma by asymmetrically reshaping the trajectory-level advantage A i into a step-wise, progress-aware signal ̃ A i,t : ̃ A i,t = Rea t · A i ,if A i > 0, D i,t ̄ D i +ε · A i , if A i < 0 and t∈T , A i ,otherwise, (7) whereTdenotes the steps sharing the uniform advantage, ̄ D i = 1 |T| P t ′ ∈T D i,t ′ is the average Future-Drift, andεensures numerical stability. This formulation branches into two mechanisms: (1) Masking Unreasonable Incentives (MUI): Aligning with Insight 1, it zeros out the local advantages of invalid actions (Rea t = 0) in preferred trajectories (A i > 0, usually successful) to prevent inadvertent reinforcement. (2) Asymmetric Penalty Redistribution (APR): Reflecting Insight 2, it leverages normalized Future-Drift to assign proportionally heavier penalties to early pivotal actions in unpreferred trajectories (A i < 0, usually failed), rectifying the unfairness of uniform suppression. 5EXPERIMENTAL SETUP To empirically validate the proposed ProAS framework, we conduct extensive experiments across complex, long-horizon agentic environments. Our experiments are structured to answer the following core research questions: RQ1: Performance & Efficiency (§ 6). Can ProAS consistently elevate task success rates and accelerate training convergence across different model scales under different environments? RQ2: Algorithm Compatibility (§ 6). Does ProAS seamlessly integrate with mainstream group- based RL baselines (e.g., GRPO, DAPO, GiGPO) as a robust plug-and-play module? RQ3: Advantage Shaping Design (§ 6.2.1). Are MUI and APR each individually necessary and mutually synergistic, and does ProAS’s Future-Drift-based redistribution outperform a simpler masking heuristic? RQ4: Robustness to ARG (§ 6.2.2). Does ProAS remain effective when the reference ARG is randomized, incomplete, static (non-evolving), or distilled from a teacher model? 5.1MODELS AND DATA Models. Our experiments are conducted across two different model scales: Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct (Qwen Team, 2024), which are denoted as 1.5B and 7B for brevity. Data. We train and validate on ALFWorld (Shridhar et al., 2021) and WebShop (Yao et al., 2023), two classical long-horizon multi-turn agentic environments (details in Appx. C). ALFWorld is a text-based embodied benchmark over six household task categories (Pick,Look,Clean,Heat,Cool,Pick2, details in Table. 5). Our 150-step training comprises 1777/1767/1784 unique executable tasks of seed 0/1/2 for training and 128 for validation. WebShop (Table 6) is an HTML-based online shopping environment, with 2015/2011/2036 tasks of seed 0/1/2 used for training and 128 for validation. 6 Preprint 5.1.1EVALUATION METRICS Performance Metrics. For ALFWorld, we report the average Success Rate (SR) across the entire validation set, alongside the per-category average SR. For WebShop, we report both the overall average SR and the Task Score (TS). TS is a checklist metric on a scale of 0 to 100: it averages the satisfaction of the requested attributes, options, and price constraint, and then scales this score by how well the purchased product matches the requested product type. Efficiency Metrics. We quantify training efficiency via speedupSpd@K = N base→K /N ProAS→K , which is defined as the ratio of environment interaction steps required by the baseline versus ProAS to first reach a targetKof SR. Reflecting task difficulties, we setK = 70%for ALFWorld and K = 50% for WebShop. 5.1.2IMPLEMENTATION DETAILS We conduct experiments upon Verl-Agent (Feng et al., 2025), training all models for 150 RL steps. We validate the policy every 10 RL steps and report metrics from the checkpoint achieving the highest SR. Unless otherwise specified, all experiments are conducted across three random seeds (0, 1, and 2), reporting the mean and standard deviation (std). See details in Appx. B. ARG Initialization. Unless otherwise specified, we initialize the ARG in ALFWorld using its official crowdsourced annotations. Given the strictly sequential nature of tasks in ALFWorld, we formulate each individual step as a distinct sub-goal. For WebShop, the ARG is initialized using its officially annotated sub-goals alongside their corresponding states and actions. 5.1.3BASELINES We consider baselines of different paradigms: (1) Proprietary models: GPT-5.6-Sol (OpenAI, 2026), the state-of-the-art model from OpenAI. We apply the reasoning effort as high, and evaluate it with ReAct prompting (Yao et al., 2022). (2) Prompting: Qwen2.5-1.5B-Instruct and Qwen2.5-7B- Instruct, the starting point to be trained. (3) Supervised Fine-Tuning (SFT): Tuning the agent by imitating curated turn-level oracle trajectories from the same training tasks as RL baselines (Details in Appx. B.3). (4) RL: the classical actor-crtic algorithm PPO (Schulman et al., 2017); mainstream group-based RL algorithms GRPO (Shao et al., 2024), DAPO (Yu et al., 2025), GiGPO (Feng et al., 2025); the state-of-the-art (SOTA) agentic RL method MiGPO (Wang et al., 2026b) with segment-level credit assignment. 6RESULTS AND ANALYSIS 6.1MAIN RESULTS Table 1 summarizes the main evaluation results on ALFWorld and WebShop. We structure our analysis to directly address our research questions regarding performance, efficiency (RQ1), and algorithm compatibility (RQ2). Baseline Comparisons. We first contrast ProAS against established learning paradigms. Although ProAS leverages annotated prior knowledge for ARG initialization, it significantly outperforms SFT, a direct strategy for utilizing such annotations. Specifically, GiGPO+ProAS surpasses SFT by 12.2 points on the 1.5B ALFWorld benchmark, demonstrating the superiority of active exploration over passive behavior cloning. Furthermore, PPO, a traditional RL algorithm featuring fine-grained credit assignment, exhibits massive variance across different random seeds in long-horizon settings, yielding a highly fluctuating36.5%± 28.7%SR on 1.5B ALFWorld. This instability likely stems from the high sensitivity of critic training to variations in the training data. In contrast, other critic-free methods, such as GRPO, DAPO, and GiGPO, maintain controllable variance while simultaneously achieving superior performance. State-of-the-Art Performance. Equipped with ProAS, group-based RL algorithms consistently establish new SOTA records. In ALFWorld, GiGPO+ProAS attains the highest SR of 94.3% on the 7B model. This surpasses the strong segment-level baseline MiGPO and eclipses the proprietary GPT-5.6-Sol by a massive 15.4 points. WebShop presents a notably steeper challenge, evidenced by GPT-5.6-Sol’s severe struggle at 21.9% SR. Despite this difficulty, ProAS variants dominate the 7 Preprint 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 ALFWorldWebShop PickLookCleanHeatCoolPick2ALLSpd.@70TSSRSpd.@50 Proprietary Model GPT-5.6-Sol (ReAct)90.983.368.083.379.268.278.9–27.621.9– Qwen2.5-1.5B-Instruct Direct Prompt24.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 – SFT99.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 – PPO51.5 ±26.4 33.3 ±22.0 33.3 ±38.9 36.1 ±33.7 33.3 ±33.1 22.7 ±19.8 36.5 ±28.7 –57.5 ±11.5 28.1 ±17.4 – MiGPO97.0 ±3.0 91.7 ±0.0 98.7 ±2.3 * 100.0 ±0.0 * 84.7 ±6.4 75.8 ±2.6 91.1 ±1.6 – 79.5 ±1.2 53.6 ±1.8 – GRPO80.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+ProAS90.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 1.59×85.3 ±2.4 64.6 ±1.2 1.79× * DAPO89.9 ±1.7 83.3 ±0.0 89.3 ±12.2 88.9 ±4.8 75.0 ±8.3 66.7 ±2.6 82.3 ±5.0 –79.2 ±2.5 57.3 ±4.6 – DAPO+ProAS93.9 ±3.0 86.1 ±9.6 84.0 ±6.9 94.4 ±4.8 83.3 ±4.2 77.3 ±4.5 86.5 ±1.2 1.27×87.2 ±0.7 66.7 ±1.2 * 1.61× GiGPO91.9 ±1.7 83.3 ±0.0 94.7 ±4.6 94.4 ±4.8 84.7 ±2.4 89.4 ±2.6 * 90.1 ±0.5 –83.9 ±0.4 64.3 ±3.9 – GiGPO+ProAS94.9 ±1.7 94.4 ±4.8 * 93.3 ±2.3 97.2 ±4.8 88.9 ±2.4 84.8 ±2.6 91.9 ±0.5 * 1.61× * 87.5 ±1.7 * 66.7 ±3.2 * 1.12× Qwen2.5-7B-Instruct Direct Prompt35.3 ±2.9 33.3 ±6.8 13.3 ±5.0 5.5 ±3.9 9.7 ±2.0 3.0 ±4.3 17.7 ±0.8 –3.4 ±1.1 0.5 ±0.4 – SFT100.0 ±0.0 * 88.9 ±4.0 96.0 ±3.3 100.0 ±0.0 * 93.1 ±1.9 * 1.5 ±2.1 80.0 ±0.4 – 81.9 ±0.5 70.0 ±0.8 – PPO87.9 ±6.1 75.0 ±16.7 56.0 ±13.9 47.2 ±12.7 37.5 ±19.1 51.5 ±11.4 60.9 ±11.7 –75.1 ±7.3 44.3 ±10.2 – MiGPO100.0 ±0.0 * 94.4 ±4.8 96.0 ±4.0 80.6 ±4.8 84.7 ±2.4 87.9 ±2.6 91.9 ±1.2 –88.0 ±2.2 67.2 ±3.1 – GRPO90.9 ±0.0 72.2 ±9.6 92.0 ±6.9 77.8 ±17.3 76.4 ±4.8 63.6 ±4.5 80.7 ±3.9 – 85.6 ±5.2 67.7 ±5.5 – GRPO+ProAS97.0 ±3.0 91.7 ±8.3 94.7 ±2.3 86.1 ±4.8 77.8 ±2.4 83.3 ±6.9 89.1 ±2.3 2.20×89.0 ±0.6 70.8 ±0.9 * 1.91× * DAPO97.0 ±3.0 83.3 ±14.4 96.0 ±4.0 88.9 ±9.6 76.4 ±6.4 84.8 ±6.9 88.8 ±5.2 –87.1 ±3.6 68.8 ±4.7 – DAPO+ProAS97.0 ±3.0 86.1 ±12.7 97.3 ±4.6 88.9 ±9.6 83.3 ±8.3 78.8 ±5.2 89.6 ±2.0 2.05×88.2 ±2.8 70.6 ±0.9 1.62× GiGPO97.0 ±3.0 100.0 ±0.0 * 97.3 ±2.3 97.2 ±4.8 87.5 ±0.0 86.4 ±9.1 93.8 ±2.1 – 88.3 ±1.8 70.3 ±1.6 – GiGPO+ProAS99.0 ±1.7 88.9 ±4.8 98.7 ±2.3 * 97.2 ±4.8 86.1 ±10.5 92.4 ±2.6 * 94.3 ±2.4 * 2.44× * 89.1 ±2.7 * 70.1 ±2.3 1.58× leaderboard. On the 1.5B model, both DAPO and GiGPO integrated with ProAS tie for the best SR at 66.7%, outperforming MiGPO by a striking 13.1 points. On the 7B scale, GRPO+ProAS peaks at 70.8%, further extending the lead over MiGPO. Algorithm Compatibility. Crucially, ProAS demonstrates remarkable plug-and-play compatibility, universally uplifting baseline RL algorithms across all tested configurations. For ALFWorld, equip- ping GRPO with ProAS yields the most dramatic improvements, boosting the SR by 16.7 points on the 1.5B model and 8.4 points on the 7B model. Consistent gains are mirrored in WebShop, where DAPO+ProAS generates a 9.4-point uplift at the 1.5B scale, and GRPO+ProAS provides a 3.1-point boost at 7B. This confirms ProAS as a versatile enhancer that elevates both the performance floor and ceiling of diverse group-based RL paradigms. Training Efficiency. Beyond asymptotic performance, ProAS significantly accelerates the training process. On average, it speeds up convergence to target success rates by approximately1.5×for the 1.5B model across both environments. Impressively, this efficiency gain scales favorably with model size: on the 7B model, ProAS accelerates learning by an average of2.2×on ALFWorld and1.7×on WebShop. 6.2ABLATION STUDY We ablate the core components of ProAS on the 1.5B model using GRPO as the base algorithm. § 6.2.1 ablates our advantage shaping mechanisms, demonstrating that disabling any single technique strictly degrades performance and disrupts their synergy. Subsequently, § 6.2.2 relaxes the ARG construction constraints to investigate ProAS’s robustness against reference quality and origin, while highlighting the critical necessity of the online dynamic evolution mechanism. 6.2.1ADVANTAGE SHAPING ABLATION To isolate the contributions of our specific advantage shaping interventions, we evaluate three ProAS variants: ProAS − , ProAS + , and ProAS msk± , as shown in Table 2(a). 8 Preprint 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. Method ALFWorld WebShop PickLookCleanHeatCoolPick2ALLTSSR GRPO80.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 + ProAS90.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 GRPO + ProAS msk± 80.8 ±4.6 72.2 ±4.8 74.7 ±12.2 83.3 ±8.3 70.8 ±4.2 56.1 ±2.6 72.9 ±2.4 83.5 ±2.0 63.8 ±2.5 (b) ARG Ablation Random67.7 ±7.0 38.9 ±9.6 56.0 ±10.6 44.4 ±4.8 34.7 ±19.7 28.8 ±6.9 47.7 ±4.8 78.6 ±2.1 49.2 ±3.6 Static87.9 ±6.1 83.3 ±0.0 94.7 ±2.3 * 86.1 ±4.8 70.8 ±7.2 72.7 ±4.5 82.8 ±2.8 85.2 ±1.7 65.9 ±2.7 * Incomplete85.9 ±1.7 75.0 ±8.3 77.3 ±4.6 77.8 ±4.8 76.4 ±2.4 66.7 ±10.5 77.3 ±2.1 85.0 ±2.4 63.0 ±3.2 Incomplete & Static82.8 ±7.6 75.0 ±8.3 76.0 ±4.0 77.8 ±4.8 62.5 ±12.5 57.6 ±6.9 72.1 ±5.2 82.3 ±1.4 57.6 ±2.4 Distill85.9 ±9.3 80.5 ±4.8 89.3 ±2.3 88.9 ±4.8 80.5 ±8.7 75.7 ±2.6 83.6 ±0.8 84.8 ±1.0 64.8 ±1.4 First, we ablate individual components: ProAS − disables MUI on preferred trajectories (A i > 0), incurring Success Rate (SR) drops of 15.4 and 1.3 points on ALFWorld and WebShop, respectively; ProAS + disables APR on unpreferred ones (A i < 0), causing a 3.7-point SR drop on ALFWorld and a 1.2-point Task Score (TS) drop on WebShop. Their suboptimality confirms that Both MUI and APR are indispensable and act synergistically. Second, we test an simpler heuristic. ProAS msk± preserves MUI but replaces APR by naively masking non-advancing actions whenA i < 0. Compared with GRPO+ProAS, it underperforms GRPO+ProAS by 14.1 points SR on ALFWorld and 0.8 points SR on WebShop. This confirms the benefit of APR’s Future-Drift weighting over simplistic masking. Notably, all three variants still outperform native GRPO on the aggregate metrics, highlighting the fundamental necessity of leveraging progress signals to resolve the uniform credit assignment dilemma. 6.2.2ARG ABLATION Randomreplaces ARG-derived annotations with random labels instead of matching against the graph. This causes a catastrophic collapse, dropping SR by 39.3 points on ALFWorld and 15.4 points on WebShop relative to ProAS (Table 2(b)). This confirms that clean, ARG-derived annotations are indispensable for accurate credit assignment. Incompleterandomly prunes 40% of the action-state pairs from the clean ARG to simulate severe degradation. Despite this, ProAS still outperforms GRPO by 7.0 points on ALFWorld. This robustness largely comes from ARG evolution (mentioned in Eq. 5): disabling it (Incomplete&Static) further drops SR by 5.2 points on ALFWorld and 5.4 points on WebShop relative toIncompletealone. Evolution matters even with a clean ARG, where disabling it (Static) lowers ALFWorld SR from 87.0% (GRPO+ProAS) to 82.8%, thoughStaticstill attains the best WebShop SR (65.9%) among all variants. These results confirm the importance of ARG evolution for ProAS, while showing ProAS remains robust to imperfect ARGs. Distill tests ProAS with synthetic references, since gold-standard trajectories are often unavailable in practice. We prompt a 7B model to generate successful rollouts across training tasks, building a distilled ARG covering 2,566 tasks. With this synthetic ARG, the 1.5B model reaches 83.6% SR on ALFWorld and 64.8% on WebShop, comparable to GRPO+ProAS and 13.3 and 7.8 points above GRPO, respectively. This validates ProAS’s applicability even on teacher-distilled trajectories. 9 Preprint 7CONCLUSION In this work, we expose the uniform credit assignment dilemma in critic-free agentic RL, where uniform advantages reinforce contextual noise in preferred trajectories (A i > 0) and ignore the cascading influence of actions in unpreferred ones (A i < 0). To address this without critic overhead, we proposed Progress-Aware Advantage Shaping (ProAS), which 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 evaluations across multiple model scales and environments confirm ProAS as a robust, universal enhancer that accelerates convergence and propels mainstream baselines to new state-of-the-art performance. The ablation study further confirms MUI-APR synergy, necessity of ARG evolution and robustness under incomplete or distilled ARGs. Together, these results establish a highly efficient, scalable pathway for elevating autonomous language agents. REFERENCES Victor Barres, Honghua Dong, Soham Ray, Xujie Si, and Karthik Narasimhan.τ 2 -bench: Evaluating conversational agents in a dual-control environment, 2025. URLhttps://arxiv.org/abs/2506. 07982. DeepSeek-AI. Deepseek-v4: Towards highly efficient million-token context intelligence, 2026. Bowen Ding, Yuhan Chen, Futing Wang, Lingfeng Ming, and Tao Lin. Do thinking tokens help or trap? towards more efficient large reasoning model, 2025. URLhttps://arxiv.org/abs/2506. 23840. Lang Feng, Zhenghai Xue, Tingcong Liu, and Bo An. Group-in-group policy optimization for llm agent training. arXiv preprint arXiv:2505.10978, 2025. GLM-5-Team, :, Aohan Zeng, Xin Lv, Zhenyu Hou, Zhengxiao Du, Qinkai Zheng, Bin Chen, Da Yin, Chendi Ge, Chenghua Huang, Chengxing Xie, Chenzheng Zhu, Congfeng Yin, Cunxiang Wang, Gengzheng Pan, Hao Zeng, Haoke Zhang, Haoran Wang, Huilong Chen, Jiajie Zhang, Jian Jiao, Jiaqi Guo, Jingsen Wang, Jingzhao Du, Jinzhu Wu, Kedong Wang, Lei Li, Lin Fan, Lucen Zhong, Mingdao Liu, Mingming Zhao, Pengfan Du, Qian Dong, Rui Lu, Shuang-Li, Shulin Cao, Song Liu, Ting Jiang, Xiaodong Chen, Xiaohan Zhang, Xuancheng Huang, Xuezhen Dong, Yabo Xu, Yao Wei, Yifan An, Yilin Niu, Yitong Zhu, Yuanhao Wen, Yukuo Cen, Yushi Bai, Zhongpei Qiao, Zihan Wang, Zikang Wang, Zilin Zhu, Ziqiang Liu, Zixuan Li, Bojie Wang, Bosi Wen, Can Huang, Changpeng Cai, Chao Yu, Chen Li, Chengwei Hu, Chenhui Zhang, Dan Zhang, Daoyan Lin, Dayong Yang, Di Wang, Ding Ai, Erle Zhu, Fangzhou Yi, Feiyu Chen, Guohong Wen, Hailong Sun, Haisha Zhao, Haiyi Hu, Hanchen Zhang, Hanrui Liu, Hanyu Zhang, Hao Peng, Hao Tai, Haobo Zhang, He Liu, Hongwei Wang, Hongxi Yan, Hongyu Ge, Huan Liu, Huanpeng Chu, Jia’ni Zhao, Jiachen Wang, Jiajing Zhao, Jiamin Ren, Jiapeng Wang, Jiaxin Zhang, Jiayi Gui, Jiayue Zhao, Jijie Li, Jing An, Jing Li, Jingwei Yuan, Jinhua Du, Jinxin Liu, Junkai Zhi, Junwen Duan, Kaiyue Zhou, Kangjian Wei, Ke Wang, Keyun Luo, Laiqiang Zhang, Leigang Sha, Liang Xu, Lindong Wu, Lintao Ding, Lu Chen, Minghao Li, Nianyi Lin, Pan Ta, Qiang Zou, Rongjun Song, Ruiqi Yang, Shangqing Tu, Shangtong Yang, Shaoxiang Wu, Shengyan Zhang, Shijie Li, Shuang Li, Shuyi Fan, Wei Qin, Wei Tian, Weining Zhang, Wenbo Yu, Wenjie Liang, Xiang Kuang, Xiangmeng Cheng, Xiangyang Li, Xiaoquan Yan, Xiaowei Hu, Xiaoying Ling, Xing Fan, Xingye Xia, Xinyuan Zhang, Xinze Zhang, Xirui Pan, Xu Zou, Xunkai Zhang, Yadi Liu, Yandong Wu, Yanfu Li, Yidong Wang, Yifan Zhu, Yijun Tan, Yilin Zhou, Yiming Pan, Ying Zhang, Yinpei Su, Yipeng Geng, Yong Yan, Yonglin Tan, Yuean Bi, Yuhan Shen, Yuhao Yang, Yujiang Li, Yunan Liu, Yunqing Wang, Yuntao Li, Yurong Wu, Yutao Zhang, Yuxi Duan, Yuxuan Zhang, Zezhen Liu, Zhengtao Jiang, Zhenhe Yan, Zheyu Zhang, Zhixiang Wei, Zhuo Chen, Zhuoer Feng, Zijun Yao, Ziwei Chai, Ziyuan Wang, Zuzhou Zhang, Bin Xu, Minlie Huang, Hongning Wang, Juanzi Li, Yuxiao Dong, and Jie Tang. Glm-5: from vibe coding to agentic engineering, 2026. URL https://arxiv.org/abs/2602.15763. Bowen Jin, Hansi Zeng, Zhenrui Yue, Jinsung Yoon, Sercan Arik, Dong Wang, Hamed Zamani, and Jiawei Han. Search-r1: Training llms to reason and leverage search engines with reinforcement learning, 2025. URL https://arxiv.org/abs/2503.09516. 10 Preprint Philippe Laban, Hiroaki Hayashi, Yingbo Zhou, and Jennifer Neville.Llms get lost in multi-turn conversation. In C. Vondrick, B. Hariharan, C. Raffel, L. Pinto, D. Yang, and A. Faust (eds.), International Conference on Learning Representations, volume 2026, p. 54738–54778, 2026. URLhttps://proceedings.iclr.c/paper_files/paper/2026/file/ 59f6421e64707225fdf5b28840679a07-Paper-Conference.pdf. Yujiang Li, Zhenyu Hou, Yi Jing, Jie Tang, and Yuxiao Dong. Compactionrl: Reinforcement learning with context compaction for long-horizon agents, 2026. URLhttps://arxiv.org/abs/2607. 05378. Siyuan Lu, Zechuan Wang, Hongxuan Zhang, Qintong Wu, Leilei Gan, Chenyi Zhuang, Jinjie Gu, and Tao Lin. Don’t just fine-tune the agent, tune the environment, 2026. URLhttps: //arxiv.org/abs/2510.10197. Run Luo, Lu Wang, Wanwei He, and Xiaobo Xia. Gui-r1: A generalist r1-style vision-language action model for gui agents. arXiv preprint arXiv:2504.10458, 2025. OpenAI. GPT-5.6: Frontier Intelligence That Scales with Your Ambition.https://openai.com/ index/gpt-5-6/, July 2026. Cheng Qian, Emre Can Acikgoz, Qi He, Hongru WANG, Xiusi Chen, Dilek Hakkani-Tur, Gokhan Tur, and Heng Ji.Toolrl: Reward is all tool learning needs.In D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen (eds.), Advances in Neural Information Processing Systems, volume 38, p. 105523–105553. Curran Asso- ciates, Inc., 2025. URLhttps://proceedings.neurips.c/paper_files/paper/2025/file/ 97c5b2707228e7e3fb67e4ecc2e0e607-Paper-Conference.pdf. Qwen Team. Qwen2.5 technical report, 2024. URL https://arxiv.org/abs/2412.15115. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017. URL https://arxiv.org/abs/1707.06347. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathe- matical reasoning in open language models, 2024. URL https://arxiv.org/abs/2402.03300. Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, et al. Alfworld: Aligning text and embodied environments for interactive learning. In International Conference on Learning Representations, 2021. Richard S. Sutton and Andrew G. Barto. Reinforcement learning - an introduction. Adaptive computation and machine learning. MIT Press, 1998. ISBN 978-0-262-19398-6. URLhttp: //w.incompleteideas.net/book/first/the-book.html. Hui-Ze Tan, Xiao-Wen Yang, Hao Chen, Jie-Jing Shao, Yi Wen, Yuteng Shen, Weihong Luo, Xiku Du, Lan-Zhe Guo, and Yu-Feng Li. Hindsight credit assignment for long-horizon llm agents, 2026. URL https://arxiv.org/abs/2603.08754. Harsh Trivedi, Tushar Khot, Mareike Hartmann, Ruskin Manku, Vinty Dong, Edward Li, Shashank Gupta, Ashish Sabharwal, and Niranjan Balasubramanian. AppWorld: A controllable world of apps and people for benchmarking interactive coding agents. In ACL, 2024. Tianyi Wang, Yixia Li, Long Li, Yibiao Chen, Shaohan Huang, Yun Chen, Peng Li, Yang Liu, and Guanhua Chen. Sppo: Sequence-level ppo for long-horizon reasoning tasks, 2026a. URL https://arxiv.org/abs/2604.08865. Zixuan Wang, Yuchen Yan, Hongxing Li, Teng Pan, Dingming Li, Ruiqing Zhang, Weiming Lu, Jun Xiao, Yueting Zhuang, and Yongliang Shen. Milestone-guided policy learning for long-horizon language agents. In Forty-third International Conference on Machine Learning, 2026b. URL https://openreview.net/forum?id=Ga3AR4EF6R. 11 Preprint Zhepei Wei, Wenlin Yao, Yao Liu, Weizhi Zhang, Qin Lu, Liang Qiu, Changlong Yu, Puyang Xu, Chao Zhang, Bing Yin, Hyokun Yun, and Lihong Li. WebAgent-R1: Training web agents via end- to-end multi-turn reinforcement learning. In The 2025 Conference on Empirical Methods in Natural Language Processing (EMNLP 2025), 2025. URL https://arxiv.org/abs/2505.16421. Frank (Fangzheng) Xu, Yufan Song, Boxuan Li, Yuxuan Tang, Kritanjali Jain, Mengxue Bao, Zora Wang, Xuhui Zhou, Zhitong Guo, Murong Cao, Mingyang Yang, Hao Yang Lu, Amaad Martin, Zhe Su, Leander Maben, Raj Mehta, Wayne Chi, Lawrence Jang, Yiqing Xie, Shuyan Zhou, and Graham Neubig.Theagentcompany: Benchmarking llm agents on consequential real world tasks. In D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen (eds.), Advances in Neural Information Process- ing Systems, volume 38, Main Conference. Curran Associates, Inc., 2025. doi: 10.52202/ 085713-0315.URLhttps://proceedings.neurips.c/paper_files/paper/2025/file/ 0d744742f6fac4d1134c019b7cef3c8a-Paper-Datasets_and_Benchmarks_Track.pdf. John Yang, Carlos E. Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. Swe-agent: Agent-computer interfaces enable automated software engineering, 2024. URL https://arxiv.org/abs/2405.15793. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022. Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents, 2023. URLhttps://arxiv.org/ abs/2207.01206. Ori Yoran, Samuel Joseph Amouyal, Chaitanya Malaviya, Ben Bogin, Ofir Press, and Jonathan Berant. AssistantBench: Can web agents solve realistic and time-consuming tasks? In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen (eds.), Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, p. 8938–8968, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024.emnlp-main.505. URL https://aclanthology.org/2024.emnlp-main.505/. Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, Xin Liu, Haibin Lin, Zhiqi Lin, Bole Ma, Guangming Sheng, Yuxuan Tong, Chi Zhang, Mofan Zhang, Wang Zhang, Hang Zhu, Jinhua Zhu, Jiaze Chen, Jiangjie Chen, Chengyi Wang, Hongli Yu, Yuxuan Song, Xiangpeng Wei, Hao Zhou, Jingjing Liu, Wei-Ying Ma, Ya-Qin Zhang, Lin Yan, Mu Qiao, Yonghui Wu, and Mingxuan Wang. Dapo: An open-source llm reinforcement learning system at scale, 2025. URL https://arxiv.org/abs/2503.14476. Yu Yue, Yufeng Yuan, Qiying Yu, Xiaochen Zuo, Ruofei Zhu, Wenyuan Xu, Jiaze Chen, Chengyi Wang, TianTian Fan, Zhengyin Du, Xiangpeng Wei, Xiangyu Yu, Gaohong Liu, Juncai Liu, Lingjun Liu, Haibin Lin, Zhiqi Lin, Bole Ma, Chi Zhang, Mofan Zhang, Wang Zhang, Hang Zhu, Ru Zhang, Xin Liu, Mingxuan Wang, Yonghui Wu, and Lin Yan. Vapo: Efficient and reliable reinforcement learning for advanced reasoning tasks, 2025. URL https://arxiv.org/abs/2504.05118. Yida Zhao, Kuan Li, Xixi Wu, Liwen Zhang, Ding-Chu Zhang, Baixuan Li, Maojia Song, Zhuo Chen, Chenxi Wang, Xinyu Wang, Kewei Tu, Pengjun Xie, Fei Huang, Jingren Zhou, and Yong Jiang. Repurposing synthetic data for fine-grained search agent supervision. In The Fourteenth International Conference on Learning Representations, 2026. URLhttps://openreview.net/ forum?id=CByVWPpb8T. 12 Preprint ADERIVATION OF THE GRPO POLICY GRADIENT We derive Eq. 4 from the clipped surrogate in Eq. 3, omitting entropy and KL regularization as in the main text. During each policy update, the sampling policyπ θ old , sampled trajectories, and group-normalized advantagesA i are fixed; in particular,∇ θ A i = 0. Leth i,t = (x,y i,<t )denote the conditioning context and assume the old policy assigns positive probability to each sampled token. Clipped token-level surrogate. Writing ρ = ρ i,t (θ), the contribution of token (i,t) is ℓ i,t (θ) = min(ρA i , clip(ρ, 1− ε, 1 + ε)A i ) = A i min(ρ, 1 + ε), A i > 0, A i max(ρ, 1− ε), A i < 0, 0,A i = 0. (8) Thus, the surrogate is flat only whenA i > 0andρ > 1 + ε, or whenA i < 0andρ < 1− ε. A ratio outside the clipping interval does not, by itself, imply zero gradient: the gradient remains active when the ratio moves in the unfavorable direction. Away from the clipping boundaries, define 1 clip i,t = 0, A i > 0 and ρ i,t > 1 + ε, 0, A i < 0 and ρ i,t < 1− ε, 1, otherwise. (9) At a clipping kink, we adopt the derivative of the active linear branch (indicator1), a valid generalized- gradient convention. For A i = 0, the gradient is zero regardless of the indicator. Importance-ratio derivative. Since the denominator is fixed, the log-derivative identity gives ∇ θ ρ i,t (θ) = ∇ θ π θ (y i,t | h i,t ) π θ old (y i,t | h i,t ) = ρ i,t (θ)∇ θ logπ θ (y i,t | h i,t ). (10) Applying the chain rule to Eq. 8 therefore yields ∇ θ ℓ i,t (θ) = 1 clip i,t A i ρ i,t (θ)∇ θ logπ θ (y i,t | h i,t ).(11) Group-level gradient.Under the usual conditions for exchanging differentiation and expectation, the fixed sampling distribution introduces no additional derivative term. Averaging the token-level derivatives gives ∇ θ J GRPO (θ) = E x,τ i G i=1 ∼π θ old " 1 G G X i=1 1 |τ i | |τ i | X t=1 1 clip i,t A i ρ i,t (θ) ·∇ θ logπ θ (y i,t | h i,t ) # , (12) which recovers Eq. 4. Atθ = θ old ,ρ i,t = 1and the clipping indicator is1forε > 0. Consequently, all tokens in a trajectory share the same advantage multiplierA i (and trajectory normalization1/|τ i |), although their score-function gradients can differ. This is the uniform credit-assignment property discussed in Sec. 3.2. BFURTHER IMPLEMENTATION DETAILS B.1TRAINING FRAMEWORK For ALFWorld and WebShop, we adopt the Verl-Agent (Feng et al., 2025) framework. To ensure robustness and reproducibility, we sample and freeze three distinct training sets with environment seeds 0, 1, and 2 for independent and repeated training. For fair evaluation, all resulting model checkpoints are assessed on a unified, static validation set of 128 tasks. This validation set is strictly 13 Preprint disjoint from the training data, rigorously preventing any potential data leakage. Validation uses a temperature of 0.4 in both ALFWorld and WebShop. RL and SFT share the same turn-level input format illustrated in Tables 11 and 12: each prompt contains the task instruction, current observation, admissible actions, and the visible interaction history from the two most recent observation-action turns. The only difference between SFT and RL data is the assistant response, which is curated offline for SFT but generated online for RL. All experiments are conducted on GPUs. For ALFWorld and WebShop, each 1.5B model run uses 2 GPUs, while each 7B model run uses 4 GPUs. B.2RL CONFIGURATION General. We follow the standard Verl-Agent (Feng et al., 2025) configuration and use the same settings across all RL methods unless otherwise specified. Models are optimized with AdamW using a learning rate of10 −6 , weight decay0.01, and gradient clipping at1.0. We use a PPO clipping ratio of0.2, an entropy coefficient of0.001, a KL-loss coefficient of0.01, and one policy-update epoch per rollout batch. At each RL iteration, we sample 16 prompts and generateG = 8trajectories per prompt with temperature 1.0 and top-p = 1.0. For ALFWorld, we set the maximum prompt and response lengths to 2,048 and 512 tokens, re- spectively, cap each episode at 50 steps, and use a PPO mini-batch size of 256. For WebShop, the corresponding settings are 4,096 prompt tokens, 512 response tokens, 15 steps, and a PPO mini-batch size of 64. Reward. Across all runs, we use the same rule-based sparse outcome reward in both environments: a successful trajectory receives10, whereas an unsuccessful trajectory receives0. Each invalid action additionally incurs a penalty of−0.1. Specifically, a response is marked invalid if it omits a complete <think>. . . </think> or <action>. . . </action> block, or contains Chinese characters. PPO. For PPO (Schulman et al., 2017), we estimate advantages using generalized advantage estima- tion (GAE) with discount factorγ = 1.0and trace-decay parameterλ = 1.0. We train a separate critic with AdamW using a learning rate of10 −5 and weight decay0.01, without critic warmup. The remaining policy optimization and rollout settings follow the shared configuration above. DAPO. For DAPO (Yu et al., 2025), we use asymmetric PPO clipping with lower and upper ratios of0.2and0.28, respectively, and a dual-clip coefficient of10.0. We disable the actor KL loss and entropy regularization, use token-mean loss aggregation, set the AdamW weight decay to0.1with 10 learning-rate warmup steps, and disable group filtering. GiGPO. For GiGPO (Feng et al., 2025), we set the temporal discount factor toγ = 0.95and the step-level advantage weight to1.0. Step advantages are normalized by both the group mean and standard deviation in ALFWorld, and by the group mean only in WebShop. GiGPO+ProAS. Since GiGPO adopts step-level group-normalized advantages, different steps within the same trajectory need not share the same advantage. This, however, does not affect the plug-in integration of ProAS. We apply MUI to actions with excessively positive advantages, and cluster negative-advantage actions within each trajectory according to their individual advantage magnitudes, rescaling them by future-miss normalization to a mean of one per cluster. MiGPO. For MiGPO (Wang et al., 2026b), we use mean-normalized segment-level advantages. In ALFWorld, we set the milestone-matching threshold to0.95, the reverse-decay factor to0.9, and the step-level advantage weight to10.0. WebShop uses environment-provided dynamic milestone signals, with a reverse-decay factor of 0.95 and a step-level advantage weight of 1.0. B.3SFT DETAILS B.3.1DATA CURATION. To construct a controlled imitation-learning baseline matching the RL methods’ task exposure, we curate a supervised dataset for each environment seed (0, 1, 2) from the frozen training tasks: ALFWorld: We execute the official annotated expert trajectory to obtain one demonstration per unique training game. 14 Preprint WebShop: Lacking official experts, we instantiate a deterministic, goal-conditioned oracle from our ARG using task metadata (target product, query, and options). The resulting trajectories strictly follow the ARG’s sub-goal progression (g 1 →·→ g 6 , details in Table 10), explicitly grounding the demonstrations in the same progress structure used by ProAS. Aligning with the data setting in RL experiments. we represent SFT data as turn-level examples rather than complete trajectories. Each input contains the task instruction, current observation, admissible actions, and the two most recent interaction turns. Table 11 and Table 12 demonstrate the SFT data example of ALFWorld and WebShop. Training Configuration. We perform full-parameter fine-tuning of Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct with the SFT trainer based on FSDP in Verl-Agent, minimizing the token-level negative log-likelihood of the oracle responses. We train for 3 epochs with AdamW (β 1 = 0.9, β 2 = 0.95), a peak learning rate of10 −5 , weight decay of0.01, and gradient clipping at1.0. The learning rate follows a cosine schedule with a3%warmup. We use a maximum sequence length of 4,096 tokens with left truncation and per-GPU micro-batch sizes of 4 and 2 for the 1.5B and 7B models, respectively. We save the checkpoint at the end of each epoch and evaluate every epoch checkpoint on the same frozen 128-task validation set used for RL. The SFT result is reported from the checkpoint with the highest validation success rate. CENVIRONMENT DETAILS ALFWorld. ALFWorld (Shridhar et al., 2021) is a text-based embodied benchmark built from household tasks in simulated indoor scenes. It covers six task families:single-object manipulation (Pick),object examination (Look),cleaning (Clean),heating (Heat), cooling (Cool), andtwo-object manipulation (Pick2). At each step, the agent observes textual environment feedback and issues one admissible natural-language action, making ALFWorld a multi-turn, single-step environment. Table 5 reports deduplicated task-family counts for the three frozen training sets and the shared validation set. 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 familyTraining seed 0Training seed 1Training seed 2Validation Pick39139239933 Look16116216212 Clean31531131025 Heat24924123912 Cool26226826624 Pick239939340822 Total177717671784128 15 Preprint WebShop. WebShop (Yao et al., 2023) is an HTML-based shopping environment in which the agent must search for a product ofFashion,Garden,Electronics,GroceryandBeauty, then navigate result and product pages, select required options, and purchase the item that matches the user instruction. The task naturally involves both ordered milestones, such as opening the target product before purchasing it, and unordered option choices, such as selecting size and color in either order. Similar to ALFWorld, WebShop allows one environment action per interaction turn. Table 6 reports the distribution of training sets of seed 0/1/2 and the validation set. 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. Task categoryTraining seed 0Training seed 1Training seed 2Validation Fashion15701568157795 Garden29429128323 Electronics5753576 Grocery3737392 Beauty5762802 Total201520112036128 16 Preprint DCASE STUDY D.1UNREASONABLE ACTION PROBING ANALYSIS IN ALFWORLD We compare two visible-history conditions while fixing the underlying environment state and rollout budget. Both conditions replay the same three-action clean prefix and reach the same continuation point: the agent is atdesk 1, holdingkeychain 2, with 47 steps remaining. From this state, we independently sample 50 continuationsc i 50 i=1 under each condition. In the noise-injected condition, four unreasonable actions are prepended only to the policy-visible interaction history; they are not executed in the continuation environment and therefore do not alter its starting state. Table 7 first presents the task ARG and then traces the clean and noise-injected conditions separately. Only the four injected unreasonable actions are highlighted in pink. The sampled suffixes are summarized by a continuation row, followed by the Expected Success Rate (ESR) for each condition. The two panels therefore differ only in the pink history segment; their clean prefix, continuation state, and rollout budget are identical. The observed ESR decrease from82%to58%thus diagnoses the effect of unreasonable content in the policy-visible history rather than a change in the underlying environment state. D.2VARYING FUTURE-DRIFT ACTIONS SUPPRESSION ANALYSIS IN ALFWORLD We examine the suppression of four non-advancing actions from the same 50-step failed ALFWorld rollout in Table 8 (c), which are actions of steps3,28,40, and47. At each position, we preserve the complete preceding prefix, reject only an exact match to the original action, and independently sample 50 continuationsc i 50 i=1 . The intervention results exhibit a monotonic relation in this case: the ESR is24%,16%,10%, and0% when suppressing actions with FD47,23,11, and4, respectively. The larger recovery at higher-FD positions supports Future-Drift as a diagnostic proxy for an action’s downstream failure burden. Because the four decisions occur at different prefixes and remaining horizons, this case is intended as direct intervention evidence for the diagnostic trend rather than a standalone estimate of a universal causal effect. D.3THE ARG DYNAMIC EVOLUTION IN ALFWORLD Table 9 illustrates the online ARG evolution mechanism using the taskLook at a pencil under the desk lamp. Because the environment’s success criterion broadly accepts any pencil index (e.g., pencil 1orpencil 2), the task inherently possesses multiple valid solutions that a single static ARG fails to cover. To capture this diversity, any rollout verified as successful during training is first purified by pruning invalid and inadmissible steps. The retained valid path is then seamlessly merged into the current ARG, dynamically expanding its coverage of viable solution trajectories. D.4THE ORDER-AGNOSTIC OF ACTIONS IN WEBSHOP Table 10 shows a WebShop case from Qwen2.5-1.5B-Instruct GRPO rollouts. The task-level ARG is ordered across sub-goals, but its option-configuration sub-goalg 3 contains an unordered set of required options. A partialg 3 state satisfies one required option, whileg 3 is completed only after all required options are selected. The price and attribute constraints,g 4 andg 5 , are checked at purchase time before the trajectory reaches g 6 . The contrast highlights the intended granularity of action annotations deriving from ARG. Trajectories A and B differ only withing 3 : they visit different intermediate option states but reach the same completion-state equivalence class, so both option orders are treated as progress-advancing. Trajectory C shows the complementary cases: a wrong option and a premature purchase are unsupported by the ARG, whereas a repeated click on an already selected option can be reasonable but non-advancing. Thus, the ARG preserves ordering constraints among high-level sub-goals while avoiding spurious penalties for valid option permutations. 17 Preprint ETRAINING SPEEDUP CURVES Fig. 2 visualizes the validation learning curves used to compute the training-speedup results in Table 1. For each base algorithm, speedup is measured by the number of RL steps required to reach a fixed success-rate target before and after adding ProAS. 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. 18 Preprint 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 TaskPut a keychain on a desk. LabelsRea t = 1 denotes an ARG-supported transition, and PA t = 1 denotes advancement to a previously unvisited ARG state. Task ARG ARGg 1 sidetable reached take keychain 2 −→ g 2 keychain held go to desk 1 −→ g 3 desk reached while holding the keychain move keychain 2 to desk 1 −→ g 4 success. Initial edgeThe initial transition go to sidetable 1 enters g 1 . Clean condition Condition tAction or operationARG annotationRea t PA t Clean1 go to sidetable 1Enters g 1 .11 2 take keychain 2 from sidetable 1 Acquires the target keychain and enters g 2 .11 3 go to desk 1Reaches the target desk while holding the keychain: g 3 . 11 4 Continuation sampling (n = 50) 50 independently sampled continuations from g 3 ; 41 reach g 4 . – Expected Success Rate: 82% (41/50); Wilson 95% CI [69.2%, 90.2%]. Noise-injected condition Condition tAction or operationARG annotationRea t PA t Noise- injected I1 go to desk 1Noise.00 I2 go to cabinet 1Noise.00 I3 open cabinet 1Noise.00 I4 go to desk 1Noise.00 1 go to sidetable 1Enters g 1 .11 2 take keychain 2 from sidetable 1 Acquires the target keychain and enters g 2 .11 3 go to desk 1Reaches the same continuation state g 3 .11 4 Continuation sampling (n = 50) 50 independently sampled continuations from the same g 3 state; 29 reach g 4 . – Expected Success Rate: 58% (29/50); Wilson 95% CI [44.2%, 70.6%]. 19 Preprint 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 TaskLook at a bowl under the desk lamp. LabelsRea t = 1 denotes an ARG-supported transition, and 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 ARGInitial state go to desk 1 −→ g 1 desk reached take bowl 1/2 −→ g 2 target bowl held use desklamp 1 −→ g 3 success. Raw trajectory ConditiontAction or operationARG annotationRea t PA t Original failure1–2 look×2Initial probe followed by a self-loop; no ARG progress.00 3 look(FD = 47)Admissible self-loop at the first intervention position.00 4–7 look×4Repeated self-loops before reaching the desk.00 8 go to desk 1Enters g 1 ; the trajectory’s only advancing action.11 9–27 look×15; probes; one unsupported bowl command Nineteen non-advancing actions remain at g 1 .00 28 look at bowl under desklamp 1(FD = 23) Inadmissible command at the second intervention position.00 29–39 Repeated bowl/lamp commands, probes, and redundant navigation Eleven non-advancing actions remain at g 1 .00 40 look at bowl 1 from desk 1 with desklamp 1(FD= 11) Inadmissible command at the third intervention position.00 41–46 Malformed or unsupported bowl/lamp commands and probes Six non-advancing actions remain at g 1 .00 47 look at bowl 2(FD = 4)Inadmissible command at the final intervention position.00 48–50 look at bowl 2×3Repeated inadmissible actions exhaust the horizon.00 Outcome: failure after the 50-step horizon. Suppressing on Step 3 (Future-Drift 47) Step 31–2Replay the original prefixReturns to the decision state immediately before Step 3.– 3Suppress exact action lookReject and resample only this action at the selected decision.00 3–50 Continuation sampling (n = 50) 12 independently sampled continuations succeed.– Expected Success Rate: 24% (12/50); Wilson 95% CI [14.3%, 37.4%]. Suppressing on Step 28 (Future-Drift 23) Step 281–27Replay the original prefixReturns to the decision state immediately before Step 28.– 28Suppress exact original bowl/lamp command Reject and resample only the selected inadmissible action.00 28–50 Continuation sampling (n = 50) 8 independently sampled continuations succeed.– Expected Success Rate: 16% (8/50); Wilson 95% CI [8.3%, 28.5%]. Suppressing on Step 40 (Future-Drift 11) Step 401–39Replay the original prefixReturns to the decision state immediately before Step 40.– 40Suppress exact original bowl/lamp command Reject and resample only the selected inadmissible action.00 40–50 Continuation sampling (n = 50) 5 independently sampled continuations succeed.– Expected Success Rate: 10% (5/50); Wilson 95% CI [4.3%, 21.4%]. Suppressing on Step 47 (Future-Drift 4) Step 471–46Replay the original prefixReturns to the decision state immediately before Step 47.– 47Suppress exact action look at bowl 2 Reject and resample only the selected inadmissible action.00 47–50 Continuation sampling (n = 50) None of the 50 independently sampled continuations succeeds. – Expected Success Rate: 0% (0/50); Wilson 95% CI [0.0%, 7.1%]. 20 Preprint Table 9: An ALFWorld case illustrating strict ARG purification and online graph evolution. The action-level annotations are computed against the pre-update graphG (17) . After the rollout succeeds, only its valid, non-self-loop transitions are extracted as a new reference path and merged intoG (18) . Case setup TaskLook at a pencil under the desk lamp. SourceQwen2.5-1.5B-Instruct rollout at training iteration 17; success; reward = 10. G (17) Existing expert path: initial state go to desk 1 −→ g 1 desk reached use desklamp 1 −→ g 2 desk lamp activated take pencil 2 from desk 1 −→ g 3 success. LabelsRea t = 1 denotes a transition supported byG (17) , and 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 tAction a t Annotation underG (17) Rea t PA t Purification 1 go to desk 1Matches the expert transition and reaches g 1 .11Retain 2 examine desk 1Invalid action.00Prune 3 examine desk 1Repeats the same abstract state (self_loop).00Prune 4 examine desk 1Repeats the same abstract state (self_loop).00Prune 5 examine desk 1Repeats the same abstract state (self_loop).00Prune 6 look at #pencil 1 with #desklamp 1 Inadmissible action.00Prune 7 inventoryRedundant examination.00Prune 8 use desklamp 1Matches the expert transition and reaches g 2 .11Retain 9 examine desk 1Redundant examination.00Prune 10 take pencil 1 from desk 1 Novel and valid action toward success.00Retain Evolved ARG G (18) initial state g 1 desk reached g 2 desk lamp activated g 3 pencil 2 acquired (existing expert path) g ′ 3 pencil 1 acquired (new online path) go to desk 1 use desklamp 1 take pencil 2 from desk 1 take pencil 1 from desk 1 21 Preprint 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. Case setup TaskFind women’s activewear with nylon spandex, color=green, size=x-large, and price below $30. Target B08G8DXR5N ARGg 1 target visible→ g 2 target opened→ g 3 options green, x-large→ g 4 price verified→ g 5 attributes verified→ g 6 purchase. LabelsRea t = 1 denotes an ARG-supported transition, and 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 tAction a t ARG annotationRea t PA t A: size first1 search[. . . ]Target product appears in the search results: s 1,1 ∈ g 1 . 11 2 click[target]Target product page is opened: s 2,1 ∈ g 2 .11 3 click[x-large]Partial g 3 state: the required size is selected.11 4 click[green]g 3 completed: all required options are selected.11 5 click[buy now]Price and attributes are verified; purchase reaches g 6 . 11 Outcome: success; reward = 10. B: color first1 search[. . . ]Target product appears in the search results: s 1,1 ∈ g 1 . 11 2 click[target]Target product page is opened: s 2,1 ∈ g 2 .11 3 click[green]Partial g 3 state: the required color is selected.11 4 click[x-large]g 3 completed: all required options are selected.11 5 click[buy now]Price and attributes are verified; purchase reaches g 6 . 11 Outcome: success; reward = 10. C: failed1 search[. . . ]Target product appears in the search results: s 1,1 ∈ g 1 . 11 2 click[target]Target product page is opened: s 2,1 ∈ g 2 .11 3 click[large]Wrong size option; the transition is not supported by the ARG. 00 4 click[description]Neutral page inspection that does not satisfy any ARG requirement. 00 5 click[buy now] Premature purchase before the required option set is completed. 00 9 click[x-large]Recovery segment reaches a partial g 3 state.11 10 click[green]g 3 completed after the required color is selected.11 11 click[x-large]Redundant option click; the valid ARG state has already been visited. 10 Outcome: failure; reward = 0. 22 Preprint Table 11: A turn-level SFT example from ALFWorld. Underlined text denotes instance-specific fields populated from the task, environment state, and interaction history. SFT Example for ALFWorld System Prompt: You are Qwen, created by Alibaba Cloud. You are a helpful assistant. User Prompt: You are an expert agent operating in the ALFRED Embodied Environment. Your task is to:puttwo bookinbed. Prior to this step, you have already taken4step(s). Below are the most recent2observations and the corresponding actions you took: [Observation3:‘Youarriveatsidetable1.Onthesidetable1,youseeanalarmclock1,acd2,and apencil2.’,Action3:‘gotoshelf1’] [Observation4:‘Youarriveatshelf1.Ontheshelf1,youseenothing.’,Action4:‘gotodrawer 1’] You are now at step 5 and your current observation is:Youarriveatdrawer1.Thedrawer1is closed. Your admissible actions of the current situation are:[‘examinedrawer1’,‘gotobed1’,‘gotodesk 1’,‘gotodrawer2’,‘gotogarbagecan1’,‘gotoshelf1’,‘gotosidetable1’,‘inventory’,‘look’, ‘opendrawer1’]. Now it’s your turn to take an action. You should first reason step-by-step about the current situation. This reasoning process MUST be enclosed within <think> </think> tags. Once you’ve finished your reasoning, you should choose an admissible action for the current step and present it within <action> </action> tags. Assistant Response (Supervision Target): <think> The best action is to open drawer 1. </think> <action> open drawer 1 </action> Table 12: A turn-level SFT example from WebShop. Underlined text denotes instance-specific fields populated from the task, environment state, and interaction history. SFT Example for WebShop System Prompt: You are Qwen, created by Alibaba Cloud. You are a helpful assistant. User Prompt: You are an expert autonomous agent operating in the WebShop e-commerce environment. Your task is to:Findmeplugplay,easyuseturntables,andpricelowerthan150.00dollars. Prior to this step, you have already taken1 step. Below is the most recent observation and the corresponding action you took: [Observation1:‘WebShop[SEP]Instruction:[SEP]Findmeplugplay,easyuseturntables,and pricelowerthan150.00dollars[SEP]Search’,Action1:‘search[turntables]’] You are now at step 2 and your current observation is:‘BacktoSearch’[SEP]‘Page1(Total results:1)’[SEP]‘Next>’[SEP]‘B09Q6CZ59K’[SEP]‘ngruama8USBPortableMiniVinyl TurntableAudioPlayer’[SEP]‘$110.54’. Your admissible actions of the current situation are:[‘click[backtosearch]’,‘click[next>]’, ‘click[b09q6cz59k]’]. Now it’s your turn to take one action for the current step. You should first reason step-by-step about the current situation, then determine which admissible action best advances the shopping goal. This reasoning process MUST be enclosed within<think> </think> tags. Once you’ve finished your reasoning, you should choose an admissible action for the current step and present it within <action> </action> tags. Assistant Response (Supervision Target): <think> Open the target product B09Q6CZ59K. </think> <action> click[b09q6cz59k] </action> 23