cs.LGMar 23, 2026
SaveDemystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipe
Organizations: The Chinese University of Hong Kong · IDEA Research · University of Macau
Abstract
Reinforcement Learning (RL) is essential for evolving Large Language Models (LLMs) into autonomous agents capable of long-horizon planning, yet a practical recipe for scaling RL in complex, multi-turn environments remains elusive. This paper presents a systematic empirical study using TravelPlanner, a challenging testbed requiring tool orchestration to satisfy multifaceted constraints. We decompose the agentic RL design space along 5 axes: reward shaping, model scaling, data composition, algorithm selection, and environmental stability. Our controlled experiments yield 7 key takeaways, e.g., (1) reward and algorithm choices are scale-dependent as smaller models benefit from staged rewards and enhanced exploration, whereas larger models converge efficiently with simpler dense rewards, (2) ~ 1K training samples with a balanced difficulty mixture mark a sweet spot for both in-domain and out-of-domain performance, and (3) environmental stability is critical to prevent policy degradation. Based on our distilled recipe, our RL-trained models achieve state-of-the-art performance on TravelPlanner, significantly outperforming leading LLMs.
Figures & tables
Figure 1: Performance on the TravelPlanner test set. Our RL-trained models significantly outperform both their SFT counterparts and leading LLMs . Results marked with ∗ are sourced from Zhu et al. [61] .
Figure 2: Overview of the TravelPlanner testbed. Top: A user query alongside the available local toolkit. Middle: The agent’s iterative reasoning and tool-use trajectory following the ReAct paradigm. Bottom: The two-dimensional evaluation protocol, requiring adherence to both commonsense rules and hard constraints to achieve a Success .
Figure 3: Overview of the STAR pipeline and the experimental design space. The pipeline consists of three stages: (1) Data Synthesis for generating feasible, difficulty-controlled queries, (2) SFT using high-quality trajectories from a teacher model, and (3) RL to optimize long-horizon planning via environmental feedback. The right panel outlines the design space explored in our subsequent experiments.
| Commonsense | Hard Constraint | |||||
| Scale | Method | Micro | Macro | Micro | Macro | Success |
| 1.5B | Base | 30.1 | 0.0 | 0.0 | 0.0 | 0.0 |
| SFT | 65.9 | 15.4 | 17.2 | 12.1 | 6.9 | |
| Sum | 95.1 | 71.6 | 51.4 | 33.4 | 33.1 | |
| Macro | 93.4 | 68.4 | 47.9 | 31.6 | 30.1 | |
| Success | 93.9 | 68.2 | 51.0 | 34.7 | 33.8 | |
Table 1: In-domain performance (%) across reward designs on the TravelPlanner test set. Best results for each model scale are in bold . Smaller models benefit most from the progressive Curriculum reward, while the stronger 7B model favors the dense Sum reward.
| Scale | Method | NQ | TriviaQA | PopQA | HotpotQA | 2Wiki | Musique | Bamboogle | Avg. |
| 1.5B | Base ⋆ | 7.1 | 22.4 | 9.9 | 5.9 | 4.3 | 2.6 | 8.0 | 8.6 |
| SFT | 13.5 | 21.4 | 13.5 | 11.6 | 7.0 | 1.2 | 12.0 | 11.5 | |
| Search-R1 ⋆ | 39.4 | 51.0 | 39.7 | 14.6 | 24.4 | 2.2 | 4.0 | 25.0 | |
| Sum | 32.1 | 44.5 | 30.9 | 26.0 | 14.8 | 5.3 | 16.8 | 24.3 | |
| Macro | 29.6 | 45.1 | 28.8 | 26.9 | 19.4 | 6.3 | 23.2 | 25.6 | |
| Success | 24.8 | 36.9 | 21.3 | 24.2 | 17.7 | 4.6 | 23.2 | 21.8 |
Table 2: Out-of-domain performance (in %) on the knowledge-intensive QA benchmarks . Results marked with ⋆ are sourced from Ji et al. [9] . The best results of each dataset across methods are highlighted in bold . Our RL-trained models achieve comparable or superior performance to the domain-specific Search-R1 baseline [ 12 ] across model scales, showing that complex tool-calling capabilities effectively generalize to other domains.
Figure 4: Performance across model scales on the TravelPlanner test set. Scaling up model capacity consistently improves success rates across all reward types, though the magnitude of improvement varies.
| Commonsense | Hard Constraint | |||||||
| Scale | Algorithm | Micro | Macro | Micro | Macro | Success | Time / Step (min) | GPU Hours |
| 1.5B | GRPO | 93.4 | 68.4 | 47.9 | 31.6 | 30.1 | 8.0 | 164 |
| DAPO | 94.4 | 77.7 | 55.6 | 38.2 | 36.9 | 8.2 | 183 | |
| ARPO | 93.1 | 76.4 | 58.1 | 39.4 | 37.5 | 9.5 | 195 | |
| 3B | GRPO | 95.1 | 79.6 | 68.8 | 52.3 | 48.2 | 8.6 | 176 |
| DAPO | 93.6 | 78.6 | 66.1 | 48.7 | 45.6 | 8.9 | 184 | |
Table 4: Performance (%) and training efficiency across different RL algorithms on the TravelPlanner test set. Best results for each metric within the same model scale are in bold . GPU Hours are calculated based on 8 A100-80G for 1.5B and 3B models and 16 A100 for the 7B model.
Figure 6: Training dynamics and test performance of the 3B model under varying environmental failure rates. The percentages denote the injected tool execution error rates during RL training. (a) Training dynamics: High environmental instability, e.g., 10% error rate, leads to slower convergence and increased variance. (b) Test performance: The agent maintains robust performance under mild noise but experiences a clear degradation across all metrics when the failure rate reaches 10%.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
| Tool | Arguments | Description | # Data Entries |
| SearchCity | state | Find cities within a specific state | 64 |
| SearchFlight | departure, destination, date | Search for flight information between cities on specific dates | 3,827,361 |
| GoogleDistance | departure, destination, mode | Calculate distance, travel time, and cost between two cities | 17,603 |
| SearchRestaurant | city | Find restaurant options in a specific city | 9,552 |
| SearchAttraction | city | Find tourist attractions in a specific city | 5,303 |
| SearchAccommodation | city | Find accommodation options in a specific city | 5,064 |
Table 5: Details of implemented tools within the TravelPlanner testbed.
| Difficulty | Example Query | Description |
| Easy | Please create a travel plan for me where I’ll be departing from Washington and heading to Myrtle Beach for a 3-day trip from March 13th to March 15th, 2022 . Can you help me keep this journey within a budget of $1,400 ? | Single people & Basic constraint: Involves planning for 1 person. The only explicit constraint is a budget limit. |
| Medium | We need to create a travel plan for 2 people departing from Lake Charles and visiting 2 cities in Texas . The trip will last for 5 days , starting from March 4th to March 8th, 2022 . The budget is set at $4,600 . In terms of accommodations, we prefer places where parties are allowed . | Specific constraints: Requires planning for a group of people. Introduces specific accommodation preferences alongside the budget. |
| Hard | Could you create a 7-day travel itinerary for 2 people, departing from Albuquerque and visiting 3 cities in Texas from March 8th to March 14th, 2022 ? Our budget is set at $5,000 . We require accommodations that allow smoking and are preferably not shared rooms . We would prefer to avoid any flights for our transportation. | Multi-dimensional constraints: Demands planning a long-horizon trip. Features multi-dimensional constraints like strict accommodation rules and transportation limitations. |
Table 6: Examples of queries across different difficulty levels on the TravelPlanner validation set. Different types of constraints are highlighted: budget , accommodation , transportation , routing , and duration .
| Commonsense | |
| Within Sandbox | All information in the plan must be within the closed sandbox. Otherwise, it will be considered a hallucination. |
| Complete Information | No key information should be left out of the plan, such as the lack of accommodation during travel. |
| Within Current City | All scheduled activities for the day must be located within that day’s city(s). |
| Reasonable City Route | Changes in cities during the trip must be reasonable. |
| Diverse Restaurants | Restaurant choices should not be repeated throughout the trip. |
| Diverse Attractions | Attraction choices should not be repeated throughout the trip. |
Table 7: Official evaluation rules on TravelPlanner.
| Type | # Data Entries | Avg. Tool Calls | Avg. Tokens | Avg. Tokens of Planning |
| Easy | 627 (52.3%) | 8.8 | 10.1K | 1204.7 |
| Medium | 373 (31.1%) | 8.4 | 9.8K | 1203.1 |
| Hard | 198 (16.5%) | 11.7 | 11.8K | 1343.1 |
| All | 1,198 | 9.2 | 10.3K | 1227.1 |
Table 8: Statistics of filtered trajectories on synthetic data. “Avg. Tokens of Planning” denotes the average token cost of the final generated itinerary.
Figure 7: Training dynamics (i.e., success rates on the training samples during each step) of different rewards. The Curriculum reward accelerates convergence and achieves higher peak performance for smaller models. Conversely, the dense rewards prove most effective for the stronger 7B model.
Figure 8: Training dynamics across model scales. For all reward types, increasing model capacity from 1.5B to 7B consistently leads to faster convergence, improved training stability, and higher performance asymptotes.
Figure 9: Training dynamics for data quantity and difficulty experiments. Configurations that yield the best generalization performance (1K and Mixed) are characterized by a stable, gradual decline in entropy. Suboptimal configurations suffer from anomalous training behaviors, e.g., premature entropy collapse and severe training instability.
| Mode | Data | NQ | TriviaQA | PopQA | HotpotQA | 2Wiki | Musique | Bamboogle | Avg. |
| SFT | 35.1 | 52.5 | 31.3 | 32.0 | 24.4 | 9.0 | 30.4 | 30.7 | |
| Quantity | 0.1K | 39.2 | 57.4 | 35.0 | 38.5 | 26.3 | 9.8 | 30.4 | 33.8 |
| 0.2K | 37.5 | 56.7 | 34.7 | 36.8 | 29.2 | 9.6 | 29.6 | 33.4 | |
| 0.5K | 39.9 | 57.3 | 34.0 | 37.4 | 25.2 | 11.8 | 29.6 | 33.6 | |
| 1K | 41.0 | 56.8 | 36.2 | 39.5 | 27.7 | 12.4 | 32.0 | 35.0 | |
| 2K | 38.5 | 56.7 | 34.4 | 34.3 | 22.4 | 9.6 | 29.6 | 32.2 | |
Table 9: Out-of-domain performance (in %) on the knowledge-intensive QA benchmarks. The best results of each dataset across data configurations are highlighted in bold .
Figure 10: Training dynamics of different RL algorithms. The plots display the success rate curves during training for 1.5B (left) , 3B (middle) , and 7B (right) models. Exploration-heavy algorithms like ARPO exhibit clear advantages at smaller scales, but this benefit diminishes as model capacity increases.