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

1. Problem Statement

Reinforcement Learning (RL) has become a primary mechanism for enhancing the reasoning capabilities of Large Language Models (LLMs) in complex, long-horizon, multi-turn scenarios. These interactions are formally modeled as turn-level Markov Decision Processes (MDPs). However, a critical limitation in existing literature is the reliance on sparse trajectory-level rewards (e.g., only the correctness of the final answer). This approach leads to poor credit assignment, where the model struggles to attribute success or failure to specific intermediate steps (turns) within a multi-turn trajectory.

While some prior works attempt to incorporate intermediate signals, they often merge outcome and intermediate rewards into a single delayed trajectory-level signal, failing to provide the fine-grained supervision necessary for effective learning in dynamic environments. Consequently, agents struggle to refine behaviors such as query selection in search tasks or strategic moves in games, as they lack dense feedback at the granularity of individual interaction turns.

2. Methodology

The paper proposes a systematic investigation into leveraging dense turn-level reward structures to enable fine-grained credit assignment. The authors categorize reward structures into three distinct types based on granularity, each corresponding to a specific turn-level MDP formulation:

1. Terminal Reward ($M_1$): Provides only a final outcome reward (e.g., answer correctness) with no intermediate signals.
2. Delayed Reward ($M_2$): Merges intermediate and outcome rewards into a single delayed signal assigned at the end of the trajectory.
3. Per-Turn Reward ($M_3$): Provides explicit, dense rewards at each turn, evaluating the correctness of individual agent-environment interactions (e.g., tool invocation and result).

The authors derive tailored RL algorithms for Group Relative Policy Optimization (GRPO) and Proximal Policy Optimization (PPO) to accommodate these different MDP formulations.

2.1. GRPO with Fine-Grained Credit Assignment (MT-GRPO)

Standard GRPO computes advantages at the trajectory level, assigning a uniform advantage to all tokens in a response. To address this, the authors introduce Multi-Turn GRPO (MT-GRPO):

• Advantage Decomposition: The method defines two types of advantages:
  • Outcome Advantage ($A^O$): Captures global task completion signals based on the final answer.
  • Intermediate Advantage ($A^I$): Captures local optimization signals by comparing returns across trajectories at the same timestep (turn).
• Aggregated Advantage: These are combined into a unified advantage function that assigns credit at both global and local scales by aggregating current and future advantages:
  $$A^{MT-GRPO}_{i,(k)} = \sum_{l=k}^{K-1} \alpha^{l-k} A^I_{i,(l)} + \alpha^{K-k} A^O_i$$
  where $\alpha$ is a discount coefficient.
• Rollout Structure: Unlike standard GRPO which performs per-trajectory rollouts, MT-GRPO performs per-state (per-turn) rollouts. This results in a tree-based structure where $G$ samples are taken at each turn, leading to $G^{K-1}$ total trajectories for a horizon of $K$ turns.

2.2. PPO with Turn-Level Rewards (MT-PPO)

For PPO, the authors leverage Generalized Advantage Estimation (GAE) to incorporate turn-level rewards:

• Reward Assignment: In the MT-PPO variant, intermediate rewards are assigned to the final token of the corresponding turn, while the outcome reward is assigned to the final token of the entire trajectory.
• TD Error Modification: The Temporal-Difference (TD) error $\delta_t$ is modified to incorporate explicit per-turn rewards ($R_I$) at turn boundaries, allowing the value function to provide fine-grained training signals at each step.
• Turn-Decomposed PPO: The paper also explores a variant where multi-turn rollouts are decomposed into single-turn training instances. However, experiments suggest this straightforward decomposition can lead to suboptimal credit assignment if not carefully aligned with final task success.

3. Key Contributions

1. Taxonomy of Reward Structures: The paper formally categorizes multi-turn RL into three MDP formulations ($M_1, M_2, M_3$) based on reward granularity and derives specific GRPO and PPO algorithms for each.
2. MT-GRPO Algorithm: A novel GRPO variant that utilizes per-turn rollouts and aggregated advantages to enable credit assignment at both global and local scales.
3. MT-PPO Strategy: A refined reward assignment strategy within GAE for PPO that explicitly utilizes dense per-turn rewards, demonstrating superior stability and convergence compared to trajectory-level baselines.
4. Empirical Validation: Extensive experiments on multi-turn search agents (using Wikipedia search) and game agents (Sokoban) demonstrate that dense per-turn reward structures consistently outperform sparse terminal and delayed reward structures.

4. Experimental Results

The authors evaluated their methods on two primary domains: Multi-Turn Search Agents and Multi-Turn Game Agents.

4.1. Search Agents (Question Answering)

• Datasets: NQ, TriviaQA, PopQA (General QA); HotpotQA, 2WikiMultiHopQA, Musique, Bamboogle (Multi-Hop QA).
• Setup: Used Qwen2.5-7B as the base model and an LLM-based judge (GPT-OSS-120B) to provide intermediate turn-level rewards.
• Findings:
  • Training Dynamics: MT-PPO exhibited significantly greater training stability and faster convergence compared to PPO-OR (terminal only) and PPO-MR (delayed). PPO-OR and PPO-MR showed high variance and performance degradation, particularly on complex multi-hop datasets.
  • Performance: MT-PPO achieved the highest answer correctness (Exact Match) across all datasets, outperforming state-of-the-art methods (including StepSearch and PPR) by significant margins (e.g., +3.5% over PPO-OR on average).
  • Format and Retrieval: MT-PPO achieved near-perfect format correctness (~100%) and more consistent retrieval accuracy, indicating that turn-level rewards effectively enforce structural constraints and guide reasoning.

4.2. Game Agents (Sokoban)

• Setup: Used Qwen2.5-VL-3B on a 6x6 grid Sokoban environment, a task requiring irreversible, long-horizon planning.
• Findings:
  • MT-PPO achieved the highest Success Rate (0.6563) and Effective Action Rate (0.9870) at step 300, significantly outperforming GRPO and PPO baselines.
  • The method demonstrated the ability to learn stable, purposeful action sequences, effectively handling the irreversible nature of the environment where a single wrong move leads to a dead-end.

4.3. GRPO Results

In the two-turn search setting, MT-GRPO outperformed GRPO-OR and GRPO-MR in all reward metrics, including tool execution, search answer correctness, and exact match accuracy. Notably, MT-GRPO showed lower variance during training and the ability to recover from temporary drops in tool usage, highlighting the robustness of fine-grained credit assignment.

5. Significance and Claims

The paper claims that dense turn-level reward structures and fine-grained credit assignment are fundamental to improving the performance of LLM agents in long-horizon, multi-turn tasks.

• Superiority over Sparse Rewards: The authors assert that for both GRPO and PPO, dense per-turn reward structures consistently outperform sparse terminal and delayed reward designs in terms of training dynamics, convergence speed, and final numerical performance.
• Stability and Robustness: The proposed methods (MT-PPO and MT-GRPO) provide greater training stability, reducing the variance and collapse often observed in trajectory-level RL approaches.
• Generalizability: The approach is shown to be effective across diverse domains, from information retrieval (search) to complex decision-making (Sokoban), validating that explicit turn-level feedback is crucial for agents to learn effective interaction strategies with dynamic environments.

The paper concludes that leveraging these dense reward structures allows LLM agents to refine their behavior at the granularity of individual interaction steps, leading to more accurate final outcomes and better-structured outputs.