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

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

Source-linked AI summary

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

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

arXiv:2505.11821v3May 17, 2025cs.LG

TL;DR

Long-horizon LLM agents often receive sparse or aggregated trajectory-level rewards, making credit assignment across interaction turns difficult. This paper formulates terminal, delayed, and per-turn reward structures for GRPO and PPO and evaluates them on multi-turn search and game-agent tasks. Dense per-turn rewards consistently outperform sparse alternatives, with PPO achieving more stable training, faster convergence, and the highest answer correctness across the reported search benchmarks.

Problem
Prior multi-turn RL methods often use sparse trajectory-level rewards or aggregate intermediate and outcome rewards, limiting fine-grained credit assignment.
Method
The paper models interactions as turn-level MDPs, categorizes terminal, delayed, and per-turn rewards, and derives GRPO and PPO formulations for each case.
Results
Dense per-turn rewards consistently outperform terminal and delayed rewards for GRPO and PPO, while PPO with dense per-turn rewards achieves more stable training, faster convergence, and the highest search answer correctness.
Takeaways & Limitations
Dense per-turn reward structures support more effective fine-grained credit assignment and superior overall performance in the evaluated multi-turn agent tasks.
Takeaways & Limitations
The per-turn rollout variant can require GK−1 rollout trajectories over K turns and assumes equal turn counts across group samples, limiting scalability and flexibility.

Abstract

from arXiv · show

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.

1. Introduction

Multi-turn LLM agents face credit-assignment challenges because prior approaches often use sparse trajectory-level rewards or merge intermediate signals into one training signal. This paper studies dense turn-level rewards in GRPO and PPO, proposing reward-granularity-specific formulations and reporting stronger results for per-turn rewards.

Motivation: Sparse trajectory-level rewards provide poor credit assignment, while dense turn-level rewards remain underexplored.Prior work often treats the entire trajectory as one decision or aggregates intermediate and outcome rewards, limiting fine-grained supervision.
Approach: The paper categorizes terminal, delayed, and per-turn rewards and derives GRPO and PPO algorithms for each turn-level MDP formulation.The three structures differ in reward granularity and distribution across interaction turns.
Approach: GRPO uses per-turn rollouts to assign credit at both global and local scales by aggregating current and future advantages.This variant is designed to provide finer supervision than trajectory-level advantage assignment.
Results: Dense per-turn rewards consistently outperform sparse terminal and delayed rewards in GRPO experiments on training dynamics and final numerical performance.The comparison spans three GRPO-based algorithms aligned with the three MDP formulations.
Results: PPO with dense per-turn rewards shows greater training stability and faster convergence, and achieves the highest answer correctness across diverse question-answering datasets.The reported PPO experiments cover multi-turn search and game-agent tasks, including in-domain and out-of-domain search settings.

2. Related Work

Related work applies RL to long-horizon LLM agents across search, tool use, games, shopping, digital applications, and mobile control. These methods commonly use terminal rewards or collapse intermediate and outcome signals into trajectory-level rewards, limiting fine-grained credit assignment.

Process rewards: Process rewards are studied in classical RL and as process reward models for inference-time scaling in LLMs.The related work connects dense rewards with credit assignment and optimization stability across these settings.
Application domains: RL has been applied to LLM agents in search, tool use, text-based games, web shopping, digital applications, and mobile device control.The surveyed approaches include GRPO and PPO for tool-using agents such as calculators, code interpreters, and search engines.
Reward design: Many existing methods use terminal rewards or collapse outcome and intermediate signals into a single trajectory-level reward.This reward design is identified as a limitation for fine-grained supervision in multi-turn settings.

3. Problem Setup for Multi-Turn Tasks

The paper models multi-turn agent interaction as a turn-level MDP in which generated responses and environment feedback form sequential actions and transitions. It distinguishes terminal, delayed, and explicit per-turn reward assignments, then studies their use in RL algorithms.

Multi-Turn Rollout: A multi-turn rollout is a sequence y = [l1, f1, . . . , lK, fK] of LLM responses and corresponding environment feedback.The response lk is generated by the policy, while fk is feedback from the environment at turn k.
Turn-Level MDP: The turn-level MDP comprises states, actions, transition dynamics, a turn-level reward function, and a discount factor.States represent interaction histories, actions are generated token sequences with available feedback, and each turn produces a reward before transitioning.
Reward Structures: Terminal reward M1 provides only a final outcome reward, delayed reward M2 merges intermediate and outcome rewards, and per-turn reward M3 assigns explicit rewards at each turn.M1 and M2 are trajectory-level reward formulations, whereas M3 provides explicit turn-level rewards.
Reward Structures: M2 and M3 are return-equivalent, but they distribute intermediate rewards differently across turns.M1 reduces the objective to maximizing the final outcome reward.
RL Formulations: The paper investigates GRPO and PPO under the three MDP formulations to enable fine-grained credit assignment.Table 1 summarizes the RL algorithms considered across these reward structures.

