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

Source-linked AI summary

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

arXiv:2608.16156v1Aug 17, 2026cs.AI

TL;DR

Long-horizon LLM agents lack fine-grained credit assignment when terminal outcomes are sparse and successful trajectories are scarce. TRCA derives step-level supervision from action-induced transitions, and consistently improves evaluated baselines across embodied interaction, web navigation, and search-augmented reasoning tasks.

Problem
Sparse terminal rewards and scarce successful trajectories make it difficult to assign fine-grained credit to individual actions in long-horizon agent training.
Method
TRCA evaluates action-induced transitions with Evidence, Invalidity, and Execution rubrics to construct foundational and breakthrough step-level rewards without successful anchors or learned evaluators.
Results
TRCA consistently improves evaluated baselines across ALFWorld, WebShop, and seven search-augmented QA benchmarks, including a 6.0% WebShop task score improvement over GraphGPO.
Takeaways & Limitations
TRCA shows that unsuccessful trajectories can provide useful transition-level supervision, improving performance, convergence speed, and sample efficiency across the evaluated tasks.
Takeaways & Limitations
Anchor-based step-level credit methods require sufficient successful trajectories and are limited during exploration when successful trajectories are scarce.

Abstract

from arXiv · show

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.

1 Introduction

Long-horizon agents receive only trajectory-level supervision from sparse outcome rewards, which obscures the contributions of individual actions and is especially problematic because successful trajectories are scarce early in training. TRCA addresses this by deriving step-level credit directly from action-induced transitions using Evidence, Invalidity, and Execution rubrics, without successful anchors or learned process evaluators.

Contribution: TRCA’s transition signals remain useful in failed rollouts, supporting foundational and breakthrough step credit without relying on successful anchors or external evaluators.Figure 1 reports that over 70% of actions in failed early-training rollouts retain useful rubric-grounded transition signals.
Problem: Sparse outcome rewards prevent PPO, GRPO, and RLOO from distinguishing beneficial steps from harmful ones, motivating fine-grained step-level supervision.Propagating the same trajectory-level outcome reward to every action obscures individual action contributions.
Limitation: Success-anchor methods are limited during exploration because reliable step-level credit propagation requires sufficient successful trajectories.This limitation is distinct from the annotation and inference costs associated with process evaluation approaches.
Motivation: 96.5% of sampled Qwen2.5-1.5B-Instruct rollouts failed terminal success, while 85.6% of task-conditioned training groups lacked any successful trajectory early in training.These figures quantify the success-scarce regime that limits methods relying on successful outcomes or success-conditioned reward propagation.
Method: TRCA derives step-level supervision directly from action-induced transitions without successful anchors or learned process evaluators.It evaluates transitions through Evidence for newly revealed task-relevant information, Invalidity for malformed or unexecutable actions, and Execution for completed task-required operations.
Results: TRCA consistently improves performance over evaluated baselines across ALFWorld, WebShop, and seven search-augmented QA benchmarks, with ablations and hyperparameter analyses validating component effectiveness and robustness.The reported experiments cover multiple model scales and include ablation and hyperparameter analyses.

2 Related Work

Prior work frames LLM-agent optimization around RLHF-derived policy methods, process supervision for intermediate decisions, and rubric-based reward design. These approaches address sparse feedback through critic-free objectives, step-level evaluation, or structured criteria, while motivating transition-wise credit assignment.

RL Optimization Methods: PPO remains widely used for LLM post-training, while GRPO and RLOO simplify the actor-critic pipeline with critic-free advantage estimation.GRPO estimates relative advantages within groups of sampled responses, whereas RLOO uses leave-one-out baselines.
Agent Credit Assignment: LLM agents’ multi-step interaction with external environments makes fine-grained credit assignment over intermediate decisions a central optimization challenge.The agents combine a policy model with an execution harness, creating sparse-feedback problems across multiple decisions.
Process Supervision: Process supervision addresses sparse feedback by scoring intermediate steps, but human-supervised PRMs require large-scale step-level annotations.Automatic process-supervision variants are also discussed as alternatives, though the supplied passage is truncated before specifying their limitations.
Rubric-Based Supervision: Rubrics decompose complex or open-ended objectives into explicit evaluation criteria, enabling structured and interpretable supervision.Recent work increasingly incorporates rubrics into LLM evaluation and post-training.
Rubric-Based Supervision: RaR uses instance-specific rubric criteria as on-policy reward signals, while GEAR models prerequisite dependencies to mitigate false credit propagation.RaR extends reinforcement learning beyond domains with directly verifiable outcomes; GEAR studies reward aggregation in rubric-based reinforcement learning.

