# Graph-Enhanced Policy Optimization in LLM Agent Training

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

## Key facts

- Cited by 5 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 41 of its 63 references that are in the map.
- First posted on arXiv 30 Oct 2025.

## 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 41)

- [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)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Self-Supervised Learning from Images with a Joint-Embedding Predictive Architecture](https://mlsanity.com/paper/2301.08243/) (2023)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)
- [RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2504.20073/) (2025)
- [ZeroSearch: Incentivize the Search Capability of LLMs without Searching](https://mlsanity.com/paper/2505.04588/) (2025)
- [The Landscape of Agentic Reinforcement Learning for LLMs: A Survey](https://mlsanity.com/paper/2509.02547/) (2025)
- [Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks](https://mlsanity.com/paper/2503.09572/) (2025)
- [Multimodal Web Navigation with Instruction-Finetuned Foundation Models](https://mlsanity.com/paper/2305.11854/) (2023)
- [Continuous Deep Q-Learning with Model-based Acceleration](https://mlsanity.com/paper/1603.00748/) (2016)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Relational Deep Reinforcement Learning](https://mlsanity.com/paper/1806.01830/) (2018)
- [AgentGym-RL: Training LLM Agents for Long-Horizon Decision Making through Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2509.08755/) (2025)
- [Exploring Autonomous Agents through the Lens of Large Language Models: A Review](https://mlsanity.com/paper/2404.04442/) (2024)
- [LLMSense: Harnessing LLMs for High-level Reasoning Over Spatiotemporal Sensor Traces](https://mlsanity.com/paper/2403.19857/) (2024)
- [How to Discount Deep Reinforcement Learning: Towards New Dynamic Strategies](https://mlsanity.com/paper/1512.02011/) (2015)
- [Deliberate Reasoning in Language Models as Structure-Aware Planning with an Accurate World Model](https://mlsanity.com/paper/2410.03136/) (2024)

## Built on by (most cited first, 5 of 5)

- [Phase-Aware Mixture of Experts for Agentic Reinforcement Learning](https://mlsanity.com/paper/2602.17038/) (2026)
- [Agentic Tool Use in Large Language Models](https://mlsanity.com/paper/2604.00835/) (2026)
- [Credit Where It Matters: Dependency-Aware Policy Optimization for Terminal Agents](https://mlsanity.com/paper/2610.03634/) (2026)
- [GraphOPD: Graph-Augmented On-Policy Distillation for LLM Agents](https://mlsanity.com/paper/2610.08959/) (2026)
- [Contextual Credit Policy Optimization](https://mlsanity.com/paper/2610.19103/) (2026)

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