Reinforcing Multi-Turn Reasoning in LLM Agents via Turn-Level Reward Design
Quan Wei, Siliang Zeng, Chenliang Li, Zhongruo Wang, William Brown, Oana Frunza, Wei Deng, Anderson Schneider, Yuriy Nevmyvaka, Yang Katie Zhao, Alfredo Garcia, Mingyi Hong
cs.LG
Submitted: 2026-08-21
Updated: 2026-08-24
Comments: work in progress
Code: https://github.com/willccbb/verifiers
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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.
Terminology
Abstract
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.
Sources
- Survey: Multi-Armed Bandits Meet Large Language Models
- Reinforcement Learning for Long-Horizon Interactive LLM Agents
- ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning
- Stop Summation: Min-Form Credit Assignment Is All Process Reward Model Needs for Reasoning
- Process Reward Models for LLM Agents: Practical Framework and Directions
- Process Reinforcement through Implicit Rewards
- ReTool: Reinforcement Learning for Strategic Tool Use in LLMs
- Group-in-Group Policy Optimization for LLM Agent Training
- ToRA: A Tool-Integrated Reasoning Agent for Mathematical Problem Solving
- DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Segment Policy Optimization: Effective Segment-Level Credit Assignment in RL for Large Language Models
- Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps
- OpenAI o1 System Card
- An Empirical Study on Reinforcement Learning for Reasoning-Search Interleaved LLM Agents
- Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning
- ToRL: Scaling Tool-Integrated RL
- Generalist Reward Models: Found Inside Large Language Models
- Let's reward step by step: Step-Level reward model as the Navigators for Reasoning
- When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories
- A Survey of Temporal Credit Assignment in Deep Reinforcement Learning
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks