# Reinforcing Multi-Turn Reasoning in LLM Agents via Fine-Grained Reward Structure and Credit Assignment

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

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 32 of its 61 references that are in the map.
- First posted on arXiv 17 May 2025.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)
- 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 32)

- [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)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [Qwen-VL: A Versatile Vision-Language Model for Understanding, Localization, Text Reading, and Beyond](https://mlsanity.com/paper/2308.12966/) (2023)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Process Reinforcement through Implicit Rewards](https://mlsanity.com/paper/2502.01456/) (2025)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [ReTool: Reinforcement Learning for Strategic Tool Use in LLMs](https://mlsanity.com/paper/2504.11536/) (2025)
- [RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2504.20073/) (2025)
- [ToolRL: Reward is All Tool Learning Needs](https://mlsanity.com/paper/2504.13958/) (2025)
- [ToRA: A Tool-Integrated Reasoning Agent for Mathematical Problem Solving](https://mlsanity.com/paper/2309.17452/) (2023)
- [ToRL: Scaling Tool-Integrated RL](https://mlsanity.com/paper/2503.23383/) (2025)
- [ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning](https://mlsanity.com/paper/2503.19470/) (2025)
- [Agentic Reasoning and Tool Integration for LLMs via Reinforcement Learning](https://mlsanity.com/paper/2505.01441/) (2025)
- [Reinforcement Learning for Long-Horizon Interactive LLM Agents](https://mlsanity.com/paper/2502.01600/) (2025)
- [Let's reward step by step: Step-Level reward model as the Navigators for Reasoning](https://mlsanity.com/paper/2310.10080/) (2023)
- [Process Reward Models for LLM Agents: Practical Framework and Directions](https://mlsanity.com/paper/2502.10325/) (2025)
- [Acting Less is Reasoning More! Teaching Model to Act Efficiently](https://mlsanity.com/paper/2504.14870/) (2025)
- [Nemotron-Research-Tool-N1: Exploring Tool-Using Language Models with Reinforced Reasoning](https://mlsanity.com/paper/2505.00024/) (2025)

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

- [A Survey of Reinforcement Learning for Large Reasoning Models](https://mlsanity.com/paper/2509.08827/) (2025)
- [SCOPE: Signal-Calibrated On-Policy Distillation Enhancement with Dual-Path Adaptive Weighting](https://mlsanity.com/paper/2604.10688/) (2026)
- [Skill1: Unified Evolution of Skill-Augmented Agents via Reinforcement Learning](https://mlsanity.com/paper/2605.06130/) (2026)
- [Orak: A Foundational Benchmark for Training and Evaluating LLM Agents on Diverse Video Games](https://mlsanity.com/paper/2506.03610/) (2025)
- [CriticSearch: Fine-Grained Credit Assignment for Search Agents via a Retrospective Critic](https://mlsanity.com/paper/2511.12159/) (2025)
- [From Reasoning to Agentic: Credit Assignment in Reinforcement Learning for Large Language Models](https://mlsanity.com/paper/2604.09459/) (2026)
- [AgentMath: Empowering Mathematical Reasoning for Large Language Models via Tool-Augmented Agent](https://mlsanity.com/paper/2512.20745/) (2025)
- [RetroAgent: From Solving to Evolving via Retrospective Dual Intrinsic Feedback](https://mlsanity.com/paper/2603.08561/) (2026)
- [MARSHAL: Incentivizing Multi-Agent Reasoning via Self-Play with Strategic LLMs](https://mlsanity.com/paper/2510.15414/) (2025)
- [InfoPO: Information-Driven Policy Optimization for User-Centric Agents](https://mlsanity.com/paper/2603.00656/) (2026)
- [Dynamic Skill Lifecycle Management for Agentic Reinforcement Learning](https://mlsanity.com/paper/2605.10923/) (2026)
- [GEAR: Granularity-Adaptive Advantage Reweighting for LLM Agents via Self-Distillation](https://mlsanity.com/paper/2605.11853/) (2026)
- [UCOB: Learning to Utilize and Evolve Agentic Skills via Credit-Aware On-Policy Bidirectional Self-Distillation](https://mlsanity.com/paper/2606.29502/) (2026)
- [Unlocking the Power of Multi-Agent LLM for Reasoning: From Lazy Agents to Deliberation](https://mlsanity.com/paper/2511.02303/) (2025)
- [MTIR-SQL: Multi-turn Tool-Integrated Reasoning Reinforcement Learning for Text-to-SQL](https://mlsanity.com/paper/2510.25510/) (2025)
- [Beyond High-Entropy Exploration: Correctness-Aware Low-Entropy Segment-Based Advantage Shaping for Reasoning LLMs](https://mlsanity.com/paper/2512.00908/) (2025)
- [Exact Is Easier: Credit Assignment for Cooperative LLM Agents](https://mlsanity.com/paper/2603.06859/) (2026)
- [Enhancing LLM-based Search Agents via Contribution Weighted Group Relative Policy Optimization](https://mlsanity.com/paper/2604.14267/) (2026)
- [GAGPO: Generalized Advantage Grouped Policy Optimization](https://mlsanity.com/paper/2605.13217/) (2026)
- [Skill0.5: Joint Skill Internalization and Utilization for Out-of-Distribution Generalization in Agentic Reinforcement Learning](https://mlsanity.com/paper/2605.28424/) (2026)
- [Beyond Pipelines: A Survey of the Paradigm Shift toward Model-Native Agentic AI](https://mlsanity.com/paper/2510.16720/) (2025)
- [VIDEOP2R: Video Understanding from Perception to Reasoning](https://mlsanity.com/paper/2511.11113/) (2025)
- [CAPO: Critic-Guided Action-Aligned Policy Optimization for Advancing LLM Agent Capabilities](https://mlsanity.com/paper/2604.18401/) (2026)
- [TSR: Trajectory-Search Rollouts for Multi-Turn RL of LLM Agents](https://mlsanity.com/paper/2602.11767/) (2026)
- [Not All Tokens See Equally: Perception-Grounded Policy Optimization for Large Vision-Language Models](https://mlsanity.com/paper/2604.01840/) (2026)
- [BiPACE: Bisimulation-Guided Policy Optimization with Action Counterfactual Estimation for LLM Agents](https://mlsanity.com/paper/2606.25556/) (2026)
- [SeeUPO: Sequence-Level Agentic-RL with Convergence Guarantees](https://mlsanity.com/paper/2602.06554/) (2026)
- [PBSD: Privileged Bayesian Self-Distillation for Long-Horizon Credit Assignment](https://mlsanity.com/paper/2606.09348/) (2026)
- [Can GRPO Help LLMs Transcend Their Pretraining Origin?](https://mlsanity.com/paper/2510.15990/) (2025)
- [TSPO: Breaking the Double Homogenization Dilemma in Multi-turn Search Policy Optimization](https://mlsanity.com/paper/2601.22776/) (2026)

## Abstract (arXiv)

Reinforcement Learning (RL) approaches have been wildly used to enhance the reasoning capabilities of Large Language Model (LLM) agents in long-horizon, multi-turn scenarios. Such interactions can be formalized as turn-level Markov decision processes (MDPs), where intermediate rewards are often available. However, most prior work relies on sparse trajectory-level rewards, resulting in poor credit assignment, while dense turn-level rewards remain underexplored. In this paper, we investigate how to effectively leverage dense turn-level reward structures in RL algorithms, specifically Group Relative Policy Optimization (GRPO) and Proximal Policy Optimization (PPO), to enable fine-grained credit assignment. We categorize reward structures into three types based on their granularity: (1) terminal reward; (2) delayed reward; (3) per-turn reward, each corresponding to a distinct turn-level MDP formulation, and derive GRPO and PPO algorithms tailored to each case, respectively. Experiments on multi-turn search and game agent tasks show that, for both GRPO and PPO, dense per-turn reward structures consistently outperform sparse terminal and delayed reward structures in terms of training dynamics and numerical results. Furthermore, on search tasks, PPO with dense per-turn rewards achieves greater training stability and faster convergence, and delivers the highest answer correctness among all state-of-the-art methods across diverse question-answering datasets.