TSR: Trajectory-Search Rollouts for Multi-Turn RL of LLM Agents

Aladin Djuhera; Swanand Kadhe; Farhan Ahmed; Syed Zawad; Heiko Ludwig; Holger Boche

cs.AIFeb 12, 2026

TSR: Trajectory-Search Rollouts for Multi-Turn RL of LLM Agents

Authors: Aladin Djuhera, Swanand Kadhe, Farhan Ahmed, Syed Zawad, Heiko Ludwig, Holger Boche

Organizations: Technical University Munich · IBM Research

Abstract

Advances in large language models (LLMs) are driving a shift toward using reinforcement learning (RL) to train agents from iterative, multi-turn interactions across tasks. However, multi-turn RL remains challenging as rewards are often sparse or delayed, and environments can be stochastic. In this regime, naive trajectory sampling can hinder exploitation and induce mode collapse. We propose TSR (Trajectory-Search Rollouts), a training-time approach that repurposes test-time scaling ideas for improved per-turn rollout generation. TSR performs lightweight tree-style search to construct higher-quality trajectories by selecting promising actions and trajectory prefixes during rollout generation. This improves rollout quality while preserving stable policy optimization and remains compatible with standard policy-gradient optimizers by design. Across Sokoban, FrozenLake, and WebShop, TSR achieves success-rate gains of up to 15 percentage points and converges in fewer optimization steps, while trading additional training-time rollout compute for stronger policies that require no search at inference time. By moving search from test time to the rollout stage of training, TSR provides a modular mechanism for stronger multi-turn agent learning, complementary to existing frameworks and rejection-sampling-style selection methods.

Figures & tables

Panel of Figure 1 — Figure 1: “Corner Trap”. Naive rollout sees Push Right as progress but traps the box in a deadlock. Best-of- $N$ explores multiple possibilities and selects one that avoids the dead-end.

Figure 2: ( Left ) Multi-turn RL with naive rollouts: trajectories are sampled independently without any search. ( Right ) Trajectory Search Rollouts (TSR): using tree-style search to construct high-quality trajectories by selecting high-scoring actions at each turn.

Panel of Figure 3 — Figure 3: Success Rate Plots. Comparison of TSR variants (Best-of- $N$ , Lookahead, Beam Search) against the Instance Filtering baseline. Shaded regions show standard deviation across 3 runs.

Task	Method	Qwen2.5-0.5B			Qwen2.5-3B
Task	Method	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )
Sokoban	Base Model	8.9	293	4.7	16.0	272	4.6
	Instance Filtering	$29.0\pm 1.7$	105	4.4	$43.7\pm 1.6$	161	4.1
	TSR (Best-of- $N$ )	$33.3\pm 1.5$	103	4.3	$47.7\pm 1.5$	165	4.0
	TSR (Lookahead)	$36.1\pm 1.4$	101	4.0	$49.5\pm 1.4$	158	3.8
	TSR (Beam Search)	$\mathbf{38.3\pm 1.3}$	98	3.8	$\mathbf{52.3\pm 1.3}$	152	3.6

Table 1: Results (Sokoban & FrozenLake). We report Success Rate (

\uparrow

; mean

\pm

std), Average Response Length in tokens (

\downarrow

), and Average Interaction Turns (

\downarrow

) on the held-out validation set.

Method	Qwen2.5-3B
Method	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )
Base Model	3.0	747	7.7
Instance Filtering	$70.3\pm 1.8$	519	6.8
TSR (Best-of- $N$ )	$73.3\pm 1.5$	504	6.5
TSR (Lookahead)	$82.3\pm 1.3$	475	6.1
TSR (Beam Search)	$\mathbf{85.3\pm 1.1}$	453	5.8

Table 2: Results (WebShop, Qwen2.5-3B). Success Rate (

\uparrow

; mean

\pm

std), Average Response Length (

\downarrow

), and Average Interaction Turns (

\downarrow

) on validation set.

