回到定义：通过轨迹图估计智能体强化学习的步骤级优势

# Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning
Source: [https://arxiv.org/html/2609.28963](https://arxiv.org/html/2609.28963)
Xincheng Yao††thanks:Work done during internship at Tencent AI Platform Department\.Affiliation:School of Information Science and Electronic Engineering, Shanghai Jiao Tong University\.Weiming LiuAffiliation:Tencent AI Platform Department\.Chongyang Zhang††thanks:Corresponding Author\.Affiliation:School of Information Science and Electronic Engineering, Shanghai Jiao Tong University\.Affiliation:MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong University\.\{i\-doversunny\_zhang\}@sjtu\.edu\.cnAffiliation:School of Information Science and Electronic Engineering, Shanghai Jiao Tong University\.\{haobofuweimingliu\}@tencent\.comAffiliation:Tencent AI Platform Department\.

###### Abstract

Group\-based reinforcement learning \(RL\) methods, such as GRPO and its variants, have become a leading paradigm for training reasoning and agentic large language models \(LLMs\)\. While their group\-normalized advantage estimation is reliable at the response level, it becomes systematically biased at the step level, since coarse\-grained trajectory\-level advantages are hard to accurately reflect the contribution of individual steps \(*i\.e*, failed trajectories may contain valuable steps\)\. Revisiting the foundational RL definition, we notice that GRPO’s success on single\-turn tasks stems from its advantage estimation strategy, which adheres to the basic definition: the mean reward of multiple actions sampled from the same state constitutes a credible state\-value estimate\. Extending the faithful estimation to step\-level would in principle demand sampling multiple actions from each intermediate state, which is too costly on a per\-state basis\. To mitigate this issue, we can aggregate similar states across trajectories to better leverage global information\. Since each trajectory is a chain of state\-action transitions, cross\-trajectory information flow requires modeling state\-action transitions across trajectories, which naturally forms a directed graph\. Building on this insight, we propose aGraph\-basedFaithful sTep\-level credit\-assignment framework \(GRAFT\) that grafts all rollout trajectories into a trajectory graph, recovering node state\-values via Bellman iteration on the graph, and assigning credit to each edge by the node value difference\. Theoretically, the estimated step\-level advantage faithfully adheres to the basic advantage definition in RL\. To further ensure the reliability of step\-level advantage estimation, we further propose Graph GAE, which extends GAE to the trajectory graph for reducing the impact of state\-value estimation bias\. Experiments across a range of multi\-turn agentic benchmarks show consistent gains over GRPO and superior performance compared to recent agentic RL algorithms\. Code will be available at[https://github\.com/xcyao00/GRAFT](https://github.com/xcyao00/GRAFT)\.

## 1Introduction

Reinforcement learning \(RL\) has emerged as a cornerstone for training reasoning and agentic large language models \(LLMs\)\([OpenAI, 2024](https://arxiv.org/html/2609.28963#bib.bib32);[DeepSeek\-AI, 2025](https://arxiv.org/html/2609.28963#bib.bib33);[Team, 2026a](https://arxiv.org/html/2609.28963#bib.bib34);[Team, 2026c](https://arxiv.org/html/2609.28963#bib.bib35);[Team, 2025](https://arxiv.org/html/2609.28963#bib.bib36);[Team, 2026b](https://arxiv.org/html/2609.28963#bib.bib37)\)\. Among the various RL algorithms\([Schulman et al\., 2017](https://arxiv.org/html/2609.28963#bib.bib1);[Ahmadian et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib25);[Rafailov et al\., 2023](https://arxiv.org/html/2609.28963#bib.bib26);[Williams, 1992](https://arxiv.org/html/2609.28963#bib.bib27);[Shao et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib2)\)adapted to the LLM domain, Group Relative Policy Optimization \(GRPO\)\([Shao et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib2)\)and its variants\([Seed, 2025](https://arxiv.org/html/2609.28963#bib.bib4);[Zheng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib3);[Gao et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib5);[Yao et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib6)\)have gained the most significant traction, primarily due to their critic\-free design\. For each prompt, GRPO samples a group ofNNresponses and estimates the advantage of each response by normalizing its reward against the group\-level statistics\. Within the standard RL framework, this strategy is theoretically well\-grounded at the response level: when the entire response is treated as a single action and the promptqqas the initial state, the group mean exactly serves as a valid estimate of the state valueVπ​\(q\)V\_\{\\pi\}\(q\), and the resulting normalized advantage aligns with the standard definitionAπ​\(q,a\)=Qπ​\(q,a\)−Vπ​\(q\)A\_\{\\pi\}\(q,a\)=Q\_\{\\pi\}\(q,a\)\-V\_\{\\pi\}\(q\)\(see Sec\.[2](https://arxiv.org/html/2609.28963#S2)\)\.

However, this mechanism shifts fundamentally in multi\-turn tasks, where trajectory\-level advantages are too coarse\-grained to accurately capture the contribution of individual steps\. A successful trajectory may contain redundant or erroneous steps that receive unwarranted credit, while a failed trajectory may include valuable steps whose benefits are obscured by subsequent mistakes\. A common remedy is to employ a Process Reward Model \(PRM\) to assign step\-wise rewards and extend the group\-based advantage estimation at each step indextt\([Shao et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib2);[Cui et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib7);[Xi et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib8)\)\. However, training PRMs requires costly step\-level annotations and often suffers from distributional shift when applied to out\-of\-distribution reasoning traces\. Moreover, as analyzed in Sec\.[2](https://arxiv.org/html/2609.28963#S2), applying group normalization per stepttincurs systematic bias\. Becausesi,ts\_\{i,t\}is a trajectory prefix, different trajectories usually occupy different intermediate states at the same step indextt; consequently, the “group” used to estimateVπ​\(si,t\)V\_\{\\pi\}\(s\_\{i,t\}\)aggregates samples from distinct states rather than a single shared state\. The resulting bias is systematic and grows with trajectory diversity\. The theoretically faithful solution is to resampleN−1N\-1additional continuations from each intermediate state, but this recovers unbiasedness at an𝒪⁡\(N2​T\)\\mathcal\{O\}\(N^\{2\}T\)rollout cost that is essentially unaffordable for long\-horizon multi\-turn training\.

To mitigate this issue while preserving theoretically faithful advantage estimation, we should aggregate similar states across trajectories to better leverage global information\. Since each trajectory can be regarded as a chain of state\-action transitions, cross\-trajectory information flow requires modeling state\-action transitions across trajectories, which naturally forms a directed graph, where nodes represent states and edges represent actions\. With this insight, we can reorganizeNNtrajectories from isolated chains into a unified trajectory graph\. Each node in this graph aggregates all actions executed from the same state across all trajectories, providing the on\-state action groups required for a more credible step\-level advantage estimation at no additional cost\.

Building on the trajectory graph insight, we propose aGraph\-basedFaithful sTep\-level credit assignment \(GRAFT\) framework, which graftsNNrollout trajectories into a unified trajectory graph so that more faithful step\-level advantages can be estimated in accordance with the foundational RL definition\. First,*graph construction*canonicalizes states via exact matching or embedding\-based similarity matching, merging semantically identical states across trajectories into a single node with a shared on\-state action group\. Second, to estimate the state\-value for every node,*value propagation*applies Bellman iteration over the graph using only the rewards attached to the terminal nodes\. In sparse reward settings, the converged value estimation is a direct empirical approximation of the definition of a standard value function\. Third, given these node values, we define the step advantage asAt=γ​V​\(st\+1\)−V⁡\(st\)A\_\{t\}=\\gamma V\(s\_\{t\+1\}\)\-V\(s\_\{t\}\), which coincides with the standard advantage definition \(see Sec\.[3](https://arxiv.org/html/2609.28963#S3)\)\. Additionally, to further ensure the reliability of step\-level advantage estimation, we take advantage of Generalized Advantage Estimation \(GAE\), which is the de facto in RL that can reduce the impact of state\-value estimation bias\. Specifically, we propose Graph GAE, which extends GAE to the trajectory graph by computing a weighted sum of the subsequent multi\-hop average advantage estimates\. Compared to prior methods, the step\-level advantage estimates obtained by our method are theoretically sound and exactly aligned with the fundamental definition\. Furthermore, GRAFT only requires outcome rewards, eliminating the reliance on PRM\-assigned step\-level rewards\. Experiments across a range of multi\-turn agentic benchmarks show consistent gains over GRPO and superior performance compared to recent agentic RL algorithms\.

## 2Preliminary Analysis

In this section, we revisit the advantage estimation problem from the perspective of standard definitions in reinforcement learning\. We begin by formally defining the state\-action \(Q\) functionQπQ\_\{\\pi\}, the value functionVπV\_\{\\pi\}, and the advantage functionAπA\_\{\\pi\}:

Qπ​\(st,at\)=𝔼st\+1,at\+1,…​\[∑l=0∞γl​r​\(st\+l\)\]\\displaystyle Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)=\\mathbb\{E\}\_\{s\_\{t\+1\},a\_\{t\+1\},\\dots\}\\bigg\[\\sum\_\{l=0\}^\{\\infty\}\\gamma^\{l\}r\(s\_\{t\+l\}\)\\bigg\]Vπ​\(st\)=𝔼at,st\+1,at\+1,…​\[∑l=0∞γl​r​\(st\+l\)\]\\displaystyle V\_\{\\pi\}\(s\_\{t\}\)=\\mathbb\{E\}\_\{a\_\{t\},s\_\{t\+1\},a\_\{t\+1\},\\dots\}\\bigg\[\\sum\_\{l=0\}^\{\\infty\}\\gamma^\{l\}r\(s\_\{t\+l\}\)\\bigg\]Aπ​\(st,at\)=Qπ​\(st,at\)−Vπ​\(st\)\\displaystyle A\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)=Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)\-V\_\{\\pi\}\(s\_\{t\}\)\(1\)whereat∼π⁡\(at∣st\)a\_\{t\}\\sim\\pi\(a\_\{t\}\\mid s\_\{t\}\)andst\+1∼P⁡\(st\+1∣st,at\)s\_\{t\+1\}\\sim P\(s\_\{t\+1\}\\mid s\_\{t\},a\_\{t\}\)\. TheQπ​\(st,at\)Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)denotes the expected return when taking an actionata\_\{t\}at statests\_\{t\},Qπ​\(st,at\)=𝔼st\+1,at\+1,…​\[r⁡\(st\)\+γ​r​\(st\+1\)\+γ2​r​\(st\+2\)\+…\]Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)=\\mathbb\{E\}\_\{s\_\{t\+1\},a\_\{t\+1\},\\dots\}\[r\(s\_\{t\}\)\+\\gamma r\(s\_\{t\+1\}\)\+\\gamma^\{2\}r\(s\_\{t\+2\}\)\+\\dots\]111If thest\+1s\_\{t\+1\}is deterministic,Qπ​\(st,at\)Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)is also equal tor⁡\(st\)\+γ​Vπ​\(st\+1\)r\(s\_\{t\}\)\+\\gamma V\_\{\\pi\}\(s\_\{t\+1\}\)\., wherer⁡\(st\)r\(s\_\{t\}\)is the reward for transition \(sts\_\{t\},ata\_\{t\},st\+1s\_\{t\+1\}\)\. Compared toQπ​\(st,at\)Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\), the only difference inVπ​\(st\)V\_\{\\pi\}\(s\_\{t\}\)is that the actionata\_\{t\}needs to be expected, which means the expected return starting from statests\_\{t\}\. Then, the connection betweenQπ​\(st,at\)Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)andVπ​\(st\)V\_\{\\pi\}\(s\_\{t\}\)is thatVπ​\(st\)=𝔼at​\[Qπ​\(st,at\)\]V\_\{\\pi\}\(s\_\{t\}\)=\\mathbb\{E\}\_\{a\_\{t\}\}\[Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)\]\. Thus, the advantage can be understood as “the benefit of performing a specific actionata\_\{t\}in statests\_\{t\}compared to the average effect of all actions at that state”\.

In LLMs, the input promptqqcan be regarded as the initial state, denoted ass1s\_\{1\}\. For action, it can be defined at various levels of granularity: as the whole responseoo, individual tokens, or intermediate reasoning steps\. In GRPO\([Shao et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib2)\), the whole response is treated as a single action, for which a scalar reward is assigned\. Since the generation process is terminated, there will be no subsequentat\+1a\_\{t\+1\}\. Moreover, state transitions in LLMs are inherently deterministic \(*i\.e\.*,st\+1s\_\{t\+1\}is obtained by concatenating the generated tokensata\_\{t\}to the previous contextsts\_\{t\}\)\. Therefore, the expectation overst\+1s\_\{t\+1\}in estimatingQπ​\(st,at\)Q\_\{\\pi\}\(s\_\{t\},a\_\{t\}\)can be omitted, also theat\+1a\_\{t\+1\}and subsequent states and actions can all be omitted\. Thus, the Q\-value of \(qq,oo\) simplifies toQ⁡\(q,o\)=rQ\(q,o\)=r\. Accordingly, the value ofqqcan be defined asV⁡\(q\)=𝔼o​\[Q⁡\(q,o\)\]=1N​∑i=1NQ⁡\(q,oi\)=1N​∑i=1NriV\(q\)=\\mathbb\{E\}\_\{o\}\[Q\(q,o\)\]=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}Q\(q,o\_\{i\}\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}r\_\{i\}\.

We now revisit the advantage estimation strategy in GRPO, where the advantage is calculated as:

