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

cs.LGSep 30, 2026

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

Authors: Bo-Wen Zhang, Junwei He, Maoqi Liu, Feiran Li, Song-Lin Lv, Wentao Ma, Rongyi Lin, Shuhan Zhong, +1 more

Organizations: State Key Laboratory of Novel Software Technology, Nanjing University · School of Intelligence Science and Technology, Nanjing University · ByteDance

Abstract

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.

Figures & tables

Figure 1: T2SPO converts historical trajectories into step-level credit. (a) Context construction. Successful historical trajectories pair each visited state with its own observed number of turns to completion (Section 4.1 ). State representations and these targets form a labeled context. (b) Step credit for policy optimization. A frozen TabPFN predicts the remaining distance at adjacent states of a current rollout using the same historical context. Their difference is normalized, gated, and scaled into auxiliary step credit, which augments the outcome advantage in GRPO. Current trajectories refresh the context only after completion and scoring.

Type	Method	ALFWorld							WebShop
		Pick	Look	Clean	Heat	Cool	Pick2	All	Score	Succ.
Qwen2.5-1.5B-Instruct
Prompting	Qwen2.5	$5.9$	$5.5$	$3.3$	$9.7$	$4.2$	$0.0$	$4.1$	$23.1$	$5.2$
Prompting	ReAct	$17.4$	$20.5$	$15.7$	$6.2$	$7.7$	$2.0$	$12.8$	$40.1$	$11.3$
RL Training	PPO (with critic)	$64.8_{\pm 3.5}$	$40.5_{\pm 6.9}$	$57.1_{\pm 4.9}$	$60.6_{\pm 6.6}$	$46.4_{\pm 4.0}$	$47.4_{\pm 1.9}$	$54.4_{\pm 3.1}$	$73.8_{\pm 3.0}$	$51.5_{\pm 2.9}$
RL Training	RLOO	$88.3_{\pm 3.0}$	$52.8_{\pm 8.6}$	$71.0_{\pm 5.9}$	$62.8_{\pm 8.7}$	$66.4_{\pm 5.5}$	$56.9_{\pm 4.7}$	$69.7_{\pm 2.5}$	$73.9_{\pm 5.6}$	$52.1_{\pm 6.7}$

Table 1: Main results on ALFWorld and WebShop. ALFWorld reports success rates (%); WebShop reports score (0–100) and success rate (%). RL results are means over three seeds; subscripts denote standard deviations. Shaded rows denote T2SPO-GRPO using only successful context examples; bold numbers indicate the highest reported mean within each model size.

\Delta

reports the difference between T2SPO-GRPO and the GRPO reference within each model size: percentage points for success rates and points for WebShop score.

		ALFWorld	WebShop
Model	Context examples	Succ. (%)	Score	Succ. (%)
Qwen2.5-1.5B-Instruct	Success only	$\mathbf{74.7}_{\pm 10.0}$	$\mathbf{88.5}_{\pm 0.3}$	$\mathbf{73.7}_{\pm 3.3}$
	With 25% failure examples	$74.0_{\pm 5.9}$	$85.0_{\pm 0.6}$	$68.2_{\pm 3.0}$
Qwen2.5-7B-Instruct	Success only	$83.6_{\pm 6.4}$	$85.4_{\pm 4.1}$	$\mathbf{75.8}_{\pm 3.6}$
	With 25% failure examples	$\mathbf{89.3}_{\pm 3.0}$	$\mathbf{86.3}_{\pm 0.6}$	$74.7_{\pm 6.1}$

Table 2: Failure-augmented context on ALFWorld and WebShop. Means over three seeds; subscripts report standard deviations. Bold numbers indicate the higher mean within each model-size pair.

Figure 2: Offline distance prediction on WebShop. (a) Remaining-distance MAE across nine context/SVD settings; parameter axes use logarithmic spacing, and facets connect evaluated points. The square marks the main RL configuration; the star marks the lowest observed MAE. (b) TabPFN and the lowest kNN MAE across five tested neighbor counts per context budget, with matched context examples, SVD32 features, and queries.