Panel of Figure 4 — Figure 4: Exploitation, Exploration, and Stability Metrics for Sokoban (Qwen2.5-3B). (a) TSR achieves higher average rewards, indicating improved exploitation from higher-quality rollouts. (b) Rollout entropy decreases smoothly over training, suggesting sustained exploration, followed by policy consolidation. (c) Gradient norms remain stable and free of large spikes across TSR variants.

Table 7

$B$	Avg. KL / Step	Success Rate
$2$	$\sim 0.02$	$\mathbf{60.7\pm 1.2}$
$5$	$\sim 0.05$	$61.3\pm 1.1$
$10$	$\sim 0.14$	$60.9\pm 1.4$
$20$	$\sim 0.31$	$53.8\pm 1.8$
$30$	$\sim 0.48$	$45.1\pm 2.1$

Table 5: Distribution Shift Analysis (FrozenLake, Qwen2.5-3B). Moderate beam widths are policy-proximal, while excessive search increases KL, degrading performance.

Appendix figures & tables20 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Illustration of TSR-adapted tree-search rollout generation for multi-turn RL training with best-of- $N$ , beam search, and shallow lookahead search strategies.

Environment	TSR Rollout Scoring Signal	Policy Optimization Reward
Sokoban	Step-level environment reward / box-target progress	Original task reward
FrozenLake	Goal-distance reduction and hole avoidance	Sparse goal-reaching reward
WebShop	Milestone progress and keyword/attribute overlap	Final purchase success reward

Appendix

Table 6: Scoring Signals Used by TSR. State-based scores guide rollout construction only, whereas PPO/GRPO updates remain based on the original task reward.

Task	Method	Generation Config.	Rel. Rollout Budget	Success Rate
Sokoban	Instance Filtering	$L_{\mathrm{gen}}=16$	$1.0{\times}$	$43.7\pm 1.6$
	Instance Filtering	$L_{\mathrm{gen}}=32$	$2.0{\times}$	$44.8\pm 1.7$
	Instance Filtering	$L_{\mathrm{gen}}=64$	$4.0{\times}$	$45.2\pm 1.6$
	TSR (Beam Search)	$M=4,\ B=2$	$2.0{\times}$	$\mathbf{52.3\pm 1.3}$
FrozenLake	Instance Filtering	$L_{\mathrm{gen}}=16$	$1.0{\times}$	$48.7\pm 1.9$
	Instance Filtering	$L_{\mathrm{gen}}=32$	$2.0{\times}$	$49.5\pm 1.7$

Appendix

Table 7: Rollout-Budget-Matched Baselines across Tasks (Qwen2.5-3B). All methods use

P=16

task groups and retain

L_{\mathrm{train}}=16

trajectories per group for policy optimization. Scaling naive instance filtering yields limited gains compared with structured search under matched rollout-generation budgets.

Budget	Qwen2.5-0.5B			Qwen2.5-3B
Budget	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )
$M{=}2,B{=}1$	$36.8\pm 1.5$	101	3.95	$50.6\pm 1.4$	156	3.70
$M{=}4,B{=}1$	$37.6\pm 1.4$	99	3.88	$51.4\pm 1.3$	154	3.65
$M{=}6,B{=}1$	$37.9\pm 1.4$	98	3.85	$51.8\pm 1.4$	153	3.62
$M{=}2,B{=}2$	$37.9\pm 1.1$	96	3.75	$53.1\pm 1.1$	155	3.75
$M{=}4,B{=}2$	$38.3\pm 1.3$	98	3.80	$52.3\pm 1.3$	152	3.60

Appendix

Table 8: Sokoban: Beam Search Scaling. Increasing beam width (

B

) from 1 to 2 yields the largest gain. Increasing samples (

M

) shows diminishing returns.

