Group-based reinforcement learning methods credit whole trajectories by final outcome, which makes it hard to see the contribution of individual steps — including valuable steps buried inside failed trajectories. The authors propose Graph-based Group Policy Optimization (GraphGPO), which aggregates all rollout trajectories into a unified state-transition graph, estimates the distance from each state to the task goal using global information encoded in the graph, and assigns credit to each edge by how much the transition reduces that distance. They report improved training efficiency and state-of-the-art performance across a range of benchmarks.
If you reward an agent on final outcome alone, you are running a search with a single bit of feedback per attempt. On a twelve-step task that is one bit for twelve decisions, and most of what the agent did right or wrong is invisible.
GraphGPO pools every rollout into one state-transition graph and then asks a better question per step: did this move get us closer to the goal. Because the graph is shared across trajectories, the distance estimate uses information no single run contains.
The paper calls out valuable steps obscured within failed trajectories. That is the practical point. A trajectory that failed for one bad action still contains eleven correct ones, and outcome-only reward throws all eleven away. Pooling recovers them.
Most teams we work with are not training agents with RL. But the underlying discipline transfers: instrument the step, not just the run. If the only metric you have is task success, you cannot tell a good plan with one bad tool call from a bad plan that got lucky.
@inproceedings{cheng2026beyond,
author = {Xin Cheng and Shuo He and Lang Feng and HaiYang Xu and Ming Yan and Lei Feng and Bo An},
title = {Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning},
booktitle = {International Conference on Machine Learning (ICML) 2026},
year = {2026},
eprint = {2605.26684},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.26684}
}Ejentic did not author this paper. Credit belongs to the authors named above; the note is ours.
2023
Cut the RLHF pipeline down to one training run. For teams without the infrastructure to run a reward model and PPO, this is usually the practical route into preference tuning.
2023
The reason fine-tuning stopped being a budget line item. Adapter-based tuning on one GPU is now the default first attempt; full fine-tuning has to justify itself.
2023
More tokens and more latency per answer, so it earns its place only where a wrong answer is expensive. We do not reach for it on classification or extraction.