3 Methodology

TRCA assigns fine-grained credit by evaluating action-induced transitions with Evidence, Invalidity, and Execution rubrics, then combining foundational and breakthrough rubric rewards. It integrates these step-level signals with episode- and step-relative advantages for policy optimization without successful anchor states.

Rubric construction: TRCA evaluates each action-induced transition with Evidence, Invalidity, and Execution rubric items that provide complementary signals for information acquisition, valid execution, and erroneous behavior.Evidence rewards task-relevant information revealed by a transition, while Invalidity identifies malformed, inadmissible, or unexecutable actions.
Foundational Rubric Reward: Foundational Rubric Reward aggregates signed rubric-item judgments at each transition and assigns the resulting step reward only to the corresponding action tokens.Category budgets are normalized by rubric-list length, and binary judgments are computed from observable semantic evidence.
Breakthrough Rubric Reward: Breakthrough Rubric Reward credits only rubric conditions satisfied for the first time, measuring transition-induced increases in cumulative task-relevant coverage.Invalidity items are excluded from the cumulative potential because foundational reward already penalizes transition-local errors.
Reward combination: TRCA combines foundational and breakthrough rewards, with λ ∈[0, 1] controlling their relative contribution, without requiring successful anchor states.The two rewards respectively capture direct rubric evidence and newly covered task-relevant conditions.
Advantage construction: TRCA clusters semantically comparable decision contexts, normalizes completion-aware returns within each step-level group, and combines step-relative and episode-relative advantages as ATRCA_i,t = AE(τi) + AS(ai,t).This preserves rollout-level completion quality while estimating the long-term utility of individual actions.

4 Experiments

Experiments evaluate TRCA across interactive environments and search-augmented QA benchmarks, finding strong performance across model scales, faster learning, complementary reward components, and a favorable λ setting. Results show consistent gains in task success and search-task performance over baselines.

Experimental Setup: TRCA is evaluated on ALFWorld, WebShop, and seven search-augmented question-answering benchmarks across task domains and model scales.ALFWorld measures category and overall success rates, while WebShop measures task score and success rate.
Experimental Setup: Baselines include GPT-4o, Gemini-2.5-Pro, ReAct, Reflexion, PPO, and RLOO.Prompting-based agents use the Qwen2.5 base policy, while RL-based methods include actor-critic and critic-free approaches.
Main Results: 92.0% overall ALFWorld success rate, 90.5% WebShop task score, and 78.4% WebShop success rate are achieved by TRCA with Qwen2.5-1.5B-Instruct.These correspond to 5.3%, 7.4%, and 13.4% improvements over GiGPO, respectively.
Main Results: 45.4% average SearchQA score is achieved by TRCA with Qwen2.5-3B-Instruct, improving over IGPO by 8.2% and GiGPO by 3.3%.TRCA also achieves the best result on each of the seven individual datasets in the 3B setting.
Learning Dynamics and Sample Efficiency: With only 1.92K sampled trajectories, TRCA raises success from 11.5% to 34.6% on Pick_two and from 15.0% to 24.0% on Pick_cool.Under identical trajectory-sampling budgets, TRCA converges substantially faster than GRPO on both subtasks.
Ablation and Sensitivity: Removing either reward component consistently degrades performance, while λ = 0.8 balances broad supervision and breakthrough-focused credit better than λ = 1.0.At λ = 1.0, overall success falls from 92.0% to 88.3%; removing Breakthrough Rubric Reward causes the larger drop across all three benchmarks.

5 Conclusion

TRCA shows that unsuccessful trajectories can still provide abundant, verifiable supervision through environment-observed state transitions. This converts otherwise discarded experience into reliable step-level credit assignment without successful anchors or learned process reward models.

Unsuccessful trajectories contain abundant, verifiable evidence in the state transitions they induce.
TRCA grounds credit assignment in environment-observed changes rather than rare terminal successes.
TRCA converts otherwise discarded experience into reliable step-level supervision without successful anchors or learned process reward models.

A Task-Conditioned Rubric Construction and Evaluation · A.1 Shared Rubric Schema and Benchmark-Level Operator Libraries

TRCA uses a shared Evidence, Invalidity, and Execution rubric schema across ALFWorld, WebShop, and SearchQA, with benchmark-specific operators constructed once and evaluated deterministically from observable transitions. Task-conditioned bindings instantiate reusable operators for each instruction without generating new task-specific libraries.

A.1 Shared Rubric Schema and Benchmark-Level Operator Libraries: ALFWorld, WebShop, and SearchQA share Evidence, Invalidity, and Execution categories, while operators adapt to each benchmark’s action grammar and observable feedback.The schema preserves category semantics across benchmarks while tailoring concrete operators to each interaction interface.
A.1 Shared Rubric Schema and Benchmark-Level Operator Libraries: 15 operators comprise each benchmark-level library, with five operators in each of the three rubric categories.An LLM constructs each reusable benchmark-specific library only once before policy training.
A.1 Shared Rubric Schema and Benchmark-Level Operator Libraries: Each operator reads canonical observable facts, required task-binding fields, and an exact Boolean condition, returning one only when evidence establishes that condition.Unsupported or ambiguous transition evidence therefore cannot produce a positive rubric judgment.
A.2 Task-Conditioned Binding across Task Instances: The shared operator library is reused across all task instances within a benchmark, while deterministic binding fills templates with instruction-specific entities, constraints, operations, and formats.No new operator library is generated for an individual task instance.
A.3 Rule-Based Transition Evaluation: During transition evaluation, benchmark adapters map actions and environment feedback into canonical facts, which are combined with task bindings to compute rubric judgments.Observable facts can include action parsing, parser status, retrieved content, acceptance or rejection feedback, and state changes.
A.3 Rule-Based Transition Evaluation: Transition evaluation does not use successful trajectories, terminal labels, future states, hidden states, performance results, or ground-truth intermediate labels.Insufficient observable evidence leaves an operator inactive; negative credit arises only from activated Invalidity operators.
A.4 Environment-Specific Observable Signals: ALFWorld, WebShop, and SearchQA adapters expose environment-specific signals for detecting newly revealed information, invalid actions, and substantive task execution.These signals include textual feedback, product and cart states, retrieved content, tool feedback, and answer-submission states.
A.5 Validity in the Diagnostic Study: Positive rubric credit requires Evidence or Execution activation; merely avoiding Invalidity does not produce positive reward.Validity is diagnostically useful for executable interaction, but reward remains tied to task-relevant information acquisition or substantive execution.

B Notation and TRCA Training Algorithm … C.3 Reward Fusion

TRCA assigns transition-level credit by grounding Evidence, Invalidity, and Execution judgments in action-induced transitions, then combines local and newly covered rubric rewards. The resulting advantages are normalized by comparison group and applied only to executable action tokens during policy optimization.

B.2 Normalization and Numerical Conventions: TRCA separates reward normalization from advantage normalization and computes normalization statistics within the relevant rollout or context comparison group.Episode-relative advantages become zero for zero-variance outcome groups, while context-relative advantages become zero with fewer than two usable transitions or zero variance.
B.1 Notation Summary: TRCA represents each task with benchmark-specific Evidence, Invalidity, and Execution operator libraries, task-conditioned bindings, transition adapters, and binary rubric judgments.A transition is ξ_i,t = (s_i,t, a_i,t, s_i,t+1), and the adapter maps it into canonical observable facts.
B.3 Action and Token Conventions: Each interaction step produces one complete environment action and one scalar transition advantage, which is broadcast only to executable tokens inside the <action>...</action> span.Reasoning, prompt, observation, retrieved-content, padding, and other-step tokens are masked out.
C Detailed TRCA Reward Construction: The detailed reward construction computes Foundational and Breakthrough Rubric Rewards from the same rubric judgments and transition notation used throughout TRCA.These are the two transition-level reward components used before fusion with terminal outcomes in training.
C.1 Foundational Rubric Reward: Foundational Rubric Reward sums signed item contributions, assigning positive credit to Evidence and Execution, negative credit to Invalidity, and zero credit when observable transition evidence supports no item.Category budgets are divided by item counts, bounding each category’s aggregate contribution and preventing reward scale from increasing solely with rubric length.
C.1 Foundational Rubric Reward: Foundational Rubric Reward evaluates transitions locally and may repeatedly credit the same rubric item, whereas Breakthrough Rubric Reward separately tracks newly covered positive conditions.This provides broad supervision for informative, invalid, and task-relevant actions while distinguishing incremental progress.
C.2 Breakthrough Rubric Reward: Breakthrough Rubric Reward is the temporal difference of cumulative potential over Evidence and Execution items, rewarding each item only when first covered in a rollout.Invalidity is excluded from positive potential, and cumulative Breakthrough Rubric Reward is bounded by r_Evi + r_Exec.
C.3 Reward Fusion: TRCA fuses the two rewards with a convex combination: Foundational Rubric Reward supplies positive and Invalidity-penalty supervision, while Breakthrough Rubric Reward highlights newly uncovered Evidence or Execution conditions.The experiments use λ = 0.8 unless otherwise specified; λ = 0 and λ = 1 select only Foundational or Breakthrough Rubric Reward, respectively.

