mlsanityData to 7 Oct 2026

Graph-Enhanced Policy Optimization in LLM Agent Training

arXiv 2510.26270 ↗First posted 30 Oct 2025cs.AIcited by 2

On the map: LLM agents and tool use → Reinforcement learning for LLM agents

Abstract (arXiv)

Multi-step LLM agents in interactive environments represent a crucial step toward long-horizon decision-making. To train such agents, group-based reinforcement learning is widely adopted, which reinforces trajectories with higher relative performance within the group. However, in most existing methods, every step within a trajectory and every trajectory with the same terminal reward receive identical credit, regardless of their actual contributions. Since different states play different structural roles in an online state-transition graph built from sampled trajectories, their impacts should be differentiated and converted into task-aware credit at both the step and trajectory levels. We therefore present Graph-Enhanced Policy Optimization (GEPO), a framework for dual-level structural credit assignment in multi-step LLM agent training. Specifically, GEPO derives a state-level Task-Conditioned Criticality score that combines topological betweenness on the state-transition graph with semantic similarity to the task prompt. Based on this score, trajectory-level credit is reshaped through a state-adaptive discount, while step-level credit is scaled by the criticality of its successor state. Experimental results show that GEPO outperforms the strongest baselines by 1.1% in success rate on ALFWorld, 3.2% on WebShop, and 3.8% on average across search-augmented QA tasks at the 7B scale. Compared with flat group-based methods, GEPO reduces across-seed variance and concentrates gradient signals on the most critical steps.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use. Builds on 41 of its 63 references that are in the map. First posted on arXiv 30 Oct 2025.

Builds on

41 of 63 references.

Closest ancestors · 5

Same direction, newest first

  1. 2025AgentGym-RL: Training LLM Agents for Long-Horizon Decision Making through Multi-Turn Reinforcement Learning10 Sep
  2. 2025The Landscape of Agentic Reinforcement Learning for LLMs: A Survey2 Sep
  3. 2025Group-in-Group Policy Optimization for LLM Agent Training16 May
  4. 2025RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning24 Apr
  5. 2023Reflexion: Language Agents with Verbal Reinforcement Learning20 Mar

Other references · 36

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,049
  4. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 8,851
  5. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  6. 2018HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answeringcited by 3,686
  7. 2017TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehensioncited by 2,895
  8. 2025Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learningcited by 1,371
  9. 2020Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Stepscited by 1,259
  10. 2022WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agentscited by 1,197
  11. 2020ALFWorld: Aligning Text and Embodied Environments for Interactive Learningcited by 1,143
  12. 2022When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memoriescited by 1,103
24 more
  1. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,054
  2. 2023Self-Supervised Learning from Images with a Joint-Embedding Predictive Architecturecited by 982
  3. 2021MuSiQue: Multihop Questions via Single-hop Question Compositioncited by 893
  4. 2025ZeroSearch: Incentivize the Search Capability of LLMs without Searchingcited by 203
  5. 2025Plan-and-Act: Improving Planning of Agents for Long-Horizon Taskscited by 190
  6. 2023Multimodal Web Navigation with Instruction-Finetuned Foundation Modelscited by 159
  7. 2016Continuous Deep Q-Learning with Model-based Accelerationcited by 149
  8. 2022Partially Observable Markov Decision Processes in Robotics: A Surveycited by 81
  9. 2018Relational Deep Reinforcement Learningcited by 72
  10. 2024Exploring Autonomous Agents through the Lens of Large Language Models: A Reviewcited by 30
  11. 2024LLMSense: Harnessing LLMs for High-level Reasoning Over Spatiotemporal Sensor Tracescited by 28
  12. 2015How to Discount Deep Reinforcement Learning: Towards New Dynamic Strategiescited by 26
  13. 2024Deliberate Reasoning in Language Models as Structure-Aware Planning with an Accurate World Modelcited by 20
  14. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspectivecited by 16
  15. 2023Deep Explainable Relational Reinforcement Learning: A Neuro-Symbolic Approachcited by 15
  16. 2022Representation Learning in Deep RL via Discrete Information Bottleneckcited by 13
  17. 2024Topology-aware Reinforcement Feature Space Reconstruction for Graph Datacited by 11
  18. 2020An Overview of Natural Language State Representation for Reinforcement Learningcited by 6
  19. 2020MAGNet: Multi-agent Graph Network for Deep Multi-agent Reinforcement Learningcited by 4
  20. 2025Deep Reinforcement Learning Based Navigation with Macro Actions and Topological Mapscited by 4
  21. 2025LLM-Driven Intrinsic Motivation for Sparse Reward Reinforcement Learningcited by 4
  22. 2025CCL: Collaborative Curriculum Learning for Sparse-Reward Multi-Agent Reinforcement Learning via Co-evolutionary Task Evolutioncited by 3
  23. 2018Discovering Blind Spots in Reinforcement Learningcited by 2
  24. 2015Fully-dynamic Approximation of Betweenness Centralitycited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Phase-Aware Mixture of Experts for Agentic Reinforcement Learningcited by 4
  2. 2026Agentic Tool Use in Large Language Modelscited by 2

Similar, not cited

Close in wording, no citation either way

  1. 2026Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning
  2. 2026TIGPO: Temporal Instance-Graph Policy Optimization for Long-Horizon LLM Agents
  3. 2026Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning
  4. 2026Semantic Consistency Policy Optimization for Reinforcement Learning of LLM Agents
  5. 2026PGPO: Potential-Guided Policy Optimization for Multi-Turn Agentic Tasks
  6. 2026Graph-GRPO: Stabilizing Multi-Agent Topology Learning via Group Relative Policy Optimization
  7. 2026When Denser Credit Is Not Enough: Evidence-Calibrated Policy Optimization for Long-Horizon LLM Agent Training
  8. 2026MileGPO: Milestone Inference with Local Evidence for Graph-Based Policy Optimization of Long-Horizon LLM Agents