Budget	Qwen2.5-0.5B			Qwen2.5-3B
Budget	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )
$M{=}2,B{=}1$	$28.7\pm 1.5$	160	3.65	$58.9\pm 1.4$	110	3.20
$M{=}4,B{=}1$	$29.3\pm 1.4$	157	3.58	$59.6\pm 1.3$	106	3.16
$M{=}6,B{=}1$	$29.5\pm 1.4$	156	3.56	$59.9\pm 1.3$	104	3.14
$M{=}2,B{=}2$	$29.4\pm 1.2$	157	3.66	$59.5\pm 1.1$	98	3.16
$M{=}4,B{=}2$	$30.0\pm 1.4$	152	3.50	$60.7\pm 1.2$	98	3.10

Appendix

Table 9: FrozenLake: Beam Search Scaling. Performance trends are consistent with Sokoban, where wider beams (

B=2

) outperform width-one search (

B=1

) across all sample counts.

Budget	Qwen2.5-3B
Budget	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )
$M{=}2,B{=}1$	$83.6\pm 1.3$	470	6.05
$M{=}4,B{=}1$	$84.5\pm 1.2$	462	5.90
$M{=}6,B{=}1$	$84.8\pm 1.2$	458	5.86
$M{=}2,B{=}2$	$83.4\pm 1.2$	461	5.93
$M{=}4,B{=}2$	$85.3\pm 1.1$	453	5.80

Appendix

Table 10: WebShop: Beam Search Scaling (Qwen2.5-3B). Performance generally improves with wider beams at moderate and larger sampling budgets, while gains saturate as

M

increases.

Beam Width $B$	$M$	Rollout Budget	Avg. KL / Step	Success Rate	Observation
2	4	$2.0\times$	$\sim 0.02$	$60.7\pm 1.2$	Safe policy-proximal regime
5	10	$2.5\times$	$\sim 0.05$	$\mathbf{61.3\pm 1.1}$	Small additional gain
10	20	$2.5\times$	$\sim 0.14$	$60.9\pm 1.4$	Diminishing returns, KL rising
20	40	$2.5\times$	$\sim 0.31$	$53.8\pm 1.8$	Performance degrades
30	60	$3.75\times$	$\sim 0.48$	$45.1\pm 2.1$	Learning becomes unstable

Appendix

Table 11: Distribution Shift Analysis (FrozenLake, Qwen2.5-3B). The per-turn expansion budget scales with beam width (

M=2B

), so wider beams never receive less rollout compute (2.0–3.75

\times

). Moderate beam widths remain policy-proximal and improve learning, while wider search increases KL divergence and degrades performance.

Model / Task	Method	Success Rate	Steps to 80%	Steps to Conv.	Step Red.	Time to Conv.	EFLOPs to Conv.
Qwen2.5-0.5B (Sokoban)	Instance Filtering	$29.0\pm 1.7$	90	180	–	1.54 h	2.77
	TSR (Best-of- $N$ )	$33.3\pm 1.5$	60	120	$33.3\%$	1.51 h	2.71
	TSR (Lookahead)	$36.1\pm 1.4$	55	105	$41.7\%$	1.63 h	2.93
	TSR (Beam Search)	$\mathbf{38.3\pm 1.3}$	50	90	50.0%	1.66 h	2.98
Qwen2.5-3B (Sokoban)	Instance Filtering	$43.7\pm 1.6$	100	180	–	1.99 h	3.58
	TSR (Best-of- $N$ )	$47.7\pm 1.5$	70	150	$16.7\%$	2.53 h	4.55

Appendix

Table 12: Convergence and Compute Analysis Across Tasks. We report final success rate (mean

\pm

standard deviation across runs), steps to reach

80\%

of final performance, steps to convergence, the relative reduction in convergence steps compared to instance filtering, wall-clock time to convergence, and estimated total compute (as EFLOPs) to convergence.

