Paper deep dive
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
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/23/2026, 1:30:19 AM
Summary
The paper introduces TRCA (Transition-wise Rubric Credit Assignment), a framework for fine-grained credit assignment in long-horizon LLM agents. TRCA addresses the 'success-scarce' problem in early-stage reinforcement learning by deriving step-level supervision directly from action-induced transitions using Evidence, Execution, and Invalidity rubrics. It generates Foundational Rubric Reward for local transition quality and Breakthrough Rubric Reward for incremental task progress, combining these with terminal outcomes to optimize policies without relying on successful anchors or external process evaluators. Experiments on ALFWorld, WebShop, and SearchQA benchmarks demonstrate consistent improvements over baselines like PPO, GRPO, and RLOO.
Entities (18)
Relation Signals (12)
TRCA → generates → Foundational Rubric Reward
confidence 95% · From these judgments, Foundational Rubric Reward measures local transition quality
TRCA → generates → Breakthrough Rubric Reward
confidence 95% · Breakthrough Rubric Reward tracks newly covered Evidence and Execution conditions to reward incremental task progress.
TRCA → uses → Evidence Rubric
confidence 95% · TRCA evaluates each transition using Evidence, Execution, and Invalidity rubrics
TRCA → uses → Execution Rubric
confidence 95% · TRCA evaluates each transition using Evidence, Execution, and Invalidity rubrics
TRCA → uses → Invalidity Rubric
confidence 95% · TRCA evaluates each transition using Evidence, Execution, and Invalidity rubrics
TRCA → avoids → successful anchors
confidence 90% · TRCA derives step-level supervision directly from action-induced transitions without learned evaluators or successful anchors.
Process Reward Models → hasdrawback → annotation and inference costs
confidence 90% · Existing approaches either rely on process evaluators, which incur annotation and inference costs
TRCA → improves → SearchQA
confidence 90% · with Qwen2.5-3B-Instruct, it improves the average SearchQA score by 1.9%-18.3%.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.16156v1
- Canonical: https://arxiv.org/abs/2608.16156v1
Trouble viewing inline? Open PDF directly →
Full Text
132,968 characters extracted from source content.
Expand or collapse full text
TRCA: Transition-wise Rubric Credit Assignment for Long-horizon LLM Agents Huan Zhang 1 , Mingju Chen 1 , Dongxu Zhou 1 , Can Lv 1 , Heng Chang 2 , Sen Cui 2 , Faguo Wu 1∗ , Shiji Zhou 1,2,3∗ 1 Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, School of Artificial Intelligence, Beihang University, 2 Tsinghua University, 3 Beijing Academy of Artificial Intelligence (BAAI), Project Lead: Heng Chang, Corresponding to: Shiji Zhou <zhoushiji25@buaa.edu.cn> Abstract Long-horizon large language model (LLM) agents are typ- ically optimized with sparse terminal outcomes, providing coarse-grained credit assignment across multi-step interac- tions. Existing approaches either introduce pretrained pro- cess evaluators, incurring substantial annotation and inference costs, or derive step-level credit using successful trajectories as anchors. However, successful trajectories are extremely scarce during early-stage reinforcement learning in our case study, substantially weakening the effectiveness of anchor- based methods. To address this success-scarce credit assign- ment problem, we propose Transition-wise Rubric Credit Assignment (TRCA), which derives step-level supervision directly from action-induced transitions without learned eval- uators or successful anchors. TRCA views interactive progress as requiring two complementary capabilities: acquiring task- relevant evidence from the environment and executing valid actions that meaningfully change it, while suppressing in- valid, redundant, or regressive behavior. It therefore evalu- ates each transition using Evidence, Execution, and Inva- lidity rubrics. From the same rubric judgments, Founda- tional Rubric Reward aggregates signed scores across the three categories to assess local transition quality, whereas Breakthrough Rubric Reward tracks the cumulative cover- age of positive Evidence and Execution conditions to re- ward newly established task progress. Together with terminal outcomes, these signals distinguish local step quality, incre- mental progress, and final task completion, producing fine- grained step-level advantages for policy optimization. Experi- ments on ALFWorld, WebShop, and seven search-augmented question-answering benchmarks show that TRCA consistently improves performance over the evaluated baselines. With Qwen2.5-7B-Instruct, TRCA improves the WebShop score by 6.0%–12.6% over competing baselines; with Qwen2.5-3B- Instruct, it improves the average SearchQA score by 1.9%– 18.3%. These results support the effectiveness of transition- wise rubric credit assignment for long-horizon interactive tasks in which successful anchors are scarce or absent. 1 Introduction As large language model (LLM) agents become more capa- ble, their applications are expanding from single-response generation to long-horizon interaction, including embodied planning (Shridhar et al. 2021), web navigation (Yao et al. 2022), search-augmented reasoning, and multi-turn plan- ning (Xie et al. 2024; Shao et al. 2026). However, when ∗ Corresponding author. Copyright © 2027, Association for the Advancement of Artificial Intelligence (w.aaai.org). All rights reserved. (A) Failed Rollouts Retain Abundant Transition Signals 100% 75% 50% 25% 0% S a m p l e d s t e p r a t i o ( % ) Early failed rollouts in training Failed rollouts >95% Others <10% Useful progress > 70% Others <30% Rubric-Step matched (%) 18% 31% 27% 24% Evidence Execution Validity Others (B) TRCA Converts Transition Rubrics into Step-Level Credit Step 1Step 2 Step n ... Step 1Step 2 Step n ... Breakthrough Rubric Sampled Rollouts +퐀 퐀 +퐀 퐀 Foundational Rubric clean some cloth and put it in cabinet. Task /Query P o l i c y m o d e l u p d a t e Evidence Step Invalidity Step Execution Step Rubric ✓ ✓ ❌ Figure 1: (A) Failed rollouts dominate early training, yet over 70% of their actions retain useful rubric-grounded tran- sition signals. (B) TRCA converts these step-level signals into foundational and breakthrough step credit without rely- ing on successful anchors or external evaluators. paired with sparse outcome rewards, PPO (Schulman et al. 2017), GRPO (Shao et al. 2024), and RLOO (Ahmadian et al. 2024) provide only trajectory-level supervision for training on long-horizon tasks. Propagating the same outcome re- ward to all actions prevents them from distinguishing ben- eficial steps from harmful ones, obscuring the contribution of individual actions. This limitation motivates the use of fine-grained step-level supervision. To address the above challenges, a natural solution is to introduce Process Reward Models (PRMs), which evalu- ate each intermediate step during rollouts to enable step- level credit assignment (Yuan et al. 2025). However, exist- ing process evaluation approaches based on supervised fine- tuning (Xi et al. 2026) or step-by-step assessment with large language model judges typically require extensive human an- notation or substantial additional inference. To avoid these labor and computational costs, another line of work derives step-level credit from structures constructed around success- ful trajectories (Feng et al. 2025; Tan et al. 2026; Cheng et al. arXiv:2608.16156v1 [cs.AI] 17 Aug 2026 2026; Feng et al. 2026), thereby avoiding the overhead asso- ciated with step-wise evaluation. However, the effectiveness of these methods fundamentally depends on the availability of success anchors: reliable step-level credit propagation can only be established when sufficient successful trajectories are obtained. Consequently, their applicability is limited in exploration stages where successful trajectories are scarce. To quantify the practical severity of this issue, we sample a group of rollouts from Qwen2.5-1.5B-Instruct on multi- ple long-horizon tasks. As shown in Figure 1 (A), 96.5% of the sampled rollouts fail to achieve terminal success, leav- ing 85.6% of task-conditioned training groups without any successful trajectory in early training. Under such a success- scarce regime, methods that rely on successful outcomes or success-conditioned structures to propagate rewards can provide only limited step-level credit. To examine whether failed rollouts are entirely uninformative, we further ana- lyze their transitions using human annotations and a frontier LLM judge. Surprisingly, 72.2% of the actions in failed tra- jectories still exhibit diagnostically useful transition signals, such as valid execution or measurable task progress. These observations suggest that reliable step-level credit remains accessible from environmental feedback even when terminal success is extremely sparse. Hence, these observations raise a core question: How can we assign reliable fine-grained credit without successful anchors or external evaluators? To answer this question, we propose Transition-wise Rubric Credit Assignment (TRCA), a step-level credit as- signment framework that derives supervision directly from action-induced transitions without relying on successful an- chors or learned process evaluators. TRCA evaluates each transition using three rubrics: Evidence captures newly re- vealed task-relevant information, Invalidity identifies mal- formed or unexecutable actions, and Execution recognizes completed task-required operations or intermediate condi- tions. Based on these judgments, Foundational Rubric Re- ward provides broad signed supervision, while Breakthrough Rubric Reward assigns additional credit to transitions that newly cover previously unsatisfied task-relevant conditions. TRCA combines the resulting step-level rewards with the sparse trajectory outcome to construct fine-grained advan- tages for training. In this way, TRCA extracts reliable step- level credit from both successful and failed rollouts under success-scarce training conditions, as illustrated in Figure 1 (B). Our contributions are as follows: • We identify the success-scarce credit assignment problem in long-horizon agent training and quantify its severity through case studies. Our analysis shows that failed roll- outs dominate early training, while their action-induced transitions still contain diagnostically useful signals. • We propose TRCA, a transition-wise step-level credit as- signment framework that evaluates action-induced transi- tions through Evidence, Invalidity, and Execution rubrics. TRCA constructs Foundational Rubric Reward for broad signed supervision and Breakthrough Rubric Reward for highlighting newly achieved task-relevant conditions, without successful anchors or external process evaluators. • Extensive experiments on ALFWorld, WebShop, and seven search-augmented QA benchmarks demonstrate that TRCA consistently improves performance over the evaluated baselines across model scales. Ablation studies and hyperparameter analyses further validate the effec- tiveness and robustness of its components. 2 Related Work 2.1 Reinforcement Learning for LLM Agents Reinforcement learning for LLMs largely inherits its op- timization machinery from RLHF. PPO stabilizes policy updates through a clipped surrogate objective and remains a widely used approach for LLM post-training (Schulman et al. 2017). More recent methods simplify this actor-critic pipeline. GRPO removes the learned value function by es- timating relative advantages within groups of sampled re- sponses (Shao et al. 2024), while RLOO employs leave-one- out baselines to obtain a simple critic-free policy-gradient estimator (Ahmadian et al. 2024). Although effective for single-response tasks, these methods provide limited guid- ance when a terminal outcome must be attributed to a long sequence of agent decisions. Recent work therefore extends group-relative optimization to multi-turn agents. GiGPO combines episode-level comparison with step-level grouping over recurrent anchor states, enabling finer-grained advan- tage estimation without additional rollouts (Feng et al. 2025). GraphGPO aggregates trajectories into a state-transition graph and estimates transition advantages using their struc- tural relation to successful terminal states (Cheng et al. 2026). These approaches substantially improve the granularity of advantage estimation by structure of success rollouts. 2.2 Process Supervision and Hindsight Credit Assignment LLM agents couple a policy model with an execution harness to support multi-step interaction with external environments, making fine-grained credit assignment over intermediate de- cisions a central challenge in agent optimization (Chen et al. 2026a; Lv et al. 2026a; Lin et al. 2026; Chen et al. 2026b). Process supervision alleviates sparse feedback by assigning scores to intermediate steps. Human-supervised PRMs re- quire large-scale step-level annotations, whereas automatic variants often rely on repeated Monte Carlo rollouts or tree search to construct training labels. Both introduce additional supervision or inference overhead (Lightman et al. 2024; Luo et al. 2024). AgentPRM extends this paradigm to interactive agent trajectories (Xi et al. 2026). Hindsight-based methods instead estimate earlier contributions after observing com- pleted trajectories: HCAPO refines step-level values through hindsight reasoning, while AgentHER relabels failed or par- tially successful trajectories (Tan et al. 2026; Ding 2026). These methods reduce explicit process evaluation, but may still depend on post-hoc goals, success proximity, or success- ful anchors that are scarce during early exploration. 2.3 Rubric-Based Supervision and Reinforcement Learning Rubrics provide structured and interpretable supervision by decomposing complex or open-ended objectives into explicit 1 Rubric Library & Definitions Three rubric dimensions express state changes as bounded judgments. ✓ Evidence (fundamental progress, positive deltas) target entity observed target attribute revealed relevant location revealed supporting evidence illegal action malformed format invalid schema execution rejected × Execution (evidence support, positive deltas) required action subgoal operation task condition intermediate objective TRCA turns state changes into step-wise rubric judgments and bounded reward signals. 2 Conceptual Rollout Sampling & Outcome Overview Single Query ... Rollout 2 Outcome: Failure Step 1Step 2Step 3Step 4 Rollout n Outcome: Success ✓ 3 Mechanism 1: Foundational Rubric Reward rubric 4 Mechanism 2: Breakthrough Rubric Reward × × × × Invalidity (parser/legal/action error, negative deltas) ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Step 1Step 2 Step 3Step 4 Rollout 1 Outcome: Partial success ... Task-relevant conditions (C) 1 relevant product found red color matched cotton material matched size M selected 2 3 4 New rubric count Sum of raw rubrics Step 2 Step 3 Step 4 ... Step 1 퐀 퐀 퐀 퐀 퐀 Step 2 Step 3 Step 4 ... Step 1 Step 1Step 2Step 3 × × 퐀 1 퐀 2 퐀 퐀 ... ... Step 4 Breakthrough (new coverage only) 퐀 퐀,퐀 = (퐀−퐀)⋅퐀 퐀,퐀 퐀 +⋅ 퐀 퐀,퐀 퐀 5 PPO/GRPO style policy optimization 퐀 퐀,퐀 퐀퐀 =퐀 퐀 (퐀 퐀 )+퐀 퐀 (퐀 퐀,퐀 ) Coverage over steps (= newly covered) Cond. Step 1 check Step 2 dark product Step 3 rugged color Step 4 select size Step 5 fill cart Step 6 checkout 1 2 – 3 – 4 – 1200 10 +1 Reward 0 0 0 0 0 +1 0 0 0 +2 퐀 퐀,퐀 퐀 =퐀 퐀,퐀 −퐀 퐀,퐀−퐀 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. evaluation criteria. Recent work has increasingly incorpo- rated rubrics into LLM evaluation and post-training. Rubrics as Rewards (RaR) uses instance-specific rubric criteria as on-policy reward signals to extend reinforcement learning beyond domains with directly verifiable outcomes (Gunjal et al. 2026). GEAR further studies reward aggregation in rubric-based reinforcement learning by modeling prereq- uisite dependencies among rubric criteria, mitigating false credit propagation caused by treating interdependent criteria as independent reward signals (Lv et al. 2026b). Reinforce- ment Learning with Rubric Anchors further scales rubric- based rewards to open-ended tasks and uses structured cri- teria to provide fine-grained supervision over response qual- ity (Huang et al. 2025). RuscaRL employs checklist-style rubrics both as guidance during rollout exploration and as references for reward computation, improving exploration in general reasoning tasks (Zhou et al. 2026). AdvancedIF and its RIFL pipeline similarly leverage expert-curated rubrics, rubric verification, and reward shaping to improve complex instruction following (He et al. 2026). Together, these stud- ies demonstrate that rubrics can provide more explicit and decomposable supervision than holistic scalar feedback. 3 Methodology 3.1 Preliminaries Long-Horizon Agentic Tasks Letx∼ p(X ) denote a task instance andπ θ an LLM policy. At interaction stept, the agent observes state s i,t , which summarizes the current observa- tion, interaction history, and relevant environment feedback, and samples an action a i,t ∼ π θ (· | s i,t ,x). After executing the action, the environment transitions to s i,t+1 and returns an environment reward r i,t . A complete rollout is repre- sented as the state-action trajectoryτ i = (x;s i,t ,a i,t ) T i t=1 . For each task x, the old policy π θ old samples N trajectories from the same initial condition. A long-horizon agentic task can be formulated as a partially observable Markov decision process, where the probability of trajectory τ i is π θ (τ i | x,s 0 ) = T i Y t=1 π θ (a i,t | x,s i,≤t ).(1) The environment assigns a binary terminal outcomeR(τ i ) = P T i t=1 r i,t , where R(τ i ) = 1 indicates successful task com- pletion andR(τ i ) = 0 otherwise. Although this terminal out- come provides a global measure of rollout quality, it cannot reliably distinguish the precise contributions of individual actions within the entire trajectory. Episode-Relative Advantage Following the group- relative setting, the old policy samples a rollout group G(x) = τ i N i=1 for the same task and initial condition. We use the total return R(τ i ) as a trajectory-level measure of task completion. The episode-relative advantage compares each trajectory with the other trajectories in the same group: A E (τ i ) = R(τ i )− μ R(τ j ) N j=1 σ R(τ j ) N j=1 .(2) Thus, A E (τ i ) indicates whether rollout τ i performs better or worse than alternative rollouts sampled for the same task. When a rollout group contains no successful trajectories, we set A E (τ i ) = 0. The step-level rewards become the primary source of learning signals for fine-grained credit assignment. 3.2 Transition-wise Rubric Design To provide informative step-level reward when success- ful trajectories are sparse, we construct a rubric set R(x) that evaluates the state transition induced by each agent action. For a long-horizon task instance x with rollout τ = (s 1 ,a 1 ,...,s T ,a T ), the rubric is defined as R(x) = R Evidence (x),R Invalidity (x),R Execution (x) , (3) where the three item types provide complementary credit signals for the action-induced transition ξ t = (s t ,a t ,s t+1 ). EvidenceR Evidence (x) items identify task-relevant entities, attributes, locations, relations, or supporting facts revealed or supported by the current transition, providing positive credit for information acquisition that supports subsequent plan- ning. Invalidity R Invalidity (x) items specify malformed, inadmissible, or otherwise unexecutable actions that cannot be correctly parsed or executed by the environment, con- tributing negative credit. Execution R Execution (x) items specify task requirements, subgoals, or intermediate ob- jectives satisfied by the action-induced transition, provid- ing additional positive credit for substantive task execu- tion. This three-aspect schema separates information acqui- sition, invalid-action detection, and task-relevant execution. For each task type, all rubric items are instantiated offline by an LLM before training. No additional judge model is invoked during subsequent policy optimization. For a task instance x belonging to task type b, we use the shared rubric library. Further details are provided in Appendix A.1. 3.3 Transition-wise Rubric Rewards TRCA converts the step-level rubric judgments into two com- plementary reward signals: Foundational Rubric Reward and Breakthrough Rubric Reward. Foundational Rubric Reward. Each judged rubric item is mapped to a signed item-level contribution according to its rubric category. Contributions associated with the same transition are then aggregated into a step-level reward and assigned only to the action tokens generated at the corre- sponding interaction step. We define the signed contribution of rubric item j at transition (i,t) as follows: q i t,j = +r Evi /M Evi ,j ∈R Evi , O i,t,j = 1, −|r Inval |/M Inval , j ∈R Inval , O i,t,j = 1, +r Exec /M Exec , j ∈R Exec , O i,t,j = 1, 0,otherwise. (4) Here, q i t,j denotes the signed contribution of rubric item j to transition andM c =|R c (x)| is the number of corresponding rubric items for taskx. Dividing the budget byM c bounds the magnitude of each category’s aggregate contribution regard- less of rubric-list length. The Foundational Rubric Reward is then obtained by summing all item-level contributions at the same transition: r F i,t = P j∈R(x) q i t,j , which aggregates both positive and negative judgments and is assigned only to the action tokens of the corresponding step. For each rubric item j, we define a binary semantic judgmentO i,t,j ∈0, 1, where O i,t,j = 1 if transition (i,t) satisfies rubric item j, and 0 otherwise. The judgment is computed from the ob- servable semantic evidence associated with the transition. Further details are provided in Appendix A.3. Breakthrough Rubric Reward. Foundational Rubric Re- ward evaluates each transition independently and may repeat- edly reward actions that satisfy the same rubric, reducing the relative advantage of truly critical steps after normalization. We introduce Breakthrough Rubric Reward to address this issue by rewarding only newly satisfied rubric conditions. We define C i,t,j = max 1≤k≤t O i,k,j , where O i,t,j = 1 if step t satisfies rubric item j, and 0 otherwise. Breakthrough Rubric Reward then constructs a cumulative rubric potential from the covered positive rubric items as follows: Φ i,t = X c∈Evi,Exec r c M c X j∈R c (x) C i,t,j ,(5) with C i,0,j = 0. And r c > 0 denotes the reward budget assigned to category c, and M c = |R c (x)| is the num- ber of rubric items in that category. We exclude Invalidity items from the cumulative potential because they describe transition-local errors and are already penalized by Foun- dational Rubric Reward. The Breakthrough Rubric Reward assigned to transition t is defined as the temporal difference of the cumulative potential: r B i,t = Φ i,t − Φ i,t−1 . Equiva- lently, the temporal difference can be expanded as r B i,t = X c∈Evi,Exec r c M c X j∈R c (x) (1− C i,t−1,j )O i,t,j . (6) Consequently, rubric item j contributes to Breakthrough Rubric Reward only when it is satisfied by the current step, O i,t,j = 1, and has not been covered by any earlier step, C i,t−1,j = 0. Overall, TRCA consists of two com- plementary reward constructions: Foundational Rubric Re- ward, which evaluates the direct rubric evidence triggered by each action, and Breakthrough Rubric Reward, which measures transition-induced increases in cumulative task- relevant rubric coverage. The two rewards are combined as r TRCA i,t = (1− λ)· r F i,t + λ· r B i,t ,(7) Here, λ ∈ [0, 1] controls the contribution of Breakthrough Rubric Reward relative to Foundational Rubric Reward. Im- portantly, TRCA constructs step-level rewards without re- quiring successful anchor states. 3.4 Policy Optimization Following the group-in-group framework, steps encountered under similar decision contexts are clustered according to environment-specific state information. For each similar state ̃s, we define the corresponding step-level group as G S ( ̃s) =(i,t)| s i,t ≃ ̃s, 1≤ i≤ N, 1≤ t≤ T i , (8) where s i,t ≃ ̃s indicates that s i,t belongs to the decision context represented by ̃s. Rather than requiring exact tex- tual matches, the grouping identifies semantically equivalent TypeMethod ALFWorldWebShop CleanPickCoolHeatPick2AllScoreSucc. Closed-Source Model Prompting GPT-4o31.275.321.656.749.848.031.823.7 Gemini-2.5-Pro 62.192.826.669.058.760.342.535.9 Qwen2.5-1.5B-Instruct Prompting Qwen2.53.35.94.29.70.04.123.15.2 ReAct15.717.47.76.22.012.840.111.3 Reflexion21.735.319.413.63.721.855.821.9 RL Training PPO57.1 (4.9) 64.8 (3.5) 46.4 (4.0) 60.6 (6.6) 47.4 (1.9) 54.4 (3.1) 73.8 (3.0) 51.5 (2.9) RLOO71.0 (5.9) 88.3 (3.0) 66.4 (5.5) 62.8 (8.7) 56.9 (4.7) 69.7 (2.5) 73.9 (5.6) 52.1 (6.7) GRPO73.9 (6.8) 82.9 (3.6) 77.8 (4.5) 78.6 (0.0) 71.4 (3.9) 77.9 (1.3) 84.7 (0.5) 71.4 (2.1) GiGPO94.8 (3.8) 94.4 (5.9) 79.8 (4.7) 94.4 (7.8) 76.4 (5.4) 86.7 (1.7) 83.1 (1.6) 65.0 (3.2) HCAPO97.6 (1.8) 88.6 (7.0) 84.2 (0.0) 90.7 (6.9) 74.2 (6.9) 87.0 (4.1) 83.8 (0.7) 68.5 (1.0) GraphGPO88.2 (5.0) 97.8 (3.2) 91.3 (1.8) 80.2 (11.1) 86.6 (2.6) 91.7 (0.4) 86.7 (1.6) 75.5 (1.2) Ours92.5 (4.3) 95.9 (2.2) 96.6 (1.5) 97.8 (0.9) 86.8 (6.9) 92.0 (2.7) 90.5 (0.9) 78.4 (1.6) Qwen2.5-7B-Instruct Prompting Qwen2.519.333.42.86.93.214.826.47.8 ReAct34.348.518.213.217.631.246.219.5 Reflexion44.962.036.330.923.842.758.128.8 RL Training PPO92.5 (2.4) 92.3 (4.0) 80.3 (2.0) 89.5 (7.0) 68.8 (8.3) 80.4 (2.7) 81.4 (3.1) 68.7 (5.1) RLOO87.3 (5.8) 87.6 (4.3) 71.9 (5.2) 81.3 (7.6) 48.9 (8.4) 75.5 (4.6) 80.3 (3.2) 65.7 (4.0) GRPO77.9 (4.6) 89.0 (5.3) 90.7 (5.2) 78.6 (0.0) 71.4 (3.9) 83.3 (2.1) 84.3 (1.3) 75.0 (2.8) GiGPO98.8 (1.6) 97.7 (1.6) 89.3 (8.2) 83.7 (7.2) 79.2 (6.6) 90.8 (1.3) 84.4 (2.9) 72.8 (3.2) HCAPO97.3 (1.9) 99.1 (1.3) 90.8 (6.6) 81.8 (8.8) 81.9 (10.0) 91.4 (2.3) 85.1 (1.3) 73.8 (2.8) GraphGPO89.6 (1.7) 98.0 (1.0) 92.5 (1.1) 90.9 (5.3) 90.4 (2.4) 93.3 (1.2) 86.9 (0.7) 80.3 (2.3) Ours95.0 (2.1) 97.7 (1.2) 100.0 (0.0) 93.3 (3.1) 94.1 (5.8) 94.5 (1.4) 92.9 (1.9) 83.8 (1.6) 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. or structurally consistent states using environment-specific information, such as page type, product identity, selected options, task predicates, or interaction stage. The original environment reward r i,t is sparse and is typi- cally assigned only at the terminal transition, withr i,t = 0 for t < T i and r i,T i = R(τ i ). TRCA combines the sparse envi- ronment reward with the step-level rubric reward to compute the completion-aware return: R i,t = T i X k=t γ k−t r i,k + r TRCA i,k ,(9) where γ ∈ [0, 1] is the discount factor. Analogous to the episode-relative advantage, the step-relative advantage is computed by normalizing the completion-aware return within the corresponding step-level group: A S (a i,t ) = R i,t − μ R j,k | (j,k)∈ G S ( ̃s) σ(R j,k | (j,k)∈ G S ( ̃s)) , (10) Here, the mean and standard deviation are computed over the completion-aware returns collected from the same com- parable decision context. WhileA E (τ i ) evaluates the relative quality of the complete rollout, A S (a i,t ) estimates the long- term utility of the individual action. TRCA combines the episode-relative and step-relative signals to construct the fi- nal advantage: A TRCA i,t = A E (τ i ) + A S (a i,t ), the clipped policy optimization objective of TRCA is: J TRCA (θ) =E h 1 N N X i=1 1 T i T i X t=1 min ρ i,t (θ)A TRCA i,t , clip(ρ i,t (θ), 1− ε, 1 + ε)A TRCA i,t i −β KL D KL (π θ ||π ref ) (11) Where ρ i,t (θ) = π θ (a i,t | s i,t ,x) π θ old (a i,t | s i,t ,x) is the action-level impor- tance ratio and β KL controls regularization toward the ref- erence policy. The KL term is omitted when explicit KL regularization is not used. The complete training procedure is provided in Appendix D.5. 4 Experiments We evaluate TRCA on two long-horizon interactive envi- ronments and seven search-augmented question-answering benchmarks. Our experiments examine (1) the overall effec- TypeMethod Single-Hop QAMulti-Hop QA Avg. NQ† TriviaQA⋆ PopQA⋆ HotpotQA† 2Wiki⋆ MuSiQue⋆ Bamboogle⋆ Base Model: Qwen2.5-3B-Instruct RL Training R1-Instruct 27.053.719.923.729.27.229.327.1 Search-R1 34.154.537.832.431.910.326.432.5 ZeroSearch 41.457.444.827.430.09.811.131.7 StepSearch –34.532.017.4–34.4 GiGPO42.059.542.436.937.012.664.142.1 HCAPO44.460.545.538.636.314.864.543.5 IGPO36.455.836.332.831.610.656.837.2 RL Training TRCA46.762.445.740.540.018.064.845.4 Base Model: Qwen2.5-7B-Instruct RL Training R1-Instruct 21.044.917.120.827.56.019.222.4 Search-R1 39.361.039.737.040.114.636.838.5 ZeroSearch 43.661.851.534.635.218.427.839.1 StepSearch –38.636.622.6–40.0 GiGPO46.464.746.141.643.618.968.947.2 HCAPO46.165.547.642.143.117.769.047.3 IGPO46.564.147.042.041.718.567.246.7 RL Training TRCA47.965.848.242.343.620.970.448.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. tiveness of TRCA across task domains and model scales, (2) its performance on multi-turn search tasks, (3) the contri- butions of Foundational Rubric Reward and Breakthrough Rubric Reward, and (4) its sensitivity to the mixing coeffi- cient λ between the two reward components. 4.1 Experimental Setup Benchmarks and metrics. We first evaluate TRCA on ALFWorld (Shridhar et al. 2021) and WebShop (Yao et al. 2022). ALFWorld is a text-based embodied environment in which an agent must complete household tasks through multi-step interactions. We report the success rate for each category and the overall success rate. WebShop is an inter- active shopping environment in which an agent navigates a simulated e-commerce website to identify and purchase a product that satisfies a natural-language instruction. Follow- ing prior work, we report both the average task score, which reflects partial attribute satisfaction, and the success rate, which measures exact task completion. We further evalu- ate TRCA on search-augmented QA, including three single- hop datasets—Natural Questions (NQ) (Kwiatkowski et al. 2019), TriviaQA (Joshi et al. 2017), and PopQA (Mallen et al. 2023)—and four multi-hop datasets—HotpotQA (Yang et al. 2018), 2WikiMultiHopQA (2Wiki) (Ho et al. 2020), MuSiQue (Trivedi et al. 2022), and Bamboogle (Press et al. 2023). We treat NQ and HotpotQA as in-domain benchmarks and use the remaining datasets to assess out-of-domain gener- alization. We report task success rate under strict binary nor- malized Exact Match (EM), counting an example as success- ful only when the normalized final answer exactly matches a ground-truth alias. Baselines. For LLMs, we compare TRCA with several competitive baselines, including: 1) Closed-source LLMs: GPT-4o and Gemini-2.5-Pro (Anil et al. 2023). 2) Prompting- based agents: ReAct (Yao et al. 2023), and Reflexion (Shinn et al. 2023), which are instantiated with the Qwen2.5 base policy (Qwen et al. 2025). 3) RL-based training methods: We choose models as follows, the actor-critic method PPO (Schulman et al. 2017), the critic-free meth- ods RLOO (Kool, van Hoof, and Welling 2019; Ahmadian et al. 2024) and GRPO (Shao et al. 2024); and recent step- level credit-assignment methods GiGPO (Feng et al. 2025), HCAPO (Tan et al. 2026), and GraphGPO (Cheng et al. 2026). For search-augmented QA tasks, following the ex- perimental protocol in prior work (Feng et al. 2025), we compare with R1-Instruct, Search-R1 (Jin et al. 2025), Ze- roSearch (Sun et al. 2026), StepSearch (Wang et al. 2025), GiGPO, HCAPO, and IGPO (Wang et al. 2026). Implementation details. For ALFWorld and Web- Shop, we use Qwen2.5-1.5B-Instruct and Qwen2.5-7B- Instruct (Qwen et al. 2025) as the policy models. All group- based methods use a rollout group size of 8. The agent generates its reasoning within <think> tags and its ex- ecutable action within <action> tags. Unless otherwise specified, we set the mixing coefficient between Founda- tional Rubric Reward and Breakthrough Rubric Reward to λ = 0.8. Results on ALFWorld and WebShop are averaged over three random seeds. For search-augmented QA, we use Qwen2.5-3B-Instruct and Qwen2.5-7B-Instruct, while keep- ing the training and evaluation settings identical to those of GiGPO. Full details are provided in Appendix F. 050100150200 Training Steps 0 20 40 60 80 100 Episode Success Rate (%) (a) Qwen2.5-1.5B-Instruct on ALFWorld TRCA w/o r F w/o r B 050100150200 Training Steps 0 20 40 60 80 (b) Qwen2.5-1.5B-Instruct on WebShop TRCA w/o r F w/o r B 050100150200 Training Steps 0 20 40 60 80 100 (c) Qwen2.5-1.5B-Instruct on WebShop (Task Score) TRCA w/o r F w/o r B 100200300400500600 Training Steps 38 40 42 44 46 48 50 (d) Qwen2.5-3B-Instruct on SearchQA (Avg.) TRCA w/o r F w/o r B Figure 3: Training dynamics of TRCA and its ablated variants on ALFWorld, WebShop, and SearchQA. Removing either Foundational Rubric Reward (r F ) or Breakthrough Rubric Reward (r B ) consistently degrades performance. Q w e n 2 . 5 - 1 . 5 B - i n s t r u c t s u c c e s s r a t e ( % ) (a) ALFWorld: pick_two success rate (%) (b) ALFWorld: pick_cool success rate (%) 0 20 40 60 80 100 +23.1 +31.7 +37.5 11.5 34.6 37.5 69.2 46.7 84.2 1.92K3.84K6.40K +9.0 +38.8 +26.9 15.015.0 53.8 57.7 84.6 1.92K3.84K6.40K Ours GRPO Sampled trajectories (K) Sampled trajectories (K) 24.0 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. 4.2 Performance on ALFWorld and WebShop Table 1 shows that TRCA achieves the strongest overall performance at both model scales. With Qwen2.5-1.5B- Instruct, TRCA reaches 92.0% overall of ALFWorld success rate,90.5% of WebShop task score, and 78.4% WebShop success rate. These results represent 5.3%, 7.4%, and 13.4% improvements over GiGPO, respectively. With Qwen2.5-7B- Instruct, TRCA obtains 94.5%, 92.9%, and 83.8% on the same metrics, obtains 3.7%, 8.5%, and 11.0% improvements over GiGPO. TRCA also improves upon the strongest prior overall baseline, under Qwen2.5-1.5B-instruct setting, our method achieves 3.8% task score and 2.9% success-rate im- provements on WebShop over GraphGPO. under Qwen2.5- 7B-instruct setting, the corresponding gains 6.0% and 3.5% improvements over GraphGPO. 4.3 Performance on Search-Augmented QA As shown in Table 2, TRCA achieves the best average per- formance at both model scales. With Qwen2.5-3B-Instruct, TRCA obtains an average score of 45.4%, and it obtains 8.2% and 3.3% improvements over IGPO and GiGPO, re- spectively. It also achieves the best result on each of the seven individual datasets in the 3B setting. With Qwen2.5- 7B-Instruct, TRCA also reaches the best average score over other baselines, which shows that TRCA maintains com- petitive performance across heterogeneous search tasks and provides the strongest aggregate result without relying on ground truth labels on every dataset. Pick2HeatPickCleanCoolALL Subtask 0.2 0.4 0.5 0.6 0.8 1.0 λ 79.281.292.095.580.884.4 89.588.986.795.283.385.9 76.573.393.085.085.784.4 94.180.090.785.095.287.5 86.897.895.992.596.692.0 85.794.191.495.081.088.3 75 80 85 90 95 100 Success Rate (%) Figure 5: Performance of TRCA under different settings of hyperparameter λ on ALFWorld success rate (%). 4.4 Learning Dynamics and Design Analysis Learning Dynamics and Sample Efficiency. Figure 4 (a) and (b) show that TRCA converges substantially faster than GRPO on both Pick_two and Pick_cool under iden- tical trajectory-sampling budgets. Notably, this advantage emerges from the earliest stage of training: with only 1.92K sampled trajectories, TRCA improves the success rate from 11.5% to 34.6% on Pick_two and from 15.0% to 24.0% on Pick_cool. On Pick_two, TRCA reaches a 69.2% suc- cess rate with 3.84K trajectories, surpassing the 46.7% achieved by GRPO with 6.40K trajectories. On Pick_cool, TRCA achieves 53.8% with 3.84K trajectories, approach- ing GRPO’s 57.7% while using 40% fewer samples. These results demonstrate that transition-wise rubric rewards im- prove the utilization of early-stage rollout experience, thereby accelerating convergence and enhancing overall sample effi- ciency. Experimental details are provided in Appendix F. Ablation Study. We ablate the two reward components of TRCA while keeping all other training configurations un- changed. As shown in Figure 3, removing either component consistently degrades performance, confirming their comple- mentarity. Removing Breakthrough Rubric Reward causes a larger drop across all three benchmarks, indicating that newly covered rubric conditions provide particularly impor- tant credit for task-critical actions, while Foundational Rubric Reward supplies broad step-level supervision. Hyperparameter sensitivity analysis. On ALFWorld, we vary λ over 0.2, 0.4, 0.5, 0.6, 0.8, 1.0, where larger val- ues place greater emphasis on Breakthrough Rubric Reward. Increasing λ generally benefits challenging subtasks such as Heat and Cool, but excessive emphasis on breakthrough progress reduces the overall success rate from 92.0% at λ = 0.8 to 88.3% at λ = 1.0. Thus, λ = 0.8 provides the best empirical balance between broad step-level supervision and breakthrough-focused credit. 5 Conclusion Our central insight is that failure does not imply the ab- sence of supervision: even unsuccessful trajectories contain abundant and verifiable evidence in the state transitions they induce. TRCA leverages this evidence by grounding credit assignment in environment-observed changes rather than rare terminal successes, thereby converting otherwise discarded experience into reliable step-level supervision without suc- cessful anchors or learned process reward models. This ca- pability is particularly valuable during early exploration, when successful rollouts are scarce but informative tran- sitions remain plentiful. Across embodied interaction, web navigation, and search-augmented reasoning, TRCA consis- tently improves performance, convergence speed, and sam- ple efficiency, especially under limited rollout budgets. More broadly, our results establish transition-level environmental evidence as a general foundation for learning long-horizon behaviors from both successful and failed experience. Acknowledgments This work was supported in part by the Beijing Ma- jor Science and Technology Project under Contract No. Z251100008125031 and the National Natural Science Foundation of China under Grant No. 62401327. This work was also supported by the Beijing Academy of Artificial Intelligence (BAAI). References Ahmadian, A.; Cremer, C.; Gallé, M.; Fadaee, M.; Kreutzer, J.; Pietquin, O.; Üstün, A.; and Hooker, S. 2024. Back to Basics: Revisiting REINFORCE-Style Optimization for Learning from Human Feedback in LLMs. In Ku, L.-W.; Martins, A.; and Srikumar, V., eds., Proceedings of the 62nd Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), 12248–12267. Bangkok, Thailand: Association for Computational Linguistics. Anil, R.; Borgeaud, S.; Alayrac, J.-B.; Yu, J.; Soricut, R.; Schalkwyk, J.; Dai, A.; Hauth, A.; Millican, K.; Silver, D.; Johnson, M.; Antonoglou, I.; Schrittwieser, J.; Glaese, A.; Chen, J.; Pitler, E.; Lillicrap, T.; Lazaridou, A.; Firat, O.; and Vinyals, O. 2023. Gemini: A Family of Highly Capable Multimodal Models. Chen, M.; Lv, C.; Zhang, G.; Chang, H.; and Zhou, S. 2026a. HarnessForge: Joint Harness and Policy Evolution for Adap- tive Agent Systems. arXiv:2606.01779. Chen, M.; Zhang, G.; Chang, H.; Guo, Y.; and Zhou, S. 2026b. A-MapReduce: Executing Wide Search via Agentic MapReduce. arXiv:2602.01331. Cheng, X.; He, S.; Feng, L.; Xu, H.; Yan, M.; Feng, L.; and An, B. 2026. Beyond Trajectory-Level Attribution: Graph- Based Credit Assignment for Agentic Reinforcement Learn- ing. arXiv:2605.26684. Ding, L. 2026. AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling. arXiv:2603.21357. Feng, L.; Xue, Z.; Liu, T.; and An, B. 2025. Group-in-Group Policy Optimization for LLM Agent Training. In Belgrave, D.; Zhang, C.; Lin, H.; Pascanu, R.; Koniusz, P.; Ghassemi, M.; and Chen, N., eds., Advances in Neural Information Pro- cessing Systems, volume 38, 46375–46408. Curran Asso- ciates, Inc. Feng, X.; Han, B.; Zhou, Z.; Fan, J.; Yao, J.; Li, K. H.; Yu, D.; and Ng, M. K.-P. 2026. RewardFlow: Topology-Aware Reward Propagation on State Graphs for Agentic RL with Large Language Models. arXiv:2603.18859. Gunjal, A.; Wang, A.; Lau, E.; Nath, V.; He, Y.; Liu, B.; and Hendryx, S. M. 2026. Rubrics as Rewards: Reinforcement Learning Beyond Verifiable Domains. In The Fourteenth International Conference on Learning Representations. He, Y.; Li, W.; Zhang, H.; Li, S.; Mandyam, K.; Khosla, S.; Xiong, Y.; Wang, N.; Peng, X.; Li, B.; Bi, S.; Patil, S. G.; Qi, Q.; Feng, S.; Katz-Samuels, J.; Pang, R. Y.; Gonugondla, S. K.; Lang, H.; Yu, Y.; Qian, Y.; Fazel-Zarandi, M.; Yu, L.; Benhalloum, A.; Awadalla, H. H.; and Faruqui, M. 2026. AdvancedIF: Rubric-Based Benchmarking and Reinforce- ment Learning for Advancing LLM Instruction Following. In Liakata, M.; Moreira, V. P.; Zhang, J.; and Jurgens, D., eds., Proceedings of the 64th Annual Meeting of the Associa- tion for Computational Linguistics (Volume 1: Long Papers), 18003–18022. San Diego, California, United States: Asso- ciation for Computational Linguistics. ISBN 979-8-89176- 390-6. Ho, X.; Duong Nguyen, A.-K.; Sugawara, S.; and Aizawa, A. 2020. Constructing A Multi-hop QA Dataset for Comprehen- sive Evaluation of Reasoning Steps. In Scott, D.; Bel, N.; and Zong, C., eds., Proceedings of the 28th International Confer- ence on Computational Linguistics, 6609–6625. Barcelona, Spain (Online): International Committee on Computational Linguistics. Huang, Z.; Zhuang, Y.; Lu, G.; Qin, Z.; Xu, H.; Zhao, T.; Peng, R.; Hu, J.; Shen, Z.; Hu, X.; Gu, X.; Tu, P.; Liu, J.; Chen, W.; Fu, Y.; Fan, Z.; Gu, Y.; Wang, Y.; Yang, Z.; Li, J.; and Zhao, J. 2025. Reinforcement Learning with Rubric Anchors. arXiv:2508.12790. Jin, B.; Zeng, H.; Yue, Z.; Yoon, J.; Arik, S.; Wang, D.; Zamani, H.; and Han, J. 2025. Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning. arXiv:2503.09516. Joshi, M.; Choi, E.; Weld, D.; and Zettlemoyer, L. 2017. TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension. In Barzilay, R.; and Kan, M.-Y., eds., Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 1601–1611. Vancouver, Canada: Association for Computational Linguistics. Kool, W.; van Hoof, H.; and Welling, M. 2019. Buy 4 RE- INFORCE Samples, Get a Baseline for Free! Kwiatkowski, T.; Palomaki, J.; Redfield, O.; Collins, M.; Parikh, A.; Alberti, C.; Epstein, D.; Polosukhin, I.; Devlin, J.; Lee, K.; Toutanova, K.; Jones, L.; Kelcey, M.; Chang, M.-W.; Dai, A. M.; Uszkoreit, J.; Le, Q.; and Petrov, S. 2019. Natural Questions: A Benchmark for Question Answering Research. Transactions of the Association for Computational Linguistics, 7: 452–466. Lightman, H.; Kosaraju, V.; Burda, Y.; Edwards, H.; Baker, B.; Lee, T.; Leike, J.; Schulman, J.; Sutskever, I.; and Cobbe, K. 2024. Let's Verify Step by Step. In Kim, B.; Yue, Y.; Chaudhuri, S.; Fragkiadaki, K.; Khan, M.; and Sun, Y., eds., International Conference on Learning Representations, vol- ume 2024, 39578–39601. Lin, J.; Liu, S.; Pan, C.; Lin, L.; Dou, S.; Xi, Z.; Huang, X.; Yan, H.; Han, Z.; Gui, T.; and Jiang, Y.-G. 2026. Agentic Harness Engineering: Observability-Driven Automatic Evo- lution of Coding-Agent Harnesses. arXiv:2604.25850. Luo, L.; Liu, Y.; Liu, R.; Phatale, S.; Guo, M.; Lara, H.; Li, Y.; Shu, L.; Zhu, Y.; Meng, L.; Sun, J.; and Rastogi, A. 2024. Improve Mathematical Reasoning in Language Models by Automated Process Supervision. arXiv:2406.06592. Lv, C.; Chang, H.; Tao, S.; Chen, M.; Fan, Z.; Zhang, Z.; Guo, Y.; and Zhou, S. 2026a. All-Mem: Agentic Lifelong Memory via Dynamic Topology Evolution. arXiv:2603.19595. Lv, C.; Chen, M.; Chang, H.; and Zhou, S. 2026b. Miti- gating False Credit Propagation: Probabilistic Graphical Re- ward Aggregation for Rubric-Based Reinforcement Learn- ing. arXiv:2606.03361. Mallen, A.; Asai, A.; Zhong, V.; Das, R.; Khashabi, D.; and Hajishirzi, H. 2023. When Not to Trust Language Models: In- vestigating Effectiveness of Parametric and Non-Parametric Memories. In Rogers, A.; Boyd-Graber, J.; and Okazaki, N., eds., Proceedings of the 61st Annual Meeting of the As- sociation for Computational Linguistics (Volume 1: Long Papers), 9802–9822. Toronto, Canada: Association for Com- putational Linguistics. Press, O.; Zhang, M.; Min, S.; Schmidt, L.; Smith, N.; and Lewis, M. 2023. Measuring and Narrowing the Composi- tionality Gap in Language Models. In Bouamor, H.; Pino, J.; and Bali, K., eds., Findings of the Association for Compu- tational Linguistics: EMNLP 2023, 5687–5711. Singapore: Association for Computational Linguistics. Qwen; :; Yang, A.; Yang, B.; Zhang, B.; Hui, B.; Zheng, B.; Yu, B.; Li, C.; Liu, D.; Huang, F.; Wei, H.; Lin, H.; Yang, J.; Tu, J.; Zhang, J.; Yang, J.; Yang, J.; Zhou, J.; Lin, J.; Dang, K.; Lu, K.; Bao, K.; Yang, K.; Yu, L.; Li, M.; Xue, M.; Zhang, P.; Zhu, Q.; Men, R.; Lin, R.; Li, T.; Tang, T.; Xia, T.; Ren, X.; Ren, X.; Fan, Y.; Su, Y.; Zhang, Y.; Wan, Y.; Liu, Y.; Cui, Z.; Zhang, Z.; and Qiu, Z. 2025. Qwen2.5 Technical Report. arXiv:2412.15115. Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O. 2017. Proximal Policy Optimization Algorithms. arXiv:1707.06347. Shao, J.-J.; Zhang, B.-W.; Yang, X.-W.; Chen, B.; Han, S.; Jinghao, P.; Wei, W.-D.; Cai, G.; Dong, Z.; Guo, L.-Z.; and Li, Y.-F. 2026. ChinaTravel: An Open-Ended Travel Plan- ning Benchmark with Compositional Constraint Validation for Language Agents. In The Fourteenth International Con- ference on Learning Representations. Shao, Z.; Wang, P.; Zhu, Q.; Xu, R.; Song, J.; Bi, X.; Zhang, H.; Zhang, M.; Li, Y. K.; Wu, Y.; and Guo, D. 2024. DeepSeekMath: Pushing the Limits of Mathematical Rea- soning in Open Language Models. arXiv:2402.03300. Shinn, N.; Cassano, F.; Berman, E.; Gopinath, A.; Narasimhan, K.; and Yao, S. 2023. Reflexion: Lan- guage Agents with Verbal Reinforcement Learning. arXiv:2303.11366. Shridhar, M.; Yuan, X.; Cote, M.-A.; Bisk, Y.; Trischler, A.; and Hausknecht, M. 2021. ALFWorld: Aligning Text and Embodied Environments for Interactive Learning. In International Conference on Learning Representations. Sun, H.; Qiao, Z.; Guo, J.; Fan, X.; Hou, Y.; Jiang, Y.; Xie, P.; Zhang, Y.; Huang, F.; and Zhou, J. 2026. ZeroSearch: In- centivize the Search Capability of LLMs without Searching. arXiv:2505.04588. Tan, H.-Z.; Yang, X.-W.; Chen, H.; Shao, J.-J.; Wen, Y.; Shen, Y.; Luo, W.; Du, X.; Guo, L.-Z.; and Li, Y.-F. 2026. Hind- sight Credit Assignment for Long-Horizon LLM Agents. arXiv:2603.08754. Trivedi, H.; Balasubramanian, N.; Khot, T.; and Sabharwal, A. 2022. MuSiQue: Multihop Questions via Single-hop Question Composition. arXiv:2108.00573. Wang, G.; Dai, S.; Ye, G.; Gan, Z.; Yao, W.; Deng, Y.; Wu, X.; and Ying, Z. 2026. Information Gain-based Policy Op- timization: A Simple and Effective Approach for Multi-Turn Search Agents. arXiv:2510.14967. Wang, Z.; Zheng, X.; An, K.; Ouyang, C.; Cai, J.; Wang, Y.; and Wu, Y. 2025. StepSearch: Igniting LLMs Search Ability via Step-Wise Proximal Policy Optimization. arXiv:2505.15107. Xi, Z.; Liao, C.; Li, G.; Zhang, Z.; Chen, W.; Wang, B.; Jin, S.; Zhou, Y.; Guan, J.; Wu, W.; Ji, T.; Gui, T.; Zhang, Q.; and Huang, X. 2026. AgentPRM: Process Reward Models for LLM Agents via Step-Wise Promise and Progress. In Proceedings of the ACM Web Conference 2026, W ’26, 4184–4195. New York, NY, USA: Association for Comput- ing Machinery. ISBN 9798400723070. Xie, J.; Zhang, K.; Chen, J.; Zhu, T.; Lou, R.; Tian, Y.; Xiao, Y.; and Su, Y. 2024. TravelPlanner: A Benchmark for Real- World Planning with Language Agents. In Salakhutdinov, R.; Kolter, Z.; Heller, K.; Weller, A.; Oliver, N.; Scarlett, J.; and Berkenkamp, F., eds., Proceedings of the 41st Inter- national Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, 54590–54613. PMLR. Yang, Z.; Qi, P.; Zhang, S.; Bengio, Y.; Cohen, W.; Salakhut- dinov, R.; and Manning, C. D. 2018. HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering. In Riloff, E.; Chiang, D.; Hockenmaier, J.; and Tsujii, J., eds., Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 2369–2380. Brussels, Bel- gium: Association for Computational Linguistics. Yao, S.; Chen, H.; Yang, J.; and Narasimhan, K. 2022. Web- Shop: Towards Scalable Real-World Web Interaction with Grounded Language Agents. In Koyejo, S.; Mohamed, S.; Agarwal, A.; Belgrave, D.; Cho, K.; and Oh, A., eds., Advances in Neural Information Processing Systems, vol- ume 35, 20744–20757. Curran Associates, Inc. Yao, S.; Zhao, J.; Yu, D.; Du, N.; Shafran, I.; Narasimhan, K.; and Cao, Y. 2023. ReAct: Synergizing Reasoning and Acting in Language Models. arXiv:2210.03629. Yuan, S.; Chen, Z.; Xi, Z.; Ye, J.; Du, Z.; and Chen, J. 2025. Agent-R: Training Language Model Agents to Reflect via Iterative Self-Training. arXiv:2501.11425. Zhou, Y.; Li, S.; Liu, S.; Fang, W.; Zhang, K.; Zhao, J.; Yang, J.; Zhou, Y.; Lv, J.; Zheng, T.; Lu, H.; Chen, W.; Xie, Y.; and Song, M. 2026. Breaking the Exploration Bottle- neck: Rubric-Scaffolded Reinforcement Learning for Gen- eral LLM Reasoning. arXiv:2508.16949. A Task-Conditioned Rubric Construction and Evaluation Overview of rubric construction and evaluation. Ap- pendix A complements the rubric formulation in the main text by specifying how a shared rubric library is constructed, instantiated for a concrete task, and applied to an action- induced transition. At the beginning, we let b∈ALFWorld, WebShop, SearchQA index the benchmark-specific interaction type, and letx∈X b denote a task instance from benchmark b. For rubric category c ∈ Evi, Inval, Exec, TRCA uses a benchmark-level operator h c b,m , a task-conditioned bind- ing ω b,m (x), and a benchmark-specific transition adapter g b . Their composition produces the binary judgment O i,t,(m,ω) = h c b,m (ω b,m (x),g b (s i,t ,a i,t ,s i,t+1 ))∈0, 1. (1) Here, h c b,m defines a reusable Boolean condition, ω b,m (x) supplies the task-specific parameters required by that con- dition, and g b maps the raw action-induced transition into canonical observable facts available at the current interac- tion step. The operator is active only when these observable facts satisfy its Boolean condition; missing, ambiguous, or unsupported evidence leaves the operator inactive. A.1 Shared Rubric Schema and Benchmark-Level Operator Libraries At the level of rubric design, ALFWorld, WebShop, and SearchQA are treated as instances of a common long-horizon interaction family. They share the same three-category rubric schema and the same library-generation protocol: Evidence, Invalidity, and Execution. The schema fixes the semantic role of each category across benchmarks, while the concrete operators are instantiated according to the action grammar and observable feedback exposed by benchmark b. Before policy training, an LLM is invoked only once for each benchmark-specific interaction type b to construct the corresponding reusable operator library. T b = T Evi b ,T Inval b ,T Exec b , T c b = h c b,m M c m=1 , (2) where c ∈ Evi, Inval, Exec. Each library therefore con- tains five operators per category and fifteen operators in total. The three categories have complementary roles. Evidence operators identify newly revealed or newly supported task- relevant entities, attributes, locations, relations, or supporting facts. Invalidity operators identify malformed, unavailable, rejected, repeated, no-op, or precondition-violating actions. Execution operators clearly identify accepted task-relevant operations, successfully achieved subgoals, completed state transformations, or explicitly satisfied task conditions. Each operator h c b,m specifies: (i) the canonical observable facts it reads, (i) the task-binding fields it requires, and (i) an exact Boolean activation condition. An operator returns one only when its required observable facts establish the condi- tion; Otherwise, it returns zero. This fully deterministic form effectively prevents unsupported or ambiguous transition ev- idence from producing positive rubric judgments. The same generation prompt, category definitions, output schema, and Boolean-writing requirements are used for all three benchmarks. Benchmark-specific information is lim- ited to the interface description required to define executable operators, including the action grammar, admissible oper- ations, observable state fields, and environment feedback format. Consequently, the generated libraries adapt to dif- ferent interaction interfaces without changing the high-level rubric design. Library construction is performed once before training and does not use successful trajectories, terminal outcomes, future transitions, task-specific answers, bench- mark performance results, or ground-truth intermediate la- bels. The LLM constructs only the reusable benchmark-level operators. It is not invoked to generate a new library for an individual task and is not used as a transition judge during rollout collection or policy optimization. Once T b has been constructed, no further LLM calls are required. For each task, the deterministic binding procedure in Appendix A.2 fills the operator fields and produces the grounded rubric set R(x). The resulting task-grounded operators are evaluated on action-induced transitions as described in Appendix A.3, using the environment-specific observable signals summa- rized in Appendix A.4. Their binary outputs are converted into Foundational and Breakthrough Rubric Rewards in Ap- pendix C. The shared generation prompt and benchmark- level libraries are provided in Appendix G. A.2 Task-Conditioned Binding across Task Instances All task instances within benchmark-specific interaction type b reuse the same operator library T b . Each operator h c b,m is a parameterized Boolean template with predefined binding fields. For a concrete task instruction x∈X b , a deterministic task binder fills these fields with task-specific parameters: ω b,m (x) =B b,m (x).(3) The binder is implemented through benchmark-specific pars- ing and field extraction and does not invoke an LLM or an- other learned model. This stage performs deterministic pa- rameter binding rather than generating a new rubric library. The bindingω b,m (x) may contain task-relevant entities, at- tributes, relations, locations, constraints, required operation types, target conditions, or output formats extracted from the task instruction and fixed benchmark metadata. For operators that depend only on benchmark-level interface properties, such as parser validity, the corresponding task binding may be empty. The grounded rubric set for task x is defined as R c (x) = h c b,m ,ω b,m (x) M c m=1 , x∈X b , (4) where c∈Evi, Inval, Exec. The operator semantics h c b,m remain fixed across all task instances of benchmark b; only the task-conditioned bindings ω b,m (x) vary with the specific instruction. Consequently, no new operator library is sepa- rately generated for any particular task instance. Accordingly, the task-conditioned rubric set R c (x) con- sists of concrete rubric items instantiated from the shared operators through deterministic parameter binding; it is not an independently generated task-specific library. For example, the ALFWorld binder extracts the target ob- ject, required state transformation, quantity, and destination receptacle. The WebShop binder extracts requested product attributes, options, and purchase constraints. The SearchQA binder extracts the target entity or subject, requested relation or information need, query constraints, and required answer format. Ground-truth answer aliases are not included in the SearchQA binding and are used only by the environment to compute the terminal Exact Match outcome. The task binding remains fixed within a task instance, while the observable facts supplied to the bound operators vary across action-induced transitions. A.3 Rule-Based Transition Evaluation For rollout i, the transition at step t is represented as ξ i,t = (s i,t ,a i,t ,s i,t+1 ),(5) where s i,t is the current interaction state, a i,t is the complete environment-facing action, and s i,t+1 is the next interaction state containing the observable environment feedback pro- duced by executing the action. During training, the deterministic benchmark adapter g b maps the raw action-induced transition into canonical ob- servable facts. For a task-grounded rubric item j = h c b,m ,ω b,m (x) ∈R c (x), the transition-level judgment is computed as O i,t,j = h c b,m (ω b,m (x),g b (s i,t ,a i,t ,s i,t+1 ))∈0, 1. (6) The binding ω b,m (x) supplies the task-specific require- ments, while g b supplies the observable facts associated with the current pre-action state, action, and post-action environ- ment feedback. These facts may include the parsed action type and arguments, parser status, currently available oper- ations, visible entities and attributes, retrieved content, ac- tion acceptance or rejection feedback, and observable state changes caused by the action. The evaluation does not access successful trajectories, ter- minal labels, future states, hidden environment states, bench- mark performance results, or ground-truth intermediate la- bels. If the observable evidence is insufficient to establish a rubric condition, the corresponding operator remains in- active and O i,t,j = 0. Here, zero denotes non-activation, rather than negative reward. Negative credit is introduced only when an Invalidity operator is activated and mapped to its signed contribution by Foundational Rubric Reward. Evidence judgments are triggered by newly revealed or newly supported task-relevant information, such as an ob- ject location in ALFWorld, a product attribute in WebShop, or a supporting fact in SearchQA. Invalidity judgments are triggered by parser failure, malformed command format, environment rejection, inadmissible action, unavailable in- terface operation, repeated ineffective execution, or another directly observable failure. Execution judgments are trig- gered when the transition satisfies a task-required operation, subgoal, or intermediate condition, such as acquiring an ob- ject, selecting an instruction-consistent option, or issuing an accepted retrieval step within the current interaction context. A single transition can satisfy multiple rubric items within the same category or across different categories. For exam- ple, an action may both reveal a task-relevant object and com- plete a required exploration operation. The resulting Boolean judgments are evaluated independently and are subsequently aggregated by the reward construction in Appendix C. Both task binding and transition evaluation are determin- istic. Neither stage invokes an LLM during rollout collection or policy optimization. Accordingly, the LLM is used ex- clusively for the one-time benchmark-level operator library construction process described in Appendix A.1. A.4 Environment-Specific Observable Signals The following signals are the transition-dependent observ- able facts extracted by the benchmark adapter g b . They are evaluated together with the corresponding task-conditioned bindings formally defined in Appendix A.2. ALFWorld. ALFWorld exposes textual feedback concern- ing action admissibility, object locations, inventory states, re- ceptacles, and object-state transformations. Evidence items detect newly observed task-relevant objects, locations, recep- tacles, or object states. Invalidity items detect malformed commands, inadmissible actions, unavailable objects, unsat- isfied preconditions, environment rejection, repeated ineffec- tive actions, or failed execution. Execution items identify task-relevant operations such as acquiring an object, apply- ing a required transformation, or placing an object in a target receptacle throughout the current interaction process. WebShop. WebShop provides structured page states, prod- uct attributes, available options, selected options, navigation feedback, cart state, and purchase status. Evidence items detect newly revealed products, attributes, or task-relevant options. Invalidity items identify malformed interface ac- tions, unavailable selections, rejected operations, repeated no-op actions, or premature purchases. Execution items identify substantive operations such as opening a candidate product, selecting an instruction-consistent option, adding a qualifying product to the cart, or reaching a purchase-ready state during the current navigation process. SearchQA. SearchQA exposes search queries, retrieved results, document content, tool-execution feedback, retrieval- state changes, and answer-submission states. Evidence items detect newly retrieved task-relevant entities, relations, pas- sages, or supporting facts. Invalidity items detect mal- formed tool calls, unavailable result or passage identifiers, unsatisfied action preconditions, rejected queries, repeated no-op retrieval actions, or invalid interaction formats. Exe- cution items identify accepted operations such as issuing a valid search, opening a retrieved source, reading a relevant passage, extracting supporting evidence, or submitting an answer in the required format during the current process. SearchQA operators may inspect retrieved text to deter- mine whether it expresses a relation relevant to the task in- struction. They do not compare the retrieved text or the sub- mitted answer against a ground-truth answer alias. Ground- truth answer aliases are used only by the benchmark to com- pute the terminal Exact Match reward and are not used to judge intermediate rubric items. A.5 Validity in the Diagnostic Study Figure 1 reports Validity as a diagnostically useful tran- sition signal because successful parsing and execution are directly verifiable from environment feedback. Although a valid action may not immediately satisfy a task subgoal, it provides reliable evidence that the agent can interact with the environment in an executable way. In the TRCA reward construction, we model the comple- mentary failure condition, Invalidity, and assign negative credit to malformed, inadmissible, rejected, repeated, or oth- erwise unexecutable actions. Thus, Validity in the diagnos- tic analysis and Invalidity in the reward construction are complementary views of action executability. The absence of an Invalidity judgment does not itself pro- duce positive reward. A valid and executable action receives positive rubric credit only when the same transition also activates an Evidence or Execution item. Thus, positive supervision remains tied to task-relevant information acqui- sition or substantive task execution rather than action validity alone. Together, Appendices A.1–A.5 specify the complete rubric instantiation and evaluation pipeline. Appendix A.1 constructs the shared benchmark-level operator library T b . Appendix A.2 deterministically binds its parameterized op- erators to a task instruction, producing the concrete rubric set R(x). Appendix A.3 applies these task-grounded operators to observable action-induced transitions to obtain the binary judgments O i,t,j , while Appendices A.4 and A.5 specify their observable inputs and executability semantics. These judgments are subsequently converted into Foundational and Breakthrough Rubric Rewards in Appendix C. B Notation and TRCA Training Algorithm B.1 Notation Summary For a task-grounded rubric item j = (h c b,m ,ω b,m (x)), its binary judgment is computed as O i,t,j = h c b,m (ω b,m (x),g b (s i,t ,a i,t ,s i,t+1 ))∈0, 1, (7) where h c b,m is a shared operator in category c ∈ Evi, Inval, Exec, ω b,m (x) is its deterministic task- conditioned binding, and g b is the benchmark-specific tran- sition adapter. Table 3 summarizes the main notation used in the rubric construction and transition-wise credit assignment of TRCA throughout the complete training pipeline; standard reinforcement-learning notation is omitted for brevity. B.2 Normalization and Numerical Conventions TRCA uses normalization only when constructing relative advantages. Reward normalization and advantage normal- ization are therefore separate operations. The rubric rewards r F i,t , r B i,t , and r TRCA i,t are defined by the category budgets and the item-count normalization in Appendix C. The episode- relative and context-relative advantages are normalized over the corresponding rollout group or context group. Table 3: Main notation used in TRCA. Symbol Definition xA concrete task instruction or query. bA benchmark-specific interaction type, where b ∈ ALFWorld, WebShop, SearchQA. T b The benchmark-level operator library shared across all task instances of benchmarkb, consisting of Evidence, Invalidity, and Execution operators. h c b,m The m-th deterministic Boolean operator in cate- gory c of libraryT b . ξ i,t The action-induced transition ξ i,t = (s i,t ,a i,t ,s i,t+1 ) at interaction step t of rollout i. ω b,m (x) The task-conditioned parameters deterministically bound to operatorh c b,m , such as an entity, attribute, relation, constraint, target condition, or required output format. g b The benchmark-specific adapter that maps the raw transition (s i,t ,a i,t ,s i,t+1 ) into canonical observ- able facts. R c (x)The grounded rubric-item set formed by pair- ing the shared operators in T c b with their task- conditioned bindings for task x. O i,t,j The binary judgment O i,t,j ∈ 0, 1 indicating whether transition ξ i,t satisfies rubric item j. r F i,t The Foundational Rubric Reward obtained by ag- gregating the signed rubric judgments at transition (i,t). C i,t,j The cumulative coverage indicator specifying whether positive rubric item j has been satisfied by any transition up to step t. r B i,t The Breakthrough Rubric Reward assigned to newly covered Evidence and Execution items. r TRCA i,t The transition-level reward obtained by combining Foundational Rubric Reward and Breakthrough Rubric Reward. λThe mixing coefficient between Foundational Rubric Reward and Breakthrough Rubric Reward. For a finite comparison groupG of scalar valuesz k , we consistently use the following normalization convention Norm G (z k ) = z k − μ G σ G + ε norm , σ G > 0, 0,σ G = 0. (8) Here, μ G and σ G are computed exclusively within the corre- sponding comparison group for the current normalization. For episode-relative normalization, the group is the roll- out group G(x) = τ i N i=1 , and the normalized values are terminal outcomes R(τ i ). If all rollouts in the group have the same outcome, such as an all-failure group or an all-success group, then the standard deviation is zero and A E (τ i ) = 0. For context-relative normalization, the group is G S (es), and the normalized values are completion-aware returns R i,t from comparable decision contexts. If the context group has fewer than two usable transitions or has zero variance, then A S (a i,t ) = 0. These conventions avoid introducing artificial preference when the sampled group contains no distinguish- able outcome or return signal. B.3 Action and Token Conventions An interaction step is an environment-facing decision point, whereas a token is an autoregressive generation unit. The variable a i,t denotes the complete agent action emitted at interaction step t, not a single token. In the experiments, the model generates reasoning in <think> tags and the executable command in <action> tags. The environment transition ξ i,t is induced by the executable action and the subsequent observable environment feedback. For each interaction step, TRCA computes one scalar transition advantage for the complete environment action. During token-level policy optimization, this advantage is broadcast only to the generated executable tokens inside the <action>...</action> span. Reasoning tokens in- side <think>...</think>, prompt tokens, observation tokens, retrieved-content tokens, padding tokens, and tokens belonging to other interaction steps are masked out. C Detailed TRCA Reward Construction This section provides additional details for the two transition- level reward components introduced in the main paper. The construction follows the same notation and formulas. C.1 Foundational Rubric Reward For rubric itemj at transition (i,t), TRCA defines the signed item-level contribution q i t,j = + r Evi M Evi , j ∈R Evi (x), O i,t,j = 1, − |r Inval | M Inval , j ∈R Inval (x), O i,t,j = 1, + r Exec M Exec , j ∈R Exec (x), O i,t,j = 1, 0,otherwise, (9) where M c = |R c (x)| is the number of rubric items in cat- egory c. Evidence and Execution contribute positive credit, while Invalidity contributes negative credit. If no rubric item is supported by observable transition evidence, then all cor- responding item contributions are zero. The Foundational Rubric Reward aggregates all item-level contributions at the same transition: r F i,t = X j∈R(x) q i t,j .(10) A transition may satisfy more than one rubric item, so Equa- tion (10) sums over all triggered Evidence, Invalidity, and Execution judgments. Dividing each category budget by M c bounds the magnitude of that category’s aggregate contribu- tion at any transition by its predefined reward budget. Con- sequently, the reward scale does not grow simply because a benchmark uses a longer rubric list. Foundational Rubric Reward evaluates the current tran- sition locally. The same rubric item can contribute at mul- tiple steps if distinct transitions repeatedly provide observ- able support for that item. This local behavior is intentional: Foundational Rubric Reward supplies broad transition-level supervision over informative, invalid, and task-relevant ac- tions, while Breakthrough Rubric Reward, defined next, sep- arately tracks newly covered positive conditions. C.2 Breakthrough Rubric Reward To distinguish newly achieved progress from repeatedly ob- served evidence, TRCA defines the cumulative coverage of item j as C i,t,j = max 1≤k≤t O i,k,j , C i,0,j = 0.(11) The cumulative potential over positive rubric items is Φ i,t = X c∈Evi,Exec r c M c X j∈R c (x) C i,t,j .(12) Invalidity items are excluded from this positive potential be- cause they describe transition-local errors and are already pe- nalized by Foundational Rubric Reward. Under the coverage definition in Equation (11), Φ i,t is monotone nondecreasing in t, assuming nonnegative Evidence and Execution budgets. The Breakthrough Rubric Reward is the temporal differ- ence of this cumulative potential: r B i,t = Φ i,t − Φ i,t−1 .(13) Equivalently, r B i,t = X c∈Evi,Exec r c M c X j∈R c (x) (1− C i,t−1,j )O i,t,j . (14) Thus, rubric item j contributes to r B i,t only when the cur- rent transition satisfies that item and no earlier transition in the same rollout has covered it. Already covered items do not receive repeated Breakthrough Rubric Reward. Since the potential is cumulative and uses a maximum over previous judgments, the current BRR definition does not introduce a coverage-regression penalty. When Evidence and Execution budgets are nonnegative, r B i,t ≥ 0, and the cumulative BRR over a rollout is bounded by r Evi + r Exec . C.3 Reward Fusion The two reward components are combined as r TRCA i,t = (1− λ)r F i,t + λr B i,t , λ∈ [0, 1].(15) Here, λ controls the trade-off between local broad super- vision and newly covered positive rubric progress. When λ = 0, TRCA uses only Foundational Rubric Reward. When λ = 1, it uses only Breakthrough Rubric Reward. We set λ = 0.8 in all experiments unless otherwise specified. Foundational Rubric Reward provides both positive and negative local supervision, including penalties for Invalidity. Breakthrough Rubric Reward highlights transitions that in- troduce previously uncovered Evidence or Execution condi- tions. Their convex combination preserves the method’s two intended sources of transition-wise credit without requiring successful anchors or learned process evaluators. D Training Algorithm and Policy Optimization D.1 Completion-Aware Return The environment reward is typically sparse in the paper’s long-horizon settings: r i,t = 0 for nonterminal steps and the Table 4: Symbolic illustration of TRCA reward construction. The example uses symbolic budgets and does not report an experimental trajectory. StepTransition evidenceTriggered judgmentsReward computation 1The agent inspects a receptacle and observes the apple. O 1,e loc = 1.r F 1 = r Evi /M Evi . Coverage changes from 0 to 1 for e loc , so r B 1 = r Evi /M Evi . 2The agent takes the apple.O 2,u take = 1.r F 2 = r Exec /M Exec . The itemu take is newly covered, so r B 2 = r Exec /M Exec . 3The agent repeats an observation that supports e loc . O 3,e loc = 1.r F 3 = r Evi /M Evi . Since C 2,e loc = 1, the repeated item gives r B 3 = 0. 4The environment rejects a mal- formed command. O 4,v bad = 1.r F 4 = −|r Inval |/M Inval . Invalidity is ex- cluded from Φ, so r B 4 = 0. terminal transition receives the task outcome R(τ i ). TRCA augments this sparse environment reward with the transition- level rubric signal for constructing the final reward: R i,t = T i X k=t γ k−t r i,k + r TRCA i,k .(16) The return starts at the current interaction step and accumu- lates future terminal and transition-level signals. We use a discount factor of γ = 0.95 in all experiments. The terminal outcome is included through the original en- vironment rewardr i,k , while TRCA adds separate transition- level supervision throughr TRCA i,k . The construction therefore does not duplicate the terminal reward; it combines the sparse completion signal with observable action-induced transition evidence before relative advantage normalization. D.2 Zero-Variance Rollout Groups For a rollout group G(x) = τ i N i=1 , the episode-relative advantage is computed from terminal outcomes: A E (τ i ) = R(τ i )− μ G σ G + ε norm , σ G > 0, 0,σ G = 0, (17) where μ G and σ G denote the mean and standard deviation of terminal outcomes within the rollout group. Zero variance occurs when sampled rollouts in the group have indistinguishable terminal outcomes. This includes all- failure groups, where every rollout has R(τ i ) = 0, and all- success groups, where every rollout has R(τ i ) = 1. In either case, terminal outcomes provide no within-group preference, so TRCA sets A E (τ i ) = 0 instead of amplifying numerical noise. The step-level transition supervision then becomes the primary differentiating signal. This convention does not imply that every failed rollout is identical in its intermediate behavior; it only states that terminal outcomes alone cannot rank rollouts inside a zero-variance group. D.3 Context-Based Step Grouping Following the standard group-in-group formulation, transi- tions arising from comparable decision contexts are consis- tently assigned to the same step-level group: G S (es) =(i,t)| s i,t ≃ es, 1≤ i≤ N, 1≤ t≤ T i . (18) The relation s i,t ≃ es indicates that the decision context is comparable under environment-specific state information. It is used exclusively for relative normalization of completion- aware returns, rather than as a successful anchor or any ad- ditional independent reward source. The grouping need not be exact textual matching. It can use structural fields exposed by the environment, such as page type, product identity, selected options, task predicates, object state, inventory, tool type, query state, or retrieval stage. Appendix F.3 lists the benchmark-specific fields used at this level of description. Context grouping uses only ob- servable benchmark-specific state fields and does not require embedding models, learned state encoders, or additional on- line LLM inference. The context-relative step advantage is A S (a i,t ) = R i,t − μ G S σ G S + ε norm , σ G S > 0, 0,σ G S = 0, (19) where the mean and standard deviation are computed over the completion-aware returns in the corresponding context group used for the current comparison. If a group is too small to support comparison or has zero variance, TRCA simply sets the corresponding step advantage to zero. The final combined advantage is A TRCA i,t = A E (τ i ) + A S (a i,t ).(20) D.4 Action-Level Policy Optimization TRCA treats the complete environment-facing action as the credit-assignment and policy-optimization unit. For rollout i at interaction step t, let a i,t denote the complete executable action generated under states i,t and task instructionx. TRCA assigns one scalar transition advantageA TRCA i,t to this action. The corresponding action-level importance ratio as follows. ρ i,t (θ) = π θ (a i,t | s i,t ,x) π θ old (a i,t | s i,t ,x) .(21) During optimization, the transition advantage is associated only with the executable action produced at the correspond- ing interaction step. Prompt tokens, environment observa- tions, retrieved content, padding tokens, and tokens belong- ing to other interaction steps are excluded from this action- level update to preserve precise step-wise credit assignment. Using the rollout group G(x) = τ i N i=1 , the clipped action-level objective is J TRCA (θ) =E h 1 N N X i=1 1 T i T i X t=1 min ρ i,t (θ)A TRCA i,t , clip(ρ i,t (θ), 1− ε, 1 + ε)A TRCA i,t i −β KL D KL (π θ ||π ref ) (22) Here, T i is the number of environment interaction steps in rollouti,ε is the PPO-style clipping coefficient, andβ KL con- trols regularization toward the reference policy. Each term indexed by t corresponds to one complete action-induced transition and receives the trajectory-level outcome advan- tage and transition-wise rubric signals. Although the underlying language model generates an ac- tion autoregressively, TRCA does not assign separate credit to individual tokens within the same environment action. Instead, all executable action tokens belonging to the same interaction step are treated as realizing the same action a i,t and share the corresponding scalar transition advantage. This action-level formulation is consistent with the objective pre- sented in the main text. D.5 Training Procedure Algorithm 1 summarizes the complete TRCA training proce- dure. For each rollout group, TRCA evaluates action-induced transitions using deterministic rubric operators, constructs Foundational and Breakthrough Rubric Rewards, and com- bines them with terminal outcomes to obtain action-level advantages for policy optimization. We next analyze the resulting credit signals in terms of boundedness, novel-coverage preference, behavior in zero- success groups, and conditional variance. D.6 Theoretical Properties of TRCA Credit Assignment This section establishes several theoretical properties of the transition-wise credit signals constructed by TRCA. We first show that the rubric rewards are bounded by the predefined category budgets and that Breakthrough Rubric Reward can- not accumulate through repeated satisfaction of the same rubric items. We then show that TRCA monotonically favors newly covered task-relevant conditions, retains discrimina- tive step-level credit in zero-success rollout groups, and pro- vides lower-variance local feedback than trajectory-outcome attribution throughout the policy optimization process. Notation and assumptions. Let the positive rubric set be defined as R + (x) =R Evi (x)∪R Exec (x),(23) which collects all Evidence and Execution items. For each j ∈ R c (x), we define its normalized category-specific weight as the following context w j = r c M c , M c =|R c (x)|.(24) We assume that each category contains at least one valid rubric item and that the transition evaluation operator is fully Algorithm 1: Training TRCA Require: Policyπ θ , old policyπ θ old , task distributionp(X ), benchmark-level operator libraries T b , deterministic task binders B b,m , benchmark adapters g b , rollout group size N, discount γ, and mixing coefficient λ. 1: for each training iteration do 2: Sample a batch of task instances x∼ p(X ). 3: Deterministically bind the operators inT b to each task x, constructingR(x). 4: For each task instance, sample a rollout group of N trajectories using π θ old . 5: Collect terminal environment outcomes R(τ i ) for all rollouts. 6: Initialize rubric coverage C i,0,j = 0 for all positive Evidence and Execution items. 7: for each rollout τ i do 8:for each transition ξ i,t do 9:Extract canonical observable facts using g b (s i,t ,a i,t ,s i,t+1 ). 10:EvaluateO i,t,j for all j ∈R(x) using the bound deterministic operators. 11:Compute r F i,t using Equation (10). 12:Update coverage C i,t,j using Equation (11). 13:Compute r B i,t using Equation (14). 14:Compute r TRCA i,t using Equation (15). 15:end for 16: end for 17: Construct comparable context groupsG S (es). 18: Compute completion-aware returns R i,t using Equa- tion (16). 19: Compute episode-relative advantages A E (τ i ). 20: Compute context-relative step advantages A S (a i,t ). 21: Construct final advantages A TRCA i,t . 22: Optimize π θ with the clipped action-level objective. 23: Update π θ old ← π θ before the next rollout collection phase. 24: end for deterministic given the corresponding observable action- induced transition. These assumptions are fully consistent with the rule-based transition evaluation adopted by TRCA. Proposition 1 (Rubric-budget boundedness and non- accumulation). Let B + = r Evi + r Exec , B − = r Inval .(25) For every rollout i and transition t, the reward components of TRCA satisfy −B − ≤ r F i,t ≤ B + ,0≤ r B i,t ≤ B + ,(26) and consequently −(1− λ)B − ≤ r TRCA i,t ≤ B + .(27) Moreover, the cumulative Breakthrough Rubric Reward is bounded independently of the rollout horizon: T i X t=1 r B i,t = Φ i,T i ≤ B + .(28) Proof of Proposition 1. For each positive category c ∈ Evi, Exec, its aggregate contribution at transition (i,t) satisfies the following constraints 0≤ r c M c X j∈R c (x) O i,t,j ≤ r c ,(29) because O i,t,j ∈ 0, 1 and M c = |R c (x)|. Similarly, the aggregate Invalidity contribution satisfies −B − ≤− B − N Inval X j∈R Inval (x) O i,t,j ≤ 0.(30) Summing the category-wise contributions gives the bound on r F i,t . Breakthrough Rubric Reward contains only newly covered positive rubric items: r B i,t = X c∈Evi,Exec r c M c X j∈R c (x) (1− C i,t−1,j )O i,t,j . (31) Every term in Equation (31) is non-negative, and the aggre- gate contribution of each category c is at most r c . Therefore, 0≤ r B i,t ≤ B + . Since r TRCA i,t = (1− λ)r F i,t + λr B i,t , λ∈ [0, 1],(32) the lower bound follows by combining the minimum possible Foundational Rubric Reward with zero breakthrough credit, while the upper bound follows because both r F i,t and r B i,t are upper bounded by B + . Finally, since r B i,t = Φ i,t − Φ i,t−1 and Φ i,0 = 0, the cumulative reward telescopes: T i X t=1 r B i,t = T i X t=1 (Φ i,t − Φ i,t−1 ) = Φ i,T i .(33) Each positive rubric item contributes to Φ i,T i at most once, and the total contribution of category c is at most r c . Hence, Φ i,T i ≤ B + . Thus, cumulative breakthrough credit is inde- pendent of rollout length and cannot grow through repeated satisfaction of previously covered rubric items. Proposition 2 (Monotonicity with respect to novel rubric coverage). Consider two transition occurrences u = (i,t) andv = (i ′ ,t ′ ) evaluated under the same task instruction and grounded rubric set R(x). Let O u,j and O v,j denote their current rubric judgments, and define their prior coverage states as C − u,j = C i,t−1,j , C − v,j = C i ′ ,t ′ −1,j .(34) Suppose that the two transitions produce identical current rubric judgments: O u,j =O v,j , ∀j ∈R(x).(35) Assume further that C − u,j ≤ C − v,j , ∀j ∈R + (x),(36) and that there exists at least one currently satisfied positive item j ⋆ such that O u,j ⋆ =O v,j ⋆ = 1, C − u,j ⋆ = 0, C − v,j ⋆ = 1. (37) Then r B u > r B v .(38) Consequently, for every λ > 0, r TRCA u > r TRCA v .(39) Proof of Proposition 2. Because the current rubric judg- ments are identical, their signed item-level contributions are identical, and therefore r F u = r F v .(40) Using the expanded definition of Breakthrough Rubric Re- ward andO u,j =O v,j , we obtain r B u − r B v = X c∈Evi,Exec r c M c X j∈R c (x) C − v,j − C − u,j O u,j . (41) Every summand is non-negative by Equation (36). More- over, the summand associated with j ⋆ is strictly positive by Equation (37). Hence, r B u − r B v > 0. The difference between the combined TRCA rewards is r TRCA u − r TRCA v = (1− λ)(r F u − r F v ) + λ(r B u − r B v ) = λ(r B u − r B v ) > 0.(42) Thus, among transitions providing the same immediate rubric evidence, TRCA strictly prefers a transition that newly covers a task-relevant condition over one that merely repeats an already covered condition. Proposition 3 (Non-degenerate credit in zero-success roll- out groups). Consider a rollout group G(x) = τ i N i=1 whose terminal outcomes are identical: R(τ 1 ) = R(τ 2 ) =· = R(τ N ).(43) Then A E (τ i ) = 0, ∀i∈1,...,N.(44) In particular, this result holds when all sampled rollouts fail. Now consider a context group G S (es) containing at least two transitions. If the completion-aware returns in this group are not all identical, then the corresponding final TRCA ad- vantages are not all zero. More precisely, there exist transi- tions u,v ∈G S (es) such that A TRCA u > 0, A TRCA v < 0.(45) Proof of Proposition 3. Letμ G andσ G denote the mean and standard deviation of the terminal outcomes. Under Equa- tion (43), every terminal outcome equals the group mean and σ G = 0. By the normalization convention in Equation (17), A E (τ i ) = 0.(46) Let H = R j,k | (j,k)∈G S (es) (47) denote the set of completion-aware returns in the context group, and let μ H and σ H denote its mean and standard deviation. Since the returns are not all identical, minH < μ H < maxH.(48) Hence, there exist transitions u and v satisfying R u > μ H and R v < μ H . Since σ H + ε norm > 0, normalization pre- serves their signs: A S u = R u − μ H σ H + ε norm > 0, A S v = R v − μ H σ H + ε norm < 0. (49) The final TRCA advantage is A TRCA i,t = A E (τ i ) + A S (a i,t ). Since A E (τ i ) = 0 for every rollout in the group, A TRCA u = A S u > 0, A TRCA v = A S v < 0.(50) Therefore, whenever rubric-enhanced completion-aware re- turns distinguish actions arising from the same decision con- text, TRCA provides discriminative positive and negative credit even when the rollout group contains no successful trajectory throughout early-stage policy optimization and ex- ploration under otherwise success-sparse training conditions. Proposition 4 (Conditional variance reduction of transition-wise feedback). Consider rollouts sampled from a fixed policy π. Define the augmented local transi- tion information as Z i,t = (x,t,ξ i,t ,C i,t−1 ),(51) where ξ i,t = (s i,t ,a i,t ,s i,t+1 ), C i,t−1 =C i,t−1,j j∈R + (x) . (52) Let the local TRCA feedback be X TRCA i,t = r TRCA i,t , and let the trajectory-outcome feedback be X E i,t = R(τ i ), where R(τ i ) ∈ 0, 1. Under deterministic rule-based transition evaluation, for every z visited with positive probability, Var X TRCA i,t | Z i,t = z ≤ Var X E i,t | Z i,t = z . (53) The inequality is strict whenever both successful and failed continuations occur with positive probability conditioned on Z i,t = z. Proof of Proposition 4. Under deterministic transition evaluation, each rubric judgment is a deterministic function of the observable transition: O i,t,j = h c b,m (ω b,m (x),g b (ξ i,t )), j = (h c b,m ,ω b,m (x)). (54) Consequently, Foundational Rubric Reward r F i,t = P j∈R(x) q i t,j is fixed once Z i,t = z is given. Since Z i,t also contains the prior coverage stateC i,t−1 , Breakthrough Rubric Reward r B i,t = X c∈Evi,Exec r c M c X j∈R c (x) (1− C i,t−1,j )O i,t,j (55) is also fixed conditioned on Z i,t = z. Therefore, r TRCA i,t is a deterministic function of Z i,t , yielding Var X TRCA i,t | Z i,t = z = 0.(56) Define the conditional success probability as p z = Pr (R(τ i ) = 1| Z i,t = z).(57) Since R(τ i ) is binary, its conditional first and second mo- ments are both equal to p z . Therefore, Var X E i,t | Z i,t = z = p z − p 2 z = p z (1− p z )≥ 0. (58) Combining Equations (56) and (58) proves Equation (53). If both successful and failed continuations have positive conditional probability, then 0 < p z < 1 andp z (1−p z ) > 0. It follows that Var X TRCA i,t | Z i,t = z < Var X E i,t | Z i,t = z . (59) Thus, after the observable transition and prior rubric cover- age are fixed, TRCA provides deterministic local feedback, whereas trajectory-outcome attribution remains affected by subsequent policy decisions. Scope of the analysis. The above results characterize the boundedness, novel-coverage preference, non-degeneracy, and conditional variance of the transition-level credit sig- nals constructed by TRCA. Proposition 4 concerns the local transition feedback before context-relative normalization. It does not imply that the complete normalized advantage or the resulting policy-gradient estimator necessarily has zero or uniformly lower variance. The analysis also does not as- sume that TRCA is an unbiased estimator of an unknown optimal advantage function or claim policy invariance under reward shaping within the present theoretical scope. E Diagnostic Study Protocol E.1 Rollout Collection The diagnostic study is conducted on ALFWorld and Web- Shop using Qwen2.5-1.5B-Instruct during the early stage of reinforcement learning. Each diagnostic batch contains 16 task instances with a rollout group size of 8, yielding 128 rollouts per batch. A failed rollout is defined as a rollout with terminal outcome R(τ i ) = 0. A success-free group is a task-conditioned rollout group in which none of the sampled rollouts achieves terminal success. The reported percentages are aggregate averages across multiple diagnostic batches and benchmarks rather than counts computed from a single 128-rollout batch under one experimental configuration. The diagnostic analysis reports three aggregate statistics: 96.5% of sampled rollouts fail to achieve terminal success, 85.6% of task-conditioned rollout groups contain no success- ful trajectory, and 72.2% of actions in failed rollouts retain diagnostically useful transition signals. E.2 Transition Annotation The annotation unit is an action-induced transition ξ i,t = (s i,t ,a i,t ,s i,t+1 ), rather than a complete trajectory. We an- notate the collected transitions using human assessment to- gether with GPT-4o as the frontier LLM judge. The diagnostic labels distinguish Evidence, Execution, Validity, and Other. Evidence identifies transitions that reveal task-relevant information. Execution identifies tran- sitions that complete a substantive task-required operation or intermediate condition. Validity identifies transitions whose actions are successfully parsed and executed, even when they do not immediately complete a subgoal. Other denotes transitions without a useful signal under the diag- nostic annotation protocol. This LLM-assisted annotation is used only for the diag- nostic analysis reported in Figure 1 and is never used to construct transition rewards during TRCA training. During policy optimization, all rubric judgments are computed by the deterministic benchmark-level operators described in Ap- pendix A.3, without any additional online model inference. E.3 Calculation of Reported Ratios The reported ratios use different denominators. We define FailureRate = N fail /N rollout , SuccessFreeGroupRate = N sf_group /N group , UsefulTransitionRate = N fail useful /N fail action . (60) In the main text, these correspond to 96.5%, 85.6%, and 72.2%, respectively. The first two are rollout-level or group- level statistics. The third is an action-level statistic computed only over actions in failed rollouts. A useful action is one an- notated as providing Evidence, Execution, or Validity under the diagnostic annotation categories. E.4 Annotation Categories and Quality Control Evidence, Execution, Validity, and Other serve only the di- agnostic study. Validity is complementary to the Invalidity rubric used during TRCA reward construction: a valid ac- tion is successfully parsed and executed, whereas Invalidity captures malformed, inadmissible, rejected, or otherwise un- executable actions and contributes negative reward. Quality control requires separating diagnostic annotation from training-time reward evaluation. Human annotation and the frontier LLM judge are used to analyze the motivating failure-scarce regime, while TRCA training does not use an online LLM judge at any stage of policy optimization. F Experimental Details F.1 Models and Rollout Configuration For ALFWorld and WebShop, the experiments use Qwen2.5- 1.5B-Instruct and Qwen2.5-7B-Instruct as policy models. For SearchQA, we use Qwen2.5-3B-Instruct and Qwen2.5- 7B-Instruct. All group-based methods use rollout group size N = 8. The agent emits reasoning within <think> tags and its executable action within <action> tags. Unless otherwise specified, the mixing coefficient between Founda- tional Rubric Reward and Breakthrough Rubric Reward is λ = 0.8. For the ALFWorld training configuration, the max- imum number of interaction steps is 25, the rollout tempera- ture is 1.0, and the maximum response length is 512 tokens. To complement the numerical results reported in the main tables, Figure 6 provides an overall view of the performance profiles of TRCA and representative baselines across bench- marks and model scales. The first two panels summarize ALFWorld subtask performance together with the WebShop task score and success rate, while the last two panels sum- marize results on the seven SearchQA benchmarks and their average. TRCA maintains a consistently strong and balanced profile, indicating that its improvements are not concentrated on a single task category or model scale. Table 5: Core reinforcement-learning hyperparameters used in the experiments. HyperparameterValue Learning rate8× 10 −7 Rollout group size N8 PPO mini-batch size256 PPO micro-batch size per GPU32 Discount factor γ0.95 PPO clipping coefficient (lower)0.20 PPO clipping coefficient (upper)0.28 KL regularization coefficient0.012 Entropy coefficient0.001 Rollout temperature1.0 Maximum response length512 TRCA mixing coefficient λ0.8 F.2 Training Hyperparameters Table 5 summarizes the core hyperparameters used for rein- forcement learning. Engineering parameters related to dis- tributed execution, logging, and checkpoint management are omitted for clarity. F.3 Benchmark-Specific Context Grouping Context grouping uses observable, benchmark-specific state information to compare actions taken under similar decision contexts. It is used for computing the context-relative step advantage and does not depend on successful terminal states. The grouping is structural rather than purely lexical: exact textual equality is not required when the environment ex- poses equivalent structured state fields. If a context group has fewer than two comparable transitions or has zero variance in completion-aware returns, the corresponding A S (a i,t ) is set to zero. Context grouping is implemented using determin- istic structural fields exposed by each environment, without embedding-based clustering, learned state encoders, or ad- ditional LLM inference. F.4 Datasets and Evaluation Protocols ALFWorld is evaluated with success rate. The main table reports the five ALFWorld task categories Clean, Pick, Cool, Heat, and Pick2, together with the overall success rate. Web- Shop is evaluated with both task score and success rate: task score captures partial attribute satisfaction, while success rate captures exact task completion. SearchQA includes seven datasets: Natural Questions (NQ), TriviaQA, PopQA, HotpotQA, 2WikiMultiHopQA (2Wiki), MuSiQue, and Bamboogle. NQ and HotpotQA are treated as in-domain benchmarks; TriviaQA, PopQA, 2Wiki, MuSiQue, and Bamboogle are treated as out-of- domain benchmarks. SearchQA reports performance using strict binary normalized Exact Match, counting an example as successful only when its normalized final answer exactly matches one of the provided ground-truth aliases. 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. Table 6: Observable context information used to define comparable decision contexts. BenchmarkComparable-context information ALFWorldTask predicates, object state, inventory, object location, and interaction stage. WebShopPage type, product identity, selected options, product attributes, and navigation stage. SearchQATool type, retrieval stage, query state, evidence stage, and answer-submission stage. F.5 Baseline Configuration and Comparison Protocol The main experiments compare TRCA with closed-source prompting baselines, prompting-based agents, and RL train- ing methods. The closed-source baselines are GPT-4o and Gemini-2.5-Pro. Prompting-based agents include Qwen2.5, ReAct, and Reflexion. RL baselines for ALFWorld and WebShop include PPO, RLOO, GRPO, GiGPO, HCAPO, and GraphGPO. For SearchQA, the compared methods are R1-Instruct, Search-R1, ZeroSearch, StepSearch, GiGPO, HCAPO, IGPO, and TRCA. For SearchQA, we follow the training and evaluation protocol of GiGPO. For ALFWorld and WebShop, we evaluate all methods under the Qwen2.5- 1.5B-Instruct and Qwen2.5-7B-Instruct settings. F.6 Sample-Efficiency Evaluation Protocol Figure 4 reports sample efficiency on the ALFWorld Pick_two and Pick_cool subtasks using Qwen2.5-1.5B- Instruct. The counting unit is a sampled trajectory, i.e., a complete rollout. In general, N traj = N iterations ×N tasks/iteration ×N rollouts/task . (61) We count each completed rollout as one sampled trajectory. The reported aggregate budgets are 1.92K, 3.84K, and 6.40K sampled trajectories over the complete evaluation process. In addition to the subtask-level comparison reported in the main text, Figure 7 presents the aggregate sample-efficiency results on ALFWorld and WebShop under matched rollout budgets. TRCA consistently achieves higher success rates than GRPO across all reported budgets, with gains of up to 19.5 percentage points on ALFWorld and 18.8 percent- age points on WebShop. The performance gap emerges early and remains visible as the sampling budget increases, show- ing that transition-wise rubric rewards extract more effective supervision from the same amount of agent–environment in- teraction. At 1.92K sampled trajectories, TRCA improves Pick_two success rate from 11.5% to 34.6% and Pick_cool success rate from 15.0% to 24.0% relative to GRPO un- der the same budget. On Pick_two, TRCA reaches 69.2% success rate with 3.84K trajectories, exceeding the 46.7% achieved by GRPO with 6.40K trajectories. On Pick_cool, TRCA reaches 53.8% with 3.84K trajectories, approaching the 57.7% GRPO result at 6.40K trajectories. The statement that TRCA uses 40% fewer samples follows from 1− 3.84K 6.40K = 0.40. F.7 Random Seeds and Reporting Results on ALFWorld and WebShop are averaged over three random seeds. Table 1 shows the standard deviation of the results from three runs. Figure 8 further reports the train- ing and validation success rates of TRCA on ALFWorld and WebShop. In both environments, the validation curves gen- erally follow the improvement of the corresponding training curves, without pronounced divergence during optimization. This agreement provides a qualitative check that observed training gains are reflected in evaluation performance. Experiments are conducted on four NVIDIA A800 80GB GPUs. The method itself does not require online LLM- judge inference for rubric evaluation during policy train- ing. Benchmark-level operator libraries are constructed once offline; deterministic task binders then instantiate task- grounded rubric items, and transition judgments are com- puted from observable environment feedback without addi- tional LLM calls. This distinguishes TRCA training from the diagnostic study, where human annotation and a frontier LLM judge are used only to analyze the motivating regime. (a) ALFWorld: success rate 0 20 40 60 80 100 5.12K10.24K15.36K19.20K Q w e n 2 . 5 - 1 . 5 B - I n s t r u c t s u c c e s s r a t e ( % ) Sampled trajectories (K) Ours GRPO 30.5 27.3 +3.1 59.4 39.8 +19.5 64.1 59.4 +4.7 76.6 71.9 +4.7 (b) WebShop: success rate 0 20 40 60 80 100 5.12K10.24K15.36K19.20K Q w e n 2 . 5 - 1 . 5 B - I n s t r u c t s u c c e s s r a t e ( % ) Sampled trajectories (K) Ours GRPO 28.1 40.6 +12.5 49.2 64.8 +15.6 53.9 72.7 +18.8 57.0 72.7 +15.6 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 effi- ciency under identical interaction and optimization settings. To examine whether the optimization gains transfer from the sampled training tasks to held-out evaluation tasks, Fig- ure 9 compares the training and validation success-rate tra- jectories of TRCA and GRPO throughout optimization. In Figure 9(a), TRCA exhibits a pronounced early-stage advan- tage on ALFWorld. Its training and validation performance rises rapidly within the first several dozen updates, reaching a high-success regime substantially earlier than GRPO. By contrast, GRPO remains near the low-performance region during the initial stage and improves only gradually after- ward. Although the training curves of both methods contain stochastic fluctuations, the validation trajectory of TRCA re- mains consistently above that of GRPO over most of the training process, indicating both faster convergence and a higher held-out performance level. The gap persists into the later stage, where TRCA maintains success rates around the upper performance range, whereas GRPO continues to im- prove more slowly and converges at a lower level. Figure 9(b) shows a similar, though more gradual, pat- tern on WebShop. The two methods begin from compa- rable low success rates and improve steadily during early optimization. After approximately the first third of training, however, TRCA begins to establish a persistent advantage in both the training and validation curves. This advantage be- comes clearer during the middle and late stages, where TRCA generally reaches higher success rates and retains a stronger validation trajectory despite occasional step-level fluctua- tions. In both panels, the validation curves closely follow the Figure 8: Training and validation success rates of TRCA on ALFWorld and WebShop. 0 20 40 60 80 100 050100150 (a) ALFWorld success rate (%) Training Steps 050100150 (b) WebShop success rate (%) Training Steps Qwen2.5-1.5B Success rate (%) Ours train Ours val GRPO train GRPO val Figure 9: Training and validation success rates of TRCA and GRPO on WebShop and ALFWorld. TRCA converges faster and achieves stronger performance, on ALFWorld. overall trends of their corresponding training curves without persistent divergence. These results suggest that TRCA not only learns more rapidly from the sampled rollouts, but also achieves stronger final success rates and more stable behav- ior than GRPO. The consistent ordering between training and held-out performance further indicates that the optimization gains are not confined to the sampled training instances, but transfer reliably to unseen evaluation tasks. G Rubric Generation Prompt and Complete Libraries Before policy training, an LLM is invoked once for each benchmark to construct a shared rubric operator library. The prompt specifies five deterministic Boolean operators for each of three categories: Evidence, which detects newly re- vealed task-relevant information; Invalidity, which detects malformed, rejected, repeated, or otherwise unexecutable ac- tions; and Execution, which detects accepted task-required operations, achieved subgoals, or satisfied intermediate con- ditions. Each operator specifies the observable facts it reads and an exact Boolean activation condition based only on the task instruction and the action-induced transition. Miss- ing, ambiguous, or unsupported observable evidence pro- duces a zero judgment. Successful trajectories, terminal out- comes, future states, and ground-truth answers are not used to evaluate intermediate transitions. The resulting operator library is shared across all task instances within the same benchmark, while task-specific entities, attributes, relations, and constraints are supplied through deterministic parameter binding. Once these bindings are established, the grounded operators are applied deterministically to every transition during rollout collection and policy optimization without fur- ther LLM calls. This design also keeps the overall evaluation procedure consistent and reproducible across task instances. Prompt Template for ALFWorld You are an expert agent operating in the ALFRED Embodied Environment. Your task is to: task_description. Prior to this step, you have already taken step_count step(s). Below are the most recent history_length observations and the corresponding actions you took: action_history. You are now at step current_step and your current observation is: current_observation. Your admissible actions are listed below. Each line is one complete valid action: admissible_actions. Now choose the single best action for this step. First output one <think> </think> block with brief English reasoning. Then output exactly one <action> </action> block. The text inside <action> must be copied verbatim from exactly one line in the admissible actions list. Do not invent, translate, summarize, or modify the action. Prompt Template for WebShop You are an expert autonomous agent operating in the WebShop e-commerce environment. Your task is to: task_description. Prior to this step, you have already taken step_count step(s). Below are the most recent history_length observations and the corresponding actions you took: action_history. You are now at step current_step and your current observation is: current_observation. Your admissible actions for the current situation are: [available_actions]. Now it's your turn to take one action for the current step. You should first reason step-by-step about the current situation, then think carefully which admissible action best advances the shopping goal. This reasoning process MUST be enclosed within <think> </think> tags. Once you've finished your reasoning, you should choose an admissible action for current step and present it within <action> </action> tags. Prompt Template for Search You are an expert agent tasked with answering the given question step-by-step. Your question: task_description. Prior to this step, you have already taken step_count step(s). Below is the interaction history where <search> </search> wrapped your past search queries and <information> </information> wrapped the corresponding search results returned by the external search engine. History: memory_context. Now it's your turn to respond for the current step. You should first conduct reasoning process. This process MUST be enclosed within <think> </think> tags. After completing your reasoning, choose only one of the following actions: if you lack some knowledge, call a search engine using <search> your query </search>; if you have enough knowledge to answer the question confidently, provide your final answer within <answer> </answer> tags, without detailed illustrations. Figure 10: Prompt templates used for ALFWorld, WebShop, and search-augmented QA agents. Task. In ALFWorld, find two pencils and put them in a drawer. Success Condition. Two distinct pencils are placed in the same drawer. <EVIDENCE> A post-transition observation newly contains an object ID matching pencil [0-9]+ with a current-location field. <EVIDENCE> A post-transition observation newly contains a second pencil [0-9]+ ID different from the first discovered pencil ID. <EVIDENCE> The current observation or location string contains an available drawer [0-9]+ ID that can bind the target receptacle. <EVIDENCE> After the first placement, the selected drawer observation contains the first placed pencil ID. <EVIDENCE> A revisited searched location contains no uncollected object ID matching pencil [0-9]+ after excluding held or already placed pencils. <INVALIDITY> The action string fails the ALFWorld parser patterns go to <object>, take <object> from <receptacle>, move <object> to <receptacle>, open <object>, close <object>, heat <object> with <object>, cool <object> with <object>, clean <object> with <object>, or examine <object>. <INVALIDITY> At least one referenced object or receptacle ID is absent from the current observation object list or admissible-action set. <INVALIDITY> A rule precondition is false: go target not reachable; take object not at source; move object not in inventory; or destination receptacle unavailable. <INVALIDITY> The environment returns an explicit failure string, rejection status, or exception for the attempted operation. <INVALIDITY> The normalized action equals the previous action under the same normalized observation/inventory signature, or an action expected to change location/inventory/object placement leaves those fields unchanged. <EXECUTION> An accepted go to <location> changes current_location to an ID in the bound candidate set desk 1, sidetable 1, drawer 1. <EXECUTION> An accepted take action adds the first discovered pencil ID to inventory. <EXECUTION> An accepted move action changes location(first_pencil_id) from inventory to selected_drawer_id. <EXECUTION> An accepted take action adds a second discovered pencil ID, different from the first, to inventory. <EXECUTION> An accepted move action changes location(second_pencil_id) from inventory to selected_drawer_id while first_pencil_id is also in Rubrics selected_drawer_id. Environment (ALFWorld, Step 1) -= Welcome to TextWorld, ALFRED! =- You are in the middle of a room. Looking quickly around you, you see a bed 1, a desk 1, a drawer 2, a drawer 1, a garbagecan 1, a shelf 1, and a sidetable 1. Your task is to: find two pencil and put them in drawer. Response (ALFWorld, Step 1) Agent response recorded in rollout: <action>go to desk 1</action> Transition Judgment (ALFWorld, Step 1) Transition alignment. This judgment uses the navigation action and the next observation at desk 1. Evidence: +1, the post-transition observation newly contains pencil 2 with current location desk 1. Invalidity: 0, desk 1 is visible and the navigation action is parseable and accepted. Execution: +1, current_location changes to desk 1, which is in the bound candidate set. Dimension score: +2 Environment (ALFWorld, Step 2) You arrive at desk 1. On the desk 1, you see a bowl 1, a cd 1, a desklamp 1, a houseplant 1, a laptop 1, and a pencil 2. Response (ALFWorld, Step 2) Agent response recorded in rollout: <action>take pencil 2 from desk 1</action> Transition Judgment (ALFWorld, Step 2) Transition alignment. This judgment uses the take action and the resulting inventory/state update. Evidence: +0, no new pencil [0-9]+ ID appears after the take transition. Invalidity: 0, pencil 2 is available on desk 1 and the take action is accepted. Execution: +1, inventory gains pencil 2. Dimension score: +1 Case Study of ALFWorld Environment (ALFWorld, Step 3) You pick up the pencil 2 from the desk 1. Response (ALFWorld, Step 3) Agent response recorded in rollout: <action>go to drawer 1</action> Transition Judgment (ALFWorld, Step 3) Transition alignment. This judgment uses the navigation action and the next observation at drawer 1. Evidence: +1, the observation/current location contains drawer 1 as an available receptacle ID. Invalidity: 0, drawer 1 is a known reachable object and the navigation action is accepted. Execution: +1, current_location changes to drawer 1, which is in the bound candidate set. Dimension score: +2 Environment (ALFWorld, Step 4) You arrive at drawer 1. On the drawer 1, you see a creditcard 3, a creditcard 1, and a keychain 2. Response (ALFWorld, Step 4) Agent response recorded in rollout: <action>move pencil 2 to drawer 1</action> Transition Judgment (ALFWorld, Step 4) Transition alignment. This judgment uses the placement action and the resulting drawer state. Evidence: +0, no new pencil [0-9]+ ID or new drawer [0-9]+ ID appears. Invalidity: 0, the agent holds pencil 2, drawer 1 exists, and the move action is accepted. Execution: +1, location(pencil 2) changes from inventory to drawer 1. Dimension score: +1 Environment (ALFWorld, Step 5) You move the pencil 2 to the drawer 1. Response (ALFWorld, Step 5) Agent response recorded in rollout: <action>go to desk 1</action> Transition Judgment (ALFWorld, Step 5) Transition alignment. This judgment uses the return navigation and the desk observation. Evidence: +1, the desk 1 observation contains no uncollected pencil [0-9]+ after excluding pencil 2. Invalidity: 0, the navigation action is parseable and accepted. Execution: +0, current_location changes but no inventory gain or placement for a second pencil occurs. Dimension score: +1 Environment (ALFWorld, Step 6) You arrive at desk 1. On the desk 1, you see a bowl 1, a cd 1, a desklamp 1, a houseplant 1, and a laptop 1. Response (ALFWorld, Step 6) Agent response recorded in rollout: <action>go to sidetable 1</action> Transition Judgment (ALFWorld, Step 6) Transition alignment. This judgment uses the navigation action and the next observation at sidetable 1. Evidence: +1, the post-transition observation newly contains pencil 4 and pencil 3 at sidetable 1. Invalidity: 0, sidetable 1 is visible and the navigation action is accepted. Execution: +1, current_location changes to sidetable 1, which is in the bound candidate set. Dimension score: +2 Environment (ALFWorld, Step 7) You arrive at sidetable 1. On the sidetable 1, you see an alarmclock 1, a pen 1, a pencil 4, and a pencil 3. Response (ALFWorld, Step 7) Agent response recorded in rollout: <action>take pencil 4 from sidetable 1</action> Transition Judgment (ALFWorld, Step 7) Transition alignment. This judgment uses the take action and the resulting inventory/state update. Evidence: +0, no new pencil [0-9]+ ID appears after the take transition. Invalidity: 0, pencil 4 is available on sidetable 1 and can be taken. Execution: +1, inventory gains pencil 4, whose ID differs from pencil 2. Dimension score: +1 Environment (ALFWorld, Step 8) You pick up the pencil 4 from the sidetable 1. Response (ALFWorld, Step 8) Agent response recorded in rollout: <action>go to drawer 1</action> Transition Judgment (ALFWorld, Step 8) Transition alignment. This judgment uses the navigation action and the next observation at drawer 1. Evidence: +1, the drawer 1 observation contains pencil 2 after the first placement. Invalidity: 0, drawer 1 remains reachable and the navigation action is accepted. Execution: +1, current_location changes to drawer 1, the selected_drawer_id. Dimension score: +2 Environment (ALFWorld, Step 9) You arrive at drawer 1. On the drawer 1, you see a creditcard 3, a creditcard 1, a keychain 2, and a pencil 2. Response (ALFWorld, Step 9) Agent response recorded in rollout: <action>move pencil 4 to drawer 1</action> Transition Judgment (ALFWorld, Step 9) Transition alignment. This judgment uses the final placement action and task-completion feedback. Evidence: +0, no new pencil [0-9]+ ID, drawer [0-9]+ ID, or eliminated location appears. Invalidity: 0, the agent holds pencil 4, drawer 1 exists, and the move action is accepted. Execution: +1, location(pencil 4) changes from inventory to drawer 1 while pencil 2 remains in drawer 1. Dimension score: +1 Environment (Final) You move the pencil 4 to the drawer 1. The task is completed: two distinct pencils are now in drawer 1. Case Summary Evidence-positive transitions: 5 / 9 Invalidity-triggered transitions: 0 / 9 Execution-positive transitions: 8 / 9 Case Study of SearchQA Task. In SearchQA, answer the question: Who wrote the novel Pride and Prejudice? Success Condition. The agent retrieves supporting evidence and submits a final answer that is evaluated separately by the environment using normalized Exact Match. Rubric <EVIDENCE> A successful search reveals at least one previously unseen result ID. <EVIDENCE> A returned result title or snippet contains the bound target entity or directly relevant query terms. <EVIDENCE> Opening a result reveals a source or passage relevant to the bound target entity and requested relation. <EVIDENCE> A read passage contains an explicit subject--relation--object statement relevant to the question. <EVIDENCE> A newly observed passage provides additional supporting evidence or reduces ambiguity among candidate answers. <INVALIDITY> The action fails the SearchQA parser patterns search[<query>], open[<result_id>], read[<passage_id>], or answer[<text>]. <INVALIDITY> The referenced result ID, passage ID, or tool is not available in the current observation or admissible-action set. <INVALIDITY> An action precondition is not satisfied: open requires a visible result ID, read requires an opened result and a visible passage ID, and answer requires previously retrieved task-relevant evidence. <INVALIDITY> The environment returns an explicit rejection, error, or exception for the attempted tool call. <INVALIDITY> The action repeats the previous action under the same observable state, or an action expected to update the search, opened-result, passage, or answer state produces no observable change. <EXECUTION> An accepted search action changes the result set from empty to non-empty. <EXECUTION> An accepted open action selects an available result relevant to the bound target entity or relation. <EXECUTION> An accepted read action exposes a task-relevant passage. <EXECUTION> The retrieved passage establishes an explicit fact matching the bound target entity and requested relation. <EXECUTION> A well-formed answer is submitted after task-relevant supporting evidence has been retrieved. Prompt (SearchQA, Step 1) Question: Who wrote the novel Pride and Prejudice? Current observation: SearchQA start page. Available tools: search[<query>]. Your admissible actions are: search[<query>]. Response (SearchQA, Step 1) <think>I should search for the title and author relation.</think> <action>search[Pride and Prejudice author]</action> Transition Judgment (SearchQA, Step 1) Transition alignment. This judgment uses the search action and the resulting search-results page. Evidence: +1, the post-search observation newly contains result IDs [1], [2], and [3]. Invalidity: 0, search[...] is parseable, admissible, and accepted. Execution: +1, the search action changes the result set from empty to non-empty. Newly covered operators: Evidence-search and Execution-search. Activated dimensions: Evidence and Execution. Prompt (SearchQA, Step 2) Search results for: Pride and Prejudice author [1] Pride and Prejudice - encyclopedia entry. Snippet: Pride and Prejudice is an 1813 novel of manners by Jane Austen. [2] Jane Austen bibliography. Snippet: Austen's novels include Pride and Prejudice. [3] Pride and Prejudice film adaptation. Snippet: Film cast and release information. Your admissible actions are: open[1], open[2], open[3], search[<query>]. Response (SearchQA, Step 2) <think>Result 1 directly names the work and appears to contain the author statement.</think> <action>open[1]</action> Transition Judgment (SearchQA, Step 2) Transition alignment. This judgment uses the selected result ID and the resulting opened page. Evidence: +1, the opened result contains the bound target entity Pride and Prejudice and is relevant to the requested authorship relation. Invalidity: 0, result ID [1] is available in the current result list and open[1] is accepted. Execution: +1, the action changes the state from the search-results page to an opened relevant result. Newly covered operators: Evidence-relevant-result and Execution-open. Activated dimensions: Evidence and Execution. Prompt (SearchQA, Step 3) Opened result [1]: Pride and Prejudice. Available passages: [1] Pride and Prejudice is an 1813 novel of manners by Jane Austen. [2] The story follows Elizabeth Bennet and Fitzwilliam Darcy. Your admissible actions are: read[1], read[2], open[2], search[<query>]. Response (SearchQA, Step 3) <think>Passage 1 contains the author statement, so I should read it as supporting evidence.</think> <action>read[1]</action> Transition Judgment (SearchQA, Step 3) Transition alignment. This judgment uses the read action and the retrieved passage content. Evidence: +1, the passage contains an explicit statement that connects the bound target entity Pride and Prejudice with the requested relation written by. Invalidity: 0, passage ID [1] is visible after opening result [1], and read[1] is accepted. Execution: +1, the read action exposes a task-relevant supporting fact that can be used to answer the question. Newly covered operators: Evidence-explicit-relation, Execution-read, and Execution-support. Activated dimensions: Evidence and Execution. Prompt (SearchQA, Step 4) Current evidence passage: Pride and Prejudice is an 1813 novel of manners by Jane Austen. Question: Who wrote the novel Pride and Prejudice? Your admissible actions are: answer[<final answer>], read[2], open[2], search[<query>]. Response (SearchQA, Step 4) <think>The passage directly supports Jane Austen as the author.</think> <action>answer[Jane Austen]</action> Transition Judgment (SearchQA, Step 4) Transition alignment. This judgment uses the answer action and the resulting terminal environment feedback. Evidence: 0, submitting an answer does not reveal additional external evidence. Invalidity: 0, answer[...] is well formed, admissible, and issued after task-relevant supporting evidence has been retrieved. Execution: +1, a well-formed answer is submitted after the supporting passage has been read. Newly covered operators: Execution-answer. Activated dimensions: Execution. Terminal outcome: evaluated separately by the environment using normalized Exact Match. Terminal Outcome Final environment feedback: correct. The environment evaluates the submitted answer separately using normalized Exact Match. Case Summary Evidence-positive transitions: 3 / 4 Invalidity-triggered transitions: 0 / 4 Execution-positive transitions: 4 / 4 Task. Find me machine wash men's dress shirts with polyester heathers, heathers cotton, cotton heather, needle sleeve, classic fit, color: navy, fit type: men, size: x-large, and price lower than 50.00 dollars. Success Condition. The purchased product satisfies all bound product, option, and price constraints. <EVIDENCE> The current search-results page introduces at least one previously unseen product ID. <EVIDENCE> The current product page exposes structured product-type and fit-type fields equal to "men's dress shirt" and "men". <EVIDENCE> The current product page exposes a structured fabric or material value equal to one of "polyester heathers", "heathers cotton", "cotton heather". <EVIDENCE> The current product page or option set exposes sleeve="needle sleeve", fit="classic fit", color="navy", and size="x-large". <EVIDENCE> The displayed numeric price of the current product is lower than 50.00 dollars. <INVALIDITY> The action cannot be parsed under the WebShop action grammar for search[...] or click[...]. <INVALIDITY> The referenced product ID, button, option value, or interface operation is absent from the current DOM or admissible-action set. <INVALIDITY> At least one observable precondition defined by the WebShop action schema is not satisfied in the current page state. <INVALIDITY> The environment returns an explicit rejection or failure signal for the attempted operation. <INVALIDITY> The normalized action repeats the previous action under the same page-state signature, or an operation expected to update the page leaves relevant state unchanged. <EXECUTION> The environment accepts a search action and the resulting page contains at least one product ID. <EXECUTION> The selected product ID changes from unset to a product whose structured product-type, fit-type, fabric, and price fields satisfy the bound task constraints. <EXECUTION> The selected color option changes to "navy". <EXECUTION> The selected size option changes to "x-large". <EXECUTION> Rubrics The environment accepts click[Buy Now] while all bound product, option, and price constraints are satisfied. Scoring convention. Evidence and Execution contribute +1 when at least one corresponding item is satisfied at a transition and 0 otherwise. Invalidity contributes -1 when at least one invalidity item is triggered and 0 otherwise; it provides no positive reward. All per-transition 0/1 judgments below are deterministic operator outputs from WebShop canonical facts; no LLM judge is used for scoring. Prompt (WebShop, Step 1) You are an expert autonomous agent operating in the WebShop e-commerce environment. Your task is to: Find me machine wash men's dress shirts with polyester heathers, heathers cotton, cotton heather, needle sleeve, classic fit, color: navy, fit type: men, size: x-large, and price lower than 50.00 dollars. Your current observation is: WebShop Instruction: Find me machine wash men's dress shirts with polyester heathers, heathers cotton, cotton heather, needle sleeve, classic fit, color: navy, fit type: men, size: x-large, and price lower than 50.00 dollars. [button] Search [button] Your admissible actions are: search[<your query>], click[Search]. Reason within <think> </think> tags and present one admissible action within <action> </action> tags. Response (WebShop, Step 1) <think>I should search using the strongest product, fabric, color, size, and price constraints.</think> <action>search[men's dress shirt cotton heather navy x-large classic fit under 50]</action> Transition Judgment (WebShop, Step 1) Transition alignment. This judgment uses the Step 1 search action and the resulting search-results page shown in Step 2. Evidence: +1, the resulting page introduces multiple product IDs not seen before. Invalidity: 0, search[...] is parseable and accepted. Execution: +1, the accepted search action returns a page containing product IDs. Dimension score: +2 Prompt (WebShop, Step 2) Your current observation is: Search results for men's dress shirt cotton heather navy x-large classic fit under 50. [B07CHNVYXL] Arrow 1851 Men's Classic Fit Cotton Heather Dress Shirt - Navy - $39.99 [B08GRAYREG] Van Heusen Men's Regular Fit Dress Shirt - Gray - $45.50 [B09BLACKL] Oxford Cotton Men's Dress Shirt - Black - $32.99 Your admissible actions are: click[B07CHNVYXL], click[B08GRAYREG], click[B09BLACKL], search[<your query>]. Response (WebShop, Step 2) <think>The first result already matches navy, cotton heather, classic fit, x-large availability, and the price limit.</think> <action>click[B07CHNVYXL]</action> Transition Judgment (WebShop, Step 2) Transition alignment. This judgment uses the selected product action and the product-detail page exposed after the click. Evidence: +1, the product page exposes product type, fit type, fabric, option set, and price fields. Invalidity: 0, product ID B07CHNVYXL is present in the current result DOM. Execution: +1, the selected product changes from unset to a product satisfying the core product constraints. Dimension score: +2 Case Study of WebShop Prompt (WebShop, Step 3) Your current observation is: Product page B07CHNVYXL. Title: Arrow 1851 Men's Classic Fit Cotton Heather Dress Shirt. Product type: men's dress shirt. Fit type: men. Fabric: cotton heather. Fit: classic fit. Sleeve: needle sleeve. Price: $39.99. Color options: white, black, navy. Size options: medium, large, x-large. Selected options: color unset, size unset. Your admissible actions are: click[white], click[black], click[navy], click[medium], click[large], click[x-large], click[Back to Search]. Response (WebShop, Step 3) <think>The task requires navy, so I should select the navy color option before buying.</think> <action>click[navy]</action> Transition Judgment (WebShop, Step 3) Transition alignment. This judgment uses the color-option action and the updated selected-options state. Evidence: +1, the option set explicitly contains the required navy color. Invalidity: 0, click[navy] refers to an available color option. Execution: +1, the selected color changes from unset to navy. Dimension score: +2 Prompt (WebShop, Step 4) Your current observation is: Product page B07CHNVYXL. Selected options: color navy, size unset. Available size options: medium, large, x-large. The product remains priced at $39.99 and satisfies men's dress shirt, men fit type, cotton heather, classic fit, and needle sleeve. Your admissible actions are: click[medium], click[large], click[x-large], click[Back to Search]. Response (WebShop, Step 4) <think>The required size is x-large, and it is available on the current page.</think> <action>click[x-large]</action> Transition Judgment (WebShop, Step 4) Transition alignment. This judgment uses the size-option action and the updated selected-options state. Evidence: +0, the required size option was already visible in the current observation. Invalidity: 0, click[x-large] refers to an available size option. Execution: +1, the selected size changes from unset to x-large. Dimension score: +1 Prompt (WebShop, Step 5) Your current observation is: Product page B07CHNVYXL. Selected options: color navy, size x-large. Verified attributes: machine wash, men's dress shirt, fit type men, cotton heather fabric, needle sleeve, classic fit. Displayed price: $39.99, which is lower than 50.00 dollars. [button] Buy Now [button] Your admissible actions are: click[Buy Now], click[Back to Search], click[navy], click[x-large]. Response (WebShop, Step 5) <think>All product, option, and price constraints are satisfied, so I can purchase this item.</think> <action>click[Buy Now]</action> Transition Judgment (WebShop, Step 5) Transition alignment. This judgment uses the purchase action and the final success feedback. Evidence: +1, the state confirms all bound attributes, selected options, and price before purchase. Invalidity: 0, the Buy Now button is available and all observable preconditions are satisfied. Execution: +1, the environment accepts the purchase while all constraints are satisfied. Dimension score: +2 Environment (Final) Final environment feedback: Your score is 1.0. The purchased product satisfies all bound product, option, and price constraints. Case Summary Evidence-positive transitions: 4 / 5 Invalidity-triggered transitions: 0 / 5 Execution-positive transitions: 5 / 5 Rubric Generation Prompt Role. You are an offline rubric-library designer for long-horizon agent training. Construct one shared benchmark-level rubric operator library. The resulting library will be reused across all task instances from the same benchmark. Core rule. Define reusable rubric operators rather than task-specific or step-specific judgments. Each operator must be implementable as a deterministic Boolean function over canonical environment facts. No LLM judge may be required during rollout collection or policy optimization. Task instantiation. For each concrete task instance, a deterministic task binder extracts task-specific entities, attributes, constraints, and target conditions from the task instruction and environment metadata. These parameters are bound to the shared benchmark-level operators. Do not generate a new rubric library for each task instance. Transition evaluation. After task-specific parameters have been bound, each operator evaluates an action-induced transition using canonical facts exposed by the benchmark adapter and returns either 0 or 1. Available canonical facts. Operators may use parsed action types and arguments, admissible actions, current and next observations, environment acceptance or rejection status, state differences, object and receptacle identifiers, inventory, DOM fields, product identifiers, available and selected options, price fields, search-result identifiers, passage identifiers, tool-return status, and normalized state-action repetition. Rubric dimensions. <EVIDENCE>: Define operators that detect newly observed task-relevant entities, attributes, locations, relations, products, passages, or other environment-grounded information. <INVALIDITY>: Define operators that detect malformed, unavailable, rejected, repeated, no-op, or precondition-violating actions. <EXECUTION>: Define operators that detect accepted task-relevant operations, satisfied subgoals, completed state transformations, valid selections, retrieval operations, or other intermediate objectives. Writing requirements. 1. Each operator must specify the canonical facts it reads. 2. Each operator must provide an exact Boolean activation condition. 3. Missing, ambiguous, or unsupported evidence must return 0. 4. Avoid subjective terms such as helpful, plausible, or good. 5. Do not generate rollout-step-specific rules. 6. Do not generate a separate rubric library for each task. 7. Prefer a compact set of high-signal operators that can be implemented directly as code. Output. Return a benchmark-level operator library. For each operator, include its identifier, rubric category, description, required canonical facts, task-binding fields, Boolean condition, positive example, negative example, and missing-evidence behavior. 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.