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

Huan Zhang; Mingju Chen; Dongxu Zhou; Can Lv; Heng Chang; Sen Cui; Faguo Wu; Shiji Zhou

cs.AIAug 17, 2026

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)

Abstract

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.

Closed-Source Model
Type	Method	ALFWorld						WebShop
Type	Method	Clean	Pick	Cool	Heat	Pick2	All	Score	Succ.
Prompting	GPT-4o	31.2	75.3	21.6	56.7	49.8	48.0	31.8	23.7
Prompting	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 .

Base Model: Qwen2.5-3B-Instruct
Type	Method	Single-Hop QA			Multi-Hop QA				Avg.
Type	Method	NQ $\dagger$	TriviaQA $\star$	PopQA $\star$	HotpotQA $\dagger$	2Wiki $\star$	MuSiQue $\star$	Bamboogle $\star$	Avg.
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.

\dagger

and

\star

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 (

r^{\mathrm{F}}

) or Breakthrough Rubric Reward (

r^{\mathrm{B}}

) 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 $\lambda$ 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\in\{\textsc{ALFWorld},\textsc{WebShop},\textsc{SearchQA}\}$ .
$\mathcal{T}_{b}$	The benchmark-level operator library shared across all task instances of benchmark $b$ , consisting of Evidence, Invalidity, and Execution operators.
$h_{b,m}^{c}$	The $m$ -th deterministic Boolean operator in category $c$ of library $\mathcal{T}_{b}$ .
$\xi_{i,t}$	The action-induced transition $\xi_{i,t}=(s_{i,t},a_{i,t},s_{i,t+1})$ at interaction step $t$ of rollout $i$ .
$\omega_{b,m}(x)$	The task-conditioned parameters deterministically bound to operator $h_{b,m}^{c}$ , 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.	$\mathcal{O}_{1,e_{\mathrm{loc}}}=1$ .	$r^{\mathrm{F}}_{1}=r^{\mathrm{Evi}}/M_{\mathrm{Evi}}$ . Coverage changes from $0$ to $1$ for $e_{\mathrm{loc}}$ , so $r^{\mathrm{B}}_{1}=r^{\mathrm{Evi}}/M_{\mathrm{Evi}}$ .
2	The agent takes the apple.	$\mathcal{O}_{2,u_{\mathrm{take}}}=1$ .	$r^{\mathrm{F}}_{2}=r^{\mathrm{Exec}}/M_{\mathrm{Exec}}$ . The item $u_{\mathrm{take}}$ is newly covered, so $r^{\mathrm{B}}_{2}=r^{\mathrm{Exec}}/M_{\mathrm{Exec}}$ .
3	The agent repeats an observation that supports $e_{\mathrm{loc}}$ .	$\mathcal{O}_{3,e_{\mathrm{loc}}}=1$ .	$r^{\mathrm{F}}_{3}=r^{\mathrm{Evi}}/M_{\mathrm{Evi}}$ . Since $C_{2,e_{\mathrm{loc}}}=1$ , the repeated item gives $r^{\mathrm{B}}_{3}=0$ .
4	The environment rejects a malformed command.	$\mathcal{O}_{4,v_{\mathrm{bad}}}=1$ .	$r^{\mathrm{F}}_{4}=-\|r^{\mathrm{Inval}}\|/M_{\mathrm{Inval}}$ . Invalidity is excluded from $\Phi$ , so $r^{\mathrm{B}}_{4}=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\times 10^{-7}$
Rollout group size $N$	8
PPO mini-batch size	256
PPO micro-batch size per GPU	32
Discount factor $\gamma$	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.
WebShop	Page type, product identity, selected options, product attributes, and navigation stage.
SearchQA	Tool type, retrieval stage, query state, evidence stage, and answer-submission stage.

Appendix

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.

Step-Level Credit Assignment in RL

Step-level credit assignment in reinforcement learning links delayed rewards to the actions or reasoning steps that produced them.

See all 165 papers

TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents
Jul 15, 2026Leitian Tao, Baolin Peng, Wenlin Yao +5Credit Assignment in RL Step-Level Credit Assignment in RL
University of Wisconsin–Madison · Microsoft Research
ARCO: Adaptive Rubric with Co-Evolution for Multi-Step LLM-Based Agents
Jun 19, 2026Zihang Tian, Jingsen Zhang, Rui Li +3Process Reward Models Credit Assignment in RL
Renmin University of China
Hindsight Credit Assignment for Long-Horizon LLM Agents
Mar 7, 2026Hui-Ze Tan, Xiao-Wen Yang, Hao Chen +7Credit Assignment in RL Long-Horizon LLM Agents
State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · FiT, Tencent, Shenzhen, China +2

Jul 15, 2026J/K move · Enter open · S save

TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents

Leitian Tao, Baolin Peng, Wenlin Yao, Tao Ge+4

University of Wisconsin–Madison · Microsoft Research

Credit Assignment in RL Step-Level Credit Assignment in RL Dense Reward RL Temporal-Difference Learning Step-Level Credit Assignment RL Post-Training+1

Open paper AskPDF arXiv

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

35.6

and Qwen3-30B-A3B from

8.4

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.

Abstract

Step-Level Credit Assignment in RL

Explore similar work

TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents

ARCO: Adaptive Rubric with Co-Evolution for Multi-Step LLM-Based Agents

Hindsight Credit Assignment for Long-Horizon LLM Agents