D Training Algorithm and Policy Optimization … D.4 Action-Level Policy Optimization

TRCA combines sparse terminal outcomes with transition-level rubric supervision to construct completion-aware returns and step-level advantages. It then normalizes these signals by comparable decision contexts and applies one scalar advantage to each complete executable action during policy optimization.

D.1 Completion-Aware Return: Nonterminal steps receive zero environment reward, while terminal transitions receive the task outcome and TRCA adds transition-level rubric supervision.The combined reward preserves the sparse completion signal without duplicating it.
D.1 Completion-Aware Return: The return accumulates future terminal and transition-level signals with γ = 0.95 in all experiments.
D.2 Zero-Variance Rollout Groups: When rollout groups have zero terminal-outcome variance, TRCA sets the episode-relative advantage AE(τi) = 0, making transition supervision the primary differentiating signal.This covers both all-failure groups with R(τi) = 0 and all-success groups with R(τi) = 1.
D.3 Context-Based Step Grouping: TRCA groups transitions from comparable decision contexts together for relative normalization of completion-aware returns, not as successful anchors or independent reward sources.
D.3 Context-Based Step Grouping: Context grouping can use observable environment fields such as page type, product identity, task predicates, object state, inventory, query state, or retrieval stage.It does not require embedding models, learned state encoders, or additional online LLM inference.
D.3 Context-Based Step Grouping: Groups that are too small or have zero variance receive a corresponding step advantage of zero before forming the final combined advantage.
D.4 Action-Level Policy Optimization: TRCA treats each complete environment-facing executable action as the policy-optimization unit and assigns it one scalar transition advantage ATRCA_i,t.
D.4 Action-Level Policy Optimization: Only executable-action tokens from the corresponding interaction step receive the transition advantage; prompt, observation, retrieval, padding, and other-step tokens are excluded.Autoregressive generation does not change this rule: tokens within one executable action share its scalar advantage rather than receiving separate token-level credit.

D.5 Training Procedure

TRCA’s training procedure evaluates action-induced transitions, builds Foundational and Breakthrough Rubric Rewards, and combines them with terminal outcomes to produce action-level advantages for policy optimization. The resulting credit signals are analyzed for boundedness, novel-coverage preference, zero-success behavior, and conditional variance.

Training Procedure: For each rollout group, deterministic rubric operators evaluate action-induced transitions.This evaluation is the first step of the complete TRCA training procedure.
Training Procedure: TRCA constructs Foundational and Breakthrough Rubric Rewards from the transition evaluations.These are the two rubric-based reward components used in the procedure.
Training Procedure: The rubric rewards are combined with terminal outcomes to obtain action-level advantages for policy optimization, with credit signals analyzed across four properties.The analysis covers boundedness, novel-coverage preference, behavior in zero-success groups, and conditional variance.

D.6 Theoretical Properties of TRCA Credit Assignment … E.4 Annotation Categories and Quality Control

TRCA’s theoretical analysis establishes bounded, nonaccumulating rubric credit, preference for novel coverage, non-degenerate advantages in zero-success groups, and deterministic local feedback with conditional variance benefits. Its diagnostic study evaluates action-induced transitions using human and GPT-4o annotations, reports distinct rollout-, group-, and action-level ratios, and separates diagnostic labeling from training-time deterministic reward evaluation.

