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

1. Introduction

• LLM-based agents are increasingly used for open-ended, long-horizon tasks, and group-based RL methods use verifiable rewards and within-group statistics without a critic model.The paper notes extensions of group-based RL to multi-turn agentic tasks.Source: §1 · p. 1
• Trajectory-level attribution rewards every step in a successful run and penalizes every step in a failed run, regardless of each step’s contribution to progress.The authors characterize the resulting step-level signals as coarse and noisy, leading to inefficient learning.Source: §1 · pp. 1–2
• About 22.0% of steps in failed trajectories contribute to progress, while about 65.3% of steps in successful trajectories do not meaningfully advance the task.Figure 1 reports these step statistics for early-stage ALFWorld training with rollout M = 8 and maximum step T = 50.Source: §1 · p. 2, Figure 1 · p. 2
• GraphGPO aggregates rollout trajectories into a unified state-transition graph and uses global information to assign step-level credit and improve training efficiency.It remains critic-free and adds only negligible graph computation, according to the authors.Source: §1 · p. 2

2. Related Work

• Early LLM reinforcement learning used human preferences for alignment, while RL with verifiable rewards uses automatically computable rewards.The discussion associates verifiable-reward methods with reasoning, mathematics, code generation, tool use, and search.Source: §2 · p. 2
• Earlier agent-learning studies typically used value-based critics across Android control, embodied environments, and card games.The cited examples include Mnih et al. (2015), Tan et al. (2024), Wen et al. (2024), Zhai et al. (2024), Bai et al. (2024), and Wang et al. (2024c).Source: §2 · p. 2
• More recent agent-learning work extends to software engineering, GUI control, and Model Context Protocol settings.The passage cites Yang et al. (2024), Zheng et al. (2024b), Da et al. (2025), Lu et al. (2025), Wang et al. (2025b), Lai et al. (2025), Shi et al. (2025), Luo et al. (2025b), Le et al. (2025), and Team & Team (2025).Source: §2 · p. 2

3.1. Multi-turn Agentic Tasks

• Multi-turn agentic tasks involve a policy repeatedly observing environment states and taking actions, with rewards often delayed until trajectory completion.The paper focuses on sparse, delayed-reward settings.Source: §3.1 · pp. 2–3

3. Preliminaries

• Figure 2 depicts shared states across successful and failed rollouts and contrasts trajectory-level and step-level advantage estimation.It also illustrates credit-assignment issues when attribution depends solely on trajectory success.Source: Figure 2 · p. 3

3.2. Group-based Reinforcement Learning

• GRPO estimates advantages from rewards and statistics within a sampled group, then extends this approach from single-turn outputs to multi-turn trajectories.The trajectory group is scored according to whether each trajectory accomplishes the task goal.Source: §3.2 · p. 3
• GRPO assigns the same episode-level advantage to steps within a trajectory, while GiGPO groups steps that share an initial state to estimate step-level advantages.GiGPO’s step-level reward remains based on the final trajectory outcome.Source: §3.2 · p. 3

4.1. Limitations of Trajectory-Level Attribution

• Trajectory-level attribution rewards redundant or erroneous steps in successful trajectories and penalizes useful steps in failed ones.In the illustration, a failed trajectory takes a favorable action before a later transition to a state that cannot reach the goal.Source: §4.1 · p. 4

4.2. The Aggregated State-Transition Graph

• GraphGPO merges identical visited states across rollout trajectories into a directed graph of state transitions, with positive transition costs and goal or length-limit terminal states.In tool-use settings, costs can represent monetary or time costs.Source: §4.2 · p. 4

4.3. The Graph-Based Advantage Estimation

• Graph-based distance measures minimum cost to the goal; states without a path have infinite distance, and the step reward discounts success reward by successor distance.For unreachable states, the method substitutes the largest finite graph distance plus one to avoid overly strong penalties that may restrict exploration.Source: §4.3 · pp. 4–5
• Graph-based advantages compare each transition’s reward with other outgoing transitions from the same state; the method adds episode-level advantage when a state has only one outgoing edge.Without that addition, a singleton step-level group would have graph-based advantage zero.Source: §4.3 · p. 5, §4.4 · p. 5
• In the illustrated graph, a transition from a failed trajectory can receive higher advantage when its successor is closer to the goal than the alternative successor.The example also identifies a successor with no path to the goal and assigns the corresponding transition the smallest advantage in its group.Source: §4.3 · p. 5
• When an action moves closer to the goal than an alternative, GraphGPO assigns it the higher graph-based advantage under the proposition’s stated conditions.The proposition assumes a deterministic environment and compares the successor-state distance plus transition cost for each action.Source: §4.3 · p. 5