Method	Rollout Scorer	FrozenLake	WebShop
Instance Filtering	None	$48.7\pm 1.9$	$70.3\pm 1.8$
TSR (Best-of- $N$ )	Raw task reward	$51.0\pm 1.6$	$73.3\pm 1.5$
TSR (Lookahead)	Raw task reward	$52.7\pm 1.7$	$75.4\pm 1.6$
TSR (Beam Search)	Raw task reward	$53.4\pm 1.5$	$75.9\pm 1.4$
TSR (Lookahead)	State-/progress-based	$57.0\pm 1.4$	$82.3\pm 1.3$
TSR (Beam Search)	State-/progress-based	$\mathbf{60.7\pm 1.2}$	$\mathbf{85.3\pm 1.1}$

Appendix

Table 13: Raw-Reward and Guided Rollout Selection (Qwen2.5-3B). We compare rollout search using only the original task reward with the state-/progress-based scoring signals used in the main experiments. Success rates are reported as mean

\pm

standard deviation across runs.

Method	Aux. Scorer	Per-Turn Search	FrozenLake	WebShop
Instance Filtering	No	No	$48.7\pm 1.9$	$70.3\pm 1.8$
Score-Augmented Instance Filtering	Yes	No	$55.6\pm 1.6$	$79.2\pm 1.5$
Greedy Score-Guided	Yes	Greedy	$56.9\pm 1.4$	$80.6\pm 1.3$
TSR (Beam Search)	Yes	Beam	$\mathbf{60.7\pm 1.2}$	$\mathbf{85.3\pm 1.1}$

Appendix

Table 14: Information-Matched Scoring Controls (Qwen2.5-3B). All score-guided methods use the same state-/progress-based scoring signal, while differing in how it is used during rollout construction.

Rollout Scorer	FrozenLake	WebShop
Instance Filtering (no scorer)	$48.7\pm 1.9$	$70.3\pm 1.8$
Raw task reward	$53.4\pm 1.5$	$75.9\pm 1.4$
Task-agnostic entropy score	$55.8\pm 1.5$	$78.6\pm 1.4$
Learned observation-only value	$57.6\pm 1.3$	$81.4\pm 1.3$
Noisy state-/progress score ( $\sigma=0.50$ )	$55.5\pm 1.6$	$80.5\pm 1.5$
Noisy state-/progress score ( $\sigma=0.25$ )	$56.2\pm 1.4$	$80.8\pm 1.2$

Appendix

Table 15: Robustness to Rollout Scoring Signals (Qwen2.5-3B). We evaluate TSR (Beam Search) with task-reward, task-agnostic, learned, noisy, and state-/progress-based scoring signals.

Method	Prefix Scoring	Rollout Cost	FrozenLake	WebShop
Instance Filtering	Terminal task reward	$1.0{\times}$	$48.7\pm 1.9$	$70.3\pm 1.8$
Scaled Instance Filtering	Terminal task reward	$2.0{\times}$	$49.5\pm 1.7$	$72.1\pm 1.6$
Scaled Instance Filtering	Terminal task reward	$4.0{\times}$	$49.8\pm 1.6$	$72.8\pm 1.5$
TSR (Best-of- $N$ )	Terminal task reward	$2.0{\times}$	$51.0\pm 1.6$	$73.3\pm 1.5$
TSR (Greedy Search)	MC-backed terminal reward	Additional MC compute	$57.0\pm 1.3$	$79.2\pm 1.2$
TSR (Lookahead)	MC-backed terminal reward	Additional MC compute	$58.0\pm 1.2$	$80.0\pm 1.1$

Appendix

Table 16: Monte Carlo-Backed Search with Terminal Task Rewards (Qwen2.5-3B). We compare heuristic-free search methods that use only the original terminal task reward. Best-of-

N

and scaled instance filtering use the indicated rollout-generation budgets, while Monte Carlo-backed variants incur additional rollout-generation compute due to terminal continuations. Success rates are mean

\pm

standard deviation across three seeds.

Outcome	FrozenLake	WebShop
TSR Beam achieves higher evaluation return	$\mathbf{23.2\%}$	$\mathbf{18.9\%}$
Best-of- $N$ achieves higher evaluation return	$15.1\%$	$9.2\%$
Tie	$61.7\%$	$71.9\%$