Figure 3: Online computation cost on WebShop. (a) Mutually exclusive training stages across three seeds and 360 ordinary optimizer steps. (b) Substages within advantage computation; times are means in seconds. Both panels report shares of summed full-step time. Other advantage work includes GRPO advantage computation, shaping, and context commit.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	ALFWorld	WebShop
Task instances per update	16	16
Rollouts per task instance	8	8
Actor learning rate	$10^{-6}$	$10^{-6}$
KL loss coefficient	0.01	0.01
Invalid-action penalty	0.10	0.10
Policy history window	2 turns	2 turns

Appendix

Table 3: Policy training and evaluation settings shared by both model sizes.

Shared settings	Value
Estimator history window	Full prefix
TabPFN package version	8.3.0
Shared context budget	256
Successful-state pool capacity	256
New successful states per round	$\leq 64$
Recent trajectory window	256

Appendix

Table 4: Estimator settings for the main T2SPO-GRPO runs at both model sizes. History refers to the estimator input; context and successful-state pool budgets count state rows.

Qwen2.5-1.5B-Instruct
Type	Method	ALFWorld
		Pick	Look	Clean	Heat	Cool	Pick2	All
RL Training	T2SPO-GRPO	$\mathbf{87.4}_{\pm 7.4}$	$56.8_{\pm 15.9}$	$\mathbf{90.3}_{\pm 10.1}$	$65.9_{\pm 18.2}$	$\mathbf{86.5}_{\pm 3.0}$	$43.7_{\pm 23.9}$	$\mathbf{74.7}_{\pm 10.0}$
RL Training	T2SPO-GRPO + Fail	$81.6_{\pm 4.6}$	$\mathbf{65.2}_{\pm 17.0}$	$82.9_{\pm 13.1}$	$\mathbf{70.2}_{\pm 11.4}$	$77.9_{\pm 2.6}$	$\mathbf{54.1}_{\pm 21.2}$	$74.0_{\pm 5.9}$
Qwen2.5-7B-Instruct
RL Training	T2SPO-GRPO	$91.3_{\pm 5.7}$	$73.8_{\pm 2.1}$	$97.3_{\pm 2.4}$	$84.5_{\pm 16.8}$	$78.4_{\pm 7.7}$	$63.5_{\pm 10.5}$	$83.6_{\pm 6.4}$

Appendix

Table 5: Failure-augmented context across ALFWorld task categories. Success rates (%), averaged over three seeds; subscripts denote sample standard deviations. T2SPO-GRPO uses success-only context, while T2SPO-GRPO + Fail admits up to 25% failure examples. Bold marks the higher mean at each size.

Context	SVD	MAE $\downarrow$	RMSE $\downarrow$	$\rho$ $\uparrow$
128	32	0.8526	1.4784	0.7293
128	64	0.8370	1.4714	0.7500
128	128	1.0666	1.6504	0.7240
256	32	0.8215	1.4698	0.7486
256	64	0.8345	1.4681	0.7838
256	128	0.7987	1.4477	0.7815

Appendix

Table 6: Offline remaining-distance prediction on WebShop. All rows use TabPFN and evaluate the same 1,951 successful query states on held-out tasks. MAE and RMSE are measured in turns;

\rho

denotes Spearman correlation. Bold numbers mark the best value for each metric.

Estimator	$M=128$	$M=256$	$M=512$
kNN ( $k=8$ )	1.1042	1.0804	1.0022
kNN ( $k=16$ )	1.0429	1.0948	1.0401
kNN ( $k=M/4$ )	0.9856	0.9978	1.0093
kNN ( $k=M/2$ )	1.0874	1.0882	1.1083
kNN ( $k=M$ )	1.4719	1.4678	1.4669
TabPFN	0.8526	0.8215	0.6500

Appendix

Table 7: TabPFN and kNN on WebShop. All results use SVD32; columns give context budgets

M

. MAE is in turns, with the lowest value in bold. At

k=M

, kNN returns the context mean.

