Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning

Xincheng Yao; Haobo Fu; Weiming Liu; Chongyang Zhang

cs.AISep 24, 2026

Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning

Authors: Xincheng Yao, Haobo Fu, Weiming Liu, Chongyang Zhang

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.

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 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 $\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 ).

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
Type	Method	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 $\pm$ 3.5	40.5 $\pm$ 6.9	57.1 $\pm$ 4.9	60.6 $\pm$ 6.6	46.4 $\pm$ 4.0	47.4 $\pm$ 1.9	54.4 $\pm$ 3.1	73.8 $\pm$ 3.0	51.5 $\pm$ 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.
Type	Method	NQ $\dagger$	TriviaQA $\star$	PopQA $\star$	HotpotQA $\dagger$	2Wiki $\star$	MuSiQue $\star$	Bamboogle $\star$	Avg.
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.

\dagger

and

\star

indicate in-domain and out-of-domain datasets, respectively. Bold indicates the best performance in each category.

Method	ALFWorld							Webshop
Method	Pick	Look	Clean	Heat	Cool	Pick2	All	Score	Succ.
GRAFT †	99.23 $\pm$ 1.08	100.0 $\pm$ 0.00	96.73 $\pm$ 2.31	97.23 $\pm$ 3.15	92.57 $\pm$ 5.35	89.60 $\pm$ 2.46	96.10 $\pm$ 1.13	89.53 $\pm$ 0.76	80.67 $\pm$ 1.68
w/o adv normalization	75.37 $\pm$ 1.51	75.47 $\pm$ 3.53	72.50 $\pm$ 4.76	63.10 $\pm$ 3.53	72.20 $\pm$ 5.67	60.90 $\pm$ 4.54	71.33 $\pm$ 2.87	85.67 $\pm$ 0.74	72.93 $\pm$ 1.46
w/ GRPO-C objective ( 4 )	100.0 $\pm$ 0.00	98.03 $\pm$ 2.78	96.00 $\pm$ 3.39	100.0 $\pm$ 0.00	96.20 $\pm$ 2.53	90.73 $\pm$ 3.78	96.87 $\pm$ 1.08	90.63 $\pm$ 1.51	81.30 $\pm$ 1.31
w/ Graph GAE ( 9 )	97.50 $\pm$ 2.18	100.0 $\pm$ 0.00	100.0 $\pm$ 0.00	100.0 $\pm$ 0.00	97.10 $\pm$ 2.11	91.53 $\pm$ 4.13	97.17 $\pm$ 0.75	90.23 $\pm$ 0.70	81.73 $\pm$ 0.75
GRAFT	99.17 $\pm$ 1.17	98.33 $\pm$ 2.35	100.0 $\pm$ 0.00	100.0 $\pm$ 0.00	93.33 $\pm$ 3.71	97.63 $\pm$ 3.34	97.43 $\pm$ 0.38	90.83 $\pm$ 0.37	82.27 $\pm$ 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

$\gamma$	ALFWorld	WebShop	$\lambda$	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

\gamma

and the weighing factor

\lambda

in Graph GAE (Eq.( 9 )).

Type	Method	ALFWorld							WebShop
Type	Method	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.

Panel of Figure 11 — Figure 11: Prompt template for ALFWorld.

Panel of Figure 12 — Figure 12: Prompt template for WebShop.

Panel of Figure 13 — Figure 13: Prompt template for SearchQA.

Explore similar work

Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning
May 26, 2026Xin Cheng, Shuo He, Lang Feng +4Group-Based Reinforcement Learning Agentic Reinforcement Learning
Nanyang Technological University, Singapore · Tongyi Lab, Alibaba Group · Southeast University, China
GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents
Sep 28, 2026Haodong Zhu, Yangyang Ren, Changbai Li +4Group-Based Reinforcement Learning Credit Assignment
Beihang University · Zhongguancun Academy · Communication University of China +1
Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning
Jun 22, 2026Yunan Wang, Minghui Song, Zihan Zhang +6Group-Based Reinforcement Learning
1Peking University · 2Microsoft Corporation

May 26, 2026, cs.LGJ/K move · Enter open · S save

Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning

Xin Cheng, Shuo He, Lang Feng, HaiYang Xu+3

Nanyang Technological University, Singapore · Tongyi Lab, Alibaba Group · Southeast University, China

Group-Based Reinforcement Learning Agentic Reinforcement Learning Credit Assignment

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning

GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents

Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning