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

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.

Large language models are increasingly used as agents that complete tasks through multiple steps, such as browsing websites, using tools, or solving games. However, training them is difficult because a whole attempt is usually judged only as a success or failure, which can unfairly reward bad steps or punish good ones. We propose GraphGPO, a method that connects many attempts into a graph, like a map of the agent’s explored paths. By looking at how each step changes the agent’s distance to the goal, GraphGPO gives more accurate feedback to individual decisions. This allows the agent to learn useful behavior from both successful and failed attempts. Across household, web shopping, and puzzle-game tasks, GraphGPO learns faster and achieves stronger performance than previous reinforcement learning methods for agents. This work provides a practical way to train more efficient and reliable AI agents for long, multi-step tasks.