Technical Summary: TCPO (Turn-Level Credit Policy Optimization)

Problem Statement

In verifier-guided multi-turn reinforcement learning (RL), Large Language Models (LLMs) iteratively refine outputs based on verifier scores received after each turn. While this setting provides dense feedback compared to outcome-only supervision, a fundamental mismatch exists between verifier scores and turn-level credit.

A verifier score measures the absolute quality of the current output, whereas turn-level credit must measure the marginal contribution of that specific turn to the overall refinement trajectory. Existing approaches fail to address this "score-to-credit conversion" problem effectively:

• Trajectory-level methods broadcast final success to all tokens, conflating useful repairs with failed attempts or post-success regressions.
• Raw turn scores reward state quality rather than marginal improvement.
• Adjacent score differences capture local changes but cannot distinguish between a turn that improves upon the best-so-far state versus a non-improving turn that enables future success.

The core challenge is not obtaining per-turn signals, but converting existing verifier scores into optimizable, turn-level credit that accurately reflects immediate progress, preservation of solved states, and delayed contributions.

Methodology: TCPO

TCPO (Turn-Level Credit Policy Optimization) is a credit-assignment method designed for verifier-guided multi-turn RL. It operates without additional human labels or learned critics, leaving the base multi-turn rollout unchanged. Instead, it converts verifier traces into turn-level advantages through three reference-based comparisons:

1. Retrospective Credit

This component compares the current turn's score against the best score achieved prior to that turn ($m_{i,k} = \max_{t<k} r_{i,t}$). It decomposes credit into three signals:

• Improvement: Rewards turns that exceed the historical best ($\Delta_{i,k} > 0$).
• Preservation: Rewards turns that maintain a successful state without further improvement (active when the trajectory is already successful and the score remains stable).
• Regression Penalty: Penalizes turns that lower the verifier score after a successful state has been reached.

2. Hindsight Delayed Credit

This addresses pre-success non-improving turns (where the current score does not exceed the historical best). These turns may be essential for enabling future repairs.

• TCPO identifies eligible non-improving turns and compares their realized future-best score ($u_{i,k} = \max_{t \ge k} r_{i,t}$) against the average future-best score of other eligible trajectories with the same prompt and turn index.
• This provides a delayed signal indicating whether a non-improving turn led to better or worse future outcomes compared to peers.

3. Fixed-History Counterfactual Estimation

To resolve ambiguity in high-surprisal, non-improving turns where hindsight estimates might be noisy, TCPO employs a budgeted counterfactual approach:

• Selection: Turns with high surprisal (uncertainty) are selected for refinement.
• Estimation: The history up to the current turn is fixed, and $M$ alternative outputs are sampled. These alternatives are scored by the verifier.
• Credit Assignment: The credit is the difference between the original output's score and the average score of the alternatives. This isolates the effect of the current output choice without mixing in later revisions.
• Integration: This counterfactual signal refines the hindsight estimate only when the alternatives reveal score variation, acting as a local refinement rather than a standalone oracle.

Optimization

The resulting raw turn signal combines retrospective and delayed credits. It is normalized within prompt-turn groups and weighted by an early-turn prior ($\gamma^{k-1}$) to encourage useful repairs earlier in the trajectory. These turn-level advantages are broadcast to all tokens in the corresponding response and optimized using a GRPO-style clipped objective.

Key Contributions

1. Problem Formulation: The paper explicitly formulates score-to-credit conversion as the central challenge in verifier-guided multi-turn RL, distinguishing between output quality and marginal contribution.
2. TCPO Algorithm: The introduction of a credit-assignment method that constructs turn-level advantages using:
   • Retrospective references for immediate progress and state preservation.
   • Hindsight references for delayed contributions of non-improving turns.
   • Fixed-history counterfactual references for refining high-surprisal turns.
3. Empirical Validation: Validation across mathematical reasoning, code generation, and interactive agent tasks (AppWorld) demonstrating that TCPO improves or matches strong baselines with modest additional training cost.

Experimental Results

Experiments were conducted on Qwen3-4B and DeepSeek-R1-Distill-Llama-8B across math (MATH-500, AIME), code (LiveCodeBench, HumanEval), and agent (AppWorld) tasks.

• Performance: TCPO achieves the best or tied-best best-turn Pass@8 across all benchmarks and model scales.
  • On Qwen3-4B, TCPO improves over MT-GRPO by +4.4 (MATH-500), +2.2 (AIME), +1.6 (LiveCodeBench), and +0.6 (HumanEval) points.
  • On DeepSeek-R1-Distill-Llama-8B, gains are even larger, outperforming MT-GRPO by +6.2 to +1.2 points across tasks.
• Efficiency: TCPO generally reduces the average turns to success, indicating more efficient refinement trajectories.
• Agent Tasks: On AppWorld, TCPO improves Task-Level Goal Completion (TGC) and Scenario-Level Goal Completion (SGC), demonstrating transferability to stateful, tool-using agents.
• Ablation Studies:
  • Removing any of the three credit components (Retrospective, Hindsight, Counterfactual) results in performance degradation, confirming that the combination is necessary.
  • Counterfactual Budgeting: Selecting high-surprisal turns for counterfactual estimation (Top-L) yields significant gains (e.g., +1.8 on MATH-500) with only a 1.03x–1.05x increase in training overhead, whereas random selection provides negligible benefit.

Significance and Claims

The paper claims that score-to-credit conversion is a central ingredient for verifier-guided multi-turn policy optimization. The significance of TCPO lies in its ability to:

• Decouple the quality of an output from its contribution to the solution path.
• Distinguish between useful repairs, state preservation, and harmful regressions without requiring learned value models or additional human annotations.
• Provide a computationally efficient mechanism (via selective counterfactuals) to resolve credit ambiguity in complex, multi-turn reasoning chains.

The authors conclude that while denser verifier scores are available, their utility is unlocked only when converted into appropriate turn-level credit through retrospective, hindsight, and counterfactual references. TCPO demonstrates that this conversion leads to robust improvements in success rates and efficiency across diverse domains.