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

Haodong Zhu; Yangyang Ren; Changbai Li; Sheng Xu; Linlin Yang; haiguang liu; Baochang Zhang

cs.LGSep 28, 2026

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

Authors: Haodong Zhu, Yangyang Ren, Changbai Li, Sheng Xu, Linlin Yang, haiguang liu, Baochang Zhang

Organizations: Beihang University · Zhongguancun Academy · Communication University of China · Hangzhou Innovation Institute of Beihang University

Abstract

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.

Figures & tables

Figure 1: Comparison of credit-assignment principles. (a) Illustration of rollout trajectory (N=8). Squares and circles denote states and actions; matching non-gray state colors indicate identical states. (b) ALFWorld success rates versus reference credit-assignment time. (c) Comparison of credit assignment across methods, highlighting the limitations of relying solely on trajectory outcomes or shortest paths.

Figure 2: Overview of GraphHCA. (a) Rollouts are merged into a graph where identical states share a node and edges carry action frequencies. (b) The success probability

\hat{\Phi}

is the fixed point of a discounted recursion with

\hat{\Phi}(F)=0

and

\hat{\Phi}(G)=1

. (c) The trajectory-level advantage

A^{T}(\tau)

is shared by all steps of

\tau

. (d) GraphHCA takes the increment of

\log\hat{\Phi}

as the step reward

R^{s}

and standardizes it among transitions sharing a source state to obtain

A^{s}

Panel of Figure 3 — Figure 3: Training success rate over update steps on ALFWorld and WebShop with Qwen2.5-1.5B-Instruct, and on Sokoban with Qwen2.5-VL-3B-Instruct. GraphHCA converges faster and reaches higher final success than the fine-grained credit-assignment baselines across all three environments.

Type	Method	ALFWorld							WebShop
Type	Method	Pick	Clean	Cool	Look	Heat	Pick2	All	Score	Succ.
Closed-Source Models
Prompting	GPT-4o	75.3	60.8	31.2	56.7	21.6	49.8	48.0	31.8	23.7
Prompting	Gemini-2.5-Pro	92.8	63.3	62.1	69.0	26.6	58.7	60.3	42.5	35.9
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

Table 1: Test performance on ALFWorld and WebShop. For ALFWorld, we report the average success rate (%) for each subtask and the overall result. For WebShop, we report the average task score and the average success rate (%). RL results are averaged over three random seeds. The best performance in each column is highlighted in bold .

	Qwen2.5-VL	GRPO	GiGPO	GraphGPO	GraphHCA
Type	Prompting	RL Training	RL Training	RL Training	RL Training
Sokoban [6 $\times$ 6]	11.7	71.1 ±3.9	79.0 ±3.1	81.6 ±4.03	84.0 ±1.2

Table 2: Test performance of VLM agents using Qwen2.5-VL-3B-Instruct on the interactive game environment Sokoban. We report the average success rate (%) over three random seeds.

$\omega$	Pick	Clean	Cool	Look	Heat	Pick2	All
$1$ (GraphHCA)	100.0 ±0.0	100.0 ±0.0	85.7 ±0.7	89.9 ±2.4	96.7 ±3.3	95.8 ±4.2	95.7 ±1.2
$5$	98.5 ±2.1	100.0 ±0.0	90.0 ±7.1	87.5 ±17.7	100.0 ±0.0	86.8 ±11.2	95.3 ±4.5
$10$	92.9 ±10.1	95.5 ±6.4	85.9 ±1.2	70.9 ±5.9	85.1 ±14.3	91.2 ±2.4	91.8 ±5.5
max ( $\omega\!\to\!\infty$ )	89.7 ±2.1	98.1 ±2.7	77.5 ±3.5	75.0 ±0.0	95.2 ±0.0	86.9 ±3.7	90.1 ±1.1
GraphGPO	95.6 ±4.4	97.6 ±2.4	83.5 ±3.5	71.3 ±8.8	97.6 ±2.4	86.6 ±2.3	91.0 ±2.0

Table 3: Ablation over the power-mean order

\omega

of Eq. ( 16 ) with Qwen2.5-1.5B-Instruct on AlfWorld: success rate (%) averaged over three random seeds. The per-column best is in bold .