D.6 Theoretical Properties of TRCA Credit Assignment: TRCA’s rubric rewards are bounded by category budgets, while cumulative Breakthrough Rubric Reward is horizon-independent and cannot repeatedly credit already-covered items.Each positive rubric item contributes at most once to cumulative breakthrough credit.
D.6 Theoretical Properties of TRCA Credit Assignment: TRCA strictly prefers transitions that newly cover task-relevant conditions over transitions that repeat covered conditions when immediate rubric evidence is identical.The preference follows from strictly positive breakthrough credit for at least one newly covered positive item.
D.6 Theoretical Properties of TRCA Credit Assignment: Even when every rollout fails, TRCA provides discriminative positive and negative step credit whenever rubric-enhanced returns distinguish actions from the same decision context.This addresses early-stage policy optimization under success-sparse training conditions.
D.6 Theoretical Properties of TRCA Credit Assignment: Under deterministic rule-based evaluation, TRCA feedback is fixed by the observable transition and prior coverage, whereas trajectory-outcome attribution remains affected by subsequent policy decisions.The variance result is conditional and applies to local transition feedback before context-relative normalization.
E.1 Rollout Collection: The diagnostic study uses ALFWorld and WebShop with Qwen2.5-1.5B-Instruct during early reinforcement learning, collecting 128 rollouts per batch from 16 tasks and groups of 8.A success-free group contains no rollout achieving terminal success.
E.2 Transition Annotation: Annotations target action-induced transitions rather than complete trajectories and classify them as Evidence, Execution, Validity, or Other.Evidence reveals task-relevant information, Execution completes substantive required operations or conditions, Validity captures successfully parsed and executed actions, and Other lacks useful signal.
E.4 Annotation Categories and Quality Control: Diagnostic categories are separate from training rewards: human annotation and GPT-4o support analysis, while TRCA training uses deterministic benchmark operators without online LLM judging.Validity is complementary to TRCA’s Invalidity rubric, which identifies unexecutable actions and contributes negative reward.
E.3 Calculation of Reported Ratios: 96.5%, 85.6%, and 72.2% report failure rate, success-free group rate, and useful-action rate, respectively, using different rollout-, group-, and action-level denominators.Useful actions are annotated as Evidence, Execution, or Validity and are counted only among actions in failed rollouts.

F Experimental Details … F.3 Benchmark-Specific Context Grouping

The experiments use benchmark-specific Qwen2.5 policy models, fixed rollout and reward-mixing settings, and documented reinforcement-learning hyperparameters. Context grouping compares actions under structurally equivalent observable states to compute context-relative advantages without successful terminal states or learned clustering.

F.1 Models and Rollout Configuration: ALFWorld and WebShop use Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct policy models.
F.1 Models and Rollout Configuration: SearchQA uses Qwen2.5-3B-Instruct and Qwen2.5-7B-Instruct policy models.
F.1 Models and Rollout Configuration: All group-based methods use rollout group size N = 8, while the default reward-mixing coefficient is λ = 0.8.
F.1 Models and Rollout Configuration: Agents emit reasoning within <think> tags and executable actions within <action> tags.
F.2 Training Hyperparameters: Table 5 summarizes the core reinforcement-learning hyperparameters used in the experiments.Engineering parameters for distributed 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 under similar decision contexts for computing context-relative step advantages.It does not depend on successful terminal states.
F.3 Benchmark-Specific Context Grouping: Structural grouping permits equivalent structured state fields to match without exact textual equality and uses deterministic environment-exposed fields.It does not use embedding-based clustering, learned state encoders, or additional LLM inference.
F.3 Benchmark-Specific Context Grouping: If a context group has fewer than two comparable transitions or zero variance in completion-aware returns, the corresponding AS(ai,t) is set to zero.

F.4 Datasets and Evaluation Protocols · F.5 Baseline Configuration and Comparison Protocol

The evaluation covers ALFWorld, WebShop, and seven SearchQA datasets with task-specific success, score, and exact-match metrics. Comparisons include closed-source, prompting-based, and reinforcement-learning baselines, with distinct method sets for ALFWorld/WebShop versus SearchQA.

