PaperlayerView exact revision on arXiv

Source-linked AI summary

T2SPO: Trajectory-to-Step Policy Optimization for Agentic Reinforcement Learning

Bo-Wen Zhang, Junwei He, Maoqi Liu, Feiran Li, Song-Lin Lv, Wentao Ma, Rongyi Lin, Shuhan Zhong, Lan-Zhe Guo

arXiv:2610.00388v1cs.LGcs.AI

TL;DR

Outcome-only rewards provide limited guidance about which intermediate decisions advance multi-step tasks. T2SPO uses successful historical trajectories to estimate remaining distance at rollout states and converts changes in those estimates into auxiliary step credit without updating its frozen regressor. Experiments report higher overall task success than GRPO on ALFWorld and WebShop at both model scales.

  • Problem

    Final-outcome rewards evaluate whole trajectories but provide limited guidance about which intermediate decisions advance a task, making step-level credit difficult.

    Source: §1 · p. 2

  • Method

    T2SPO pairs states from successful trajectories with remaining-turn targets, predicts remaining distance with a frozen TabPFN regressor, and uses adjacent prediction changes as auxiliary step credit.

    Source: §1 · p. 2

  • Results

    T2SPO-GRPO achieves higher overall ALFWorld success and higher WebShop scores and success rates than reported GRPO baselines at both model sizes.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    Historical successful trajectories can provide auxiliary step-level credit alongside task-level supervision without training an additional scoring model.

    Source: §1 · p. 2

    The mixed effects of a fixed proportion of failure examples motivate supervision that adapts to the task and the agent’s experience.

    Source: §6 · p. 10

Abstract

from arXiv · show

Reinforcement learning enables large language model (LLM) agents to learn multi-step behaviors through interaction with their environments. However, rewards in many interactive tasks reflect only the final outcome, providing limited guidance on which intermediate decisions advance the task. Successful training trajectories contain intermediate states that can provide supervision for subsequent interactions. We introduce Trajectory-to-Step Policy Optimization (T2SPO), a method that uses past interaction trajectories to provide step-level feedback for policy learning. T2SPO derives remaining-distance targets from successful trajectories and pairs them with representations of the states visited along the way. Conditioned on these examples, a pretrained TabPFN regressor estimates the remaining distance to success at each state of a new rollout. Changes in this distance estimate across consecutive states yield auxiliary credit for agent steps alongside task-level supervision. As training proceeds, newly completed trajectories refresh the estimator's context, incorporating new experience without updating its parameters. Experiments with 1.5B and 7B language models on ALFWorld and WebShop show that T2SPO consistently improves overall task success over GRPO.

1 Introduction

Outcome-only rewards provide little guidance about which decisions advance a multi-step task, motivating finer-grained credit assignment. T2SPO uses successful training trajectories to estimate progress at states and provide auxiliary step credit, improving overall success over reported GRPO baselines on ALFWorld and WebShop at both model scales.

1 Introduction

  • Final-outcome rewards evaluate a whole trajectory but do not show how individual decisions contribute, limiting step-level credit assignment.The section frames task-progress estimation and its changes across steps as a way to connect decisions with outcomes.Source: §1 · p. 2
  • T2SPO pairs states from successful historical trajectories with their remaining turns and uses changes in predicted distance to supply auxiliary step credit.The auxiliary signal accompanies task-level supervision.Source: §1 · p. 2
  • A frozen TabPFN regressor predicts remaining distance from historical state representations and completion-length labels, while newly completed trajectories refresh its context.The regressor and encoder remain frozen; the auxiliary credit can augment GRPO advantages or enter a PPO optimizer as an auxiliary reward.Source: §1 · p. 2
  • Experiments show higher overall task success than reported GRPO baselines on ALFWorld and WebShop at both model scales.Offline evaluations also assess remaining-distance prediction across context sizes and SVD dimensions.Source: §1 · p. 2

2 Related Work

