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

arXiv: https://arxiv.org/abs/2605.26684 · HTML: https://mlsanity.com/paper/2605.26684/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 81 of its 93 references that are in the map.
- First posted on arXiv 26 May 2026.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 30 of 81)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Qwen2.5-VL Technical Report](https://mlsanity.com/paper/2502.13923/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [PaLM-E: An Embodied Multimodal Language Model](https://mlsanity.com/paper/2303.03378/) (2023)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)

## Built on by (most cited first, 30 of 31)

- [Progress-conditioned Group Policy Optimization for Long-Horizon Agentic Tasks](https://mlsanity.com/paper/2607.22724/) (2026)
- [TRCA: Transition-wise Rubric Credit Assignment for Long-horizon LLM Agents](https://mlsanity.com/paper/2608.16156/) (2026)
- [SAPO: Single-Rollout Autoregressive Policy Optimization for Agentic Reinforcement Learning](https://mlsanity.com/paper/2608.19842/) (2026)
- [Gated-BEPO: Confidence-Gated Bellman Credit Assignment for Large Language Model Agents](https://mlsanity.com/paper/2608.06861/) (2026)
- [DART-SD: Diamond-topology Aware Retrieval and Tuning for Self-Distillation of Multi-Turn Tool-Calling Agents](https://mlsanity.com/paper/2608.18524/) (2026)
- [MileGPO: Milestone Inference with Local Evidence for Graph-Based Policy Optimization of Long-Horizon LLM Agents](https://mlsanity.com/paper/2608.19803/) (2026)
- [When Does Muon Help Agentic Reinforcement Learning?](https://mlsanity.com/paper/2607.16169/) (2026)
- [The Horizon Gap: Planning, Memory, Execution, Training, and Evaluation for Long-Horizon LLM Agents](https://mlsanity.com/paper/2608.06663/) (2026)
- [Learning from Environmental Feedback: Credit Assignment across Multiple Timescales for Agentic Reinforcement Learning](https://mlsanity.com/paper/2608.08255/) (2026)
- [TIGPO: Temporal Instance-Graph Policy Optimization for Long-Horizon LLM Agents](https://mlsanity.com/paper/2609.03383/) (2026)
- [Groupwise Agentic Grading and Advantage Redistribution for Code Agent RL](https://mlsanity.com/paper/2609.32577/) (2026)
- [Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning](https://mlsanity.com/paper/2609.28963/) (2026)
- [From Trajectories to Grounded Preferences: Process Preference Synthesis via Interaction Element Graphs for Web PRMs](https://mlsanity.com/paper/2609.32351/) (2026)
- [Multi-Agent System Search via Active Substructure-aware Policy Optimization](https://mlsanity.com/paper/2609.32430/) (2026)
- [SWE-MILE: Asynchronous Potential-Induced Milestone Credit Assignment for Long-Horizon Software Engineering Agents](https://mlsanity.com/paper/2609.32631/) (2026)
- [UniOPSD: Unifying Outcome and Hindsight Feedback for Agentic Reinforcement Learning](https://mlsanity.com/paper/2609.34810/) (2026)
- [TIDE: Teacher-Student Transition via Informative Distillation and Exploration for Agentic RL](https://mlsanity.com/paper/2609.35058/) (2026)
- [Cross-Rollout Bellman Closure for Long-Horizon Agentic Reinforcement Learning](https://mlsanity.com/paper/2609.35082/) (2026)
- [GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents](https://mlsanity.com/paper/2609.35084/) (2026)
- [Graph-Conditioned On-Policy Agent Distillation from Off-the-Shelf Teachers](https://mlsanity.com/paper/2609.37522/) (2026)
- [PRICE the Action Chunks: Physical Relational Credit Assignment for Embodied Reinforcement Learning](https://mlsanity.com/paper/2609.38890/) (2026)
- [It Takes Workflows to Evolve Better Workflows](https://mlsanity.com/paper/2610.01026/) (2026)
- [Dependency-Aware Reward Shaping for Agentic Reinforcement Learning](https://mlsanity.com/paper/2610.01207/) (2026)
- [Credit Where It Matters: Dependency-Aware Policy Optimization for Terminal Agents](https://mlsanity.com/paper/2610.03634/) (2026)
- [RELACE: retrospective likelihood-based action credit estimation for long-horizon language agents](https://mlsanity.com/paper/2610.07349/) (2026)
- [VETTA: Coordinating Turn- and Token-Level Credit Assignment for Multi-Turn LLM Agents](https://mlsanity.com/paper/2610.08402/) (2026)
- [When Should Agents Think? Adaptive Reasoning via Cross-Turn Estimation](https://mlsanity.com/paper/2610.12061/) (2026)
- [SynAct: Synergistic Active Feedback Learning for LLM Agents](https://mlsanity.com/paper/2610.12651/) (2026)
- [Matched-Context Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2610.13755/) (2026)
- [VH-GPO: Verified Handoff for LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2610.14000/) (2026)

## Abstract (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.