Technical Summary: TRCA - Transition-wise Rubric Credit Assignment for Long-horizon LLM Agents

1. Problem Statement

Long-horizon Large Language Model (LLM) agents are typically optimized using sparse terminal rewards (e.g., success/failure at the end of a trajectory). This approach provides only coarse-grained credit assignment, making it difficult to distinguish beneficial intermediate steps from harmful or redundant ones.

Existing solutions face significant limitations:

• Process Reward Models (PRMs): While effective, they require extensive human annotation or substantial inference costs from large judge models.
• Anchor-based Methods: These derive step-level credit from successful trajectories. However, in early-stage reinforcement learning (RL), successful trajectories are extremely scarce (often <5% of rollouts). Consequently, methods relying on "success anchors" fail to provide reliable supervision during the critical exploration phase.

The authors identify a success-scarce credit assignment problem: In early training, failed rollouts dominate, yet analysis shows that over 72% of actions in these failed trajectories still contain diagnostically useful transition signals (e.g., valid execution or partial progress) that are currently discarded.

2. Methodology: Transition-wise Rubric Credit Assignment (TRCA)

TRCA is a framework designed to assign fine-grained, step-level credit directly from action-induced transitions without relying on successful anchors or learned process evaluators. It operates by evaluating state transitions using three specific rubrics:

2.1 Rubric Definitions

For any transition $\xi_t = (s_t, a_t, s_{t+1})$, TRCA evaluates:

1. Evidence: Captures newly revealed task-relevant information (e.g., observing a target entity, revealing an attribute). This provides positive credit for information acquisition.
2. Execution: Recognizes completed task-required operations or intermediate conditions (e.g., performing a subgoal operation). This provides positive credit for substantive task execution.
3. Invalidity: Identifies malformed, inadmissible, or unexecutable actions (e.g., illegal actions, format errors). This provides negative credit.

These rubrics are instantiated offline for each task type using an LLM, requiring no additional judge models during policy optimization.

2.2 Reward Construction

TRCA aggregates these judgments into two complementary reward signals:

• Foundational Rubric Reward ($r^F$):
  Maps each judged rubric item to a signed contribution (positive for Evidence/Execution, negative for Invalidity). These are aggregated per step to provide broad, signed supervision. This rewards the immediate quality of a transition regardless of whether it is a "first time" occurrence.
  $$r^F_{i,t} = \sum_{j \in \mathcal{R}(x)} q^i_{t,j}$$

• Breakthrough Rubric Reward ($r^B$):
  Addresses the issue of repeatedly rewarding the same condition. It tracks the cumulative coverage of positive Evidence and Execution conditions. It assigns credit only when a rubric condition is satisfied for the first time in a trajectory (i.e., a "breakthrough").
  $$r^B_{i,t} = \Phi_{i,t} - \Phi_{i,t-1}$$
  Where $\Phi$ is the cumulative potential of covered positive rubrics.

The final TRCA reward is a weighted combination:
$$r^{TRCA}_{i,t} = (1 - \lambda) \cdot r^F_{i,t} + \lambda \cdot r^B_{i,t}$$

2.3 Policy Optimization

TRCA combines these step-level rewards with the sparse terminal environment reward to compute a "completion-aware return." It then calculates:

1. Episode-Relative Advantage ($A_E$): Comparing the total return of a trajectory against others in the same group.
2. Step-Relative Advantage ($A_S$): Normalizing the completion-aware return within groups of semantically similar decision contexts.

The final advantage signal $A^{TRCA} = A_E + A_S$ is used to optimize the policy via a PPO-style clipped objective.

3. Key Contributions

1. Problem Identification: The authors quantify the severity of the success-scarce regime in long-horizon agent training, demonstrating that failed rollouts dominate early training but retain valuable transition signals.
2. TRCA Framework: A novel step-level credit assignment method that derives supervision from environmental transitions using Evidence, Execution, and Invalidity rubrics. It eliminates the need for successful anchors or external process evaluators.
3. Dual Reward Mechanism: The introduction of Foundational Rubric Reward (broad supervision) and Breakthrough Rubric Reward (highlighting new progress) to balance immediate step quality with cumulative task progress.
4. Empirical Validation: Extensive experiments showing consistent improvements across diverse benchmarks and model scales.

4. Experimental Results

The authors evaluated TRCA on ALFWorld, WebShop, and seven search-augmented QA benchmarks using Qwen2.5 models (1.5B, 3B, and 7B).

• ALFWorld & WebShop:
  • With Qwen2.5-1.5B-Instruct, TRCA achieved a 92.0% success rate on ALFWorld (5.3% improvement over the best baseline, GiGPO) and a 90.5% task score on WebShop (7.4% improvement).
  • With Qwen2.5-7B-Instruct, TRCA reached 94.5% on ALFWorld and 92.9% on WebShop, outperforming GiGPO by 3.7% and 8.5% respectively.
• Search-Augmented QA:
  • On Qwen2.5-3B-Instruct, TRCA achieved an average score of 45.4%, outperforming IGPO (8.2% gain) and GiGPO (3.3% gain). It achieved the best results on all seven individual datasets in this setting.
  • Similar improvements were observed with the 7B model, achieving an average score of 48.4%.
• Learning Dynamics:
  • TRCA demonstrated significantly faster convergence and higher sample efficiency compared to GRPO. For instance, on ALFWorld's pick_two subtask, TRCA reached a 69.2% success rate with 3.84K trajectories, whereas GRPO required 6.40K trajectories to reach only 46.7%.
• Ablation Studies:
  • Removing either the Foundational or Breakthrough reward component consistently degraded performance, confirming their complementary nature. The Breakthrough component was found to be particularly critical for task-critical actions.

5. Significance and Claims

The paper claims that TRCA addresses a fundamental bottleneck in training long-horizon agents: the reliance on rare successful trajectories for supervision. By grounding credit assignment in environment-observed state transitions rather than terminal outcomes, TRCA converts "failed" experience into reliable, fine-grained supervision.

The authors assert that this approach is particularly valuable during the early exploration stage of RL, where successful rollouts are scarce but informative transitions are plentiful. The results suggest that transition-level environmental evidence serves as a general foundation for learning long-horizon behaviors, enabling agents to improve performance, convergence speed, and sample efficiency without the overhead of learned process evaluators or the dependency on successful anchors.