Prior work addresses step-level feedback with learned evaluators, action comparisons, and tabular in-context prediction. T2SPO instead estimates remaining distance at intermediate states using successful-trajectory labels and uses adjacent-state differences for policy credit.

Reinforcement learning for LLM agents

Step-level feedback and credit assignment

Tabular in-context learning for value estimation

  • Tabular foundation models predict from labeled context examples, and V0 and V0.5 apply TabPFN to instruction–performance pairs for rollout allocation, routing, baseline estimation, or adaptive sampling [Müller et al., 2022; Hollmann et al., 2023; 2025; Qu et al., 2025; Zhang et al., 2026b;a].T2SPO instead pairs intermediate-state representations with remaining lengths from successful source trajectories and uses adjacent predictions for policy credit.Source: §2 · p. 3

3 Preliminaries

The preliminaries set up multi-turn agent interaction and the regression interface used to transfer trajectory-derived supervision to current states. They contrast outcome-based GRPO and learned-critic PPO, then describe fixed-parameter, context-conditioned prediction.

3 Preliminaries

  • An LLM agent conditions each textual action on an instruction, current observation, and processed interaction history; a trajectory comprises turns and receives sparse task feedback at episode end.The section introduces this setting before the regression interface.Source: §3.1 · p. 3, §3 · p. 3

3.1 Multi-Turn Reinforcement Learning

  • Outcome-supervised GRPO normalizes final scores across trajectories for the same task, assigning one advantage to every decision in a trajectory; PPO can instead use a learned value function and GAE for turn-varying advantages.With equal group outcomes, GRPO advantages are zero even when intermediate progress or redundant behavior differs; PPO’s clipped surrogate is also described, with auxiliary-credit integration deferred to Section 4.4.Source: §3.1 · pp. 3–4

3.2 Prior-Data Fitted Networks

  • A PFN predicts a query target from labeled context, and its pretrained parameters remain fixed while adapting the context changes the prediction.T2SPO uses interaction states as queries and historical states with trajectory-derived labels as context.Source: §3.2 · p. 4

4 Trajectory-to-Step Policy Optimization

T2SPO turns successful historical trajectories into remaining-distance supervision, predicts distance at later states, and uses changes in those estimates to supply auxiliary step credit alongside task-level learning.

4 Trajectory-to-Step Policy Optimization

  • T2SPO reuses historical successful trajectories to turn state-level progress estimates into auxiliary credit for individual agent steps.It retains task-level supervision while describing target construction, context-based prediction, and integration into policy updates.Source: §4 · p. 4

4.1 Supervision from Historical Trajectories

  • Each successful trajectory labels its visited decision states with the number of interactions remaining along that trajectory.The main experiments exclude unsuccessful states; the failure-augmented variant instead uses the rollout horizon as a capped heuristic target, not an observed time to success.Source: §4.1 · p. 4

4.2 Estimating Current States from Past Trajectories

  • A shared historical context lets a pretrained TabPFN regressor estimate remaining distance for represented states without updating its parameters.Current rollouts are scored before their outcomes can enter the next context, so a trajectory does not use its own outcome to evaluate itself.Source: §4.2 · pp. 4–5

4.3 From State Estimates to Step Credit

  • Adjacent-state remaining-distance estimates produce auxiliary step credit, with terminal rules, gating, and normalization shaping its contribution.Successful termination sets the successor potential to zero, while unsuccessful termination receives zero final process signal; the full procedure does not retain the standard policy-invariance guarantee.Source: §4.3 · p. 5

4.4 Policy Optimization with Step Credit

  • GRPO adds step credit directly to advantages, whereas PPO adds it to rewards before GAE; both keep current-batch targets fixed and refresh later contexts.The encoder and TabPFN receive no gradient updates, and the GRPO integration retains task-level supervision without a learned critic.Source: §4.4 · p. 6

5 Experiments

T2SPO-GRPO improves reported benchmark outcomes over GRPO, while offline tests find lower distance-prediction error with larger contexts and lower MAE than tested kNN settings. The section also reports evaluation settings and the online computation profile.