A^i=ri−mean⁡\(\{r1,r2,…,rN\}\)std⁡\(\{r1,r2,…,rN\}\)\\hat\{A\}\_\{i\}=\\frac\{r\_\{i\}\-\{\\rm mean\}\(\\\{r\_\{1\},r\_\{2\},\\dots,r\_\{N\}\\\}\)\}\{\{\\rm std\}\(\\\{r\_\{1\},r\_\{2\},\\dots,r\_\{N\}\\\}\)\}\(2\)It can be found that this estimator aligns precisely with the standard definition of the advantage function in Eq\.\([1](https://arxiv.org/html/2609.28963#S2.Ex1)\), asri=Q⁡\(q,oi\)r\_\{i\}=Q\(q,o\_\{i\}\)andmean⁡\(\{ri,r2,…,rN\}\)=V⁡\(q\)\{\\rm mean\}\(\\\{r\_\{i\},r\_\{2\},\\dots,r\_\{N\}\\\}\)=V\(q\)\(GRPO has additional normalization\)\. However, a critical mismatch arises: while the derivation treats the entire response as a single action, GRPO assignsA^i\\hat\{A\}\_\{i\}uniformly to each token within the response\.

To correctly utilize the advantage in Eq\.\([2](https://arxiv.org/html/2609.28963#S2.E2)\), we need to treat the whole response as an action and compute the importance ratio at the sequence level\. The sequence\-level importance ratio can be derived from the likelihood decomposition,πθ​\(oi\|q\)πθo​l​d​\(oi\|q\)=πθ​\(oi,1\|q\)​πθ​\(oi,2\|q,oi,<2\)​…πθo​l​d​\(oi,1\|q\)​πθo​l​d​\(oi,2\|q,oi,<2\)​…\\frac\{\\pi\_\{\\theta\}\(o\_\{i\}\|q\)\}\{\\pi\_\{\\theta\_\{old\}\}\(o\_\{i\}\|q\)\}=\\frac\{\\pi\_\{\\theta\}\(o\_\{i,1\}\|q\)\\pi\_\{\\theta\}\(o\_\{i,2\}\|q,o\_\{i,<2\}\)\\dots\}\{\\pi\_\{\\theta\_\{old\}\}\(o\_\{i,1\}\|q\)\\pi\_\{\\theta\_\{old\}\}\(o\_\{i,2\}\|q,o\_\{i,<2\}\)\\dots\}\. To avoid numerical instability caused by the cumulative multiplication, we can adopt the geometric mean\. Accordingly, the importance ratiowi​\(θ\)w\_\{i\}\(\\theta\)for the responseoio\_\{i\}is defined as follows:

wi​\(θ\)=\(πθ​\(oi\|q\)πθo​l​d​\(oi\|q\)\)1\|oi\|=exp⁡\(1\|oi\|​∑t=1\|oi\|log​πθ​\(oi,t\|q,oi,<t\)πθo​l​d​\(oi,t\|q,oi,<t\)\)w\_\{i\}\(\\theta\)=\\bigg\(\\frac\{\\pi\_\{\\theta\}\(o\_\{i\}\|q\)\}\{\\pi\_\{\\theta\_\{old\}\}\(o\_\{i\}\|q\)\}\\bigg\)^\{\\frac\{1\}\{\|o\_\{i\}\|\}\}=\{\\rm exp\}\\bigg\(\\frac\{1\}\{\|o\_\{i\}\|\}\\sum\_\{t=1\}^\{\|o\_\{i\}\|\}\{\\rm log\}\\frac\{\\pi\_\{\\theta\}\(o\_\{i,t\}\|q,o\_\{i,<t\}\)\}\{\\pi\_\{\\theta\_\{old\}\}\(o\_\{i,t\}\|q,o\_\{i,<t\}\)\}\\bigg\)\(3\)Then, the calibrated GRPO optimization objective is defined as follows:

𝒥G​R​P​O−C\(θ\)=𝔼q∼𝒟,\{oi\}i=1N∼πθo​l​d\(⋅\|q\)\[1N∑i=1Nmin\(wi\(θ\)A^i,clip\(wi\(θ\),1−ϵ,1\+ϵ\)A^i\)\]\\mathcal\{J\}\_\{GRPO\-C\}\(\\theta\)=\\mathbb\{E\}\_\{q\\sim\\mathcal\{D\},\\\{o\_\{i\}\\\}\_\{i=1\}^\{N\}\\sim\\pi\_\{\\theta\_\{old\}\}\(\\cdot\|q\)\}\\bigg\[\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\{\\rm min\}\\Big\(w\_\{i\}\(\\theta\)\\hat\{A\}\_\{i\},\{\\rm clip\}\(w\_\{i\}\(\\theta\),1\-\\epsilon,1\+\\epsilon\)\\hat\{A\}\_\{i\}\\Big\)\\bigg\]\(4\)
However, assigning a single advantage to the whole response still suffers from coarse granularity, especially in multi\-turn agentic tasks that are inherently step\-by\-step\. To this end, we further analyze how to perform step\-level advantage estimation that can adhere to the standard definition\. Fors1s\_\{1\}\(the prompt\) andai,1a\_\{i,1\}\(the first step\), the advantage isA^i,1=Q⁡\(s1,ai,1\)−V⁡\(s1\)=ri,1−1N​∑j=1Nrj,1\\hat\{A\}\_\{i,1\}=Q\(s\_\{1\},a\_\{i,1\}\)\-V\(s\_\{1\}\)=r\_\{i,1\}\-\\frac\{1\}\{N\}\\sum\_\{j=1\}^\{N\}r\_\{j,1\}, whereri,1r\_\{i,1\}is the reward for the first step of theii\-th response\. Here, we use the reward to approximate the return, strictly according to the definition, it should beQ⁡\(s1,ai,1\)=ri,1\+γ​ri,2\+…Q\(s\_\{1\},a\_\{i,1\}\)=r\_\{i,1\}\+\\gamma r\_\{i,2\}\+\\dots\. Then, fors1s\_\{1\}anda1a\_\{1\}, the advantage estimation can align with GRPO\. However, the situation diverges from the second step onward\. Sinces2s\_\{2\}is the concatenation ofs1s\_\{1\}anda1a\_\{1\}, there is no guarantee thatsi,2s\_\{i,2\}remains identical across allNNresponses\. The worst case is that if everyai,1a\_\{i,1\}differs, eachsi,2s\_\{i,2\}will be distinct\. Forsi,2s\_\{i,2\}andai,2a\_\{i,2\}, the valueV⁡\(s2\)V\(s\_\{2\}\)cannot be reliably estimated because there are notNNsamples ofai,2a\_\{i,2\}conditioned on the samesi,2s\_\{i,2\}\. Despite this, in GRPO with process supervision\([Shao et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib2);[Cui et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib7)\), the advantage is directly calculated byA^i,t=ri,t−mean⁡\(r1,t,r2,t,…,rN⁡\(t\),t\)std⁡\(r1,t,r2,t,…,rN⁡\(t\),t\)\\hat\{A\}\_\{i,t\}=\\frac\{r\_\{i,t\}\-\{\\rm mean\}\(r\_\{1,t\},r\_\{2,t\},\\dots,r\_\{N\(t\),t\}\)\}\{\{\\rm std\}\(r\_\{1,t\},r\_\{2,t\},\\dots,r\_\{N\(t\),t\}\)\}, whereN⁡\(t\)N\(t\)is the number of responses that reach steptt\. This introduces a systematic bias: actionsaj,t,j≠ia\_\{j,t\},j\\neq ithat don’t belong tosi,ts\_\{i,t\}are also incorrectly used to estimateV⁡\(st\)V\(s\_\{t\}\)\. To mitigate this bias, a straightforward solution is to adopt the Monte Carlo sampling\. Forsi,ts\_\{i,t\}, we treat it as the prefix and sampleN−1N\-1extra\{ai,tj\}j=1N−1\\\{a^\{j\}\_\{i,t\}\\\}\_\{j=1\}^\{N\-1\}from the LLM\. With the existingai,ta\_\{i,t\}, theseNNactions enable an unbiased estimation of the advantageA^i,t\\hat\{A\}\_\{i,t\}\.

## 3Proposed Method

![Refer to caption](https://arxiv.org/html/2609.28963v1/framework.png)Figure 1:Method overview\. GivenNNrollouts for each prompt, GRAFT merges trajectories into a trajectory graph\. Terminal rewards are then propagated backward via Bellman iteration to estimate node state\-values\. The state\-value difference between two nodesγ​V​\(st\+1\)−V⁡\(st\)\\gamma V\(s\_\{t\+1\}\)\-V\(s\_\{t\}\)is assigned as the step\-level advantage, which coincides with the standard advantage function definition \(see Sec\.[3\.3](https://arxiv.org/html/2609.28963#S3.SS3)\)\.The analysis in Sec\.[2](https://arxiv.org/html/2609.28963#S2)reveals a fundamental challenge in applying GRPO\-style advantage estimation to agentic RL: the value functionVπ​\(si,t\)V\_\{\\pi\}\(s\_\{i,t\}\)at an intermediate statesi,ts\_\{i,t\}cannot be reliably estimated unless multiple actions are sampled from the same state\. The sampling\-based remedy outlined in Sec\.[2](https://arxiv.org/html/2609.28963#S2)is theoretically sound but computationally prohibitive, requiring𝒪⁡\(N2​T\)\\mathcal\{O\}\(N^\{2\}T\)rollout cost\.

To mitigate this issue while preserving definition\-adherent estimation, we should aggregate similar states across trajectories to better leverage global information\. Crucially, different trajectories are not fully independent, different actions can also reach semantically identical intermediate states \(see experiments in Appendix[D\.2](https://arxiv.org/html/2609.28963#A4.SS2)\)\. This means all rollout data from a prompt can form a directed graph, where nodes represent states and edges represent actions, rather than being regarded asNNisolated chains\. By aggregating all edges outgoing from the same node, we obtain a natural group of actions sampled from the same state, enabling more faithful step\-level advantage estimation at no additional rollout cost\. The full framework is illustrated in Fig\.[1](https://arxiv.org/html/2609.28963#S3.F1)\. Note that GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\)has employed the way of aggregating cross\-trajectory steps sharing the same state into a group to compute step\-level advantages within the group\. Compared to this plain method of aggregating all steps into multiple independent groups, we further discuss that our method would have more advantages over GiGPO in Appendix[A\.1](https://arxiv.org/html/2609.28963#A1.SS1)\.

### 3\.1Graph Construction

Formal definition\.Let𝒯=\{\(si,t,ai,t,si,t\+1\)\}\\mathcal\{T\}=\\\{\(s\_\{i,t\},a\_\{i,t\},s\_\{i,t\+1\}\)\\\}denotes the set of all transition tuples collected fromNNparallel rollouts for a given task with promptqq\. We construct a task\-specific directed graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\), where each nodeu,v∈𝒱u,v\\in\\mathcal\{V\}corresponds to a canonicalized state, and each edge\(u,v,a\)∈ℰ\(u,v,a\)\\in\\mathcal\{E\}corresponds to a transitionst→𝑎st\+1s\_\{t\}\\xrightarrow\{a\}s\_\{t\+1\}such thatu=ϕ⁡\(st\)u=\\phi\(s\_\{t\}\)andv=ϕ⁡\(st\+1\)v=\\phi\(s\_\{t\+1\}\)\.

State canonicalization\.In our framework, the state represents both the predefined environment state and the LLM response prefix up to a specific step \(as discussed in Sec\.[2](https://arxiv.org/html/2609.28963#S2)\)\. Two statesssands′s^\{\\prime\}will be mapped to the same node ifϕ⁡\(s\)=ϕ⁡\(s′\)\\phi\(s\)=\\phi\(s^\{\\prime\}\)\. In practice, we can employ two canonicalization modes: \(i\)exact matching, applied when all states are predefined strings provided by the environment, hereϕ⁡\(s\)\\phi\(s\)is a deterministic hash of the state string; and \(ii\)similarity\-based matching, applied when states are derived from raw LLM contexts, heressands′s^\{\\prime\}are merged into a node if the cosine similarity between their encoded embedding vectors exceeds a thresholdτ\\tau, andϕ⁡\(s\)\\phi\(s\)returns a unique identifier \(UID\) for the resulting cluster\. The latter handles a key practical reality: language models frequently introduce minor lexical variations even when generating semantically identical content, rendering exact string matching insufficient for reliable state identification in unstructured settings\.

Sink nodes\.For each trajectoryii, the final statesi,Ts\_\{i,T\}\(the state terminated or reached the max turns\) is designated as a sink node with terminal rewardRi∈\{0,1\}R\_\{i\}\\in\\\{0,1\\\}, where00and11indicate the failure and success of the trajectory, respectively\.

### 3\.2State\-Value Estimation via Bellman Iteration

Given the graph𝒢\\mathcal\{G\}and the rewards in the terminal nodes, our goal is to assign a state\-value estimateV⁡\(u\)V\(u\)to every nodeu∈𝒱u\\in\\mathcal\{V\}\. To leverage the graph’s transition structure, we can perform the classical Bellman value iteration on the graph: starting from the terminal nodes with their outcome rewards, we iteratively propagate value estimates backward through the graph until convergence\.

Bellman equation\.For sink nodesf∈𝒮sinkf\\in\\mathcal\{S\}\_\{\\text\{sink\}\}, the value is fixed to the terminal reward:V⁡\(f\)=R⁡\(f\),f∈𝒮sinkV\(f\)=R\(f\),f\\in\\mathcal\{S\}\_\{\\text\{sink\}\}\. For non\-sink nodes, we adopt the “action\-level” aggregation scheme, where the node value is computed as the mean over distinct actions of the expected next\-state value:

V⁡\(u\)=∑a∈𝒜⁡\(u\)π^​\(a∣u\)​∑v∈𝒱P^​\(v∣u,a\)⋅γ⋅V⁡\(v\)V\(u\)=\\sum\_\{a\\in\\mathcal\{A\}\(u\)\}\\hat\{\\pi\}\(a\\mid u\)\\sum\_\{v\\in\\mathcal\{V\}\}\\hat\{P\}\(v\\mid u,a\)\\cdot\\gamma\\cdot V\(v\)\(5\)where𝒜⁡\(u\)\\mathcal\{A\}\(u\)is the set of distinct actions executed from nodeuu, andπ^​\(a∣u\)\\hat\{\\pi\}\(a\\mid u\)andP^​\(v∣u,a\)\\hat\{P\}\(v\\mid u,a\)are the empirical transition probability estimated from edge counts:

π^​\(a∣u\)=count\(u→𝑎⋅\)∑a′count\(u→a′⋅\),P^​\(v∣u,a\)=count​\(u→𝑎v\)∑v′count​\(u→𝑎v′\)\\hat\{\\pi\}\(a\\mid u\)=\\frac\{\\text\{count\}\(u\\xrightarrow\{a\}\\cdot\)\}\{\\sum\_\{a^\{\\prime\}\}\\text\{count\}\(u\\xrightarrow\{a^\{\\prime\}\}\\cdot\)\},\\quad\\quad\\hat\{P\}\(v\\mid u,a\)=\\frac\{\\text\{count\}\(u\\xrightarrow\{a\}v\)\}\{\\sum\_\{v^\{\\prime\}\}\\text\{count\}\(u\\xrightarrow\{a\}v^\{\\prime\}\)\}\(6\)
Theoretical connection\.The action\-level Bellman equation is a direct empirical approximation of the standard value function \(Eq\.\([1](https://arxiv.org/html/2609.28963#S2.Ex1)\)\)\. Under sparse reward settings \(rewards are assigned only at sink nodes\), the state\-value satisfiesV⁡\(st\)=𝔼at​\[Q⁡\(st,at\)\]V\(s\_\{t\}\)=\\mathbb\{E\}\_\{a\_\{t\}\}\[Q\(s\_\{t\},a\_\{t\}\)\]andQ⁡\(st,at\)=𝔼st\+1​\[γ​V​\(st\+1\)\]Q\(s\_\{t\},a\_\{t\}\)=\\mathbb\{E\}\_\{s\_\{t\+1\}\}\[\\gamma V\(s\_\{t\+1\}\)\]\(see Sec\.[2](https://arxiv.org/html/2609.28963#S2)\)\. Combining these yields:

V⁡\(st\)=𝔼at​\[𝔼st\+1​\[γ​V​\(st\+1\)\]\]=∑a∈𝒜⁡\(st\)π^​\(a∣u\)​∑vP^​\(v∣st,a\)⋅γ⋅V⁡\(v\)V\(s\_\{t\}\)=\\mathbb\{E\}\_\{a\_\{t\}\}\\left\[\\mathbb\{E\}\_\{s\_\{t\+1\}\}\[\\gamma V\(s\_\{t\+1\}\)\]\\right\]=\\sum\_\{a\\in\\mathcal\{A\}\(s\_\{t\}\)\}\\hat\{\\pi\}\(a\\mid u\)\\sum\_\{v\}\\hat\{P\}\(v\\mid s\_\{t\},a\)\\cdot\\gamma\\cdot V\(v\)\(7\)which is precisely the action\-level update rule defined in Eq\.\([5](https://arxiv.org/html/2609.28963#S3.E5)\)\.

Iterative solver\.We solve the Bellman equation via Gauss\-Seidel value iteration\([Wikipedia, 2006](https://arxiv.org/html/2609.28963#bib.bib49)\)\. To accelerate convergence, we determine the updating order by computing the reverse\-BFS distance from each node to the nearest sink node: nodes closer to a sink node are updated earlier, so information propagates from sinks back to source nodes in as few sweeps as possible\. Nodes that cannot reach any sink node retainV⁡\(u\)=0V\(u\)=0, which constitutes the correct fixed point under sparse rewards\. The iteration terminates whenmaxu⁡\|V\(k\+1\)​\(u\)−V\(k\)​\(u\)\|<ϵ\\max\_\{u\}\|V^\{\(k\+1\)\}\(u\)\-V^\{\(k\)\}\(u\)\|<\\epsilon\(defaultϵ=10−8\\epsilon=10^\{\-8\}\)\. Sinceγ<1\\gamma<1, the Bellman operator is a contraction mapping and convergence is guaranteed\. The maximum number of iterations is set adaptively askmax=⌈log⁡\(ϵ\)/log⁡\(γ\)⌉\+50k\_\{\\max\}=\\lceil\\log\(\\epsilon\)/\\log\(\\gamma\)\\rceil\+50to ensure convergence for anyγ∈\(0,1\)\\gamma\\in\(0,1\)\.

### 3\.3Step\-Level Advantage Estimation

Given the converged value estimates\{V⁡\(u\)\}u∈𝒱\\\{V\(u\)\\\}\_\{u\\in\\mathcal\{V\}\}, we define the step\-level advantage for each executed transition\(st,at,st\+1\)\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)as:

At=γ⋅V⁡\(ϕ⁡\(st\+1\)\)−V⁡\(ϕ⁡\(st\)\)A\_\{t\}=\\gamma\\cdot V\(\\phi\(s\_\{t\+1\}\)\)\-V\(\\phi\(s\_\{t\}\)\)\(8\)
Notably, as analyzed in Sec\.[2](https://arxiv.org/html/2609.28963#S2), we know thatA⁡\(st,at\)=Q⁡\(st,at\)−V⁡\(st\)=r⁡\(st\)\+γ​V​\(st\+1\)−V⁡\(st\)A\(s\_\{t\},a\_\{t\}\)=Q\(s\_\{t\},a\_\{t\}\)\-V\(s\_\{t\}\)=r\(s\_\{t\}\)\+\\gamma V\(s\_\{t\+1\}\)\-V\(s\_\{t\}\)\. In sparse\-reward settings where the environment step rewardr⁡\(st\)r\(s\_\{t\}\)is zero, theAtA\_\{t\}coincides exactly with the standard advantage function definition \(*i\.e\.*, which is also called TD\(0\) in RL\)\. Intuitively,At\>0A\_\{t\}\>0indicates that actionata\_\{t\}moves the agent toward a higher\-value state \(closer to success\), andAt<0A\_\{t\}<0signals a transition toward a lower\-value state\.

###### Proposition 1\(Lower Advantage Estimation Error\)\.

Given rollouts sampled from a fixed policyπ\\piin a finite\-horizon deterministic environment with sparse rewards\. Define

Ω=\{\(s,a\):0<Pr⁡\(R⁡\(τ\)\>0∣St=s,At=a\)<1\}\\Omega=\\left\\\{\(s,a\):0<\\Pr\\\!\\left\(R\(\\tau\)\>0\\mid S\_\{t\}=s,A\_\{t\}=a\\right\)<1\\right\\\}as the set of state\-action pairs that admit both successful and failed continuations\. Let

XtG=rt\+γ​Vπ​\(St\+1\)−Vπ​\(St\)X\_\{t\}^\{G\}=r\_\{t\}\+\\gamma V^\{\\pi\}\(S\_\{t\+1\}\)\-V^\{\\pi\}\(S\_\{t\}\)denote the graph\-based step\-level credit, and let

XtS=Gt−Vπ​\(St\),XtE=R⁡\(τ\)−𝔼τ∼π​\[R⁡\(τ\)∣S0=s0\]X\_\{t\}^\{S\}=G\_\{t\}\-V^\{\\pi\}\(S\_\{t\}\),\\qquad X\_\{t\}^\{E\}=R\(\\tau\)\-\\mathbb\{E\}\_\{\\tau\\sim\\pi\}\[R\(\\tau\)\\mid S\_\{0\}=s\_\{0\}\]denote the population counterparts of the step\-level credit of GiGPO and the trajectory\-level credit of GRPO, respectively\. Then

ℰ⁡\(XG\)≤min⁡\{ℰ⁡\(XS\),ℰ⁡\(XE\)\}\\mathcal\{E\}\(X^\{G\}\)\\leq\\min\\left\\\{\\mathcal\{E\}\(X^\{S\}\),\\mathcal\{E\}\(X^\{E\}\)\\right\\\}whereℰ⁡\(X\)=𝔼τ∼π​\[\(Xt−Aπ​\(St,At\)\)2\]\\mathcal\{E\}\(X\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\}\\left\[\\bigl\(X\_\{t\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\\bigr\)^\{2\}\\right\]is the population estimation error of a credit signal X\. Moreover, the inequality is strict wheneverΩ\\Omegahas positive visitation probability underπ\\pi\.

The proof of Proposition[1](https://arxiv.org/html/2609.28963#Thmproposition1)is provided in Appendix[C](https://arxiv.org/html/2609.28963#A3)\. This proposition identifies the structural benefit of our graph\-based Bellman credit assignment\. At the population level, graph\-based TD credit replaces the trajectory\-specific sampled continuation with the policy\-averaged value of the successor state, thereby producing a Bellman\-aligned credit signal for the current decision\. Thus, the superiority of our GRAFT arises from merging trajectories at shared states and aggregating information from their different continuations via Bellman backups into a lower\-error, state\-specific credit signal\.

Figure 2:Intuitive comparison of advantage estimation methods: trajectory\-level advantage in GRPO, state\-grouping\-based advantage in GiGPO, and our proposed graph\-bootstrapped advantage\.To more intuitively illustrate our method’s advantages, in Fig\.[2](https://arxiv.org/html/2609.28963#S3.F2), we compare our graph\-based advantage estimation with the trajectory\-level advantage in GRPO and the state\-grouping\-based approach in GiGPO\. By bootstrapping \(Bellman backups\) over the graph, our method estimates state values more accurately, thus effectively identifying valuable steps within failed trajectories \(*e\.g\.*,S→DS\\rightarrow DinT2T\_\{2\}\) and erroneous steps within successful ones \(*e\.g\.*,S→LS\\rightarrow LinT1T\_\{1\}\)\. In contrast, advantage estimation in GRPO and GiGPO is heavily influenced by terminal outcomes \(*i\.e\.*, bothT1T\_\{1\}’sS→LS\\rightarrow LandT2T\_\{2\}’sS→DS\\rightarrow Dare affected by the outcome of the belonging trajectory, resulting wrong advantages\)\. Thus, they fail to properly credit beneficial actions in failed rollouts or penalize detrimental actions in successful ones\. In Appendix[D\.5](https://arxiv.org/html/2609.28963#A4.SS5), we also provide case studies to demonstrate the advantages of our method\.

However, since this single\-step TD residualAtA\_\{t\}relies solely on the state\-value difference between two consecutive nodes, any bias in the state\-value estimation directly propagates to the advantage estimation\. To obtain a more robust advantage estimation, we further take the advantage of Generalized Advantage Estimation \(GAE\), which is the de facto in RL that can reduce the impact of state\-value estimation bias by computing a weighted sum of the subsequent multi\-step advantage estimates\. Specifically, we propose Graph GAE, which extends GAE to the trajectory graph\. For each executed transition\(st,at,st\+1\)\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\), we define the Graph GAE advantage as:

AtGAE=γ​V​\(ϕ⁡\(st\+1\)\)−V⁡\(ϕ⁡\(st\)\)⏟At\+∑k=1T−t\(γ​λ\)k⋅A¯t\+kA\_\{t\}^\{\\text\{GAE\}\}=\\underbrace\{\\gamma V\(\\phi\(s\_\{t\+1\}\)\)\-V\(\\phi\(s\_\{t\}\)\)\}\_\{A\_\{t\}\}\+\\sum\_\{k=1\}^\{T\-t\}\(\\gamma\\lambda\)^\{k\}\\cdot\\bar\{A\}\_\{t\+k\}\(9\)whereA¯t\+k\\bar\{A\}\_\{t\+k\}is the meankk\-hop TD residual, defined as the average single\-step TD residual over all raw edge instances\(u′,a′,v′\)\(u^\{\\prime\},a^\{\\prime\},v^\{\\prime\}\)reachable fromata\_\{t\}in exactlykkhops on the graph𝒢\\mathcal\{G\}:

A¯t\+k=1\|ℰk​\(at\)\|​∑\(u′,a′,v′\)∈ℰk​\(at\)\[γ​V​\(v′\)−V⁡\(u′\)\]\\bar\{A\}\_\{t\+k\}=\\frac\{1\}\{\|\\mathcal\{E\}\_\{k\}\(a\_\{t\}\)\|\}\\sum\_\{\(u^\{\\prime\},a^\{\\prime\},v^\{\\prime\}\)\\in\\mathcal\{E\}\_\{k\}\(a\_\{t\}\)\}\\bigl\[\\gamma V\(v^\{\\prime\}\)\-V\(u^\{\\prime\}\)\\bigr\]\(10\)whereℰk​\(at\)\\mathcal\{E\}\_\{k\}\(a\_\{t\}\)denotes the set of all directed edges reachable fromata\_\{t\}in exactlykkhops\. The parameterλ∈\[0,1\]\\lambda\\in\[0,1\]controls the bias\-variance trade\-off: whenλ=0\\lambda=0,AtGAEA\_\{t\}^\{\\text\{GAE\}\}reduces to the one\-step estimateAtA\_\{t\}with low variance but high bootstrap bias\. Asλ\\lambdaincreases, the effective horizon of the estimator expands, thereby reducing the reliance on intermediate state\-value bootstrapping, this mitigates bootstrap bias at the cost of higher variance\. Intuitively, if the edges reachable fromata\_\{t\}have overall high advantages, this means that starting fromata\_\{t\}will be easier to reach good states, thereby contributing to increase the advantage estimate forata\_\{t\}; Conversely, if the reachable edges yield predominantly low advantages, the advantage ofata\_\{t\}is correspondingly reduced\. The characteristic of Graph GAE is that it smoothly interpolates between two extremes—the single\-step advantage and the Monte Carlo advantage∑k=0T−tγk​r​\(st\+k\)−V⁡\(st\)\\sum\_\{k=0\}^\{T\-t\}\\gamma^\{k\}r\(s\_\{t\+k\}\)\-V\(s\_\{t\}\)—viaλ\\lambda, achieving a better bias\-variance trade\-off\.

Advantage normalization\.AlthoughAtG​A​EA\_\{t\}^\{GAE\}itself can serve as a robust step\-level advantage estimate, to further eliminate scale sensitivity, we additionally apply advantage normalization within each node’s on\-state group \(please see the experiments in Tab\.[3](https://arxiv.org/html/2609.28963#S4.T3)\)\. For each nodeuu, all outgoing edges\(u,a,v\)\(u,a,v\)form a natural step group corresponding to the set of actions sampled from the same states=ϕ−1​\(u\)s=\\phi^\{\-1\}\(u\)\. Within this group, we apply advantage normalization:

A^step​\(st,at\)=AtG​A​E−μ𝒢⁡\(st\)σ𝒢⁡\(st\)\+ϵ\\hat\{A\}\_\{\\text\{step\}\}\(s\_\{t\},a\_\{t\}\)=\\frac\{A^\{GAE\}\_\{t\}\-\\mu\_\{\\mathcal\{G\}\(s\_\{t\}\)\}\}\{\\sigma\_\{\\mathcal\{G\}\(s\_\{t\}\)\}\+\\epsilon\}\(11\)whereμ𝒢⁡\(st\)\\mu\_\{\\mathcal\{G\}\(s\_\{t\}\)\}andσ𝒢⁡\(st\)\\sigma\_\{\\mathcal\{G\}\(s\_\{t\}\)\}are the mean and standard deviation of step advantages within the step group𝒢⁡\(st\)=\{AtG​A​E:\(st,⋅,⋅\)∈ℰ\}\\mathcal\{G\}\(s\_\{t\}\)=\\\{A\_\{t\}^\{GAE\}:\(s\_\{t\},\\cdot,\\cdot\)\\in\\mathcal\{E\}\\\}\. For groups containing only one edge, to avoid yielding a normalized advantage of zero, we perform normalization by setting the mean to 0 and using the absolute value as the standard deviation\. The whole GRAFT algorithm is in Alg\.[1](https://arxiv.org/html/2609.28963#alg1)in Appendix[B](https://arxiv.org/html/2609.28963#A2)\.

## 4Experiments

### 4\.1Experimental Setup

Table 1:Performance on ALFWorld and WebShop\. Results are averaged over 3 random seeds\. For ALFWorld, we report the average success rate \(%\) for each subtask as well as the overall result\. For WebShop, we report both the average score and the average success rate \(%\)\. Best results arebolded\.TypeMethodALFWorldWebShopPickLookCleanHeatCoolPick2AllScoreSucc\.Qwen2\.5\-1\.5B\-InstructPromptingQwen2\.55\.95\.53\.39\.74\.20\.04\.123\.15\.2PromptingReAct17\.420\.515\.76\.27\.72\.012\.840\.111\.3PromptingReflexion35\.322\.221\.713\.619\.43\.721\.855\.821\.9RL TrainingPPO64\.8±\\pm3\.540\.5±\\pm6\.957\.1±\\pm4\.960\.6±\\pm6\.646\.4±\\pm4\.047\.4±\\pm1\.954\.4±\\pm3\.173\.8±\\pm3\.051\.5±\\pm2\.9RL TrainingRLOO88\.3±\\pm3\.052\.8±\\pm8\.671\.0±\\pm5\.962\.8±\\pm8\.766\.4±\\pm5\.556\.9±\\pm4\.769\.7±\\pm2\.573\.9±\\pm5\.652\.1±\\pm6\.7RL TrainingGRPO85\.3±\\pm1\.553\.7±\\pm8\.084\.5±\\pm6\.878\.2±\\pm7\.959\.7±\\pm5\.053\.5±\\pm5\.672\.8±\\pm3\.675\.8±\\pm3\.556\.8±\\pm3\.8RL TrainingGiGPO94\.4±\\pm5\.967\.5±\\pm4\.694\.8±\\pm3\.894\.4±\\pm7\.879\.8±\\pm4\.776\.4±\\pm5\.486\.7±\\pm1\.783\.1±\\pm1\.665\.0±\\pm3\.2RL TrainingSALT96\.2±\\pm1\.765\.2±\\pm10\.893\.1±\\pm4\.781\.8±\\pm8\.385\.0±\\pm6\.977\.0±\\pm4\.785\.2±\\pm2\.586\.9±\\pm0\.674\.7±\\pm2\.4RL TrainingGraphGPO95\.2±\\pm1\.685\.7±\\pm5\.8100\.0±\\pm0\.096\.3±\\pm2\.685\.3±\\pm2\.693\.7±\\pm2\.292\.7±\\pm1\.389\.3±\\pm1\.578\.7±\\pm3\.9RL TrainingGRAFT \(Ours\)99\.2±\\pm1\.298\.3±\\pm2\.4100\.0±\\pm0\.0100\.0±\\pm0\.093\.3±\\pm3\.797\.6±\\pm3\.397\.4±\\pm0\.490\.8±\\pm0\.482\.3±\\pm1\.0Qwen2\.5\-7B\-InstructPromptingQwen2\.533\.421\.619\.36\.92\.83\.214\.826\.47\.8PromptingReAct48\.535\.434\.313\.218\.217\.631\.246\.219\.5PromptingReflexion62\.041\.644\.930\.936\.323\.842\.758\.128\.8RL TrainingPPO92\.3±\\pm4\.064\.0±\\pm8\.492\.5±\\pm2\.489\.5±\\pm7\.080\.3±\\pm2\.068\.8±\\pm8\.380\.4±\\pm2\.781\.4±\\pm3\.168\.7±\\pm5\.1RL TrainingRLOO87\.6±\\pm4\.378\.2±\\pm8\.387\.3±\\pm5\.881\.3±\\pm7\.671\.9±\\pm5\.248\.9±\\pm8\.475\.5±\\pm4\.680\.3±\\pm3\.265\.7±\\pm4\.0RL TrainingGRPO90\.8±\\pm5\.166\.1±\\pm6\.789\.3±\\pm5\.474\.7±\\pm6\.972\.5±\\pm5\.464\.7±\\pm7\.377\.6±\\pm5\.279\.3±\\pm2\.866\.1±\\pm3\.7RL TrainingGiGPO97\.7±\\pm1\.682\.7±\\pm7\.998\.8±\\pm1\.683\.7±\\pm7\.289\.3±\\pm8\.279\.2±\\pm6\.690\.8±\\pm1\.384\.4±\\pm2\.972\.8±\\pm3\.2RL TrainingSALT93\.4±\\pm2\.172\.6±\\pm7\.591\.5±\\pm3\.290\.3±\\pm3\.578\.1±\\pm2\.776\.4±\\pm4\.487\.3±\\pm4\.483\.1±\\pm3\.875\.2±\\pm5\.5RL TrainingGraphGPO100\.0±\\pm0\.092\.9±\\pm5\.8100\.0±\\pm0\.094\.4±\\pm0\.091\.4±\\pm1\.592\.1±\\pm2\.295\.3±\\pm1\.186\.9±\\pm0\.780\.3±\\pm1\.3RL TrainingGRAFT \(Ours\)99\.0±\\pm1\.5100\.0±\\pm0\.098\.4±\\pm2\.3100\.0±\\pm0\.097\.2±\\pm2\.996\.8±\\pm2\.698\.4±\\pm0\.691\.5±\\pm1\.382\.8±\\pm0\.6

Benchmarks\.Following the agentic RL baseline GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\), we evaluate our method on a suite of challenging multi\-turn agentic benchmarks, including ALFWorld\([Shridhar et al\., 2021](https://arxiv.org/html/2609.28963#bib.bib13)\), WebShop\([Yao et al\., 2022a](https://arxiv.org/html/2609.28963#bib.bib14)\), and SearchQA\([Jin et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib15)\)\. The introduction of these benchmarks is deferred to Appendix[E](https://arxiv.org/html/2609.28963#A5)\. In SearchQA, the training set is drawn from NQ and HotpotQA, making these two datasets for in\-domain evaluation, while the remaining datasets are used to assess out\-of\-domain generalization\.

Baselines\.To ensure a standardized and rigorous comparison, we adopt the baseline results directly from the original GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\)and GraphGPO\([Cheng et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib31)\)papers\. For ALFWorld and WebShop, the baselines include: \(1\) Prompting\-based agents: ReAct\([Yao et al\., 2022b](https://arxiv.org/html/2609.28963#bib.bib23)\)and Reflexion\([Shinn et al\., 2023](https://arxiv.org/html/2609.28963#bib.bib24)\); and \(2\) RL training methods: PPO\([Schulman et al\., 2017](https://arxiv.org/html/2609.28963#bib.bib1)\), a widely used critic\-based RL algorithm, group\-based RL methods including RLOO\([Ahmadian et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib25)\), GRPO\([Shao et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib2)\), and GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\), as well as graph\-based policy optimization methods, SALT\([Li et al\., 2025a](https://arxiv.org/html/2609.28963#bib.bib50)\), GraphGPO\([Cheng et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib31)\)\(In appendix[A\.2](https://arxiv.org/html/2609.28963#A1.SS2),[A\.3](https://arxiv.org/html/2609.28963#A1.SS3), we provide detailed discussions about the differences between our method and these two methods\)\. For searchQA tasks, we also follow the experimental protocol in GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\)and compare GRAFT against a specific suite of baselines including R1\-Instruct, Search\-R1\([Jin et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib15)\), ZeroSearch\([Sun et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib28)\), StepSearch\([Wang et al\., 2025b](https://arxiv.org/html/2609.28963#bib.bib29)\)and the agentic RL methods: GiGPO, GraphGPO\.

Implementation Details\.To ensure a direct and fair comparison with the prior methods, we utilize Qwen2\.5\-Instruct series \(1\.5B, 3B, 7B\) as our base models \(the compared methods report results based on Qwen2\.5\-Instruct series\)\. For all benchmarks, we follow GiGPO’s training and evaluation configurations as our basic configurations, including rollout batch size, group size, mini\-batch size, learning rate, and sampling temperature, etc\. Additionally, the specific hyperparameters of our method are: the value discount factorγ=0\.99\\gamma=0\.99, the advantage weighting factorλ=0\.95\\lambda=0\.95for ALFWorld,0\.80\.8for WebShop, and0\.60\.6for SearchQA\. Further implementation details are provided in Appendix[E](https://arxiv.org/html/2609.28963#A5)\.

### 4\.2Main Results

As shown in Tab\.[1](https://arxiv.org/html/2609.28963#S4.T1), GRAFT achieves significant gains over the trajectory\-level baseline GRPO and demonstrates superior performance compared to the state\-of\-the\-art GiGPO and GraphGPO across both ALFWorld and WebShop\. On ALFWorld, GRAFT achieves improvements on nearly all subtasks, resulting in average success rate gains of 24\.6% and 20\.8% over GRPO for the 1\.5B and 7B models, respectively\. On WebShop, GRAFT not only attains higher task scores but also improves the average success rate over GRPO by 25\.5% and 16\.7% for the 1\.5B and 7B models, respectively\. These results highlight that our method effectively overcomes the limitations of coarse\-grained trajectory\-level advantages\. In addition, GRAFT also surpasses both step\-group\-based GiGPO and graph\-based GraphGPO by 10\.7%/17\.3% and 4\.7%/3\.6% on ALFWorld and WebShop, respectively, both of which are step\-level credit assignment algorithms\. As the advantage estimation in our method closely revolves around the standard definition, compared to heuristic advantage estimation approaches in GiGPO, SALT, and GraphGPO, our method can provide more credible step\-level advantage estimates\.

Tab\.[2](https://arxiv.org/html/2609.28963#S4.T2)presents the results on searchQA tasks\. We observe that GRAFT achieves strong and consistent gains across both single\-hop and multi\-hop reasoning datasets\. Notably, GRAFT reaches an average success rate of 48\.6% at 7B, outperforming prior baselines such as Search\-R1 and StepSearch, and also outperforms the strong step\-level credit assignment methods, GiGPO and GraphGPO\. In Appendix[D\.4](https://arxiv.org/html/2609.28963#A4.SS4), to demonstrate the generalization of our method, we further provide results on the Qwen3 model series\.

Table 2:Performance on searchQA tasks\.†\\daggerand⋆\\starindicate in\-domain and out\-of\-domain datasets, respectively\.Boldindicates the best performance in each category\.TypeMethodSingle\-Hop QAMulti\-Hop QAAvg\.NQ†\\daggerTriviaQA⋆\\starPopQA⋆\\starHotpotQA†\\dagger2Wiki⋆\\starMuSiQue⋆\\starBamboogle⋆\\starQwen2\.5\-3B\-InstructRL TrainingR1\-Instruct27\.053\.719\.923\.729\.27\.229\.327\.1RL TrainingSearch\-R134\.154\.537\.832\.431\.910\.326\.432\.5RL TrainingZeroSearch41\.457\.444\.827\.430\.09\.811\.131\.7RL TrainingStepSearch–––34\.532\.017\.4–34\.4RL TrainingGiGPO42\.059\.542\.436\.937\.012\.664\.142\.1RL TrainingGraphGPO44\.559\.746\.236\.237\.212\.163\.744\.0RL TrainingGRAFT \(Ours\)45\.361\.846\.437\.237\.312\.464\.945\.2Qwen2\.5\-7B\-InstructRL TrainingR1\-Instruct21\.044\.917\.120\.827\.56\.019\.222\.4RL TrainingSearch\-R139\.361\.039\.737\.040\.114\.636\.838\.5RL TrainingZeroSearch43\.661\.851\.534\.635\.218\.427\.839\.1RL TrainingStepSearch–––38\.636\.622\.6–40\.0RL TrainingGiGPO46\.464\.746\.141\.643\.618\.968\.947\.2RL TrainingGraphGPO46\.865\.447\.741\.142\.717\.069\.048\.0RL TrainingGRAFT \(Ours\)46\.965\.647\.841\.943\.417\.770\.248\.6

### 4\.3Ablation Studies & Further Analysis

Tab\.[3](https://arxiv.org/html/2609.28963#S4.T3)isolates the effects of the key components of our GRAFT\. We start with a baseline GRAFT†that uses the step\-level advantage defined in Eq\.\([8](https://arxiv.org/html/2609.28963#S3.E8)\)\. Removing advantage normalization suffers a substantial performance drop across both benchmarks \(*e\.g\.*, ALFWorld’s “All” declines from 96\.10 to 71\.33, and WebShop success rate falls to 72\.93\), demonstrating that normalization is critical for stabilizing gradient updates and preventing scale\-induced optimization instability\. When we replace the original GRPO objective with the GRPO\-C objective \(Eq\.\([4](https://arxiv.org/html/2609.28963#S2.E4)\)\), performance surpasses the baseline across nearly all metrics\. This confirms that aligning the optimization granularity with the advantage estimator \(treating the entire step as a single action to match the step\-level advantage\) is superior to GRPO’s mismatched token\-level assignment\. Integrating Graph GAE further delivers consistent gains, analogous to the bias\-variance trade\-off in standard GAE, our Graph GAE effectively fuses multiple k\-step estimators to produce a more faithful and robust advantage estimate than the single\-step estimator, leading to improved policy optimization\. The complete GRAFT framework achieves the highest performance, confirming that these components are not independent but can synergistically enhance policy learning in long\-horizon agentic tasks\.

Table 3:Ablation study results\. “w/o adv normalization” denotes directly using the step\-level advantage defined in Eq\.\([8](https://arxiv.org/html/2609.28963#S3.E8)\) without further advantage normalization\. GRAFT†is a variant of GRAFT without GRPO\-C objective \(Eq\.\([4](https://arxiv.org/html/2609.28963#S2.E4)\)\) and Graph GAE, serving as the baseline for ablation studies\. The results are based on Qwen2\.5\-1\.5B\-Instruct\.MethodALFWorldWebshopPickLookCleanHeatCoolPick2AllScoreSucc\.GRAFT†99\.23±\\pm1\.08100\.0±\\pm0\.0096\.73±\\pm2\.3197\.23±\\pm3\.1592\.57±\\pm5\.3589\.60±\\pm2\.4696\.10±\\pm1\.1389\.53±\\pm0\.7680\.67±\\pm1\.68w/o adv normalization75\.37±\\pm1\.5175\.47±\\pm3\.5372\.50±\\pm4\.7663\.10±\\pm3\.5372\.20±\\pm5\.6760\.90±\\pm4\.5471\.33±\\pm2\.8785\.67±\\pm0\.7472\.93±\\pm1\.46w/ GRPO\-C objective \([4](https://arxiv.org/html/2609.28963#S2.E4)\)100\.0±\\pm0\.0098\.03±\\pm2\.7896\.00±\\pm3\.39100\.0±\\pm0\.0096\.20±\\pm2\.5390\.73±\\pm3\.7896\.87±\\pm1\.0890\.63±\\pm1\.5181\.30±\\pm1\.31w/ Graph GAE \([9](https://arxiv.org/html/2609.28963#S3.E9)\)97\.50±\\pm2\.18100\.0±\\pm0\.00100\.0±\\pm0\.00100\.0±\\pm0\.0097\.10±\\pm2\.1191\.53±\\pm4\.1397\.17±\\pm0\.7590\.23±\\pm0\.7081\.73±\\pm0\.75GRAFT99\.17±\\pm1\.1798\.33±\\pm2\.35100\.0±\\pm0\.00100\.0±\\pm0\.0093\.33±\\pm3\.7197\.63±\\pm3\.3497\.43±\\pm0\.3890\.83±\\pm0\.3782\.27±\\pm0\.99

![Refer to caption](https://arxiv.org/html/2609.28963v1/inference_step.png)Figure 3:The average number of execution turns required to finish tasks\.Task Efficiency Analysis\. In Fig\.[3](https://arxiv.org/html/2609.28963#S4.F3), we further illustrate the average number of interaction turns required by the trained models to complete tasks on WebShop and ALFWorld\. Across both benchmarks, GRAFT\-trained models consistently require fewer turns than those trained with GRPO or GiGPO\. This indicates that our method can yield more faithful step\-level advantage estimates, which enable the agent to avoid redundant actions and make more efficient decisions\. Fewer interaction turns inherently translate to lower model inference costs and reduced environment API calls\. Together with Tab\.[1](https://arxiv.org/html/2609.28963#S4.T1), these results demonstrate that our GRAFT achieves substantial advantages over existing methods in both task accuracy and cost efficiency\.

In appendix[D](https://arxiv.org/html/2609.28963#A4), we further provide additional experimental analysis, including training dynamics, hyperparameter experiments, method mechanism analysis, additional results, and case studies\.

![Refer to caption](https://arxiv.org/html/2609.28963v1/computation_cost.png)Figure 4:Breakdown of time consumption per training step\.Computional Cost\.Our method incurs no additional GPU memory overhead, as we have not introduced any extra models or modules\. Due to inconvenience in comparing FLOPs between advantage estimation and model computation, we analyze the time consumption per training step\. We use Qwen2\.5\-1\.5B\-Instruct as the base model and train it on the ALFWorld benchmark\. The per\-step runtime breakdown is shown in Fig\.[4](https://arxiv.org/html/2609.28963#S4.F4)\. As illustrated, a typical training step involves a rollout stage, advantage estimation, probability computation for sampled responses under both the reference and old policies, and policy update\. Our method operates specifically within the advantage estimation stage\. The additional costs introduced by GRAFT stem from graph construction and graph\-based advantage estimation\. These costs are negligible compared to rollout and policy update, occupying merely 0\.43% of the total RL training time and introducing virtually no extra computational burden\.

## 5Related Work

Reinforcement Learning for LLMs\. RL for LLMs has evolved from preference alignment to reasoning enhancement\. Early PPO\-based RLHF methods\([Schulman et al\., 2017](https://arxiv.org/html/2609.28963#bib.bib1);[Bai et al\., 2022](https://arxiv.org/html/2609.28963#bib.bib38);[Ouyang et al\., 2022](https://arxiv.org/html/2609.28963#bib.bib39)\), while effective, were computationally burdensome due to the need for separate reward and value models, prompting a shift toward alternatives like DPO\([Rafailov et al\., 2023](https://arxiv.org/html/2609.28963#bib.bib26)\)and its variants \(e\.g\., SimPO\([Meng et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib9)\), KTO\([Ethayarajh et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib10)\), ORPO\([Hong et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib11)\)\)\. However, the offline characteristics of the DPO series result in inherently performance\-bounded compared to online methods\. The recent success of DeepSeek\-R1\([DeepSeek\-AI, 2025](https://arxiv.org/html/2609.28963#bib.bib33)\)established RL with Verifiable Rewards \(RLVR\) as a new paradigm, demonstrating that strong reasoning can emerge via online outcome\-based algorithms \(*e\.g\.*, GRPO\([Shao et al\., 2024](https://arxiv.org/html/2609.28963#bib.bib2)\), DAPO\([Seed, 2025](https://arxiv.org/html/2609.28963#bib.bib4)\), GSPO\([Zheng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib3)\)\) without SFT cold\-start or process supervision\. Although such group\-based methods enable scalable, memory\-efficient training by eliminating critic models, they predominantly rely on sparse outcome rewards and suffer from the credit assignment problem at the step level\. While Process Reward Models\([Cui et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib7);[Cao et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib40);[Xi et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib8)\)offer finer\-grained guidance, they incur prohibitive annotation costs and are prone to reward hacking\. Consequently, recent efforts\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12);[Tan et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib30);[Cheng et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib31)\)have pivoted on deriving dense, multi\-granularity advantages directly from sampling statistics or state transitions, aiming to achieve precise credit assignment without the overhead of learned critics or expensive process annotations\.

Agentic Reinforcement Learning\. RL has become a cornerstone for empowering LLM agents in dynamic, open\-ended environments\([Zhang et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib41);[Wang et al\., 2025b](https://arxiv.org/html/2609.28963#bib.bib29);[Team, 2025](https://arxiv.org/html/2609.28963#bib.bib36)\), evolving from early value\-based methods\([Peng et al\., 2019](https://arxiv.org/html/2609.28963#bib.bib48);[Zha et al\., 2021](https://arxiv.org/html/2609.28963#bib.bib42)\)to modern policy gradient approaches for complex tasks like web navigation\([Shi et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib44)\), tool use\([Jiang et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib45)\), and software engineering\([Da et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib43)\)\. Recent works such as Search\-R1\([Jin et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib15)\)and WebSailor\([Li et al\., 2025b](https://arxiv.org/html/2609.28963#bib.bib46)\)demonstrate that agentic RL can effectively instill multi\-step information\-seeking and long\-horizon planning capabilities without human\-curated supervision\. Despite these advances, training efficacy remains limited by sparse outcome\-based rewards, which hinder the agent’s ability to correct intricate intermediate errors\. To address this credit assignment problem, Process Reward Models offer step\-level supervision but incur prohibitive annotation costs\. Alternatively, intrinsic reward mechanisms such as EMPG\([Wang et al\., 2025a](https://arxiv.org/html/2609.28963#bib.bib47)\)utilize dynamic entropy to encourage exploration\. More recently, GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\)introduces state\-based anchoring to aggregate all states into step\-wise groups for normalized advantage estimation in the aggregated groups\. HCAPO\([Tan et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib30)\)proposes to leverage the LLM itself as a post\-hoc critic to refine step\-level credit through hindsight reasoning\. A recent work, GraphGPO\([Cheng et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib31)\), employs the graph structure to model the state\-action transition relationship and achieves step\-level credit assignment via heuristic reward shaping\. Although both use the graph structure, our method differs fundamentally from GraphGPO in motivation, implementation, and effectiveness; we provide a detailed comparative discussion in Appendix[A\.2](https://arxiv.org/html/2609.28963#A1.SS2)\.

## 6Conclusion

In this work, we revisit the basic advantage estimation problem and group\-based RL, and identify a critical gap: GRPO\-style advantage estimation is reliable at the response level, but systematically biased when extending the group\-based estimation strategy to the step\-level\. To address this, we propose GRAFT, a graph\-based credit\-assignment framework that grafts all rollout trajectories into a unified trajectory graph, recovers node state\-values via Bellman iteration on the graph, and assigns credit to each edge by the node value difference\. The resulting step\-level advantage is not a heuristic surrogate but faithfully adheres to the basic advantage definition in RL, and asymptotically converges to the true target as the graph reaches sufficiently saturated\. Across diverse multi\-turn agentic benchmarks, GRAFT consistently outperforms GRPO and demonstrates superior performance compared to recent SOTA agentic RL algorithms, while remaining critic\-free and PRM\-free\.

## Acknowledgments

This work was completed during the internship at Tencent AI Platform Department\. We gratefully acknowledge Tencent Inc\. for providing computing resources that greatly supported the completion of this work\. This work was also supported in part by the National Natural Science Fund of China \(No\.62371295\), the Shanghai Jiao Tong University AI for Engineering Initiative \(No\.WH410263001/001\), and the Science and Technology Commission of Shanghai Municipality \(No\.22DZ2229005\)\.

## References

- Ahmadianet al\.\(2024\)A\. Ahmadian, C\. Cremer, M\. Gallé, M\. Fadaee, J\. Kreutzer, O\. Pietquin, A\. Üstün, and S\. HookerBack to basics: revisiting reinforce style optimization for learning from human feedback in llms\.arXiv preprint arXiv:2402\.14740\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1),[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1)\.
- Baiet al\.\(2022\)Y\. Bai, A\. Jones, K\. Ndousse, A\. Askell, A\. Chen, N\. DasSarma, D\. Drain, S\. Fort, D\. Ganguli, T\. Henighan, and et alTraining a helpful and harmless assistant with reinforcement learning from human feedback\.arXiv preprint arXiv:2204\.05862\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Caoet al\.\(2025\)L\. Cao, R\. Chen, Y\. Zou, C\. Peng, H\. Xua, Y\. Wang, W\. Ning, Q\. Chen, M\. Peng, Z\. Chen, and et alMore bang for the buck: process reward modeling with entropy\-driven uncertainty\.arXiv preprint arXiv:2503\.22233\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Chenget al\.\(2026\)X\. Cheng, S\. He, L\. Feng, H\. Xu, M\. Yan, L\. Feng, and B\. AnBeyond trajectory\-level attribution: graph\-based credit assignment for agentic reinforcement learning\.In ICML\.Cited by:[§A\.2](https://arxiv.org/html/2609.28963#A1.SS2.p1.1),[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1),[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Cuiet al\.\(2025\)G\. Cui, L\. Yuan, Z\. Wang, H\. Wang, Y\. Zhang, J\. Chen, W\. Li, B\. He, Y\. Fan, T\. Yu, Q\. Xu, W\. Chen, J\. Yuan, H\. Chen, K\. Zhang, X\. Lv, S\. Wang, Y\. Yao, X\. Han, H\. Peng, Y\. Cheng, Z\. Liu, M\. Sun, B\. Zhou, and N\. DingProcess reinforcement through implicit rewards\.arXiv preprint arXiv:2502\.01456\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p2.1),[§2](https://arxiv.org/html/2609.28963#S2.p5.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Daet al\.\(2025\)J\. Da, C\. Wang, X\. Deng, Y\. Ma, N\. Barhate, and S\. HendryxAgent\-rlvr: training software engineering agents via guidance and environment rewards\.arXiv preprint arXiv:2506\.11425\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- DeepSeek\-AI \(2025\)DeepSeek\-AIDeepseek\-r1: incentivizing reasoning capability in llms via reinforcement learning\.arXiv preprint arXiv:2501\.12948\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Ethayarajhet al\.\(2024\)K\. Ethayarajh, W\. Xu, N\. Muennighoff, D\. Jurafsky, and D\. KielaKTO: model alignment as prospect theoretic optimization\.In ICML\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Fenget al\.\(2025\)L\. Feng, Z\. Xue, T\. Liu, and B\. AnGroup\-in\-group policy optimization for llm agent training\.In NeurIPS\.Cited by:[§A\.1](https://arxiv.org/html/2609.28963#A1.SS1.p1.1),[Appendix C](https://arxiv.org/html/2609.28963#A3.SS0.SSS0.Px2.p1.1),[§E\.2](https://arxiv.org/html/2609.28963#A5.SS2.p1.1),[§3](https://arxiv.org/html/2609.28963#S3.p2.1),[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1),[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Gaoet al\.\(2025\)C\. Gao, C\. Zheng, X\. Chen, K\. Dang, S\. Liu, B\. Yu, A\. Yang, S\. Bai, J\. Zhou, and J\. LinSoft adaptive policy optimization\.arXiv preprint arXiv: 2511\.20347\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1)\.
- Hoet al\.\(2020\)X\. Ho, A\. D\. Nguyen, S\. Sugawara, and A\. AizawaConstructing a multi\-hop qa dataset for comprehensive evaluation of reasoning steps\.In Proceedings of the 28th International Conference on Computational Linguistics\.Cited by:[§E\.1](https://arxiv.org/html/2609.28963#A5.SS1.p1.1)\.
- Honget al\.\(2024\)J\. Hong, N\. Lee, and J\. ThornenORPO: monolithic preference optimization without reference model\.arXiv preprint arXiv: 2403\.07691\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Jianget al\.\(2025\)D\. Jiang, Y\. Lu, Z\. Li, Z\. Lyu, P\. Nie, H\. Wang, A\. Su, H\. Chen, K\. Zou, C\. Du, T\. Pang, and W\. ChenVerlTool: towards holistic agentic reinforcement learning with tool use\.arXiv preprint arXiv:2509\.01055\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Jinet al\.\(2025\)B\. Jin, H\. Zeng, Z\. Yue, J\. Yoon, S\. Arik, D\. Wang, H\. Zamani, and J\. HanSearch\-r1: training llms to reason and leverage search engines with reinforcement learning\.arXiv preprint arXiv:2503\.09516\.Cited by:[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1),[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Joshiet al\.\(2017\)M\. Joshi, E\. Choi, D\. SWeld, and L\. ZettlemoyerTriviaqa: a large scale distantly supervised challenge dataset for reading comprehension\.In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics\.Cited by:[§E\.1](https://arxiv.org/html/2609.28963#A5.SS1.p1.1)\.
- Kwiatkowskiet al\.\(2019\)T\. Kwiatkowski, J\. Palomaki, O\. Redfield, M\. Collins, A\. Parikh, C\. Alberti, D\. Epstein, I\. Polosukhin, J\. Devlin, K\. Lee, and et alNatural questions: a benchmark for question answering research\.Transactions of the Association for Computational Linguistics\.Cited by:[§E\.1](https://arxiv.org/html/2609.28963#A5.SS1.p1.1)\.
- Liet al\.\(2025a\)J\. Li, Y\. Wang, D\. Yan, Y\. Tian, Z\. Xu, H\. Song, P\. Xu, and L\. L\. CheongSALT: step\-level advantage assignment for long\-horizon agents via trajectory graph\.arXiv preprint arXiv:2510\.20022\.Cited by:[§A\.3](https://arxiv.org/html/2609.28963#A1.SS3.p1.1),[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1)\.
- Liet al\.\(2025b\)K\. Li, Z\. Zhang, H\. Yin, L\. Zhang, L\. Ou, J\. Wu, W\. Yin, B\. Li, Z\. Tao, X\. Wang, W\. Shen, J\. Zhang, D\. Zhang, X\. Wu, Y\. Jiang, M\. Yan, P\. Xie, F\. Huang, and J\. ZhouWebSailor: navigating super\-human reasoning for web agent\.arXiv preprint arXiv:2507\.02592\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Mallenet al\.\(2023\)A\. Mallen, A\. Asai, V\. Zhong, R\. Das, D\. Khashabi, and H\. HajishirziWhen not to trust language models: investigating effectiveness of parametric and non\-parametric memories\.In Proceedings of the 61st annual meeting of the association for computational linguistics\.Cited by:[§E\.1](https://arxiv.org/html/2609.28963#A5.SS1.p1.1)\.
- Menget al\.\(2024\)Y\. Meng, M\. Xia, and D\. ChenSimPO: simple preference optimization with a reference\-free reward\.In NeurIPS\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- OpenAI \(2024\)OpenAILearning to reason with llms\.https://openai\.com/index/ learning\-to\-reason\-with\-llms/\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1)\.
- Ouyanget al\.\(2022\)L\. Ouyang, J\. Wu, X\. Jiang, D\. Almeida, C\. Wainwright, P\. Mishkin, C\. Zhang, S\. Agarwal, K\. Slama, A\. Ray, and et alTraining language models to follow instructions with human feedback\.In NeurIPS\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Penget al\.\(2019\)X\. B\. Peng, A\. Kumar, G\. Zhang, and S\. LevineAdvantage\-weighted regression: simple and scalable off\-policy reinforcement learning\.arXiv preprint arXiv:1910\.00177\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Presset al\.\(2023\)O\. Press, M\. Zhang, S\. Min, L\. Schmidt, N\. A\. Smith, and M\. LewisMeasuring and narrowing the compositionality gap in language models\.In Findings of the Association for Computational Linguistics: EMNLP 2023\.Cited by:[§E\.1](https://arxiv.org/html/2609.28963#A5.SS1.p1.1)\.
- Rafailovet al\.\(2023\)R\. Rafailov, A\. Sharma, E\. Mitchell, S\. Ermon, C\. D\. Manning, and C\. FinnDirect preference optimization: your language model is secretly a reward model\.In NeurIPS\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Schulmanet al\.\(2017\)J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. KlimovProximal policy optimization algorithms\.arXiv preprint arXiv: 1707\.06347\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1),[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Seed \(2025\)B\. SeedDAPO: an open\-source llm reinforcement learning system at scale\.arXiv preprint arXiv: 2503\.14476\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Shaoet al\.\(2024\)Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, X\. Bi, H\. Zhang, M\. Zhang, Y\.K\. Li, Y\. Wu, and D\. GuoDeepSeekMath: pushing the limits of mathematical reasoning in open language models\.arXiv preprint arXiv:2402\.03300\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1),[§1](https://arxiv.org/html/2609.28963#S1.p2.1),[§2](https://arxiv.org/html/2609.28963#S2.p2.1),[§2](https://arxiv.org/html/2609.28963#S2.p5.1),[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Shiet al\.\(2025\)Y\. Shi, W\. Yu, Z\. Li, Y\. Wang, H\. Zhang, N\. Liu, H\. Mi, and D\. YuMobileGUI\-rl: advancing mobile gui agent through reinforcement learning in online environment\.arXiv preprint arXiv:2507\.05720\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Shinnet al\.\(2023\)N\. Shinn, F\. Cassano, E\. Berman, A\. Gopinath, K\. Narasimhan, and S\. YaoReflexion: language agents with verbal reinforcement learning\.In NeurIPS\.Cited by:[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1)\.
- Shridharet al\.\(2021\)M\. Shridhar, X\. Yuan, M\. Côté, Y\. B\. A\. Trischler, and M\. HausknechtAlfworld: aligning text and embodied environments for interactive learning\.In ICLR\.Cited by:[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p1.1)\.
- Sunet al\.\(2025\)H\. Sun, Z\. Qiao, J\. Guo, X\. Fan, Y\. Hou, Y\. Jiang, P\. Xie, Y\. Zhang, F\. Huang, and J\. ZhouZerosearch: incentivize the search capability of llms without searching\.arXiv preprint arXiv:2505\.04588\.Cited by:[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1)\.
- Tanet al\.\(2026\)H\. Tan, X\. Yang, H\. Chen, J\. Shao, Y\. Wen, Y\. Shen, W\. Luo, X\. Du, L\. Guo, and Y\. LiHindsight credit assignment for long\-horizon llm agents\.arXiv preprint arXiv:2603\.08754\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p1.1),[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Team \(2026a\)K\. TeamKimi k2\.5: visual agentic intelligence\.arXiv preprint arXiv:2602\.02276\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1)\.
- Team \(2026b\)Q\. TeamQwen\-agentworld: language world models for general agents\.arXiv preprint arXiv:2606\.24597\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1)\.
- Team \(2026c\)Q\. TeamQwen3\.5: accelerating productivity with native multimodal agents\.External Links:[Link](https://qwen.ai/blog?id=qwen3.5)Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1)\.
- Team \(2025\)T\. D\. TeamTongyi deepresearch technical report\.arXiv preprint arXiv:2510\.24701\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1),[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Trivediet al\.\(2022\)H\. Trivedi, N\. Balasubramanian, T\. Khot, and A\. SabharwalMusique: multi\-hop questions via single\-hop question composition\.Transactions of the Association for Computational Linguistics\.Cited by:[§E\.1](https://arxiv.org/html/2609.28963#A5.SS1.p1.1)\.
- Wanget al\.\(2025a\)J\. Wang, J\. Li, Y\. Fu, Y\. Li, X\. Wang, Y\. Lin, Y\. Yue, L\. Zhang, Y\. Wang, and K\. WangHarnessing uncertainty: entropy\-modulated policy gradients for long\-horizon llm agents\.arXiv preprint arXiv:2509\.09265\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Wanget al\.\(2026\)T\. Wang, S\. Zheng, and X\. XuRTMC: step\-level credit assignment via rollout trees\.arXiv preprint arXiv:2604\.11037\.Cited by:[§A\.4](https://arxiv.org/html/2609.28963#A1.SS4.p1.1)\.
- Wanget al\.\(2025b\)Z\. Wang, X\. Zheng, K\. An, C\. Ouyang, J\. Cai, Y\. Wang, and Y\. WuStepSearch: igniting llms search ability via step\-wise proximal policy optimization\.arXiv preprint arXiv:2505\.15107\.Cited by:[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1),[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Wikipedia \(2006\)WikipediaGauss–seidel method\.https://en\.wikipedia\.org/wiki/Gauss\-Seidel\_method\.Cited by:[§3\.2](https://arxiv.org/html/2609.28963#S3.SS2.p4.1)\.
- Williams \(1992\)R\. J\. WilliamsSimple statistical gradient\-following algorithms for connectionist reinforcement learning\.Mach\. Learn\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1)\.
- Xiet al\.\(2025\)Z\. Xi, C\. Liao, G\. Li, Y\. Yang, W\. Chen, Z\. Zhang, B\. Wang, S\. Jin, Y\. Zhou, J\. Guan, W\. Wu, T\. Ji, T\. Gui, Q\. Zhang, and X\. HuangAgentPRM: process reward models for llm agents via step\-wise promise and progress\.arXiv preprint arXiv:2511\.08325\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p2.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.
- Yanget al\.\(2018\)Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. Cohen, R\. Salakhutdinov, and C\. D\. ManningHotpotqa: a dataset for diverse, explainable multi\-hop question answering\.In Proceedings of the 2018 conference on empirical methods in natural language processing\.Cited by:[§E\.1](https://arxiv.org/html/2609.28963#A5.SS1.p1.1)\.
- Yaoet al\.\(2022a\)S\. Yao, H\. Chen, J\. Yang, and K\. NarasimhanWebshop: towards scalable real\-world web interaction with grounded language agents\.In NeurIPS\.Cited by:[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p1.1)\.
- Yaoet al\.\(2022b\)S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. CaoReact: synergizing reasoning and acting in language models\.In ICLR\.Cited by:[§4\.1](https://arxiv.org/html/2609.28963#S4.SS1.p2.1)\.
- Yaoet al\.\(2026\)X\. Yao, R\. Li, C\. Chen, D\. Zhang, Y\. Wu, and Y\. HuHTPO: towards exploration\-exploitation balanced policy optimization via hierarchical token\-level objective control\.arXiv preprint arXiv:2605\.08283\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1)\.
- Zhaet al\.\(2021\)D\. Zha, J\. Xie, W\. Ma, S\. Zhang, X\. Lian, X\. Hu, and J\. LiuDouzero: mastering doudizhu with self\-play deep reinforcement learning\.In ICML\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Zhanget al\.\(2025\)H\. Zhang, X\. Liu, B\. Lv, X\. Sun, B\. Jing, I\. L\. Iong, Z\. Hou, Z\. Qi, H\. Lai, Y\. Xu, and et alAgentrl: scaling agentic reinforcement learning with a multi\-turn, multi\-task framework\.arXiv preprint arXiv:2510\.04206\.Cited by:[§5](https://arxiv.org/html/2609.28963#S5.p2.1)\.
- Zhenget al\.\(2025\)C\. Zheng, S\. Liu, M\. Li, X\. Chen, B\. Yu, C\. Gao, K\. Dang, Y\. Liu, R\. Men, A\. Yang, J\. Zhou, and J\. LinGroup sequence policy optimization\.arXiv preprint arXiv:2507\.18071\.Cited by:[§1](https://arxiv.org/html/2609.28963#S1.p1.1),[§5](https://arxiv.org/html/2609.28963#S5.p1.1)\.

## Appendix

## Appendix AMore Discussions

### A\.1Advantages over GiGPO

As stated in Sec\.[3](https://arxiv.org/html/2609.28963#S3), GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\)has proposed to estimate step\-level advantages by grouping steps that share the same state and normalizing their discounted Monte Carlo returnsRt=∑l≥0γl​rt\+lR\_\{t\}=\\sum\_\{l\\geq 0\}\\gamma^\{l\}r\_\{t\+l\}within each group\. Since our method relies on aggregating cross\-trajectory steps into graph nodes, we discuss the advantages of our method over the plain state\-grouped advantage estimation approach in GiGPO\.

The design in GiGPO has a fundamental limitation: the value signal for statessis derived only from trajectories that pass throughss, making the estimate high\-variance and sample\-inefficient, especially for states visited infrequently\. Our method addresses this by constructing an empirical transition graph𝒢\\mathcal\{G\}over the rollout group and estimatingV⁡\(s\)V\(s\)via Bellman value iteration \(see Sec\.[3](https://arxiv.org/html/2609.28963#S3)\)\. The step advantage for each executed edge\(s→𝑎s′\)\(s\\xrightarrow\{a\}s^\{\\prime\}\)is then defined asA⁡\(s,a,s′\)=γ​V​\(s′\)−V⁡\(s\)A\(s,a,s^\{\\prime\}\)=\\gamma\\,V\(s^\{\\prime\}\)\-V\(s\), which exactly aligns with the standard advantage function in RL\. This formulation offers two key advantages over GiGPO’s vanilla state\-grouping approach:

1\. Broader information aggregation\. BecauseV⁡\(s\)V\(s\)is computed by backward propagation through the graph, it implicitly aggregates reward signals from all trajectories reachable from the successors ofss, rather than only those passing throughssitself\. Concretely, ifssbranches intos1′s^\{\\prime\}\_\{1\}ands2′s^\{\\prime\}\_\{2\}, and these successors are collectively visited byKKdownstream trajectories, thenV⁡\(s\)V\(s\)incorporates rewards from allKKtrajectories, whereas GiGPO’s allRtR\_\{t\}forssare confined to the trajectories that directly visitss\. In Appendix\.[D\.3](https://arxiv.org/html/2609.28963#A4.SS3), we compare the information propagation degree \(the number of distinct trajectories contributing reward information to the value estimation of a node \(or state\)\) between our method and GiGPO\. The results show that our method consistently achieves a higher information propagation degree than GiGPO throughout training\.

2\. Theoretical soundness\. The step advantageγ​V​\(s′\)−V⁡\(s\)\\gamma V\(s^\{\\prime\}\)\-V\(s\)is precisely aligned with the standard definition of the advantage functionA⁡\(s,a\)=Q⁡\(s,a\)−V⁡\(s\)A\(s,a\)=Q\(s,a\)\-V\(s\), since under a deterministic transitionQ⁡\(s,a\)=γ​V​\(s′\)Q\(s,a\)=\\gamma V\(s^\{\\prime\}\)\. This theoretical grounding ensures that the step\-level signal faithfully measures how much better actionaais relative to the expected value of statess, whereas GiGPO’s Monte Carlo returnRtR\_\{t\}introduces high variance from stochastic future trajectories\.

3\. GiGPO can be viewed as a special case of our method in which each trajectory is treated as an independent graph, and Bellman iteration is performed separately on these isolated graphs to estimate node values\. Subsequently, step\-level groups are constructed across trajectories, and values are normalized within each group to obtain step\-level advantages\. Compared to graph\-based value estimation, single\-trajectory value estimation is inherently less accurate due to the stochasticity of individual trajectories, resulting in higher variance\.

Together, these properties make our graph\-based estimator both more sample\-efficient and more theoretically grounded than GiGPO’s state\-grouping baseline\. As for performance, the results in Tab\.[1](https://arxiv.org/html/2609.28963#S4.T1)and[2](https://arxiv.org/html/2609.28963#S4.T2)show that our method can achieve significantly better results than GiGPO, validating the superiority of our method over GiGPO in estimating step\-level advantages\.

### A\.2Discussion with GraphGPO

In GraphGPO\([Cheng et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib31)\), the authors also utilized the graph structure to model state\-action transitions across trajectories, which coincides with the idea in our work\. Therefore, it is necessary to clarify the distinctions between our work and GraphGPO\. Although both methods use the graph structure, our method differs fundamentally from GraphGPO in motivation, implementation, and performance\. We elaborate on these differences below:

1\. In terms of motivation, GraphGPO is driven by empirical observations: it finds that 65% of steps in successful trajectories do not meaningfully advance the task, while 22% of steps in failed trajectories contribute to task progress\. Arguing that trajectory\-level credit attribution is too coarse, GraphGPO aggregates all rollout trajectories into a state transition graph to leverage global connectivity for finer\-grained credit assignment\. In contrast, our motivation stems from the preliminary analysis in Sec\.[2](https://arxiv.org/html/2609.28963#S2), which demonstrates that extending GRPO\-style advantage estimation to the step level introduces systematic bias\. To obtain theoretically grounded estimates while not incurring prohibitive Monte Carlo sampling costs, we should aggregate similar states across trajectories to better leverage global information\. To this end, the graph structure serves as a natural representation for modeling the cross\-trajectory state\-action transition relationship\.

2\. In terms of implementation, GraphGPO adopts a heuristic approach that defines the step\-level rewards based on the shortest\-path distance from each node to any successful nodesr⁡\(s,a,s′\)=rs​u​c​c​wd⁡\(s\)r\(s,a,s^\{\\prime\}\)=r\_\{succ\}w^\{d\(s\)\}, whered⁡\(s\)d\(s\)is the shortest distance fromssto any successful states andw∈\(0,1\)w\\in\(0,1\)is a distance discount factor\. Then, the rewards are normalized within each node group to obtain step\-level advantages\. This heuristic reward assignment approach is based on the assumption that beneficial actions can reduce the distance to the task goal\. In contrast, our method is grounded in fundamental RL theory\. We treat the constructed graph as an empirical Markov Decision Process \(MDP\) and apply Bellman iteration \(V⁡\(u\)=∑a∈𝒜⁡\(u\)π^​\(a∣u\)​∑v∈𝒱P^​\(v∣u,a\)⋅γ⋅V⁡\(v\)V\(u\)=\\sum\_\{a\\in\\mathcal\{A\}\(u\)\}\\hat\{\\pi\}\(a\\mid u\)\\sum\_\{v\\in\\mathcal\{V\}\}\\hat\{P\}\(v\\mid u,a\)\\cdot\\gamma\\cdot V\(v\)\) to estimate the state\-value of each node\. The step\-level advantage between two nodes is then defined asAt=γ⋅V⁡\(u\)−V⁡\(v\)A\_\{t\}=\\gamma\\cdot V\(u\)\-V\(v\)\. Theoretically, the estimated node values conform to the standard definition of state\-value in RL \(see Eq\.\([7](https://arxiv.org/html/2609.28963#S3.E7)\)\), and the derived step\-level advantages coincide exactly with the standard advantage function \(see Sec\.[3\.3](https://arxiv.org/html/2609.28963#S3.SS3)\)\. Rather than relying on hand\-crafted heuristics, our approach is principled and theory\-driven\.

3\. In GraphGPO, after obtaining the step\-level advantages, these values are uniformly allocated to individual tokens within each step and the GRPO optimization objective is applied\. However, as our analysis in Sec\.[2](https://arxiv.org/html/2609.28963#S2)demonstrates, this token\-level allocation introduces systematic bias\. To this end, we employ the calibrated GRPO optimization objective defined in Eq\.\([4](https://arxiv.org/html/2609.28963#S2.E4)\) in our method, which can further outperform the original objective formulation as shown in Tab\.[3](https://arxiv.org/html/2609.28963#S4.T3)\.

4\. As for method performance, Tab\.[1](https://arxiv.org/html/2609.28963#S4.T1)and[2](https://arxiv.org/html/2609.28963#S4.T2)both demonstrate that our method consistently outperforms GraphGPO across multiple multi\-turn agentic benchmarks, even though both methods are based on graph representation\. This indicates that our advantage estimation method, grounded in standard RL definitions, yields more accurate step\-level advantages than GraphGPO’s heuristic approach\. Furthermore, we provide theoretical guarantees showing that as the graph becomes saturated, the estimated step\-level advantages in our method converge to the true advantages\.

### A\.3Discussion with SALT

In SALT\([Li et al\., 2025a](https://arxiv.org/html/2609.28963#bib.bib50)\), the authors also claimed to propose a step\-level advantage assignment method based on the trajectory graph\. However, their approach underutilizes the graph structure, which actually can be reduced to the plain state aggregation method akin to GiGPO\. Specifically, SALT first computes trajectory\-level advantages via GRPO, then identifies identical transitions\(s,a,s′\)\(s,a,s^\{\\prime\}\)across trajectories into a group and averages their inherited advantages \(*i\.e\.*, the trajectory\-level advantages\) within the group\. This mechanism mirrors the state\-based grouping in GiGPO, but differently SALT groups actions \(along with their adjacent states\) and assigns the group\-averaged advantage to each action\. Consequently, SALT inherits GiGPO’s fundamental limitations as discussed in Appendix[A\.1](https://arxiv.org/html/2609.28963#A1.SS1): information propagation also remains limited\. That is, advantage averaging within each group solely utilizes trajectory\-level signals from the corresponding trajectories containing the specific action\. Although this heuristic advantage adjustment method can mitigate trajectory\-level noise \(*e\.g\.*, if a good action receives a misleading trajectory\-level advantage due to subsequent failures, averaging across multiple trajectories may mitigate the credit misalignment issue\), it cannot adjust advantages for actions that appear only once across all trajectories\. In contrast, our method applies Bellman iteration to estimate the state\-value of each node on the graph, deriving step\-level advantages from the value differences between two nodes\. This formulation does not depend on the occurrences number of the action, and even for actions appearing only once, our method can take advantage of bootstrapping on the graph to achieve a good step\-level advantage estimation\.

As for performance, the results in Tab\.[1](https://arxiv.org/html/2609.28963#S4.T1)show that our method can achieve significantly better results than SALT, validating the superiority of our method over SALT in estimating step\-level advantages\.

### A\.4Discussion with RTMC

We further discuss with RTMC\([Wang et al\., 2026](https://arxiv.org/html/2609.28963#bib.bib51)\), the authors proposed Rollout\-Tree Monte Carlo advantage estimation, which aggregates return statistics from group rollouts over a tree structure to compute per\-step Q\-values and advantages, enabling fine\-grained credit assignment\. Specifically, for each steptt, the discounted return is computed asRt=∑l=0T−tγl​rt\+lR\_\{t\}=\\sum\_\{l=0\}^\{T\-t\}\\gamma^\{l\}r\_\{t\+l\}\. Then, for each state\-action pair\(s,a\)\(s,a\), the Q\-value is estimated by averaging returns across rollouts visiting\(s,a\)\(s,a\):Q^\(s,a\)=1N⁡\(s,a\)∑i:\(sti,ati\)=\(s,a\)Rti\\widehat\{Q\}\(s,a\)=\\frac\{1\}\{N\(s,a\)\}\\sum\_\{i:\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)=\(s,a\)\}R\_\{t\}^\{i\}, whereN⁡\(s,a\)N\(s,a\)counts the number of rollouts that visit statessand take actionaa\. The state value forssis estimated asV^\(s\)=1N⁡\(s\)∑i:sti=sRti\\widehat\{V\}\(s\)=\\frac\{1\}\{N\(s\)\}\\sum\_\{i:s\_\{t\}^\{i\}=s\}R\_\{t\}^\{i\}, whereN⁡\(s\)=∑aN⁡\(s,a\)N\(s\)=\\sum\_\{a\}N\(s,a\)\. The per\-step advantage is finally derived as the difference between the action value and the state value:A^​\(s,a\)=Q^​\(s,a\)−V^​\(s\)\\widehat\{A\}\(s,a\)=\\widehat\{Q\}\(s,a\)\-\\widehat\{V\}\(s\)\.

Fundamentally, the advantage estimation in RTMC is equivalent to that in GiGPO\. First, both methods compute discounted returns for each step and then group steps that share the same state into a group and normalize the discounted returns within each group\. While RTMC additionally averages the returns for each\(s,a\)\(s,a\)pair within the state\-action group before state\-group normalization, this does not introduce any essential difference with GiGPO’s step\-level advantage estimation\. Consequently, the advantages of our method over GiGPO discussed in Appendix[A\.1](https://arxiv.org/html/2609.28963#A1.SS1)apply equally to RTMC\.

## Appendix BThe Overall Algorithmic Procedure for GRAFT

We present the overall algorithmic procedure of our GRAFT in Algorithm[1](https://arxiv.org/html/2609.28963#alg1)\. Our method utilizes graph as the basic representation structure to model state\-action transition relationship\. Its key characteristic is that it is grounded in reinforcement learning theory rather than heuristics: we perform Bellman iteration on the graph to estimate the state\-value of each node, and then derive the step\-level advantage from the difference in node values\. Furthermore, we extend GAE on the graph to obtain more robust advantage estimation\. Additionally, for loss computation, we identify the misalignment between the step\-level advantage and the optimization objective in GRPO, thus we further adopt a calibrated optimization objective \(Eq\.\([4](https://arxiv.org/html/2609.28963#S2.E4)\)\) to ensure better alignment\.

Algorithm 1GRAFT:GRAph\-basedFaithful STep\-level Credit Assignment0:Policy

πθ\\pi\_\{\\theta\}, environment

ℰ\\mathcal\{E\}, dataset

𝒟\\mathcal\{D\}, group size

NN, discount factor

γ\\gamma, weighting factor

λ\\lambda
1:foreach training iterationdo

2:Sample tasks

\{qk\}\\\{q\_\{k\}\\\}from

𝒟\\mathcal\{D\}; collect

NNrollouts per task under

πθ\\pi\_\{\\theta\}→\\rightarrowbatch

𝒯\\mathcal\{T\}
3:// Graph construction

4:foreach task

qkq\_\{k\}do

5:Build trajectory graph

𝒢k\\mathcal\{G\}\_\{k\}from

\{\(st,at,st\+1\)\}⊂𝒯\\\{\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)\\\}\\subset\\mathcal\{T\}via state canonicalization

ϕ\\phi
6:Identify sink nodes; assign terminal reward

Ri∈\{0,1\}R\_\{i\}\\in\\\{0,1\\\}
7:endfor

8:// State\-value estimation

9:foreach task

qkq\_\{k\}do

10:Solve the Bellman equation \([5](https://arxiv.org/html/2609.28963#S3.E5)\) on

𝒢k\\mathcal\{G\}\_\{k\}via value iteration

→\{V⁡\(u\)\}\\rightarrow\\\{V\(u\)\\\}
11:endfor

12:// Step\-level advantage computation

13:foreach step

\(st,at,st\+1\)∈𝒯\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)\\in\\mathcal\{T\}do

14:

At←γ⋅V⁡\(ϕ⁡\(st\+1\)\)−V⁡\(ϕ⁡\(st\)\)A\_\{t\}\\leftarrow\\gamma\\cdot V\(\\phi\(s\_\{t\+1\}\)\)\-V\(\\phi\(s\_\{t\}\)\)
15:

AtG​A​E←At\+∑k=1T−t\(γ​λ\)k⋅A¯t\+k,A¯t\+k=1\|ℰk​\(at\)\|​∑\(u′,a′,v′\)∈ℰk​\(at\)\[γ​V​\(ϕ⁡\(v′\)\)−V⁡\(ϕ⁡\(u′\)\)\]A\_\{t\}^\{GAE\}\\leftarrow A\_\{t\}\+\\sum\_\{k=1\}^\{T\-t\}\(\\gamma\\lambda\)^\{k\}\\cdot\\bar\{A\}\_\{t\+k\},\\quad\\bar\{A\}\_\{t\+k\}=\\frac\{1\}\{\|\\mathcal\{E\}\_\{k\}\(a\_\{t\}\)\|\}\\sum\_\{\(u^\{\\prime\},a^\{\\prime\},v^\{\\prime\}\)\\in\\mathcal\{E\}\_\{k\}\(a\_\{t\}\)\}\\bigl\[\\gamma V\(\\phi\(v^\{\\prime\}\)\)\-V\(\\phi\(u^\{\\prime\}\)\)\\bigr\]
16:

A^step​\(st,at\)←GroupNorm​\(AtG​A​E,𝒢⁡\(ϕ⁡\(st\)\)\)\\hat\{A\}\_\{\\text\{step\}\}\(s\_\{t\},a\_\{t\}\)\\leftarrow\\text\{GroupNorm\}\(A\_\{t\}^\{GAE\};\\,\\mathcal\{G\}\(\\phi\(s\_\{t\}\)\)\)
17:endfor

18:// Policy update

19:Update

πθ\\pi\_\{\\theta\}via the calibrated optimization objective in Eq\.\([4](https://arxiv.org/html/2609.28963#S2.E4)\) on batch

𝒯\\mathcal\{T\}using

\{A^i,t\}\\\{\\hat\{A\}\_\{i,t\}\\\}
20:endfor

## Appendix CProof of Proposition 1

###### Proof\.

We first formalize the distribution under which the advantage estimation error is evaluated\. Letdπd^\{\\pi\}denote the state\-action visitation distribution induced by policyπ\\piover the time steps used for policy optimization\. For a step\-level credit signalXX, its population estimation error is

ℰ⁡\(X\)=𝔼τ∼π​\[\(Xt−Aπ​\(St,At\)\)2\]\\mathcal\{E\}\(X\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\}\\left\[\\bigl\(X\_\{t\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\\bigr\)^\{2\}\\right\]\(12\)where the expectation is taken over both the visitation of\(St,At\)\(S\_\{t\},A\_\{t\}\)and the stochastic continuation of the trajectory after timett\.

#### Graph\-based TD credit\.

Because the environment is deterministic, each state\-action pair\(s,a\)\(s,a\)has a unique successor state

s′=T⁡\(s,a\)s^\{\\prime\}=T\(s,a\)\(13\)The Bellman equation therefore gives

Qπ​\(s,a\)=r⁡\(s,a,s′\)\+γ​Vπ​\(s′\)Q^\{\\pi\}\(s,a\)=r\(s,a,s^\{\\prime\}\)\+\\gamma V^\{\\pi\}\(s^\{\\prime\}\)\(14\)Using the standard definition of the policy advantage,

Aπ​\(s,a\)=Qπ​\(s,a\)−Vπ​\(s\)A^\{\\pi\}\(s,a\)=Q^\{\\pi\}\(s,a\)\-V^\{\\pi\}\(s\)\(15\)we obtain

Aπ​\(s,a\)=r⁡\(s,a,s′\)\+γ​Vπ​\(s′\)−Vπ​\(s\)=XtGA^\{\\pi\}\(s,a\)=r\(s,a,s^\{\\prime\}\)\+\\gamma V^\{\\pi\}\(s^\{\\prime\}\)\-V^\{\\pi\}\(s\)=X\_\{t\}^\{G\}\(16\)Hence, the population estimation error of our graph\-based step\-level creditXtGX\_\{t\}^\{G\}follows that

ℰ⁡\(XG\)=𝔼τ∼π​\[\(XtG−Aπ​\(St,At\)\)2\]=0\\mathcal\{E\}\(X^\{G\}\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\}\\left\[\\bigl\(X\_\{t\}^\{G\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\\bigr\)^\{2\}\\right\]=0\(17\)

#### State\-grouped step\-level credit\.

Recall that the population counterpart of the state\-grouped step\-level signal in GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\)is

XtS=Gt−Vπ​\(St\)X\_\{t\}^\{S\}=G\_\{t\}\-V^\{\\pi\}\(S\_\{t\}\)\(18\)whereGt=∑k=tTτγk−t​rkG\_\{t\}=\\sum\_\{k=t\}^\{T\_\{\\tau\}\}\\gamma^\{k\-t\}r\_\{k\}is the sampled return from timett\.

For a fixed state\-action pair\(s,a\)\(s,a\), subtracting the true policy advantage from Equation \([18](https://arxiv.org/html/2609.28963#A3.E18)\) yields

XtS−Aπ​\(s,a\)\\displaystyle X\_\{t\}^\{S\}\-A^\{\\pi\}\(s,a\)=Gt−Vπ​\(s\)−\[Qπ​\(s,a\)−Vπ​\(s\)\]\\displaystyle=G\_\{t\}\-V^\{\\pi\}\(s\)\-\\left\[Q^\{\\pi\}\(s,a\)\-V^\{\\pi\}\(s\)\\right\]=Gt−Qπ​\(s,a\)\\displaystyle=G\_\{t\}\-Q^\{\\pi\}\(s,a\)\(19\)By the definition of the action\-value function,

Qπ\(s,a\)=𝔼\[Gt∣St=s,At=a\]Q^\{\\pi\}\(s,a\)=\\mathbb\{E\}\[G\_\{t\}\\mid S\_\{t\}=s,A\_\{t\}=a\]\(20\)Therefore,

𝔼\[\(XtS−Aπ\(s,a\)\)2∣St=s,At=a\]\\displaystyle\\mathbb\{E\}\\left\[\\bigl\(X\_\{t\}^\{S\}\-A^\{\\pi\}\(s,a\)\\bigr\)^\{2\}\\mid S\_\{t\}=s,A\_\{t\}=a\\right\]=𝔼\[\(Gt−Qπ\(s,a\)\)2∣s,a\]\\displaystyle=\\mathbb\{E\}\\left\[\\bigl\(G\_\{t\}\-Q^\{\\pi\}\(s,a\)\\bigr\)^\{2\}\\mid s,a\\right\]=Var⁡\(Gt∣St=s,At=a\)\\displaystyle=\\operatorname\{Var\}\\left\(G\_\{t\}\\mid S\_\{t\}=s,A\_\{t\}=a\\right\)\(21\)Taking the expectation over the visitation distribution gives

ℰ⁡\(XS\)=𝔼\(s,a\)∼dπ​\[Var⁡\(Gt∣St=s,At=a\)\]\\mathcal\{E\}\(X^\{S\}\)=\\mathbb\{E\}\_\{\(s,a\)\\sim d^\{\\pi\}\}\\left\[\\operatorname\{Var\}\\left\(G\_\{t\}\\mid S\_\{t\}=s,A\_\{t\}=a\\right\)\\right\]\(22\)In particular,ℰ⁡\(XS\)≥0\\mathcal\{E\}\(X^\{S\}\)\\geq 0\. We next establish when the inequality is strict\. Under sparse rewards, suppose that

rk=0for​k<Tτ,R⁡\(τ\)=rTτr\_\{k\}=0\\quad\\text\{for \}k<T\_\{\\tau\},\\qquad R\(\\tau\)=r\_\{T\_\{\\tau\}\}\(23\)where a failed trajectory receivesR⁡\(τ\)=0R\(\\tau\)=0and a successful trajectory receivesR⁡\(τ\)\>0R\(\\tau\)\>0\. The return from timettis then

Gt=γTτ−t​R​\(τ\)G\_\{t\}=\\gamma^\{T\_\{\\tau\}\-t\}R\(\\tau\)\(24\)For every\(s,a\)∈Ω\(s,a\)\\in\\Omega, both successful and failed continuations occur with positive probability\. Consequently,

Pr⁡\(Gt=0∣s,a\)\>0andPr⁡\(Gt\>0∣s,a\)\>0\\Pr\(G\_\{t\}=0\\mid s,a\)\>0\\qquad\\text\{and\}\\qquad\\Pr\(G\_\{t\}\>0\\mid s,a\)\>0\(25\)Thus,GtG\_\{t\}is not constant conditional on\(s,a\)\(s,a\), which implies

Var⁡\(Gt∣s,a\)\>0,\(s,a\)∈Ω\\operatorname\{Var\}\(G\_\{t\}\\mid s,a\)\>0,\\qquad\(s,a\)\\in\\Omega\(26\)IfΩ\\Omegahas positive visitation probabilitydπ​\(Ω\)\>0d^\{\\pi\}\(\\Omega\)\>0, then Equations \([22](https://arxiv.org/html/2609.28963#A3.E22)\) and \([26](https://arxiv.org/html/2609.28963#A3.E26)\) implyℰ⁡\(XS\)\>0\\mathcal\{E\}\(X^\{S\}\)\>0\.

#### Trajectory\-level credit\.

Let

bE=𝔼τ∼π​\[R⁡\(τ\)∣S0=s0\]b\_\{E\}=\\mathbb\{E\}\_\{\\tau\\sim\\pi\}\[R\(\\tau\)\\mid S\_\{0\}=s\_\{0\}\]\(27\)denotes the population trajectory\-level baseline for the fixed task\. The population counterpart of the trajectory\-level credit credit in GRPO is

XtE=R⁡\(τ\)−bEX\_\{t\}^\{E\}=R\(\\tau\)\-b\_\{E\}\(28\)Although the same trajectory\-level signal is assigned to every step in the trajectory, the desired target at stepttis the state\-dependent advantageAπ​\(St,At\)A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\. For a fixed state\-action pair\(s,a\)\(s,a\), define

μE\(s,a\)=𝔼\[XtE∣St=s,At=a\]\\mu\_\{E\}\(s,a\)=\\mathbb\{E\}\[X\_\{t\}^\{E\}\\mid S\_\{t\}=s,A\_\{t\}=a\]\(29\)The estimation error can be decomposed as

XtE−Aπ​\(s,a\)=\[XtE−μE​\(s,a\)\]\+\[μE​\(s,a\)−Aπ​\(s,a\)\]X\_\{t\}^\{E\}\-A^\{\\pi\}\(s,a\)=\\left\[X\_\{t\}^\{E\}\-\\mu\_\{E\}\(s,a\)\\right\]\+\\left\[\\mu\_\{E\}\(s,a\)\-A^\{\\pi\}\(s,a\)\\right\]\(30\)Squaring both sides and taking the conditional expectation gives

𝔼\[\(XtE−Aπ\(s,a\)\)2∣St=s,At=a\]=Var\(XtE∣s,a\)\+\[μE\(s,a\)−Aπ\(s,a\)\]2\\mathbb\{E\}\\left\[\\bigl\(X\_\{t\}^\{E\}\-A^\{\\pi\}\(s,a\)\\bigr\)^\{2\}\\mid S\_\{t\}=s,A\_\{t\}=a\\right\]=\\operatorname\{Var\}\(X\_\{t\}^\{E\}\\mid s,a\)\+\\left\[\\mu\_\{E\}\(s,a\)\-A^\{\\pi\}\(s,a\)\\right\]^\{2\}\(31\)The above derivation is because the cross term has conditional expectation zero\.

SincebEb\_\{E\}is a constant for the fixed task, thus

Var⁡\(XtE∣s,a\)=Var⁡\(R⁡\(τ\)∣s,a\)\\operatorname\{Var\}\(X\_\{t\}^\{E\}\\mid s,a\)=\\operatorname\{Var\}\(R\(\\tau\)\\mid s,a\)\(32\)Substituting Equation \([32](https://arxiv.org/html/2609.28963#A3.E32)\) into Equation \([31](https://arxiv.org/html/2609.28963#A3.E31)\) yields

𝔼\[\(XtE−Aπ\(s,a\)\)2∣s,a\]=Var\(R\(τ\)∣s,a\)\+\[μE\(s,a\)−Aπ\(s,a\)\]2\\mathbb\{E\}\\left\[\\bigl\(X\_\{t\}^\{E\}\-A^\{\\pi\}\(s,a\)\\bigr\)^\{2\}\\mid s,a\\right\]=\\operatorname\{Var\}\(R\(\\tau\)\\mid s,a\)\+\\left\[\\mu\_\{E\}\(s,a\)\-A^\{\\pi\}\(s,a\)\\right\]^\{2\}\(33\)Taking the expectation overdπd^\{\\pi\}gives

ℰ⁡\(XE\)=𝔼\(s,a\)∼dπ​\[Var⁡\(R⁡\(τ\)∣s,a\)\]\+𝔼\(s,a\)∼dπ​\[\(μE​\(s,a\)−Aπ​\(s,a\)\)2\]\\mathcal\{E\}\(X^\{E\}\)=\\mathbb\{E\}\_\{\(s,a\)\\sim d^\{\\pi\}\}\\left\[\\operatorname\{Var\}\(R\(\\tau\)\\mid s,a\)\\right\]\+\\mathbb\{E\}\_\{\(s,a\)\\sim d^\{\\pi\}\}\\left\[\\left\(\\mu\_\{E\}\(s,a\)\-A^\{\\pi\}\(s,a\)\\right\)^\{2\}\\right\]\(34\)Both terms on the right\-hand side are non\-negative, and henceℰ⁡\(XE\)≥0\\mathcal\{E\}\(X^\{E\}\)\\geq 0\.

For every\(s,a\)∈Ω\(s,a\)\\in\\Omega, both successful and failed trajectories occur with positive probability\. Therefore,

Pr⁡\(R⁡\(τ\)=0∣s,a\)\>0andPr⁡\(R⁡\(τ\)\>0∣s,a\)\>0\\Pr\(R\(\\tau\)=0\\mid s,a\)\>0\\qquad\\text\{and\}\\qquad\\Pr\(R\(\\tau\)\>0\\mid s,a\)\>0\(35\)It follows that

Var⁡\(R⁡\(τ\)∣s,a\)\>0,\(s,a\)∈Ω\\operatorname\{Var\}\(R\(\\tau\)\\mid s,a\)\>0,\\qquad\(s,a\)\\in\\Omega\(36\)Ifdπ​\(Ω\)\>0d^\{\\pi\}\(\\Omega\)\>0, Equation \([31](https://arxiv.org/html/2609.28963#A3.E31)\) therefore impliesℰ⁡\(XE\)\>0\\mathcal\{E\}\(X^\{E\}\)\>0\.

#### Comparison\.

Equation \([17](https://arxiv.org/html/2609.28963#A3.E17)\) establishes thatℰ⁡\(XG\)=0\\mathcal\{E\}\(X^\{G\}\)=0, Equations \([22](https://arxiv.org/html/2609.28963#A3.E22)\) and \([31](https://arxiv.org/html/2609.28963#A3.E31)\) establish thatℰ⁡\(XS\)≥0,ℰ⁡\(XE\)≥0\\mathcal\{E\}\(X^\{S\}\)\\geq 0,\\mathcal\{E\}\(X^\{E\}\)\\geq 0\. Therefore,

ℰ⁡\(XG\)≤min⁡\{ℰ⁡\(XS\),ℰ⁡\(XE\)\}\\mathcal\{E\}\(X^\{G\}\)\\leq\\min\\left\\\{\\mathcal\{E\}\(X^\{S\}\),\\mathcal\{E\}\(X^\{E\}\)\\right\\\}\(37\)
Furthermore, ifΩ\\Omegahas positive visitation probability underπ\\pi, Equations \([26](https://arxiv.org/html/2609.28963#A3.E26)\) and \([32](https://arxiv.org/html/2609.28963#A3.E32)\) give

ℰ⁡\(XS\)\>0,ℰ⁡\(XE\)\>0\\mathcal\{E\}\(X^\{S\}\)\>0,\\qquad\\mathcal\{E\}\(X^\{E\}\)\>0\(38\)Combining Equations \([37](https://arxiv.org/html/2609.28963#A3.E37)\) and \([38](https://arxiv.org/html/2609.28963#A3.E38)\), we obtain the strict inequality

ℰ⁡\(XG\)<min⁡\{ℰ⁡\(XS\),ℰ⁡\(XE\)\}\\mathcal\{E\}\(X^\{G\}\)<\\min\\left\\\{\\mathcal\{E\}\(X^\{S\}\),\\mathcal\{E\}\(X^\{E\}\)\\right\\\}\(39\)This completes the proof\. ∎

#### Remark\.

Proposition[1](https://arxiv.org/html/2609.28963#Thmproposition1)compares the population credit signals underlying the three methods\. In practice, GRAFT replacesVπV^\{\\pi\}with the graph\-based estimatorV^\\widehat\{V\}\. For

X^tG=rt\+γ​V^​\(St\+1\)−V^​\(St\)\\widehat\{X\}\_\{t\}^\{G\}=r\_\{t\}\+\\gamma\\widehat\{V\}\(S\_\{t\+1\}\)\-\\widehat\{V\}\(S\_\{t\}\)its deviation from the population graph\-based TD credit satisfies

X^tG−XtG=γ⁡\[V^​\(St\+1\)−Vπ​\(St\+1\)\]−\[V^​\(St\)−Vπ​\(St\)\]\\widehat\{X\}\_\{t\}^\{G\}\-X\_\{t\}^\{G\}=\\gamma\\left\[\\widehat\{V\}\(S\_\{t\+1\}\)\-V^\{\\pi\}\(S\_\{t\+1\}\)\\right\]\-\\left\[\\widehat\{V\}\(S\_\{t\}\)\-V^\{\\pi\}\(S\_\{t\}\)\\right\]Thus, the empirical graph\-based step\-level advantage estimator approaches the zero\-error population target as the graph\-based value estimates become more accurate\.

###### Proposition 2\(Lower Finite\-Sample Advantage Estimation Error\)\.

ConsiderN≥2N\\geq 2independent length\-TTrollouts from the same initial state under a fixed policyπ\\piin a deterministic environment with sparse terminal\-state rewardsR∈\[0,1\]R\\in\[0,1\], andγ∈\(0,1\)\\gamma\\in\(0,1\)\. Let

XtG=γ​V^​\(St\+1\)−V^​\(St\),XtS=Gt−G¯​\(St\),XtE=R−R¯X\_\{t\}^\{G\}=\\gamma\\widehat\{V\}\(S\_\{t\+1\}\)\-\\widehat\{V\}\(S\_\{t\}\),\\quad X\_\{t\}^\{S\}=G\_\{t\}\-\\overline\{G\}\(S\_\{t\}\),\\quad X\_\{t\}^\{E\}=R\-\\overline\{R\}be the unnormalized graph\-based, state\-grouped, and trajectory\-level credits of GRAFT, GiGPO, and GRPO, respectively\.V^\\widehat\{V\}is the empirical Bellman solution withV^​\(ST\)=R\\widehat\{V\}\(S\_\{T\}\)=R,Gt=γT−t​RG\_\{t\}=\\gamma^\{T\-t\}R,G¯​\(u\)\\overline\{G\}\(u\)averages over all visits touuacross trajectories and time steps, andR¯\\overline\{R\}is the whole\-group mean\. Letet=V^​\(St\)−Vπ​\(St\)e\_\{t\}=\\widehat\{V\}\(S\_\{t\}\)\-V^\{\\pi\}\(S\_\{t\}\)denotes the state\-value estimation error\. Define the mean\-squared advantage estimation error asℰ⁡\(X\)=𝔼τ∼π​\[\(Xt−Aπ​\(St,At\)\)2\]\\mathcal\{E\}\(X\)=\\mathbb\{E\}\_\{\\tau\\sim\\pi\}\[\(X\_\{t\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\)^\{2\}\], where the expectation is taken over the sampled rollout group and an action selected uniformly from that group\. If

‖γ​et\+1−et‖2\+max⁡\{‖G¯​\(St\)−Vπ​\(St\)‖2,Var⁡\(R\)N\}≤𝔼⁡\[Var⁡\(Gt∣St,At\)\]\\displaystyle\\\|\\gamma e\_\{t\+1\}\-e\_\{t\}\\\|\_\{2\}\+\\max\\\!\\left\\\{\\\|\\overline\{G\}\(S\_\{t\}\)\-V^\{\\pi\}\(S\_\{t\}\)\\\|\_\{2\},\\sqrt\{\\frac\{\\operatorname\{Var\}\(R\)\}\{N\}\}\\right\\\}\\leq\\sqrt\{\\mathbb\{E\}\[\\operatorname\{Var\}\(G\_\{t\}\\mid S\_\{t\},A\_\{t\}\)\]\}\(40\)then

ℰ⁡\(XG\)≤min⁡\{ℰ⁡\(XS\),ℰ⁡\(XE\)\}\\mathcal\{E\}\(X^\{G\}\)\\leq\\min\\\{\\mathcal\{E\}\(X^\{S\}\),\\mathcal\{E\}\(X^\{E\}\)\\\}\(41\)Both comparisons are strict if Eq\.[40](https://arxiv.org/html/2609.28963#A3.E40)is strict\.

###### Proof\.

We evaluate all three credit signals on the same rollout group\. Independently of the group, selectiiuniformly from\{1,…,N\}\\\{1,\\ldots,N\\\}andttuniformly from\{0,…,T−1\}\\\{0,\\ldots,T\-1\\\}, and write\(St,At,St\+1,R\)=\(Si,t,Ai,t,Si,t\+1,Ri\)\(S\_\{t\},A\_\{t\},S\_\{t\+1\},R\)=\(S\_\{i,t\},A\_\{i,t\},S\_\{i,t\+1\},R\_\{i\}\)\. For any random variableZZ, let‖Z‖2=\(𝔼⁡\[Z2\]\)1/2\\\|Z\\\|\_\{2\}=\(\\mathbb\{E\}\[Z^\{2\}\]\)^\{1/2\}\.

Following the terminal\-value convention,Vπ​\(Si,T\)=RiV^\{\\pi\}\(S\_\{i,T\}\)=R\_\{i\}and

Gi,t=γT−tRi,Qπ\(St,At\)=𝔼\[Gt∣St,At\],Aπ=Qπ−VπG\_\{i,t\}=\\gamma^\{T\-t\}R\_\{i\},\\qquad Q^\{\\pi\}\(S\_\{t\},A\_\{t\}\)=\\mathbb\{E\}\[G\_\{t\}\\mid S\_\{t\},A\_\{t\}\],\\qquad A^\{\\pi\}=Q^\{\\pi\}\-V^\{\\pi\}\(42\)Define the state visit group

ℐ\(u\)=\{\(j,k\):1≤j≤N,0≤k<T,Sj,k=u\}\\mathcal\{I\}\(u\)=\\\{\(j,k\):1\\leq j\\leq N,\\ 0\\leq k<T,\\ S\_\{j,k\}=u\\\}\(43\)The empirical baselines are

G¯​\(u\)=1\|ℐ⁡\(u\)\|​∑\(j,k\)∈ℐ⁡\(u\)Gj,k,R¯=1N​∑j=1NRj\\overline\{G\}\(u\)=\\frac\{1\}\{\|\\mathcal\{I\}\(u\)\|\}\\sum\_\{\(j,k\)\\in\\mathcal\{I\}\(u\)\}G\_\{j,k\},\\qquad\\overline\{R\}=\\frac\{1\}\{N\}\\sum\_\{j=1\}^\{N\}R\_\{j\}\(44\)All occurrences are included, including the selected occurrence and repeated visits within one trajectory\. The evaluated group is always nonempty\. For brevity in the proof, set

σG\\displaystyle\\sigma\_\{G\}=𝔼⁡\[Var⁡\(Gt∣St,At\)\],\\displaystyle=\\sqrt\{\\mathbb\{E\}\[\\operatorname\{Var\}\(G\_\{t\}\\mid S\_\{t\},A\_\{t\}\)\]\},\(45\)σR\\displaystyle\\sigma\_\{R\}=𝔼⁡\[Var⁡\(R∣St,At\)\],\\displaystyle=\\sqrt\{\\mathbb\{E\}\[\\operatorname\{Var\}\(R\\mid S\_\{t\},A\_\{t\}\)\]\},ηS\\displaystyle\\eta\_\{S\}=‖G¯​\(St\)−Vπ​\(St\)‖2,ηE=Var⁡\(R\)/N\\displaystyle=\\\|\\overline\{G\}\(S\_\{t\}\)\-V^\{\\pi\}\(S\_\{t\}\)\\\|\_\{2\},\\qquad\\eta\_\{E\}=\\sqrt\{\\operatorname\{Var\}\(R\)/N\}

#### Graph\-based TD credit\.

Because the environment is deterministic, the true Bellman equation at an executed transition gives

Aπ​\(St,At\)=γ​Vπ​\(St\+1\)−Vπ​\(St\)A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)=\\gamma V^\{\\pi\}\(S\_\{t\+1\}\)\-V^\{\\pi\}\(S\_\{t\}\)\(46\)Consequently,

XtG−Aπ​\(St,At\)\\displaystyle X\_\{t\}^\{G\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)=γ⁡\[V^​\(St\+1\)−Vπ​\(St\+1\)\]−\[V^​\(St\)−Vπ​\(St\)\]\\displaystyle=\\gamma\\bigl\[\\widehat\{V\}\(S\_\{t\+1\}\)\-V^\{\\pi\}\(S\_\{t\+1\}\)\\bigr\]\-\\bigl\[\\widehat\{V\}\(S\_\{t\}\)\-V^\{\\pi\}\(S\_\{t\}\)\\bigr\]\(47\)=γ​et\+1−et\\displaystyle=\\gamma e\_\{t\+1\}\-e\_\{t\}Thus the finite\-sample graph\-credit error is exactly

ℰ⁡\(XG\)=‖γ​et\+1−et‖2\\sqrt\{\\mathcal\{E\}\(X^\{G\}\)\}=\\\|\\gamma e\_\{t\+1\}\-e\_\{t\}\\\|\_\{2\}\(48\)

#### State\-grouped step\-level credit\.

Subtracting the true advantage yields

XtS−Aπ​\(St,At\)=\\displaystyle X\_\{t\}^\{S\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)=\{\}\[Gt−Qπ​\(St,At\)\]−\[G¯​\(St\)−Vπ​\(St\)\]\\displaystyle\\bigl\[G\_\{t\}\-Q^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\\bigr\]\-\\bigl\[\\overline\{G\}\(S\_\{t\}\)\-V^\{\\pi\}\(S\_\{t\}\)\\bigr\]\(49\)By the definition ofQπQ^\{\\pi\},

‖Gt−Qπ​\(St,At\)‖22=𝔼⁡\[Var⁡\(Gt∣St,At\)\]=σG2\\\|G\_\{t\}\-Q^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\\\|\_\{2\}^\{2\}=\\mathbb\{E\}\[\\operatorname\{Var\}\(G\_\{t\}\\mid S\_\{t\},A\_\{t\}\)\]=\\sigma\_\{G\}^\{2\}\(50\)Applying the reverse triangle inequality gives

ℰ⁡\(XS\)≥\(σG−ηS\)\+,\(x\)\+=max⁡\{x,0\}\\sqrt\{\\mathcal\{E\}\(X^\{S\}\)\}\\geq\(\\sigma\_\{G\}\-\\eta\_\{S\}\)\_\{\+\},\\qquad\(x\)\_\{\+\}=\\max\\\{x,0\\\}\(51\)The argument permits arbitrary dependence between the sampled return and its empirical state\-grouped baseline\. In particular, it applies to cross\-time groups and repeated visits without treating them as independent samples\.

#### Trajectory\-level credit\.

LetbE=𝔼⁡\[R\]b\_\{E\}=\\mathbb\{E\}\[R\]and define the population\-centered signalYtE=R−bEY\_\{t\}^\{E\}=R\-b\_\{E\}\. Its conditional bias–variance decomposition is

𝔼⁡\[\(YtE−Aπ​\(St,At\)\)2\]=\\displaystyle\\mathbb\{E\}\[\(Y\_\{t\}^\{E\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\)^\{2\}\]=\{\}𝔼⁡\[Var⁡\(R∣St,At\)\]\\displaystyle\\mathbb\{E\}\[\\operatorname\{Var\}\(R\\mid S\_\{t\},A\_\{t\}\)\]\(52\)\+𝔼\[\(𝔼\[R∣St,At\]−bE−Aπ\(St,At\)\)2\]\\displaystyle\+\\mathbb\{E\}\\\!\\left\[\\bigl\(\\mathbb\{E\}\[R\\mid S\_\{t\},A\_\{t\}\]\-b\_\{E\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\\bigr\)^\{2\}\\right\]Hence‖YtE−Aπ​\(St,At\)‖2≥σR\\\|Y\_\{t\}^\{E\}\-A^\{\\pi\}\(S\_\{t\},A\_\{t\}\)\\\|\_\{2\}\\geq\\sigma\_\{R\}\. Since the true state includesttandGt=γT−t​RG\_\{t\}=\\gamma^\{T\-t\}R,

σG2=𝔼⁡\[γ2​\(T−t\)​Var⁡\(R∣St,At\)\]≤σR2\\sigma\_\{G\}^\{2\}=\\mathbb\{E\}\[\\gamma^\{2\(T\-t\)\}\\operatorname\{Var\}\(R\\mid S\_\{t\},A\_\{t\}\)\]\\leq\\sigma\_\{R\}^\{2\}\(53\)The empirical baseline includes the selected trajectory, so

XtE=Ri−R¯=\(1−1N\)​Ri−1N​∑j≠iRjX\_\{t\}^\{E\}=R\_\{i\}\-\\overline\{R\}=\\left\(1\-\\frac\{1\}\{N\}\\right\)R\_\{i\}\-\\frac\{1\}\{N\}\\sum\_\{j\\neq i\}R\_\{j\}\(54\)TheNNcomplete rollouts are independent and identically distributed\. Therefore,

‖XtE−YtE‖22=𝔼⁡\[\(R¯−bE\)2\]=Var⁡\(R\)N=ηE2\\\|X\_\{t\}^\{E\}\-Y\_\{t\}^\{E\}\\\|\_\{2\}^\{2\}=\\mathbb\{E\}\[\(\\overline\{R\}\-b\_\{E\}\)^\{2\}\]=\\frac\{\\operatorname\{Var\}\(R\)\}\{N\}=\\eta\_\{E\}^\{2\}\(55\)A further application of the reverse triangle inequality gives

ℰ⁡\(XE\)≥\(σR−ηE\)\+≥\(σG−ηE\)\+\\sqrt\{\\mathcal\{E\}\(X^\{E\}\)\}\\geq\(\\sigma\_\{R\}\-\\eta\_\{E\}\)\_\{\+\}\\geq\(\\sigma\_\{G\}\-\\eta\_\{E\}\)\_\{\+\}\(56\)No independence betweenRiR\_\{i\}andR¯\\overline\{R\}is assumed\.

#### Comparison\.

Setη=max⁡\{ηS,ηE\}\\eta=\\max\\\{\\eta\_\{S\},\\eta\_\{E\}\\\}\. Equations[51](https://arxiv.org/html/2609.28963#A3.E51)and[56](https://arxiv.org/html/2609.28963#A3.E56)imply

min⁡\{ℰ⁡\(XS\),ℰ⁡\(XE\)\}≥\(σG−η\)\+\\min\\\!\\left\\\{\\sqrt\{\\mathcal\{E\}\(X^\{S\}\)\},\\sqrt\{\\mathcal\{E\}\(X^\{E\}\)\}\\right\\\}\\geq\(\\sigma\_\{G\}\-\\eta\)\_\{\+\}\(57\)Under condition[40](https://arxiv.org/html/2609.28963#A3.E40),

ℰ⁡\(XG\)=‖γ​et\+1−et‖2≤σG−η\\sqrt\{\\mathcal\{E\}\(X^\{G\}\)\}=\\\|\\gamma e\_\{t\+1\}\-e\_\{t\}\\\|\_\{2\}\\leq\\sigma\_\{G\}\-\\eta\(58\)The right\-hand side is nonnegative\. Squaring proves

ℰ⁡\(XG\)≤min⁡\{ℰ⁡\(XS\),ℰ⁡\(XE\)\}\\mathcal\{E\}\(X^\{G\}\)\\leq\\min\\\{\\mathcal\{E\}\(X^\{S\}\),\\mathcal\{E\}\(X^\{E\}\)\\\}\(59\)If condition[40](https://arxiv.org/html/2609.28963#A3.E40)is strict, the preceding comparison of square roots is strict andσG−η\>0\\sigma\_\{G\}\-\\eta\>0, yielding strict inequalities against both baselines\. This completes the proof\. ∎

#### Remark\.

Condition[40](https://arxiv.org/html/2609.28963#A3.E40)relates the admissible graph\-credit error to the accuracy of the empirical baselines\. For a fixed level of conditional return variability, smaller baseline errors increase the marginσG−max⁡\{ηS,ηE\}\\sigma\_\{G\}\-\\max\\\{\\eta\_\{S\},\\eta\_\{E\}\\\}, allowing a larger graph\-credit estimation error while preserving the comparison\. With correct state aggregation and adequate coverage of relevant states, additional independent rollouts can improve both the empirical baselines and the transition statistics used for graph\-value estimation\. These improvements act in complementary directions: more accurate baselines enlarge the admissible error margin, while more accurate graph values can reduce the graph\-credit error\. Thus, the condition describes a regime in which reliable cross\-trajectory statistics support more accurate credit assignment, without requiring exact value estimates\.

## Appendix DAdditional Experimental Analysis

### D\.1Hyperparameter Ablation Studies

Tab\.[4](https://arxiv.org/html/2609.28963#A4.T4)investigates the sensitivity of our method to the discount factorγ\\gammaand the weighting factorλ\\lambda\. Forγ\\gamma, we observe that larger values yield better performance\. This is expected in long\-horizon agentic tasks, where a higherγ\\gammafacilitates the backward propagation of sparse terminal rewards to earlier steps; conversely, lower values may cause initial steps to receive insufficient reward signals for effective learning\. Regardingλ\\lambda, a larger value indicates a longer backward\-looking horizon during Graph GAE estimation, incorporating more k\-hop step estimators to refine the single\-step estimator\. Since the optimal lookback depth varies with task complexity,λ\\lambdais typically tuned per benchmark\. Overall, the results demonstrate robust performance across a reasonable range of hyperparameters\.

Table 4:Hyperparameter ablation studies on the discount factorγ\\gammaand the weighing factorλ\\lambdain Graph GAE \(Eq\.\([9](https://arxiv.org/html/2609.28963#S3.E9)\)\)\.γ\\gammaALFWorldWebShopλ\\lambdaALFWorldWebShop0\.895\.676\.30\.595\.679\.70\.996\.179\.20\.697\.281\.20\.9596\.478\.10\.896\.482\.80\.9796\.980\.50\.996\.477\.30\.9996\.981\.00\.9597\.781\.2

### D\.2Node Group Size

![Refer to caption](https://arxiv.org/html/2609.28963v1/average_group_size.png)Figure 5:Dynamics of average node group size during the training process\.
![Refer to caption](https://arxiv.org/html/2609.28963v1/group_size_distribution.png)Figure 6:The distributions of node group size during training\.

Here, we present the dynamics of the average node group size \(*i\.e\.*, the number of outgoing edges per node\) during training and the distributions of group size\. As shown in Fig\.[6](https://arxiv.org/html/2609.28963#A4.F6), the average group size for WebShop and ALFWorld is around 4 and 5\. This indicates that many environmental observations recur in distinct trajectories yet lead to divergent outcomes, underscoring the necessity of aggregating trajectories into a unified trajectory graph\. In WebShop, the average group size initially increases, suggesting that the agent’s decisions converge during early training, leading to more frequent state revisits\. Subsequently, the group size decreases because fine\-grained credit assignment helps the agent to eliminate redundant steps, leading to shorter trajectories and fewer total observations\. In ALFWorld, the average group size increases, this is because that ALFWorld tasks inherently require repetitive actions, forcing the agent to revisit identical states\. This inherent repetition amplifies the upward trend in group size, outweighing the downward trend caused by redundant step removal\. Furthermore, as shown in Fig\.[6](https://arxiv.org/html/2609.28963#A4.F6), on both WebShop and ALFWorld benchmarks, more than 60% of steps fall into groups of 2 or larger, meaning the more faithful step\-level advantage estimation benefit from the shared state group\-aggregation mechanism\.

### D\.3Information Propagation Degree

![Refer to caption](https://arxiv.org/html/2609.28963v1/average_reward_degree.png)Figure 7:Dynamics of average information propagation degree during training\.
![Refer to caption](https://arxiv.org/html/2609.28963v1/reward_degree_distribution.png)Figure 8:The distributions of information propagation degree\.

We further analyze the dynamics and distributions of the information propagation degree during training\. The information propagation degree is defined as the number of distinct trajectories contributing reward information to the value estimation of a node \(or state\), as starting from one node in the graph can lead to multiple different trajectories\. As shown in Fig\.[8](https://arxiv.org/html/2609.28963#A4.F8), our method consistently achieves a higher information propagation degree than GiGPO across training\. This indicates that graph\-based state\-value estimation will aggregate reward signals from a broader set of trajectories for each node\. In contrast, GiGPO’s simple state grouping restricts reward propagation to the existing trajectory, preventing cross\-trajectory credit flow\. The results further support the analysis in Appendix[A\.1](https://arxiv.org/html/2609.28963#A1.SS1)that: graph\-based state\-value estimation will be more reliable as it can leverage more reward information\. Furthermore, in Fig\.[8](https://arxiv.org/html/2609.28963#A4.F8), up to 60% of the steps in GiGPO receive reward information from only a single trajectory, whereas in our GRAFT, this proportion significantly drops to 20%\.

### D\.4Additional Results

Performance based on Qwen3 model series\.In Tab\.[1](https://arxiv.org/html/2609.28963#S4.T1), for the convenience of direct and fair comparison with prior methods, we conducted experiments based on the Qwen2\.5\-Instruct model series\. Here, to further validate generalizability, we further extend our evaluation to the Qwen3 family \(*e\.g\.*, Qwen3\-4B and Qwen3\-8B, we reproduce GiGPO and GraphGPO for comparison\)\. The results in Tab\.[5](https://arxiv.org/html/2609.28963#A4.T5)show that our method significantly outperforms GiGPO and GraphGPO on both Qwen3\-4B and Qwen3\-8B models\. These evaluations confirm that our method is not tied to a specific base model, but can be effectively transferred to other base models\.

Table 5:Performance on ALFWorld and WebShop\. These results are based on the Qwen3 model series,*e\.g\.*, Qwen3\-4B and Qwen3\-8B\.TypeMethodALFWorldWebShopPickLookCleanHeatCoolPick2AllScoreSucc\.Qwen3\-4BRL TrainingGiGPO100\.081\.877\.354\.572\.084\.082\.084\.170\.6RL TrainingGraphGPO100\.070\.083\.378\.692\.969\.685\.985\.878\.9RL TrainingGRAFT \(Ours\)100\.090\.091\.792\.9100\.091\.395\.389\.682\.8Qwen3\-8BRL TrainingGiGPO91\.773\.382\.885\.789\.281\.286\.782\.771\.1RL TrainingGraphGPO95\.390\.083\.378\.6100\.095\.791\.488\.078\.9RL TrainingGRAFT \(Ours\)100\.0100\.0100\.087\.590\.594\.796\.190\.980\.5

### D\.5Case Study

![Refer to caption](https://arxiv.org/html/2609.28963v1/alfworld_graph1.png)Figure 9:A case study illustrating the constructed graph during training on ALFWorld\. In this task, all trajectories finally reach success\.To provide a more intuitive understanding of why our method can yield more faithful step\-level advantage estimates, we visualize some case graphs constructed during training on ALFWorld\. The graphs are shown in Fig\.[9](https://arxiv.org/html/2609.28963#A4.F9)and[10](https://arxiv.org/html/2609.28963#A4.F10)\. In Fig\.[9](https://arxiv.org/html/2609.28963#A4.F9), all trajectories ultimately lead to success, whereas Fig\.[10](https://arxiv.org/html/2609.28963#A4.F10)contains a mix of successful and failing trajectories\. Node color reflects state\-value: red indicates lower values, while green indicates higher values\. The visualization reveals that state\-values increase with proximity to successful terminal states and remain low for nodes from which success is unreachable\. Furthermore, nodes with mixed outcomes—where some trajectories succeed and others fail—exhibit intermediate state\-values, reflecting the expected value under the current policy\.

In Fig\.[9](https://arxiv.org/html/2609.28963#A4.F9), the task is to clean some cloth and put it in dresser\. Although all trajectories ultimately succeed, our method still effectively identifies specific erroneous steps\. Consider the actions highlighted by the red boxes, the preceding state is “you pick up the cloth 3 from the countertop 1”\. According to the task goal, after obtaining the cloth, it needs to be cleaned first and then placed in the dresser\. However, the action “go to dresser 1” is to directly put the cloth in the dresser, which results in deviating from the goal\. Subsequently, with making multiple corrective actions, the trajectory ultimately succeeds\. In the graph, this action leads to a lower\-value state, resulting in a negative advantage to successfully capture this erroneous action\. The action “go to sinkbasin 1” instead results in successful cleaning before placing in the dresser, thereby transitioning the agent into a higher\-value state\. Meanwhile, “go to bathroom sinkhole 1” is an invalid action, and it takes an additional step to reach the “sinkhole 1” state\. It can be found that the computed advantage of “go to bathroom sinkhole 1” is also slightly lower than that of “go to sinkhole 1”\. Overall, this qualitative analysis demonstrates that our method can discriminate among individual actions based on their true contributions, whereas trajectory\-level advantage estimation assigns uniform credit to all steps in a successful trajectory, failing to capture fine\-grained action quality\.

![Refer to caption](https://arxiv.org/html/2609.28963v1/alfworld_graph2.png)Figure 10:A case study illustrating the constructed graph during training on ALFWorld\. This graph contains a mix of successful and failing trajectories\.In Fig\.[10](https://arxiv.org/html/2609.28963#A4.F10), the task is to put two kettle in cabinet\. Let’s first focus on the actions marked in the upper red boxes\. The preceding state is “you move the kettle 1 to the cabinet 2”\. Now that a kettle has been placed in the cabinet, when action “go to stoveburner 3” is taken, it enables the agent to locate the second kettle\. Consequently, this action leads to a significant increase in the subsequent state values\. In contrast, “go to countertop 1” returns the agent to a location where kettle 1 was originally found; since the kettle has already been moved, no new kettle can be obtained there\. This results in a marked decrease in downstream state values\. A similar situation appears in the lower red boxes: “go to stoveburner 1” enters a state without a kettle, resulting in a low value, whereas “go to stoveburner 4” allows the agent to find kettle 3, again producing a substantial increase in value\. This example demonstrates that, in tasks containing both successful and failed trajectories, our method effectively identifies critical decision points, assigning higher advantages to steps pivotal to success and lower advantages to those leading toward failure\.

## Appendix EExperiment Details

### E\.1Descriptions of Benchmarks

ALFWorld is a text\-based environment aligned with the ALFRED embodied AI benchmark, which is designed to assess an agent’s ability to perform long\-horizon, multi\-step decision\-making tasks\. WebShop is a complex web\-based interactive environment that tests LLM agents in realistic online shopping scenarios, requiring them to navigate a realistic web interface to purchase items matching user specifications\. The SearchQA benchmark comprises several widely\-used search\-augmented QA datasets, including single\-hop QA \(NQ\([Kwiatkowski et al\., 2019](https://arxiv.org/html/2609.28963#bib.bib16)\), TriviaQA\([Joshi et al\., 2017](https://arxiv.org/html/2609.28963#bib.bib17)\), PopQA\([Mallen et al\., 2023](https://arxiv.org/html/2609.28963#bib.bib18)\)\) and multi\-hop QA \(HotpotQA\([Yang et al\., 2018](https://arxiv.org/html/2609.28963#bib.bib19)\), 2Wiki\([Ho et al\., 2020](https://arxiv.org/html/2609.28963#bib.bib20)\), MuSiQue\([Trivedi et al\., 2022](https://arxiv.org/html/2609.28963#bib.bib21)\), Bamboogle\([Press et al\., 2023](https://arxiv.org/html/2609.28963#bib.bib22)\)\)\.

### E\.2Training Details

To ensure a direct and fair comparison with previous methods, we follow the training and evaluation configurations from GiGPO\([Feng et al\., 2025](https://arxiv.org/html/2609.28963#bib.bib12)\)across all benchmarks\. The detailed settings for each benchmark are described below:

Hyperparameters for ALFWorld\. In ALFWorld, since states are predefined strings provided by the environment, state aggregation for building graph node is based on exact matching\. We set the maximum prompt and response lengths to 2048 and 512 tokens, respectively\. Each trajectory allows up to 50 environment steps\. Training runs for 150 steps with a policy learning rate of1​e−61e^\{\-6\}\. We employ a rule\-based reward scheme:\+10\+10for success, 0 for failure\. To handle invalid actions generated by the agent, we apply a reward penalty of−0\.1\-0\.1\. For all group\-based RL methods \(GRPO, GiGPO, HCAPO, GraphGPO\), we use a group size ofG=8G=8and sample 16 different tasks per rollout step, yielding16×8=12816\\times 8=128parallel environments\. In contrast, PPO uses 128 independent environments for fair comparison\. The rollout and validation temperatures are set to 1\.0 and 0\.4, respectively\. The mini\-batch size is 256, and the KL\-divergence loss coefficientβK​L\\beta\_\{KL\}is 0\.01\.

Hyperparameters for WebShop\. In WebShop, state aggregation is also based on exact matching\. We set the maximum prompt and response lengths to 5120 and 512 tokens, respectively, with each episode capped at 15 environment steps\. Training runs for 150 steps with a policy learning rate of1​e−61e^\{\-6\}\. We adopt a rule\-based reward scheme: assigning\+10\+10for success and 0 for failure\. Invalid actions are penalized with a reward of−0\.1\-0\.1\. Consistent with ALFWorld, all group\-based RL methods use a group size ofG=8G=8and sample 16 tasks per rollout step, yielding 128 parallel environments\. PPO uses 128 distinct environments for rollouts\. The rollout and validation temperatures are set to 1\.0 and 0\.4, respectively\. The mini\-batch size is 64, andβk​L\\beta\_\{kL\}is 0\.01\.

Hyperparameters for SearchQA\. In SearchQA, as there are no predefined state strings provided by the environment, the state aggregation is based on similarity\-based matching, with the similarity thresholdτ\\tauset to 0\.9\. state aggregation for building graph node is based on exact matching\. We set the maximum prompt and response lengths to 4096 and 512 tokens, respectively\. The maximum number of turns is set to 4\. The learning rate is1​e−61e^\{\-6\}for the policy model\. We employ a rule\-based reward scheme: assigning\+1\+1for success and 0 for failure\. Invalid actions are penalized with a reward of−0\.01\-0\.01\. We set the training data size to 256 and use a group size ofG=5G=5\. The rollout and validation temperatures are set to 1\.0 and 0\.0, respectively\. The mini\-batch size is 512, andβK​L\\beta\_\{KL\}is 0\.001\.

### E\.3Training Prompts

The prompts we use for LLM agents are constructed using Python\-style string formatting, where placeholders enclosed in curly braces \(*e\.g\.*, task description, step count, and current observation\) serve as semantic slots dynamically populated at runtime via Python’s \.format\(\) function\. To enrich the agent’s context, we incorporate historical information and set the history length to 2 for ALFWorld and WebShop, while retaining the full history for search\-augmented QA experiments\.

The<<think\>\><</think\>\>block instructs the agent to perform explicit step\-by\-step reasoning, thereby facilitating Chain\-of\-Thought \(CoT\) deliberation\. The<<action\>\><</action\>\>block is used to clearly indicate the final action decision\. For the search agent, reasoning traces are enclosed in<<think\>\><</think\>\>, search queries in<<search\>\><</search\>\>, and final answers in<<answer\>\><</answer\>\>tags\. Retrieved evidence from the search engine is presented within<<information\>\><</information\>\>tags\. The detailed prompt templates for each benchmark are provided in Fig\.[11](https://arxiv.org/html/2609.28963#A5.F11)\(ALFWorld\), Fig\.[12](https://arxiv.org/html/2609.28963#A5.F12)\(Webshop\), Fig\.[13](https://arxiv.org/html/2609.28963#A5.F13)\(SearchQA\)\.

Prompt Template for ALFWorldYou are an expert agent operating in the ALFRED embodied environment\. Your task is to:\{task\_description\}\. Prior to this step, you have already taken\{step\_count\}step\(s\)\. Below are the most recent\{history\_length\}observations and the corresponding actions you took:\{action\_history\}\. You are now at step\{current\_step\}and your current observation is:\{current\_observation\}\. Your admissible actions of the current situation are: \[\{admissible\_actions\}\]\.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 current step and present it within<<action\>\><</action\>\>tags\.Figure 11:Prompt template for ALFWorld\.Prompt Template for WebShopYou are an expert autonomous agent operating in the WebShop e\-commerce environment\. Your task is to:\{task\_description\}\. Prior to this step, you have already taken\{step\_count\}step\(s\)\. Below are the most recent\{history\_length\}observations and the corresponding actions you took:\{action\_history\}\. You are now at step\{current\_step\}and your current observation is:\{current\_observation\}\. Your admissible actions for the current situation are: \[\{available\_actions\}\]\.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 think carefully 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 current step and present it within<<action\>\><</action\>\>tags\.Figure 12:Prompt template for WebShop\.Prompt Template for SearchQAYou are an expert agent tasked with answering the given question step\-by\-step\.Your question:\{task\_description\}\.Prior to this step, you have already taken\{step\_count\}step\(s\)\. Below is the interaction history where<<search\>\><</search\>\>wrapped your past search queries and<<information\>\><</information\>\>wrapped the corresponding search results returned by the external search engine\.History:\{memory\_context\}Now it’s your turn to respond for the current step\. You should first conduct reasoning process\. This process MUST be enclosed within<<think\>\><</think\>\>tags\. After completing your reasoning, choose only one of the following actions \(do not perform both\):\(1\) If you find you lack some knowledge, you can call a search engine to get more external information using format:<<search\>\>your query<</search\>\>\.\(2\) If you have enough knowledge to answer the question confidently, provide your final answer within<<answer\>\><</answer\>\>tags, without detailed illustrations\. For example,<<answer\>\>Beijing<</answer\>\>\.Figure 13:Prompt template for SearchQA\.