4. Credit Assignment for GRPO-Type Algorithms in Multi-Turn Tasks

The paper contrasts trajectory-level and per-turn credit assignment for GRPO in multi-turn tasks. MT-GRPO uses per-turn rollouts and unified global-local advantages, improving training stability and validation performance but with exponential rollout cost.

GRPO limitations: Trajectory-level GRPO assigns the same advantage across an entire trajectory, limiting credit assignment among turns and tokens.This coarse assignment can produce unstable training and suboptimal performance in long-horizon tasks.
Fine-grained credit assignment: MT-GRPO combines outcome and intermediate advantages to assign credit at both global and local scales.The aggregated advantage incorporates current and future advantages, with α controlling their relative weighting, and is assigned to tokens within each turn.
Rollout structures: GRPO-OR and GRPO-MR use per-trajectory chain rollouts, whereas MT-GRPO uses per-state tree rollouts.The corresponding computational complexity scales linearly with turns for GRPO and exponentially for MT-GRPO.
Rollout structures: MT-GRPO requires G rollout samples at each nonfinal turn, producing GK−1 trajectories and imposing equal-turn groups.These requirements make the approach computationally prohibitive for long horizons and restrict it to fixed-turn settings.
Experiments: MT-GRPO achieves more stable tool usage, 100% tool-execution success, and higher exact-match accuracy in training curves.Its training variance is lower than GRPO-OR and GRPO-MR, although tool execution temporarily drops around steps 230–250 before recovering.
Experiments: +0.1664 exact-match margin: MT-GRPO improves over GRPO-MR, whose final-search-answer and exact-match scores are 0.3724 and 0.3346.MT-GRPO achieves the highest performance across all validation reward metrics, while GRPO-OR scores 0 in intermediate rewards and 0.04 in XML format.

5. Credit Assignment for PPO-Type Algorithms in Multi-Turn Tasks

The paper adapts PPO to three turn-level reward formulations and uses GAE to assign rewards either terminally, after merging signals, or at each turn. It also compares trajectory-based and turn-decomposed training for credit assignment.

Reward assignment: PPO incorporates turn-level rewards through GAE under three MDP formulations: terminal, merged delayed, and explicit per-turn assignment.In the per-turn formulation, intermediate rewards are assigned to the final token of their corresponding turns.
Reward assignment: MT-PPO uses explicit per-turn rewards, while PPO-OR and PPO-MR assign rewards only at the trajectory endpoint.The three variants correspond respectively to outcome, merged, and per-turn reward structures.
Turn-decomposed training: Turn-decomposed PPO splits each multi-turn rollout into independent single-turn instances and applies PPO using the reward assigned to each instance.The assigned reward may derive from terminal, delayed, or explicit per-turn structures.
Experimental comparison: The experiments compare trajectory-based PPO with turn-decomposed PPO and test how reward structure affects learning effectiveness and credit assignment.This comparison covers both training organization and reward granularity.

6. Experiments on Multi-Turn Search Agents

Experiments evaluate PPO variants and related methods on multi-turn search across general and multi-hop question-answering datasets. MT-PPO provides more stable, faster training and higher answer correctness than sparse-reward PPO variants, while naïve turn decomposition underperforms.

Experimental setup: The search experiments use Search-R1 with datasets spanning general question answering and multi-hop question answering.The datasets include NQ, TriviaQA, PopQA, HotpotQA, 2WikiMultiHopQA, Musique, and Bamboogle.
Training dynamics: MT-PPO converges faster during the first 100 steps and maintains more stable improvement than PPO-OR and PPO-MR.The sparse-reward variants show high variance and performance degradation, especially on HotpotQA.
Benchmark performance: MT-PPO consistently outperforms PPO-OR and PPO-MR in answer correctness across all datasets.It improves exact-match accuracy by approximately 3.5% over PPO-OR and 4.2% over PPO-MR on average.
Training comparison: Turn-decomposed PPO underperforms standard trajectory-based PPO despite often achieving high intermediate rewards.This pattern suggests local turn-level optimization can become misaligned with final outcome rewards.
Comparison with concurrent work: MT-PPO with judge-based turn-level rewards achieves higher answer correctness than concurrent MT-PPO approaches such as PPR and StepSearch.The benchmark also reports near-perfect format correctness across datasets.

7. Experiments on Multi-Turn Game Agents

The game-agent study evaluates reward structures in Sokoban, where actions are irreversible and success depends on sequential interaction. MT-PPO achieves higher success and effective action rates than the PPO and GRPO baselines.