5.1 Experimental Setup

  • Evaluation uses ALFWorld and WebShop with Qwen2.5-1.5B-Instruct and Qwen2.5-7B-Instruct, primarily comparing T2SPO-augmented GRPO against GRPO.The main configuration uses 256 historical state examples and evaluates checkpoints after 150 updates.Source: §5.1 · p. 7

5.2 Main Results

  • T2SPO-GRPO exceeds reported GRPO means in overall ALFWorld success and WebShop success and task score at both model sizes, while GiGPO retains higher overall ALFWorld success.With failure-augmented context, ALFWorld 7B success rises from 83.6% to 89.3%, while effects vary by benchmark and model size.Source: §5.2 · p. 8

5.3 Offline Distance Prediction

  • Increasing WebShop context from 256 to 512 examples reduces offline distance-prediction MAE at every tested SVD dimension; at SVD32, MAE falls from 0.8215 to 0.6500 turns.The lowest observed MAE is 0.5948 with 512 examples and SVD64; higher feature dimension does not improve prediction uniformly.Source: §5.3 · p. 8

5.4 Comparison with Nearest Neighbors

  • At SVD32, TabPFN has lower MAE than the best tested kNN settings at context budgets 128, 256, and 512, with reductions of 13.5%, 17.7%, and 35.1%.The comparison matches context examples, feature transformation, and query states; Figure 2b plots the lowest kNN MAE among tested neighbor counts.Source: §5.4 · p. 8, Figure 2 · p. 9

5.5 Computation Cost

  • Across 360 WebShop optimizer steps, mean step time is 380.21 seconds; rollout generation, actor updates, and advantage computation account for 45.17%, 22.31%, and 21.22% of summed step time.State estimation accounts for 21.06% of step time and preparing the next context for 0.075%.Source: §5.5 · p. 9, Figure 3 · p. 10

6 Conclusion

T2SPO converts historical completion lengths into auxiliary step credit through a frozen distance estimator whose context evolves during training. The conclusion identifies settings that motivate future adaptations and reports the paper's AI-tool use.

6 Conclusion

  • T2SPO-GRPO achieves higher overall ALFWorld success and higher WebShop scores and success rates than reported GRPO baselines at both model sizes.The offline WebShop evaluation also finds lower MAE for TabPFN than the best tested kNN settings at all three context budgets.Source: §6 · p. 10
  • The authors identify mixed effects from fixed-proportion failure examples, irreversible dead ends, scarce successful trajectories, and more complex tasks as motivations for future work.Proposed directions include adaptive supervision and context updates, adapting auxiliary-credit strength to experience reliability, and predictor fine-tuning.Source: §6 · p. 10

AI Use Statement

  • AI tools assisted with manuscript editing, literature search, figure preparation, parts of code implementation, and discussions of experimental design and result interpretation.The authors state that they developed the core idea and algorithmic procedure and take responsibility for the final work.Source: AI Use Statement · p. 10

A T2SPO Implementation and Evaluation Details

A.1 Training and Evaluation Protocol

The protocol describes shared policy-training and evaluation settings, alongside separate estimator configuration and context refresh procedures. Successful states from online experience progressively replace archived examples in the context.

A.1 Training and Evaluation Protocol

  • Each update collects 128 rollouts from eight trajectories for each of 16 task instances, and reported results use the checkpoint after update 150.ALFWorld uses training and in-distribution evaluation splits; WebShop reserves 500 instruction indices for evaluation and samples 128 instructions per evaluation.Source: §A.1 · p. 13

A.2 Estimator and Context Configurations

  • Main estimator configurations use a frozen Qwen3-Embedding-0.6B encoder and official TabPFN V2; ALFWorld uses structured summaries, while WebShop uses raw observations.The estimator uses full available interaction history, with step and collection-round features added before context-fitted standardization and SVD.Source: §A.2 · p. 13
  • Each benchmark starts from an archive of 128 training trajectories, while completed batches add up to 64 successful states to an online pool capped at 256.Context selection takes online states first and fills remaining positions from the archive, gradually replacing archived examples; failure-augmented variants cap unsuccessful states at 25%.Source: §A.2 · pp. 13–14

