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 Φ^ is the fixed point of a discounted recursion with Φ^(F)=0 and Φ^(G)=1 . (c) The trajectory-level advantage AT(τ) is shared by all steps of τ . (d) GraphHCA takes the increment of logΦ^ as the step reward Rs and standardizes it among transitions sharing a source state to obtain As .
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
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 × 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.
ω
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 ( ω→∞ )
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 ω 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
AT only ( ws=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
Astep 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
ws=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
ws=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
ws=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 ws=0 recovers GRPO exactly (reproduced from Table 1 ). The lower block keeps both and varies their relative weight around the default ws=1 (highlighted). The per-column best is in bold .
γˉ
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 γˉ of Eq. ( 9 ) with Qwen2.5-1.5B-Instruct: per-subtask and overall success rate (%) over three random seeds. The default γˉ=0.95 is highlighted. Small γˉ drives the potential toward the distance surrogate γˉd(s) of Eq. ( 15 ). The per-column best is in bold .
ϵ
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 ϵ of Eq. ( 10 ) with Qwen2.5-1.5B-Instruct: per-subtask and overall success rate (%) over three random seeds. The default ϵ=10−2 is highlighted. The per-column best is in bold .
Figure 5: Prompt template and illustrative filled example for ALFWorld.
Figure 6: Prompt template and illustrative filled example for WebShop.
Figure 7: Prompt template and illustrative filled example for Sokoban.
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
Reinforcement learning is now the standard way to train large language model agents on long-horizon tasks, where dozens of interdependent actions precede a single sparse reward. Critic-free, group-relative methods such as GRPO suit this regime, but they broadcast one trajectory-level scalar to every step and cannot say which decision drove the outcome. GiGPO recovers a step-level signal by grouping time steps that share an anchor state, yet it merges the step- and episode-level estimates under one fixed weight, spending the same resolution on a pivotal branching decision as on a routine, near-deterministic transition. We argue that the right resolution is state-dependent, and propose GACA, a critic-free estimator whose granularity follows an uncertainty-based criticality proxy. GACA scores every step by the negative log-likelihood its own rollout already records, then blends the two advantages with a per-step weight that grows with that score, so the gradient places more weight on the fine-grained signal at above-average NLL and on the episode-level signal below it. We derive an exact risk decomposition for the implemented mixture and show that sufficiently small modulation improves on fixed mixing under positive directional alignment. A separate conditional result bounds local action-value variation using expected NLL, while an error-projection analysis characterizes when mixing adds value beyond scalar uncertainty reweighting. On ALFWorld and WebShop, GACA improves task success over GRPO and GiGPO at both 1.5B and 7B scales.
Taoran Liang, Yang Liu, Shang Luo +9
Nankai University · Peking University · Supply Chain Tech Team Y, JD.com +2
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.
Xincheng Yao, Haobo Fu, Weiming Liu +1
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.