Environment and setup: Sokoban requires placing boxes on targets in a discrete 6 × 6 grid, with irreversible pushes making wrong moves potentially unrecoverable.Episodes allow up to 100 steps, three actions per turn, and three turns.
Reward design: The game-agent reward design combines a success reward, box-placement rewards, format rewards, and a stepwise failure penalty.The success reward is 10, each target placement gives 1, format correctness gives 0.5, and incomplete steps incur −0.1.
Training results: MT-PPO maintains a higher success rate and substantially higher effective action rate throughout Sokoban training.The effective action rate measures the proportion of actions producing valid box movement.
Training results: MT-PPO outperforms all PPO and GRPO baselines on both success rate and effective action rate.The results extend the reported benefits of explicit turn-level rewards beyond language-based search tasks.

8. Conclusion

The paper evaluates PPO and GRPO variants under terminal, delayed, and per-turn reward formulations, alongside reward definitions and experimental settings. The supplied conclusion passage states that dense per-turn rewards outperform sparse alternatives in training dynamics and overall performance.

The study compares PPO and GRPO methods trained with terminal, delayed, and per-turn reward structures.
Dense per-turn rewards consistently outperform sparse terminal and delayed rewards, producing more stable training dynamics and superior overall performance.
PPO-OR uses only binary outcome rewards, whereas PPO-MR merges intermediate and outcome rewards into a trajectory-level signal.
MT-PPO uses intermediate and outcome rewards as turn-level rewards under the turn-level-reward MDP M3.
GRPO-OR and GRPO-MR analogously represent terminal-reward and delayed-reward MDPs, respectively.
Rewards evaluate answer correctness, format correctness, and retrieval correctness, with each criterion assigned 1.0 when satisfied and 0 otherwise.

A.3. Additional Experiment Results (PPO)

The PPO experiments compare training and validation reward curves for PPO-OR, PPO-MR, and MT-PPO on NQ and HotpotQA. Curves report correctness-related rewards across five independent runs, with means and variability shown.

Figures 6 and 7 compare PPO-OR, PPO-MR, and MT-PPO on NQ and HotpotQA.
The plotted rewards include answer correctness, format correctness, and retrieval correctness.
Solid lines show mean reward values, while shaded regions indicate variability across five independent runs.

A.4. Ablation Study (PPO)

The PPO ablations examine search-count rewards and maximum turn limits, showing that moderate search penalties improve stability and correctness while MT-PPO remains robust across tested turn budgets.

λs = 0.1 achieves the highest and most consistent accuracy, whereas λs = 0.3 degrades performance.
λs = 0.1 helps the agent reduce unnecessary search calls early and stabilize around an efficient number of turns.
λs = 0.0 produces excessive or erratic turn usage that harms convergence.
Figure 8 reports answer correctness, average turns, and accuracy under different Nmax settings.
Adjusting Nmax from 4 to 6 yields nearly identical accuracy curves, indicating robustness across these turn limits.
Figure 9 compares full-trajectory training with turn-decomposed training, where each turn becomes an instance conditioned on dialogue history.

B. PPO Experiments on Game Agents

The game-agent experiments evaluate RL algorithms on Sokoban while describing a multi-turn tool-use pipeline and verifiable intermediate and outcome rewards. The reward design separates first-turn tool performance from final-answer quality.

Table 6 reports final test performance for different RL algorithms on Sokoban at step 300.
The agent pipeline involves reasoning, tool use, and answer summarization across multiple interaction steps.
The game-agent evaluation uses short-answer tasks scored by exact match with ground-truth answers.
Intermediate rewards evaluate first-turn tool execution and search-result answer presence, while outcome rewards evaluate final answer correctness and formatting.
The XML format reward checks the expected reasoning-tool-or-answer structure and related field, spacing, start, and end conditions.
Intermediate rewards assess only the first turn, whereas outcome rewards assess the quality of the entire trajectory.

C.3. Experiment Setup (GRPO)

The experiments use an open-source multi-turn tool-use training codebase, with GRPO training conducted on eight H100 GPUs under fixed generation and optimization settings. Training curves track intermediate and outcome reward components across GRPO variants and repeated runs.

Experiment platform: The codebase trains LLM agents for multi-turn tool-use tasks involving math calculators, code interpreters, and search engines.
Hardware and software: Training uses one H100 GPU for rollout generation and seven H100 GPUs for model training, with vLLM handling rollouts and Huggingface TRL implementing GRPO.
Hyperparameters: All methods use 21 rollout generations, 1024-token maximum completions, β = 0, a 1 × 10^-6 learning rate, batch size 12, four accumulation steps, two iterations per batch, and 300 training steps.
Training diagnostics: Figure 11 tracks intermediate and outcome reward components for MT-GRPO, GRPO-OR, and GRPO-MR using averages across 10 runs and EMA-smoothed trends.
Training diagnostics: Figures 12–14 show reward-component curves for GRPO-OR, GRPO-MR, and MT-GRPO, with shaded regions spanning the maximum-to-minimum range across 10 runs.