Figure 4: Per-iteration runtime breakdown of the training stages. Blue bars denote stages shared by all group-based methods, while red bars denote the overhead of GraphHCA.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Advantage	Pick	Clean	Cool	Look	Heat	Pick2	All
$A^{\mathrm{T}}$ only ( $w_{\mathrm{s}}\!=\!0$ , GRPO)	88.2 ±2.9	72.6 ±15.9	67.5 ±7.5	43.3 ±18.3	76.6 ±0.4	51.6 ±9.5	71.1 ±1.6
$A^{\mathrm{step}}$ only	97.1 ±0.05	100.0 ±0.0	82.5 ±2.5	81.25 ±6.3	97.6 ±2.4	84.2 ±5.3	92.5 ±0.4
$w_{\mathrm{s}}=0.5$	100.0 ±0.0	100.0 ±0.0	82.5 ±2.5	68.8 ±6.3	95.2 ±0.0	92.1 ±2.6	93.4 ±0.5
$w_{\mathrm{s}}=0.7$	100.0 ±0.0	100.0 ±0.0	95.0 ±5.0	77.1 ±10.4	92.9 ±7.2	93.8 ±0.9	94.9 ±0.4
$w_{\mathrm{s}}=1$ (default)	100.0 ±0.0	100.0 ±0.0	85.7 ±0.7	89.9 ±2.4	96.7 ±3.3	95.8 ±4.2	95.7 ±1.2

Appendix

Table 4: ALFWorld ablation on the composition of the combined advantage of Eq. ( 12 ) with Qwen2.5-1.5B-Instruct: per-subtask and overall success rate (%) over three random seeds. The upper block removes one of the two terms, where

w_{\mathrm{s}}\!=\!0

recovers GRPO exactly (reproduced from Table 1 ). The lower block keeps both and varies their relative weight around the default

w_{\mathrm{s}}\!=\!1

(highlighted). The per-column best is in bold .

$\bar{\gamma}$	Pick	Clean	Cool	Look	Heat	Pick2	All
$0.55$	96.4 ±3.6	95.5 ±4.6	85.8 ±0.8	79.2 ±4.2	97.6 ±2.4	90.2 ±4.5	90.7 ±3.2
$0.75$	98.6 ±1.5	100.0 ±0.0	87.5 ±2.5	87.5 ±0.0	97.6 ±2.4	92.1 ±2.7	93.3 ±1.6
$0.95$ (default)	100.0 ±0.0	100.0 ±0.0	85.7 ±0.7	89.9 ±2.4	96.7 ±3.3	95.8 ±4.2	95.7 ±1.2

Appendix

Table 5: ALFWorld ablation over the propagation discount

\bar{\gamma}

of Eq. ( 9 ) with Qwen2.5-1.5B-Instruct: per-subtask and overall success rate (%) over three random seeds. The default

\bar{\gamma}\!=\!0.95

is highlighted. Small

\bar{\gamma}

drives the potential toward the distance surrogate

\bar{\gamma}^{\,d(s)}

of Eq. ( 15 ). The per-column best is in bold .

$\epsilon$	Pick	Clean	Cool	Look	Heat	Pick2	All
$10^{-6}$	100.0 ±0.0	100.0 ±0.0	90.0 ±0.0	81.3 ±6.3	95.3 ±4.8	89.5 ±5.3	94.9 ±2.0
$10^{-4}$	98.6 ±1.5	100.0 ±0.0	90.0 ±10.0	87.5 ±0.0	97.6 ±2.4	92.1 ±2.6	94.1 ±1.2
$10^{-2}$ (default)	100.0 ±0.0	100.0 ±0.0	85.7 ±0.7	89.9 ±2.4	96.7 ±3.3	95.8 ±4.2	95.7 ±1.2

Appendix

Table 6: ALFWorld ablation over the failure floor

\epsilon

of Eq. ( 10 ) with Qwen2.5-1.5B-Instruct: per-subtask and overall success rate (%) over three random seeds. The default

\epsilon\!=\!10^{-2}

is highlighted. The per-column best is in bold .

Panel of Figure 5 — Figure 5: Prompt template and illustrative filled example for ALFWorld.

Panel of Figure 6 — Figure 6: Prompt template and illustrative filled example for WebShop.

Panel of Figure 7 — Figure 7: Prompt template and illustrative filled example for Sokoban.

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
Granularity-Adaptive Credit Assignment for Long-Horizon LLM Agent Reinforcement Learning
Sep 14, 2026Taoran Liang, Yang Liu, Shang Luo +9Credit Assignment Large Language Model Agents
Nankai University · Peking University · Supply Chain Tech Team Y, JD.com +2
Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning
Sep 24, 2026Xincheng Yao, Haobo Fu, Weiming Liu +1Group-Based Reinforcement Learning Agentic Reinforcement Learning
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.

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

Granularity-Adaptive Credit Assignment for Long-Horizon LLM Agent Reinforcement Learning

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