F.4 Datasets and Evaluation Protocols: ALFWorld reports success rates for Clean, Pick, Cool, Heat, Pick2, and the overall task suite.The main table includes all five task categories plus the overall success rate.
F.4 Datasets and Evaluation Protocols: WebShop reports both task score for partial attribute satisfaction and success rate for exact task completion.These metrics distinguish partial progress from fully completed tasks.
F.4 Datasets and Evaluation Protocols: SearchQA spans seven datasets: NQ, TriviaQA, PopQA, HotpotQA, 2Wiki, MuSiQue, and Bamboogle.NQ and HotpotQA are in-domain; the other five datasets are out-of-domain.
F.4 Datasets and Evaluation Protocols: SearchQA uses strict binary normalized Exact Match, counting success only when the final answer exactly matches a provided ground-truth alias.The protocol normalizes the final answer before exact comparison.
F.4 Datasets and Evaluation Protocols: Figure 6 summarizes ALFWorld subtask success rates, WebShop task score and success rate, and seven-benchmark SearchQA performance with averages across model scales.All values are scaled to [0, 1] for visualization.
F.4 Datasets and Evaluation Protocols: Table 6 defines the observable context information used to construct comparable decision contexts.The table supports the baseline-comparison protocol by specifying the context information used for comparison.
F.5 Baseline Configuration and Comparison Protocol: The main comparisons include GPT-4o, Gemini-2.5-Pro, Qwen2.5, ReAct, Reflexion, and RL methods such as PPO, RLOO, GRPO, GiGPO, HCAPO, and GraphGPO.SearchQA additionally compares R1-Instruct, Search-R1, ZeroSearch, StepSearch, IGPO, and TRCA.

F.6 Sample-Efficiency Evaluation Protocol

The sample-efficiency evaluation counts each complete rollout as one sampled trajectory and compares TRCA with GRPO under matched rollout budgets. TRCA outperforms GRPO consistently, with early gains that persist as sampling increases and substantial improvements on ALFWorld subtasks.

Evaluation protocol: Each completed rollout counts as one sampled trajectory, with aggregate budgets of 1.92K, 3.84K, and 6.40K trajectories.The evaluation uses complete rollouts as the sampling unit throughout the process.
Aggregate sample efficiency: TRCA consistently achieves higher success rates than GRPO across reported matched rollout budgets, with gains of up to 19.5 percentage points on ALFWorld.The performance gap emerges early and remains visible as the sampling budget increases.
Subtask results: At 1.92K trajectories, TRCA raises Pick_two success from 11.5% to 34.6% and Pick_cool success from 15.0% to 24.0% versus GRPO.These comparisons use the same sampling budget for both methods.
Subtask results: With 3.84K trajectories, TRCA reaches 69.2% on Pick_two, exceeding GRPO’s 46.7% with 6.40K trajectories.TRCA also reaches 53.8% on Pick_cool with 3.84K trajectories, approaching GRPO’s 57.7% with 6.40K.

F.7 Random Seeds and Reporting … Case Study of WebShop

The paper reports reproducible, transferable optimization gains and presents deterministic rubric construction through benchmark-level operators instantiated for task-specific transitions. ALFWorld, SearchQA, and WebShop case studies show how Evidence, Invalidity, and Execution judgments convert observable state changes into progress signals and successful outcomes.

F.7 Random Seeds and Reporting: ALFWorld and WebShop results are averaged over three random seeds, with validation curves generally following training curves without pronounced divergence.Figure 8 reports training and validation success rates for TRCA in both environments.
F.7 Random Seeds and Reporting: TRCA gains transfer beyond sampled tasks: it rises earlier than GRPO on ALFWorld and establishes a persistent training-and-validation advantage on WebShop after roughly one-third of training.The reported ordering between training and held-out performance indicates reliable transfer to unseen evaluation tasks.
G Rubric Generation Prompt and Complete Libraries: Before training, one LLM call per benchmark constructs reusable Evidence, Invalidity, and Execution operator libraries, while task binders instantiate grounded rubric items deterministically.Transition judgments use observable environment feedback without additional LLM calls during policy training.
Case Study of ALFWorld: In ALFWorld, transitions receive positive Evidence and Execution judgments for discovering pencils, navigating to candidate locations, taking objects, and placing two distinct pencils in one drawer.The case study ends with two distinct pencils in drawer 1 and a completed task.
Case Study of SearchQA: In SearchQA, searching, opening a relevant result, and reading an explicit relation progressively activate Evidence and Execution operators before the agent submits the correct answer.The environment separately evaluates the submission using normalized Exact Match.
Case Study of WebShop: In WebShop, search, product selection, option clicks, and purchase transitions receive deterministic rubric judgments as constraints become satisfied.Evidence and Execution contribute +1 when corresponding items are satisfied, while Invalidity contributes -1 only when triggered.
Case Study of WebShop: 1.0 is the final WebShop score after purchasing a product satisfying all bound product, option, and price constraints.The demonstrated item is a navy, x-large, cotton-heather men's dress shirt priced at $39.99.