TRCA: Transition-wise Rubric Credit Assignment for Long-horizon LLM Agents
Authors: Huan Zhang, Mingju Chen, Dongxu Zhou, Can Lv, Heng Chang, Sen Cui, Faguo Wu, Shiji Zhou
Organizations: Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, School of Artificial Intelligence, Beihang University · Tsinghua University · Beijing Academy of Artificial Intelligence (BAAI)
Long-horizon large language model (LLM) agents are typically optimized with sparse terminal outcomes, making fine-grained credit assignment across multi-step interactions difficult. Existing approaches either rely on process evaluators, which incur annotation and inference costs, or derive step-level credit from successful trajectories. However, successful trajectories are extremely scarce during early-stage reinforcement learning, substantially weakening anchor-based methods. We propose Transition-wise Rubric Credit Assignment (TRCA), which derives step-level supervision directly from action-induced transitions without learned evaluators or successful anchors. TRCA evaluates each transition using Evidence, Execution, and Invalidity rubrics to capture task-relevant information acquisition, valid task execution, and invalid or regressive behavior. From these judgments, Foundational Rubric Reward measures local transition quality, while Breakthrough Rubric Reward tracks newly covered Evidence and Execution conditions to reward incremental task progress. Combined with terminal outcomes, these signals produce fine-grained step-level advantages for policy optimization. Experiments on ALFWorld, WebShop, and seven search-augmented question-answering benchmarks show consistent improvements over the evaluated baselines. With Qwen2.5-7B-Instruct, TRCA improves the WebShop score by 6.0%-12.6%; with Qwen2.5-3B-Instruct, it improves the average SearchQA score by 1.9%-18.3%. These results demonstrate the effectiveness of transition-wise rubric credit assignment for long-horizon tasks with sparse successful anchors.
Figures & tables
Figure 1: (A) Failed rollouts dominate early training, yet over 70% of their actions retain useful rubric-grounded transition signals. (B) TRCA converts these step-level signals into foundational and breakthrough step credit without relying on successful anchors or external evaluators.
Figure 2: Overview of TRCA. Foundational Rubric Reward converts step-level rubric judgments into step-aligned credit, while breakthrough step rubric reward rewards newly covered task-relevant rubric conditions. The combined TRCA reward augments the original sparse environment reward to construct normalized step advantages, which are fused with the episode-relative trajectory advantage and optimized using the underlying PPO-style clipped objective.
Type
Method
ALFWorld
WebShop
Clean
Pick
Cool
Heat
Pick2
All
Score
Succ.
Closed-Source Model
Prompting
GPT-4o
31.2
75.3
21.6
56.7
49.8
48.0
31.8
23.7
Gemini-2.5-Pro
62.1
92.8
26.6
69.0
58.7
60.3
42.5
35.9
Qwen2.5-1.5B-Instruct
Prompting
Qwen2.5
3.3
5.9
4.2
9.7
0.0
4.1
23.1
5.2
Table 1: Performance on ALFWorld and WebShop. Results are averaged over 3 random seeds. For ALFWorld, we report the average success rate (%) for each subtask as well as the overall result. For WebShop, we report both the average score and the average success rate (%). We compare TRCA with other representative baselines. Best results are bolded .
Type
Method
Single-Hop QA
Multi-Hop QA
Avg.
NQ †
TriviaQA ⋆
PopQA ⋆
HotpotQA †
2Wiki ⋆
MuSiQue ⋆
Bamboogle ⋆
Base Model: Qwen2.5-3B-Instruct
RL Training
R1-Instruct
27.0
53.7
19.9
23.7
29.2
7.2
29.3
27.1
Search-R1
34.1
54.5
37.8
32.4
31.9
10.3
26.4
32.5
ZeroSearch
41.4
57.4
44.8
27.4
30.0
9.8
11.1
31.7
StepSearch
–
–
–
34.5
32.0
17.4
–
34.4
Table 2: Performance on search-augmented QA tasks. † and ⋆ indicate in-domain and out-of-domain datasets, respectively. Bold indicates the best performance in each category.
Figure 3: Training dynamics of TRCA and its ablated variants on ALFWorld, WebShop, and SearchQA. Removing either Foundational Rubric Reward ( rF ) or Breakthrough Rubric Reward ( rB ) consistently degrades performance.
Figure 4: Learning dynamics and sample efficiency of our method with Qwen2.5-1.5B-Instruct. (a) and (b) compare the best success rates achieved by our method and GRPO on the ALFWorld pick_two and pick_cool subtasks.
Figure 5: Performance of TRCA under different settings of hyperparameter λ on ALFWorld success rate (%).
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Definition
x
A concrete task instruction or query.
b
A benchmark-specific interaction type, where b∈{\textscALFWorld,\textscWebShop,\textscSearchQA} .
Tb
The benchmark-level operator library shared across all task instances of benchmark b , consisting of Evidence, Invalidity, and Execution operators.
hb,mc
The m -th deterministic Boolean operator in category c of library Tb .
ξi,t
The action-induced transition ξi,t=(si,t,ai,t,si,t+1) at interaction step t of rollout i .
ωb,m(x)
The task-conditioned parameters deterministically bound to operator hb,mc , such as an entity, attribute, relation, constraint, target condition, or required output format.
Appendix
Table 3: Main notation used in TRCA.
Step
Transition evidence
Triggered judgments
Reward computation
1
The agent inspects a receptacle and observes the apple.
O1,eloc=1 .
r1F=rEvi/MEvi . Coverage changes from 0 to 1 for eloc , so r1B=rEvi/MEvi .
2
The agent takes the apple.
O2,utake=1 .
r2F=rExec/MExec . The item utake is newly covered, so r2B=rExec/MExec .
3
The agent repeats an observation that supports eloc .
O3,eloc=1 .
r3F=rEvi/MEvi . Since C2,eloc=1 , the repeated item gives r3B=0 .
4
The environment rejects a malformed command.
O4,vbad=1 .
r4F=−∣rInval∣/MInval . Invalidity is excluded from Φ , so r4B=0 .
Appendix
Table 4: Symbolic illustration of TRCA reward construction. The example uses symbolic budgets and does not report an experimental trajectory.
Figure 6: Performance profiles of TRCA and representative baselines across model scales. The first two panels summarize ALFWorld subtask success rates and WebShop task score and success rate, while the last two panels summarize performance on seven search-augmented QA benchmarks and their average. Values are scaled to [0,1] for visualization.
Hyperparameter
Value
Learning rate
8×10−7
Rollout group size N
8
PPO mini-batch size
256
PPO micro-batch size per GPU
32
Discount factor γ
0.95
PPO clipping coefficient (lower)
0.20
Appendix
Table 5: Core reinforcement-learning hyperparameters used in the experiments.
Benchmark
Comparable-context information
ALFWorld
Task predicates, object state, inventory, object location, and interaction stage.
Table 6: Observable context information used to define comparable decision contexts.
Figure 7: Sample-efficiency comparison between TRCA and GRPO on ALFWorld and WebShop using Qwen2.5-1.5B-Instruct. TRCA consistently outperforms GRPO across sampled-trajectory budgets, showing stronger sample efficiency under identical interaction and optimization settings.
Figure 8: Training and validation success rates of TRCA on ALFWorld and WebShop.
Figure 9: Training and validation success rates of TRCA and GRPO on WebShop and ALFWorld. TRCA converges faster and achieves stronger performance, on ALFWorld.
Figure 10: Prompt templates used for ALFWorld, WebShop, and search-augmented QA agents.
Figure 17
Figure 11: Prompt used to construct the shared benchmark-level rubric operator library. The generated library defines reusable deterministic operators; task-specific entities and constraints are subsequently bound to these operators without additional LLM generation.
Multi-turn agents solve complex tasks through extended sequences of tool interactions before producing a final answer, making credit assignment a fundamental challenge during post-training. Outcome rewards provide reliable supervision for short-horizon reasoning, but become sparse and high-variance as trajectories grow to tens or hundreds of tool calls. They can also be misleading: a failed rollout may contain many useful actions that move the agent closer to the goal, yet outcome-only training assigns them the same negative advantage as the eventual mistake. We propose TRACE (Turn-level Reward Assignment via Credit Estimation), a dense credit-assignment method for agentic reinforcement learning. TRACE represents rollouts as state transitions at tool-call boundaries, obtains gold-answer log-probabilities from a frozen reference model, transforms them into log-ratio state values, and derives per-action rewards as Temporal-Difference changes in those values. This requires no additional critic or process-label training, and its one-step log-ratio TD component telescopes across redundant tool calls. On long-horizon complex search, TRACE substantially improves base-model tool-use ability using pure RL, without a cold-start supervised fine-tuning stage, an agentic mid-training stage, or training on live-web data. On the closed-web BrowseComp-Plus benchmark, it raises Qwen3-4B from 7.2 to 35.6 and Qwen3-30B-A3B from 8.4 to 42.6. The learned search behavior also transfers to open-web benchmarks, and the learning curves show earlier improvement and faster convergence during RL training.
Leitian Tao, Baolin Peng, Wenlin Yao +5
University of Wisconsin–Madison · Microsoft Research
Reinforcement learning for multi-step LLM agents often relies on scalar rewards that indicate success but cannot explain why a trajectory is good or bad. Rubric-based rewards improve interpretability through natural-language criteria, but existing methods score at the trajectory level and freeze the scorer behind a closed-source judge, leaving step-level credit assignment unresolved and the judge itself static. We propose ARCO (Adaptive Rubric CO-evolution), a rubric framework in which a same-scale model μ shares a backbone with two heads: a generation head that produces per-step criteria, and a score head that predicts rubric-conditioned step-level rewards. A trajectory decomposition constraint ties the sum of step rewards to the terminal outcome, enabling credit assignment without step-level labels, while μ and the policy π are jointly updated on on-policy data so that the rubric content and the scoring function co-evolve at the parameter level. Across HotpotQA, 2WikiMultiHopQA, and MuSiQue with two open-source backbones, ARCO improves the best EM in every setting over strong outcome-, rubric-, and process-reward baselines, and analyses show that its rubrics are step-specific, robust to design choices, and useful for diagnosing agent behavior. Codes and data are available at https://github.com/zihangtian/ARCO.
Large Language Model (LLM) agents often face significant credit assignment challenges in long-horizon, multi-step tasks due to sparse rewards. Existing value-free methods, such as Group Relative Policy Optimization (GRPO), encounter two fundamental bottlenecks: inaccurate step-level Q-value estimation and misaligned value baselines for intermediate states. To address these limitations, we introduce HCAPO, the first framework to integrate hindsight credit assignment into LLM agents. HCAPO leverages the LLM itself as a post-hoc critic to refine step-level Q-values through hindsight reasoning. Furthermore, HCAPO's multi-scale advantage mechanism effectively supplements the inaccurate value baselines at critical decision states. Evaluations across three challenging benchmarks, including WebShop and ALFWorld, demonstrate that HCAPO consistently outperforms state-of-the-art RL methods. Notably, HCAPO achieves a 7.7% improvement in success rate on WebShop and a 13.8% on ALFWorld over GRPO using the Qwen2.5-7B-Instruct model. These results indicate that HCAPO significantly enhances exploration efficiency, promotes concise decision-making, and ensures scalability in complex, long-horizon tasks.
Hui-Ze Tan, Xiao-Wen Yang, Hao Chen +7
State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · FiT, Tencent, Shenzhen, China +2