A.3 Failure-Augmented Results by Task Category

Failure-augmented context raises all six ALFWorld category means at 7B, while category changes vary at 1.5B. The appendix also specifies update ordering and a Turn-PPO extension that adds auxiliary rewards.

A.3 Failure-Augmented Results by Task Category

  • At 7B, all six ALFWorld category means increase with failure examples; at 1.5B, changes vary across categories.Table 5 compares success-only context with context admitting up to 25% failure examples; overall ALFWorld and WebShop comparisons are in Table 2.Source: §A.3 · p. 14, Table 5 · p. 14

A.4 Algorithm and Reproducibility Details

  • The estimator predicts and fixes batch targets before completed trajectories enter context for subsequent batches; neither the encoder nor TabPFN receives gradient updates.Estimator errors can disable process credit or stop an update, and unchanged ALFWorld observations receive zero process gate and normalization mask.Source: §A.4 · pp. 14–15

A.5 Actor–Critic Extension

  • The PPO extension retains a learned critic and GAE, replacing rewards with augmented rewards for advantage estimation and optimizing complete generated turns.At terminal states the successor value is zero; truncated rollouts use a bootstrapped successor value, and the PFN evaluates the actual successor state when constructing auxiliary reward.Source: §A.5 · p. 15

B Offline Distance Prediction

The WebShop offline evaluation tests remaining-distance prediction on held-out successful-trajectory states across context sizes and SVD dimensions. A second comparison evaluates TabPFN against kNN using shared examples and features.

B Offline Distance Prediction

  • The WebShop query set contains 1,951 successful-trajectory states, and context and query targets use each successful trajectory’s own remaining length.Tasks are split with seed 20260812; nested context pools contain 128, 256, or 512 successful states, and the same cached embeddings and query states are reused across configurations.Source: B Offline Distance Prediction · p. 16, Table 6 · p. 16

B.1 Nearest-Neighbor Comparison

  • At each context budget, TabPFN and kNN use the same examples, SVD32 features, and 1,951 successful query states.The figure selects the lowest kNN MAE among five tested neighbor counts: k=32, 64, and 8 for context sizes 128, 256, and 512, respectively.Source: §B.1 · p. 16, Table 7 · p. 16

C Computation Cost

In the measured WebShop runs, state estimation and online-context preparation account for 21.138% of step time. The timing breakdown describes component shares, not a matched-control slowdown.

C Computation Cost

  • 21.138% of step time is spent on state estimation and online-context preparation, while six mutually exclusive stage timers cover 99.966%.Measurements cover 360 optimizer steps across three success-only WebShop Qwen2.5-1.5B-Instruct runs; the reported shares are component times divided by summed full-step time, not a matched-control slowdown.Source: C Computation Cost · p. 17, Table 8 · p. 17

D Additional Turn-PPO Results

The ALFWorld Turn-PPO comparison reports unchanged mean success at 1.5B and a 1.2-point increase at 7B with T2SPO. At each scale, one seed improves and the other declines.

D Additional Turn-PPO Results

  • The Turn-PPO control and T2SPO variant retain the same learned critic, GAE, and turn-level objective; T2SPO adds auxiliary rewards with weight 0.10.Each update uses one rollout for each of 128 task instances, a 50-turn horizon, and 150 training updates.Source: D Additional Turn-PPO Results · p. 18
  • At 1.5B, mean success is unchanged; at 7B, it increases by 1.2 percentage points with T2SPO, with one seed improving and one declining at each scale.The comparison uses the same two training seeds and evaluates final checkpoints on 128 episodes after 150 updates.Source: D Additional Turn-PPO Results · p. 18, Table 9 · p. 18

Related papers

Loading 2610.00388v1…