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

arXiv: https://arxiv.org/abs/2602.11767 · HTML: https://mlsanity.com/paper/2602.11767/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 33 of its 47 references that are in the map.
- First posted on arXiv 12 Feb 2026.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 30 of 33)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment](https://mlsanity.com/paper/2304.06767/) (2023)
- [Process Reinforcement through Implicit Rewards](https://mlsanity.com/paper/2502.01456/) (2025)
- [Group-in-Group Policy Optimization for LLM Agent Training](https://mlsanity.com/paper/2505.10978/) (2025)
- [RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2504.20073/) (2025)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [Thinking Fast and Slow with Deep Learning and Tree Search](https://mlsanity.com/paper/1705.08439/) (2017)
- [ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL](https://mlsanity.com/paper/2402.19446/) (2024)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling](https://mlsanity.com/paper/2406.00832/) (2024)
- [SWEET-RL: Training Multi-Turn LLM Agents on Collaborative Reasoning Tasks](https://mlsanity.com/paper/2503.15478/) (2025)
- [Agent Lightning: Train ANY AI Agents with Reinforcement Learning](https://mlsanity.com/paper/2508.03680/) (2025)
- [Reinforcing Multi-Turn Reasoning in LLM Agents via Fine-Grained Reward Structure and Credit Assignment](https://mlsanity.com/paper/2505.11821/) (2025)
- [Tree Search for LLM Agent Reinforcement Learning](https://mlsanity.com/paper/2509.21240/) (2025)
- [AgentPRM: Process Reward Models for LLM Agents via Step-Wise Promise and Progress](https://mlsanity.com/paper/2511.08325/) (2025)
- [Sample More to Think Less: Group Filtered Policy Optimization for Concise Reasoning](https://mlsanity.com/paper/2508.09726/) (2025)
- [Scaling Test-time Compute for LLM Agents](https://mlsanity.com/paper/2506.12928/) (2025)
- [Offline Reinforcement Learning for LLM Multi-Step Reasoning](https://mlsanity.com/paper/2412.16145/) (2024)
- [SkyRL-Agent: Efficient RL Training for Multi-turn LLM Agent](https://mlsanity.com/paper/2511.16108/) (2025)
- [Revisiting Group Relative Policy Optimization: Insights into On-Policy and Off-Policy Training](https://mlsanity.com/paper/2505.22257/) (2025)
- [Thinking vs. Doing: Agents that Reason by Scaling Test-Time Interaction](https://mlsanity.com/paper/2506.07976/) (2025)

## Built on by (most cited first, 7 of 7)

- [RewardFlow: Topology-Aware Reward Propagation on State Graphs for Agentic RL with Large Language Models](https://mlsanity.com/paper/2603.18859/) (2026)
- [Process Reward Informed Tree Rollout for Effective Multi-Turn RL](https://mlsanity.com/paper/2607.15610/) (2026)
- [Reflective Prompted Policy Optimization: Trajectory-Grounded Revision and Salience Bias](https://mlsanity.com/paper/2605.08315/) (2026)
- [MedDDC-Eval: Diagnosis-Decoupled Evaluation of Multi-Turn Medical Consultation Agents](https://mlsanity.com/paper/2607.18999/) (2026)
- [Counterfactual Rollout Replay: Forkable Environments as Free Process Rewards for Software Engineering Agents](https://mlsanity.com/paper/2609.33875/) (2026)
- [SIPO: Selective-Inference Policy Optimization for Tree-Structured Agentic RL](https://mlsanity.com/paper/2609.34805/) (2026)
- [ForkPilot: Self-Evolving Policy for Retrospective Search in Long-Horizon Agents](https://mlsanity.com/paper/2610.04889/) (2026)

## Abstract (arXiv)

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.