Large Language Model (LLM) agents have shown strong results on multi-turn tool-use tasks, yet they operate in isolation during training, failing to leverage experiences accumulated across episodes. Existing experience-augmented methods address this by organizing trajectories into retrievable libraries, but they retrieve experiences only once based on the initial task description and hold them constant throughout the episode. In multi-turn settings where observations change at every step, this static retrieval becomes increasingly mismatched as episodes progress. We propose SLEA-RL (Step-Level Experience-Augmented Reinforcement Learning), a framework that retrieves relevant experiences at each decision step conditioned on the current observation. SLEA-RL operates through three components: (i) step-level observation clustering that groups structurally equivalent environmental states for efficient cluster-indexed retrieval; (ii) a self-evolving experience library that distills successful strategies and failure patterns through score-based admission and rate-limited extraction; and (iii) policy optimization with step-level credit assignment for fine-grained advantage estimation across multi-turn episodes. The experience library evolves alongside the policy through semantic analysis rather than gradient updates. Experiments on long-horizon multi-turn agent benchmarks demonstrate that SLEA-RL achieves superior performance compared to various reinforcement learning baselines.
Figures & tables
Figure 1: Validation success rate on WebShop (Qwen2.5-1.5B-Instruct). SLEA -RL achieves faster convergence and higher asymptotic performance compared to GiGPO and GRPO. Training curves are included in Appendix E .
Figure 2: Overview of SLEA -RL compared to standard GRPO. Left : the LLM agent interacts with the environment in a multi-turn loop; an experience library E (comprising strategy zone E+ and warning zone E− ) provides step-level guidance. Center : GRPO (top, gray) samples G trajectories without experience augmentation, while SLEA -RL (bottom, orange) retrieves experiences εt(i) at each step via cluster-indexed lookup over observation clusters C .
Figure 3: Ablation studies on ALFWorld and WebShop (Qwen2.5-7B-Instruct). GRPO is shown as the vanilla RL baseline. (a) Step-level retrieval consistently outperforms task-level retrieval across all subtasks. (b) Removing step-level advantage ( ω =0) degrades performance below GRPO on several metrics.
ALFWorld
WebShop
Type
Method
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
Qwen2.5-7B-Instruct: RL Methods
RLOO ∗
87.6
78.2
87.3
81.3
71.9
48.9
75.5
80.3
65.7
GRPO ∗
90.8
66.1
89.3
74.7
72.5
64.7
77.6
79.3
66.1
GiGPO ∗
97.7
82.7
98.8
83.7
89.3
79.2
90.8
84.4
72.8
MemRL
62.8
38.5
22.2
12.5
8.00
0.00
21.4
29.5
9.20
Table 1: Performance on ALFWorld and WebShop. We report average success rate (%) for ALFWorld subtasks and overall, and both average score and success rate (%) for WebShop. ∗ : results from Feng et al. (2025) . Best and second best in bold and underline . The full table including the prompt-based models is included in Appendix I .
Single-Hop QA
Multi-Hop QA
Type
Method
NQ †
TriviaQA
PopQA
HotpotQA †
2Wiki
MuSiQue
Bamboogle
Avg.
Qwen2.5-7B-Instruct
RLOO
40.7
72.5
43.1
49.6
55.0
62.2
24.8
49.7
PPO
38.7
75.4
48.7
48.6
59.7
63.4
26.2
51.5
GRPO
40.3
77.0
49.6
48.9
57.7
65.1
25.0
51.9
Reinforce++
34.3
67.5
44.3
45.9
54.5
61.2
23.7
47.3
Table 2: Performance on search-augmented QA tasks. SLEA -RL is trained on NQ and HotpotQA. † : in-domain datasets. Best and second best among RL methods in bold and underline .
Figure 4: Effect of per-zone capacity ( C ) of the experience library on WebShop. Performance peaks at the default C =100 and slightly degrades at C =200. All configurations outperform GRPO (dashed lines).
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
Value
Step-Level Retrieval
Retrieval mode
clustered
Top- k golden strategies
2
Top- k warnings
1
Max experience tokens
200
Similarity threshold δ
0.85
Appendix
Table 3: SLEA -RL hyperparameter configuration.
Figure 5: Validation success rates on ALFWorld (left) and WebShop (right) with Qwen2.5-1.5B-Instruct. Faint traces show raw values; bold lines are smoothed. SLEA -RL achieves faster convergence and higher asymptotic performance than GiGPO and GRPO.
Figure 6: Training dynamics on ALFWorld (left) and WebShop (right) with Qwen2.5-1.5B-Instruct. Top row : training episode success rate. SLEA -RL achieves higher success than GiGPO throughout training, with the gap widening as the experience library matures. Bottom row : mean episode length. SLEA -RL reduces episode length faster, indicating more efficient task completion via experience-guided action selection.
Figure 7: System prompts used in the SLEA -RL pipeline. Prompt A augments each step’s observation with retrieved experiences. Prompt B extracts reusable strategies from successful trajectories into the strategy zone E+ . Prompt C diagnoses failures and populates the warning zone E− . These prompts enable semantic library evolution without gradient updates.
ALFWorld
WebShop
Type
Method
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
Closed-Source LLMs
GPT-4o
75.3
60.8
31.2
56.7
21.6
49.8
48.0
31.8
23.7
Gemini-2.5-Pro
92.8
63.3
62.1
69.0
26.6
58.7
60.3
42.5
35.9
Qwen2.5-7B-Instruct: Prompt / Memory Methods
ReAct ∗
48.5
35.4
34.3
13.2
18.2
17.6
31.2
46.2
19.5
Appendix
Table 4: Performance on ALFWorld and WebShop. We report average success rate (%) for ALFWorld subtasks and overall, and both average score and success rate (%) for WebShop. ∗ : results from Feng et al. (2025) . Best and second best in bold and underline .
Single-Hop QA
Multi-Hop QA
Type
Method
NQ †
TriviaQA
PopQA
HotpotQA †
2Wiki
MuSiQue
Bamboogle
Avg.
Qwen2.5-7B-Instruct: Prompting Methods
Qwen2.5
11.6
35.6
14.4
1.20
16.4
4.80
22.2
15.2
CoT
12.8
35.6
24.0
3.80
16.2
6.60
22.6
17.4
RAG
27.4
58.2
16.8
17.8
25.8
9.40
23.2
25.5
Search-o1
19.4
40.6
30.4
11.4
17.0
8.60
27.0
22.1
Appendix
Table 5: Performance on search-augmented QA tasks. SLEA -RL is trained on NQ and HotpotQA. † : in-domain datasets. Best and second best among RL methods in bold and underline .
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.
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.
Training multi-turn LLM agents with reinforcement learning typically relies on trajectory-level rewards, which assign a uniform advantage to every step and cannot identify which decisions led to success or failure. Self-distillation methods can provide finer-grained supervision by augmenting RL with privileged information. However, existing approaches usually apply the same type of privileged information to every step in an indistinguishable manner, ignoring a key asymmetry: routine steps need little additional guidance, while critical error steps require corrective direction that environment feedback alone cannot provide. We propose AHEAD, a step-aware framework that matches different supervision sources to different step types. The teacher receives environment feedback on all steps as a grounded dense signal, and additionally receives LLM-generated corrective hints on error steps to supply the direction that environment feedback lacks. The method introduces minimal changes to the standard GRPO algorithm. Across ALFWorld, WebShop, and Search-based QA, and across three model scales, AHEAD raises task success (+13.3 points on ALFWorld and +11.0 on WebShop at 7B over GRPO), reaches a given success rate in fewer training steps, and solves tasks within tighter interaction budgets than outcome-only RL and prior self-distillation baselines.