Appendix

Table 17: Paired Beam Search vs. Best-of-

N

Outcome Analysis. We compare evaluation outcomes of Monte Carlo-backed Beam Search and Best-of-

N

on matched

(\text{seed},\text{evaluation instance})

pairs. Both methods use only the original terminal task reward, while Beam Search incurs additional rollout-generation compute during training.

Method	Success Rate ( $\uparrow$ )	Resp. Len ( $\downarrow$ )	Turns ( $\downarrow$ )	Steps to Conv. ( $\downarrow$ )
Instance Filtering	$70.3\pm 1.8$	519	6.8	85
ARPO	$75.2\pm 1.5$	492	6.3	63
GiGPO	$80.2\pm 1.3$	478	6.1	59
TSR (Beam Search)	$\mathbf{85.3\pm 1.1}$	453	5.8	50

Appendix

Table 18: Comparison to Related Multi-Turn RL Baselines (WebShop, Qwen2.5-3B). All methods use matched model initialization, task distribution, optimizer, rollout-generation budget, policy-optimization reward, and evaluation protocol. Success rates are reported as mean

\pm

standard deviation across three runs.

Method	Rollout Scorer	Success Rate	Steps to Conv.
ARPO	Task-agnostic entropy	$75.2\pm 1.5$	63
TSR (Beam Search)	Task-agnostic entropy	$\mathbf{78.6\pm 1.4}$	56
ARPO + Score Selection	State-/progress-based	$80.4\pm 1.3$	58
TSR (Beam Search)	State-/progress-based	$\mathbf{85.3\pm 1.1}$	50

Appendix

Table 19: Information-Matched Comparison with ARPO (WebShop, Qwen2.5-3B). ARPO and TSR use identical rollout-scoring information and matched rollout-generation budgets.

Method	FrozenLake	WebShop
GiGPO	$56.8\pm 1.5$	$80.2\pm 1.3$
TSR (Beam Search)	$60.7\pm 1.2$	$85.3\pm 1.1$
GiGPO + TSR	$\mathbf{62.4\pm 1.2}$	$\mathbf{87.0\pm 1.0}$

Appendix

Table 20: Complementarity of TSR and GiGPO (Qwen2.5-3B). TSR modifies rollout construction, while GiGPO provides finer-grained credit assignment. Success rates are reported as mean

\pm

standard deviation across runs.

Optimizer	Method	Success Rate ( $\uparrow$ )	Resp. Len. ( $\downarrow$ )	Turns ( $\downarrow$ )
PPO	Instance Filtering	$43.7\pm 1.6$	161	4.1
PPO	TSR (Beam Search)	$\mathbf{52.3\pm 1.3}$	152	3.6
GRPO	Instance Filtering	$42.4\pm 1.8$	166	4.2
GRPO	TSR (Beam Search)	$\mathbf{50.1\pm 1.5}$	156	3.7

Appendix

Table 21: Optimizer Compatibility on Sokoban (Qwen2.5-3B). We compare instance filtering and TSR (Beam Search) under PPO and GRPO while keeping the model, rollout, scoring, and evaluation configurations fixed. Success rates are reported as mean

\pm

standard deviation across three runs.

Model / Method	Sokoban	FrozenLake
GPT-4o (zero-shot)	27.73	26.56
Qwen2.5-72B (zero-shot)	19.53	23.83
Qwen2.5-0.5B (Instance Filtering)	29.00	19.70
Qwen2.5-0.5B (TSR Best-of- $N$ )	33.30	25.00
Qwen2.5-0.5B (TSR Lookahead)	36.10	27.80
Qwen2.5-0.5B (TSR Beam Search)	38.30	30.00

Appendix

Table 22: Comparison to Larger Zero-Shot Models. This comparison contextualizes the magnitude of task-specific RL gains and is not intended as a compute- or training-matched comparison.

