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

• URL: http://arxiv.org/abs/2605.26684v2
• Date: Mon, 01 Jun 2026 06:20:12 GMT
• Title: Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning
• Abstract summary: Group-based reinforcement learning (RL) methods have achieved remarkable success in improving the performance of large language models (LLMs)<n>We propose Graph-based Group Policy Optimization (GraphGPO), which aggregates all rollout trajectories into a unified state-transition graph.<n>It estimates the distance from each state to the task goal using the global information encoded in the graph.<n>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.
• Score: 30.228760269449072
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning [85.02566758103008]
  Group-Graph Policy Optimization (G2PO) is a novel group-based Reinforcement Learning algorithm tailored for multi-turn agentic tasks.<n>G2PO substantially outperforms state-of-the-art prompt-based and RL baselines, achieving remarkable success rate improvements of up to 22.2% over GRPO.
  arXiv  Detail & Related papers  (2026-06-22T08:12:47Z)
• Beyond Trajectory Rewards: Step-level Credit Assignment for Agentic Search via Graph Modeling [26.540951598344787]
  In Agentic Search, trajectory-level outcome rewards fail to quantify the behavioral contributions of individual steps.<n>We propose Graph-Distance Contribution Reward (GDCR), a step-level process reward that scores newly-retrieved and newly-cited entities by their distance to the answer node.
  arXiv  Detail & Related papers  (2026-05-28T09:57:12Z)
• Graph-GRPO: Training Graph Flow Models with Reinforcement Learning [14.937302684130257]
  We propose Graph-GRPO, an online reinforcement learning framework for training graph flow models (GFMs) under verifiable rewards.<n>With only 50 denoising steps, our method achieves 95.0% and 97.5% Valid-Unique-Novelty scores on the planar and tree datasets.
  arXiv  Detail & Related papers  (2026-03-11T04:20:45Z)
• Graph-GRPO: Stabilizing Multi-Agent Topology Learning via Group Relative Policy Optimization [7.961090665261694]
  We propose Graph-GRPO, a novel topology optimization framework that integrates Group Relative Policy Optimization.<n>By normalizing rewards across the sampled group, our method effectively mitigates the noise derived from task difficulty variance and enables fine-grained credit assignment.
  arXiv  Detail & Related papers  (2026-03-03T07:45:40Z)
• SketchVL: Policy Optimization via Fine-Grained Credit Assignment for Chart Understanding and More [15.102512433806751]
  We introduce SketchVL, a novel MLLM that optimized with FinePO, a new RL algorithm designed for fine-grained credit assignment within each trajectory.<n>During training, the FinePO algorithm leverages a Fine-grained Process Reward Model (FinePRM) to score each drawing action within a trajectory, thereby precisely assigning credit for each step.<n>Experiments show that SketchVL learns to align its step-level behavior with the FinePRM, achieving an average performance gain of 7.23% over its base model.
  arXiv  Detail & Related papers  (2026-01-09T10:13:01Z)
• Incorporating Spatial Information into Goal-Conditioned Hierarchical Reinforcement Learning via Graph Representations [37.10671332775445]
  The integration of graphs with Goal-conditioned Reinforcement Learning (GCHRL) has recently gained attention.<n>Existing approaches typically rely on domain-specific knowledge to construct these graphs.<n>This paper proposes a solution by developing a graph encoder-decoder to evaluate unseen states.
  arXiv  Detail & Related papers  (2025-11-14T00:58:39Z)
• AutoGraph-R1: End-to-End Reinforcement Learning for Knowledge Graph Construction [60.51319139563509]
  We introduce AutoGraph-R1, the first framework to directly optimize KG construction for task performance using Reinforcement Learning (RL)<n>We design two novel, task-aware reward functions, one for graphs as knowledge carriers and another as knowledge indices.<n>Our work shows it is possible to close the loop between construction and application, shifting the paradigm from building intrinsically good'' graphs to building demonstrably useful'' ones.
  arXiv  Detail & Related papers  (2025-10-17T06:03:36Z)
• GRAIL:Learning to Interact with Large Knowledge Graphs for Retrieval Augmented Reasoning [13.481673780508215]
  GRAIL is a framework designed to interact with large-scale graphs for retrieval-augmented reasoning.<n>GRAIL achieves an average accuracy improvement of 21.01% and F1 improvement of 22.43% on knowledge graph question-answering datasets.
  arXiv  Detail & Related papers  (2025-08-07T15:34:41Z)
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning [58.73279333365234]
  Reinforcement Learning (RL) on synthetic graph-theoretic tasks can significantly scale graph reasoning abilities.<n>With RL on Erdos, G1 obtains substantial improvements in graph reasoning, where our finetuned 3B model even outperforms Qwen2.5-72B-Instruct (24x size)<n>Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph-theoretic tasks.
  arXiv  Detail & Related papers  (2025-05-24T04:33:41Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• FedGraph: A Research Library and Benchmark for Federated Graph Learning [57.769105634569314]
  Federated graph learning is an emerging field with significant practical challenges.<n>We introduce FedGraph, a research library designed for practical distributed training.<n>FedGraph supports a range of state-of-the-art graph learning methods and includes a monitoring class that evaluates system performance.
  arXiv  Detail & Related papers  (2024-10-08T20:18:18Z)
• Overcoming Pitfalls in Graph Contrastive Learning Evaluation: Toward Comprehensive Benchmarks [60.82579717007963]
  We introduce an enhanced evaluation framework designed to more accurately gauge the effectiveness, consistency, and overall capability of Graph Contrastive Learning (GCL) methods.
  arXiv  Detail & Related papers  (2024-02-24T01:47:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.