4.4. Policy Optimization

• The policy objective uses graph-based and episode-level advantages, with importance sampling and a KL penalty controlled by β.The episode-level advantage helps prevent graph-based advantage from becoming zero for states with only one outgoing edge.Source: §4.4 · p. 5
• Graph-style step feedback has no greater conditional variance than trajectory-style feedback under the proposition’s rollout and transition assumptions.The result assumes a fixed policy in a deterministic environment, both successful and failed trajectories pass through the transition, and the transition is independent of step t.Source: §4.4 · p. 6

5.1. Experimental Setup

• Evaluation covers ALFWorld, WebShop, and Sokoban, with LLM and VLM agents compared against prompting and reinforcement-learning baselines.The setup uses Qwen2.5 LLMs and a Qwen2.5-VL model, retains the two most recent interaction steps as memory, and sets the rollout group size to 8.Source: §5.1 · p. 6

5.2. Experimental Results

• GraphGPO raises ALFWorld average success rates over GRPO by 14.85% and 11.98% for 1.5B and 7B models, respectively, and WebShop average success rates by 7.30% and 5.31%.GraphGPO also attains higher WebShop task scores; Table 1 reports ALFWorld subtasks and overall results alongside WebShop task score and success rate.Source: Table 1 · p. 7, §5.2 · p. 7
• GraphGPO exceeds GRPO by 19.88% and GiGPO by 10.06% on Sokoban.The benchmark uses vision-language agents in an interactive game environment.Source: Table 2 · p. 7, §5.2 · p. 7
• GraphGPO maintains the leading position and highest peak across ALFWorld, WebShop, and Sokoban, with faster early improvement and the largest baseline gap mid-training.All three methods trend upward; the paper attributes GraphGPO’s advantage to graph-based estimates using global rollout information, especially when rollout success is low.Source: §5.2 · p. 7
• Removing episode-level advantages degrades GraphGPO and GiGPO on every benchmark, while GraphGPO remains ahead of GiGPO, including by 20.57% on Sokoban.With dynamic sampling, both methods benefit, but GraphGPO remains superior; sampling resamples all-success or all-failure rollout sets for up to 10 attempts.Source: §5.2 · pp. 7–8
• Graph construction takes 0.108s and graph-based advantage computation 0.025s, together accounting for 0.04% of per-iteration runtime.Rollout takes 216.9s and policy update takes 74.2s; the graph search has complexity O((|V| + |E|) log |V|).Source: §5.2 · p. 8

6. Conclusion

• GraphGPO aggregates rollout trajectories into a unified state-transition graph and assigns step-level credit according to global progress toward the task goal.The conclusion frames the method as complementary to existing group-based RL and a practical mechanism for credit assignment in long-horizon agentic tasks.Source: §6 · p. 8
• Across diverse multi-turn agentic benchmarks, GraphGPO consistently outperforms prior group-based methods.The conclusion attributes the approach to using global structural information across rollouts for step-level credit assignment.Source: §6 · p. 8
• The paper presents GraphGPO as a practical mechanism for improving credit assignment in long-horizon agentic tasks.Source: §6 · p. 8

A. Pseudo Code.

• Each iteration samples tasks and actions across multiple environments for up to T steps, producing rollout trajectories.Source: A. Pseudo Code · p. 13
• The algorithm constructs a directed state-transition graph, computes each node’s distance, forms step-level groups, and estimates episode-level and graph-based advantages.Source: A. Pseudo Code · p. 13
• The resulting advantages guide a policy update; the method retains critic-free, low-memory, stable-convergence properties while aggregating rollout information globally.The passage also characterizes this aggregation as enabling finer-grained, more informative credit assignment.Source: A. Pseudo Code · p. 13

B.1. Proof of Proposition 4.1

• The comparison assumes that the good action moves closer to the goal than the bad action.Source: §B.1 · p. 13
• Because ω lies between 0 and 1, the proof uses the strictly decreasing function x → ω^x to preserve the ordering implied by distance.Source: §B.1 · p. 13
• At a shared state, the compared edges use the same group mean and standard deviation; distinct rewards make the standard deviation positive, yielding the good edge’s higher graph-based advantage.Source: §B.1 · p. 13