Model	Method	ALFWorld SR ( $\uparrow$ )	AppWorld TGC ( $\uparrow$ )
Qwen2.5-3B	Instance Filtering	$69.8\pm 1.8$	$20.4\pm 1.6$
	ARPO	$74.6\pm 1.6$	$23.6\pm 1.5$
	GiGPO	$78.3\pm 1.4$	$25.2\pm 1.4$
	TSR (Beam Search)	$\mathbf{84.7\pm 1.3}$	$\mathbf{31.5\pm 1.2}$
Qwen2.5-7B	Instance Filtering	$79.4\pm 1.5$	$28.7\pm 1.5$
	ARPO	$84.1\pm 1.4$	$32.1\pm 1.4$

Appendix

Table 23: Additional Agentic Environments. Results on ALFWorld and AppWorld for Qwen2.5-3B and Qwen2.5-7B. We report ALFWorld task success rate and AppWorld Task Goal Completion (TGC). Results are mean

\pm

standard deviation across three runs.

Explore similar work

Process Reward Informed Tree Rollout for Effective Multi-Turn RL
Jul 17, 2026Xintong Li, Sha Li, Yuwei Zhang +8Autoregressive Rollout Rollout
1UC San Diego · 2Amazon · 3MIT Alumni
RTPO: Reverse-Turn Policy Optimization for Stabilizing Agentic RL Training
Aug 19, 2026Yugu Li, Zehong Cao, Jianglin Qiao +1Agentic Reinforcement Learning Frictive Policy Optimization
School of CSIT · ACFR · School of EECMS
T $^2$ PO: Uncertainty-Guided Exploration Control for Stable Multi-Turn Agentic Reinforcement Learning
May 4, 2026Haixin Wang, Hejie Cui, Chenwei Zhang +7Multi-Turn Reinforcement Learning Frictive Policy Optimization
University of California, Los Angeles · 2Amazon.com Inc.

Jul 17, 2026, cs.CLJ/K move · Enter open · S save

Process Reward Informed Tree Rollout for Effective Multi-Turn RL

Xintong Li, Sha Li, Yuwei Zhang, Changlong Yu+7

1UC San Diego · 2Amazon · 3MIT Alumni

Autoregressive Rollout Rollout Efficient Exploration

Open paper AskPDF arXiv

Reinforcement learning (RL) has become a key approach for training LLM agents, yet popular methods such as GRPO/RLOO rely on multiple independently sampled complete trajectories for advantage estimation. In long-horizon agentic tasks, such a uniform rollout strategy can waste budget on uninformative dead-end attempts, while promising intermediate states do not receive sufficient exploration. The multi-turn structure of agentic trajectories, with interleaved actions and observations, naturally supports organizing a trajectory group as a tree, where each turn serves as a decision point for exploration. This perspective reframes effective exploration as the problem of deciding where to branch. We propose Process-Scorer Guided Adaptive Tree Rollout (PATR), a quality-aware rollout framework for multi-turn agent RL. PATR uses task-appropriate process feedback to score partial trajectories, selectively branches from promising states, reuses shared prefixes, and conservatively stops degenerate paths to reduce wasted sampling. The resulting rollout groups remain compatible with standard policy optimization while providing more efficient exploration under the same training budget. We evaluate PATR on FrozenLake and the challenging SWE-Bench, which is largely unexplored by prior tree-rollout agent RL methods. Experiments show that PATR improves performance by up to +5.0 points on SWE-Bench and +9.3 points on FrozenLake, highlighting process-guided tree rollouts as an effective strategy for scalable multi-turn RL.

Abstract

Explore similar work

Process Reward Informed Tree Rollout for Effective Multi-Turn RL

RTPO: Reverse-Turn Policy Optimization for Stabilizing Agentic RL Training

T2^22PO: Uncertainty-Guided Exploration Control for Stable Multi-Turn Agentic Reinforcement Learning

T $^2$ PO: Uncertainty-Guided Exploration Control for Stable Multi-Turn Agentic Reinforcement Learning