Organizations: School of Information Science and Electronic Engineering, Shanghai Jiao Tong University. · Tencent AI Platform Department. · MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong University.
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 propose a Graph-based Faithful 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.
Figures & tables
Figure 1: Method overview. Given N rollouts 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) is assigned as the step-level advantage, which coincides with the standard advantage function definition (see Sec. 3.3 ).
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.
Type
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
Qwen2.5-1.5B-Instruct
Prompting
Qwen2.5
5.9
5.5
3.3
9.7
4.2
0.0
4.1
23.1
5.2
Prompting
ReAct
17.4
20.5
15.7
6.2
7.7
2.0
12.8
40.1
11.3
Prompting
Reflexion
35.3
22.2
21.7
13.6
19.4
3.7
21.8
55.8
21.9
RL Training
PPO
64.8 ± 3.5
40.5 ± 6.9
57.1 ± 4.9
60.6 ± 6.6
46.4 ± 4.0
47.4 ± 1.9
54.4 ± 3.1
73.8 ± 3.0
51.5 ± 2.9
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 are bolded .
Type
Method
Single-Hop QA
Multi-Hop QA
Avg.
NQ †
TriviaQA ⋆
PopQA ⋆
HotpotQA †
2Wiki ⋆
MuSiQue ⋆
Bamboogle ⋆
Qwen2.5-3B-Instruct
RL Training
R1-Instruct
27.0
53.7
19.9
23.7
29.2
7.2
29.3
27.1
RL Training
Search-R1
34.1
54.5
37.8
32.4
31.9
10.3
26.4
32.5
RL Training
ZeroSearch
41.4
57.4
44.8
27.4
30.0
9.8
11.1
31.7
RL Training
StepSearch
–
–
–
34.5
32.0
17.4
–
34.4
Table 2: Performance on searchQA tasks. † and ⋆ indicate in-domain and out-of-domain datasets, respectively. Bold indicates the best performance in each category.
Method
ALFWorld
Webshop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
GRAFT †
99.23 ± 1.08
100.0 ± 0.00
96.73 ± 2.31
97.23 ± 3.15
92.57 ± 5.35
89.60 ± 2.46
96.10 ± 1.13
89.53 ± 0.76
80.67 ± 1.68
w/o adv normalization
75.37 ± 1.51
75.47 ± 3.53
72.50 ± 4.76
63.10 ± 3.53
72.20 ± 5.67
60.90 ± 4.54
71.33 ± 2.87
85.67 ± 0.74
72.93 ± 1.46
w/ GRPO-C objective ( 4 )
100.0 ± 0.00
98.03 ± 2.78
96.00 ± 3.39
100.0 ± 0.00
96.20 ± 2.53
90.73 ± 3.78
96.87 ± 1.08
90.63 ± 1.51
81.30 ± 1.31
w/ Graph GAE ( 9 )
97.50 ± 2.18
100.0 ± 0.00
100.0 ± 0.00
100.0 ± 0.00
97.10 ± 2.11
91.53 ± 4.13
97.17 ± 0.75
90.23 ± 0.70
81.73 ± 0.75
GRAFT
99.17 ± 1.17
98.33 ± 2.35
100.0 ± 0.00
100.0 ± 0.00
93.33 ± 3.71
97.63 ± 3.34
97.43 ± 0.38
90.83 ± 0.37
82.27 ± 0.99
Table 3: Ablation study results. “w/o adv normalization” denotes directly using the step-level advantage defined in Eq.( 8 ) without further advantage normalization. GRAFT † is a variant of GRAFT without GRPO-C objective (Eq.( 4 )) and Graph GAE, serving as the baseline for ablation studies. The results are based on Qwen2.5-1.5B-Instruct.
Figure 3: The average number of execution turns required to finish tasks.
Figure 4: Breakdown of time consumption per training step.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
γ
ALFWorld
WebShop
λ
ALFWorld
WebShop
0.8
95.6
76.3
0.5
95.6
79.7
0.9
96.1
79.2
0.6
97.2
81.2
0.95
96.4
78.1
0.8
96.4
82.8
0.97
96.9
80.5
0.9
96.4
77.3
0.99
96.9
81.0
0.95
97.7
81.2
Appendix
Table 4: Hyperparameter ablation studies on the discount factor γ and the weighing factor λ in Graph GAE (Eq.( 9 )).
Figure 9Figure 10
Type
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
Qwen3-4B
RL Training
GiGPO
100.0
81.8
77.3
54.5
72.0
84.0
82.0
84.1
70.6
RL Training
GraphGPO
100.0
70.0
83.3
78.6
92.9
69.6
85.9
85.8
78.9
RL Training
GRAFT (Ours)
100.0
90.0
91.7
92.9
100.0
91.3
95.3
89.6
82.8
Qwen3-8B
Appendix
Table 5: Performance on ALFWorld and WebShop. These results are based on the Qwen3 model series, e.g. , Qwen3-4B and Qwen3-8B.
Figure 9: A case study illustrating the constructed graph during training on ALFWorld. In this task, all trajectories finally reach success.
Figure 10: A case study illustrating the constructed graph during training on ALFWorld. This graph contains a mix of successful and failing trajectories.
Group-based reinforcement learning (RL) methods have achieved remarkable success in improving the performance of large language models (LLMs) and have been rapidly extended to agentic tasks. However, their credit assignment relies heavily on coarse-grained trajectory-level attribution according to final outcomes, making it difficult to capture the contribution of individual steps, such as valuable steps obscured within failed trajectories. To uncover latent information and enable more faithful step-level credit assignment, we propose Graph-based Group Policy Optimization (GraphGPO), which first aggregates all rollout trajectories into a unified state-transition graph and then estimates the distance from each state to the task goal using the global information encoded in the graph. Finally, GraphGPO assigns credit to each edge by estimating a graph-based advantage, based on how much the transition reduces the distance to the task goal. In this way, GraphGPO significantly improves training efficiency and achieves state-of-the-art performance across a range of challenging benchmarks.
Xin Cheng, Shuo He, Lang Feng +4
Nanyang Technological University, Singapore · Tongyi Lab, Alibaba Group · Southeast University, China
Group-based reinforcement learning (RL) has advanced large language models (LLMs) and is increasingly extending to agentic tasks, where sparse terminal rewards make step-level credit assignment essential. Existing methods assign credit from what follows an action in sampled rollouts, but do not explicitly capture its retrospective relation to the realized outcome. Hindsight credit assignment (HCA) instead attributes credit through the ratio of hindsight to behavior-policy probabilities, but estimating the hindsight distribution requires an auxiliary model or an extra pass. To address this estimation bottleneck, we propose GraphHCA, a model-free realization of HCA that eliminates explicit hindsight-distribution estimation. For terminal-goal tasks with deterministic transitions, Bayes' rule reduces the hindsight ratio to a ratio of behavior-policy success probabilities at consecutive states. Taking logs yields a state-wise success potential, whose increment across a transition provides step-level credit. GraphHCA estimates this potential from pooled rollouts through a discounted recursion on the induced transition graph, which admits a unique fixed point on any directed graph. The resulting step-level signal is combined with the trajectory-level advantage, requiring neither a learned hindsight model nor an extra forward pass and recovering GRPO when the step-level weight is zero. Among all compared baselines, GraphHCA achieves state-of-the-art results on ALFWorld and WebShop at both LLM scales, and on Sokoban with a vision-language agent. For example, on ALFWorld it improves overall success rate by up to 24.6 points over GRPO and by up to 4.7 points over the strongest step-level baseline.
Haodong Zhu, Yangyang Ren, Changbai Li +4
Beihang University · Zhongguancun Academy · Communication University of China +1
Group-based Reinforcement Learning (RL) has significantly enhanced Large Language Models (LLMs) in agentic scenarios. To achieve finer-grained policy updates, recent agentic RL frameworks have shifted from trajectory-level to step-level training. However, long-horizon agentic RL suffers from severe reward sparsity and delay, as feedback is often deferred for dozens of interaction steps. While existing step-level frameworks refine training granularity, their credit assignment remains coarse-grained and still treats agent exploration as isolated, linear trajectories. This oversimplified perspective ignores the inherent graph structure of state transitions, leading to high-variance state-value estimation and myopic, localized credit assignment. To overcome these critical bottlenecks, we propose Group-Graph Policy Optimization (G2PO), a novel group-based RL algorithm tailored for multi-turn agentic tasks. G2PO explicitly transforms linear interaction trajectories into a global state-transition graph. By aggregating identical observations across different trajectories, we introduce group-aggregation state-value estimation that reduces sampling variance and trajectory-dependent bias. Furthermore, we redefine agent actions as transitions between state nodes and propose an edge-centric advantage estimation strategy. By globally standardizing Temporal Difference (TD) errors across the entire graph, G2PO explicitly identifies and prioritizes critical transitions that drive absolute task progress. Extensive experiments on representative long-horizon benchmarks-WebShop, ALFWorld, and AppWorld-demonstrate that G2PO substantially outperforms state-of-the-art prompt-based and RL baselines, achieving remarkable success rate improvements of up to 22.2% over GRPO.