• The analysis assumes both successful and failed trajectories visit the transition with positive probability and notes that transition occurrence can depend on step t.The transition's step dependence means its associated quantity need not be independent of t.Source: §B.2 · p. 14
• For failed trajectories visiting a transition, trajectory-style feedback has zero conditional variance.Source: §B.2 · p. 14
• Graph-style feedback is deterministic for an observed transition once the rollout graph is fixed in a deterministic environment.The successor state and feedback are therefore deterministic under these conditions.Source: §B.2 · p. 14

C.1. Computing Details

• Training runs for 150 epochs; the 1.5B and 3B models use two H100 GPUs, while the 7B model uses four.Source: §C.1 · p. 14

C.2. Prompts

• Prompts use Python-style formatting, with placeholders instantiated at each interaction step; visible interaction history is set to 2.Source: §C.2 · p. 15
• ALFWorld prompts add current location, held objects, and object-manipulation history, omitting the latter when no movement has occurred.Source: §C.2 · p. 15
• Control tags enclose reasoning and the selected action, while <image> represents visual observations in vision-language settings.Source: §C.2 · p. 15

C.3. Comparing Methods

• The comparisons include GPT-4o and Gemini-2.5-Pro, plus the prompting-based ReAct and Reflexion agents.Source: §C.3 · pp. 15–16
• RL baselines include PPO, RLOO, GRPO, and GiGPO; GRPO and GiGPO results are reproduced under the same settings, while other comparison results are adopted from GiGPO.Source: §C.3 · p. 16

C.4. ALFWorld

• ALFWorld observations are augmented with the agent's location and held objects; GraphGPO uses ω=0.10, and reproduced group-based methods perform noticeably better than in the original setting.Source: §C.4 · pp. 16–17

C.5. WebShop

• WebShop uses the official text-rich environment; reproduced group-based methods perform noticeably better than in the original setting, and GraphGPO uses ω=0.20.Source: §C.5 · p. 17

C.6. Sokoban

• Sokoban evaluates vision-based interaction with Qwen2.5-VL-3B-Instruct, using 15-step episodes, group size 8, 128 training environments, and GraphGPO ω=0.80.Source: §C.6 · p. 17

D.1. Hyperparameter

• On ALFWorld, varying ω has relatively mild influence; GraphGPO is comparable to the baseline in the worst case and usually outperforms it.Source: §D.1 · p. 18, Table 4 · p. 18
• On WebShop, GraphGPO is reported robust to ω, with a recommended range of 0.1–0.4.Source: §D.1 · p. 18, Table 5 · p. 18

• GraphGPO consistently outperforms GRPO and GiGPO during training, especially in the early and middle stages, which the authors attribute to more informative step-level credit assignment.Source: §D.2 · p. 18
• GraphGPO reaches comparable validation performance about 30 training steps before GiGPO and 110 before GRPO on ALFWorld, and about 80 and 90 steps earlier, respectively, on WebShop.Source: §D.2 · p. 18
• The authors conclude that global state relationships provide faithful, low-variance step-level supervision that accelerates policy improvement and supports faster, more stable convergence in long-horizon tasks.Source: §D.2 · p. 18

D.3. Noise Environments

• With embedding-based matching at a 95% similarity threshold, GraphGPO remains highly robust to severe graph sparsity and advertisement noise on WebShop.The evaluation inserts random advertisements and compares raw-text with embedding-based matching; Table 6 reports average success rates across noise settings.Source: Table 6 · p. 19, §D.3 · p. 19
• When no states can be matched, GraphGPO falls back to trajectory-level advantage and degenerates to GRPO, making GRPO a lower bound in this extreme case.Minor formatting or environment-response variations can fragment graphs in high-dimensional or long-text observations.Source: §D.3 · pp. 18–19

D.4. Group Sizes

• More rollouts can reveal environment structure and improve credit assignment, but GraphGPO works without a complete graph, whose construction is costly because rollout is the iteration’s most time-consuming part.The paper examines the trade-off using different rollout counts on WebShop; Table 7 reports average success rates across group sizes.Source: §D.4 · p. 19, Table 7 · p. 19

E. Case Study

• In the WebShop walkthrough, the agent selects men, navy, and x-large, then chooses buy now for a shirt it says meets the requested criteria.The request also specifies machine wash, classic fit, and a price below $50.Source: E. Case Study · pp. 24–26