Component	Mean $\pm$ SD	Median	Share (%)
Rollout generation	$171.729\pm 34.274$	165.729	45.167
Reward extraction	$0.560\pm 0.215$	0.515	0.147
Old-policy log-probability	$21.657\pm 6.640$	19.245	5.696
Reference-policy log-probability	$20.616\pm 6.416$	18.093	5.422
Advantage computation	$80.682\pm 13.747$	79.454	21.221
Actor update	$84.830\pm 28.138$	73.509	22.312

Appendix

Table 8: Online training-step timing on WebShop. Means and standard deviations are over 360 optimizer steps from three seeds; times are in seconds. Shares use summed full-step time. The lower block expands the advantage row in the upper block.

Model	Turn-PPO	T2SPO-Turn-PPO	$\Delta$
Qwen2.5-1.5B-Instruct	$91.4_{\pm 6.6}$	$91.4_{\pm 3.3}$	$0.0$
Qwen2.5-7B-Instruct	$90.2_{\pm 9.4}$	$91.4_{\pm 1.1}$	$+1.2$

Appendix

Table 9: Turn-PPO with and without T2SPO on ALFWorld. Success rates (%) are means with sample standard deviations over the same two training seeds, 0 and 1 (

n=2

). Each final checkpoint is evaluated on 128 episodes after 150 updates;

\Delta

is the change in mean success in percentage points.

Explore similar work

3SPO: State-Score-Supervised Policy Optimization for LLM Agents
Jun 8, 2026Yu Han, Kailing Li, Yang Jiao +4Large Language Model Reinforcement Learning Offline Reinforcement Learning
School of Computer Science and Technology, East China Normal University · Fudan University · KAUST +1
TAPO: Transition-Aware Policy Optimization for LLM Agents
Jul 30, 2026Cong Li, Peixi Peng, Yisen Zhao +4Frictive Policy Optimization Large Language Model Agents
School of Electronic and Computer Engineering, Peking University · Pengcheng Laboratory
STAPO: Selective Trajectory-Aware Policy Optimization for LLM Agent Training
Jul 6, 2026Qiuyi Qi, Tian Liang, Mutian Bao +8Agentic Reinforcement Learning Trajectory-Aware Hidden-State Analyses
Zhejiang University · Ant Group · City University of Hong Kong

Jun 8, 2026, cs.LGJ/K move · Enter open · S save

3SPO: State-Score-Supervised Policy Optimization for LLM Agents

Yu Han, Kailing Li, Yang Jiao, Yulin Dai+3

School of Computer Science and Technology, East China Normal University · Fudan University · KAUST+1

Large Language Model Reinforcement Learning Offline Reinforcement Learning Large Language Model Agents

Open paper AskPDF arXiv

Training large language models (LLMs) as autonomous agents via reinforcement learning (RL) has enabled frontier models to achieve superhuman performance in long-horizon tasks. However, existing RL algorithms operate at the trajectory level, performing policy optimization only after collecting complete episode rollouts. This coarse-grained approach faces fundamental challenges in multi-turn agent settings where rewards are sparse, delayed, and credit assignment across individual steps is critical. In this work, we propose \textbf{State-Score-Supervised Policy Optimization (3SPO)}, a novel RL algorithm that performs post-step policy optimization with dynamic state score supervision. At each step, 3SPO computes the state score based on historical success rates, supervising step-wise credit assignment, adaptive rollout and post-step policy optimization without requiring value function estimation or additional auxiliary models. Theoretically, under a per-state bandit abstraction, we show that the proposed score-supervised allocation mechanism achieves logarithmic allocation regret and provide sample-complexity guarantees for action identification, score distinguishability, and filtering stability. Experiments on ALFWorld and WebShop with Qwen2.5-1.5B/7B-Instruct show that 3SPO consistently outperforms GRPO by

+22.6\%

on ALFWorld and

+15.6

points on WebShop, while using comparable resources to achieve

2.4\times

more state exploration and

1.8\times

faster convergence. Code is available at https://github.com/genalyu/3SPO.

Abstract

Explore similar work

3SPO: State-Score-Supervised Policy Optimization for LLM Agents

TAPO: Transition-Aware Policy Optimization for LLM Agents

STAPO: Selective Trajectory-Aware Policy Optimization for LLM Agent Training