PaperlayerView exact revision on arXiv

Source-linked AI summary

Demystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipe

Xixi Wu, Qianguo Sun, Ruiyang Zhang, Chao Song, Junlong Wu, Yiyan Qi, Hong Cheng

arXiv:2603.21972v1cs.LGcs.CL

TL;DR

Long-horizon agentic RL lacks a practical, systematically validated recipe for complex multi-turn tool use. This paper studies five design axes with the STAR pipeline on TravelPlanner, finding scale-aware reward and algorithm choices, a data sweet spot, and benchmark-leading performance. The authors also identify simulated environments, limited OOD coverage, and model sizes up to 7B as scope boundaries.

  • Problem

    Existing agentic RL insights largely come from short-horizon or few-turn tasks, leaving the design space for long-horizon tool-using agents insufficiently explored.

  • Method

    STAR combines data synthesis, SFT, and RL on TravelPlanner while systematically varying reward shaping, model scale, data composition, algorithms, and environmental stability.

  • Results

    STAR achieves a new SOTA on TravelPlanner, with smaller models favoring staged curriculum rewards and enhanced exploration while larger models favoring simpler dense rewards and standard GRPO.

  • Takeaways & Limitations

    Approximately 1K balanced-difficulty training samples provide a practical trade-off between in-domain mastery and OOD generalization, while environmental noise can degrade performance.

  • Takeaways & Limitations

    The study uses a simulated environment, restricts OOD evaluation to one knowledge-intensive QA setting, and studies models up to 7B parameters.

Abstract

from arXiv · show

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.

1 Introduction

Long-horizon tool-using agents require RL, but existing agentic RL evidence has focused mainly on short interactions and explored only limited design choices. This paper addresses the gap with a systematic TravelPlanner study spanning five RL axes and derives a practical training recipe.

  • Motivation: Existing agentic RL evidence primarily covers short-horizon or few-turn tasks, leaving long-horizon planning insufficiently characterized.Long-horizon workflows may involve dozens of tool invocations and extensive trajectories.
  • Testbed: TravelPlanner provides a computationally tractable testbed for orchestrating diverse tools under budget, preference, and hallucination constraints.It uses a local sandbox rather than costly external APIs, enabling scalable RL exploration.
  • Study Design: The study isolates reward shaping, model scaling, data composition, algorithm selection, and environmental stability across the long-horizon RL design space.Experiments compare model sizes, reward forms, data quantities and difficulty, optimization algorithms, and injected tool failures.
  • Key Findings: Smaller models benefit from staged curriculum rewards and exploration-heavy algorithms, whereas larger models favor simpler dense rewards and standard GRPO.The reported recipe is explicitly scale-aware rather than uniform across model capacities.
  • Key Findings: Approximately 1K training samples with balanced difficulty provide a favorable trade-off between in-domain performance and OOD generalization.The study identifies data quantity and difficulty composition as practical training choices.
  • Results: STAR-trained open-weight models achieve SOTA performance on TravelPlanner and surpass leading proprietary LLMs.The recipe is presented as both an actionable training guideline and a source of benchmark-leading performance.

2 Preliminaries

TravelPlanner evaluates ReAct agents that iteratively reason, use tools, and produce structured travel itineraries under explicit and implicit constraints. Success requires full compliance with both commonsense rules and hard constraints.

  • TravelPlanner Testbed: TravelPlanner presents travel queries combining explicit requirements such as budgets and preferences with implicit commonsense rules.The platform simulates a travel-agency scenario using six information-gathering tools connected to a local database.
  • ReAct Inference: The agent follows ReAct cycles of reasoning, tool action, and observation until producing a final natural-language itinerary.A complete trajectory contains the query and the successive reasoning, action, and observation steps.
  • Evaluation Protocol: A formatting model converts the final itinerary into structured JSON before automated evaluation.This accommodates the unstructured natural-language output produced by the agent.
  • Evaluation Protocol: Evaluation measures commonsense and hard-constraint compliance using micro scores for satisfied checks and binary macro scores for full compliance.The two dimensions include logical consistency, hallucination avoidance, and explicit task constraints.
  • Evaluation Protocol: A trajectory is classified as Success only when all required constraints are met.Partial satisfaction is distinguished from full compliance by the macro evaluation criteria.

3 STAR Pipeline

STAR is a three-stage post-training pipeline that synthesizes controllable TravelPlanner queries, obtains task-aware policies through SFT, and improves long-horizon planning with RL feedback. Its modular design supports systematic comparisons of rewards, algorithms, data, and environmental dynamics.

  • STAR Pipeline: STAR sequentially performs data synthesis, supervised fine-tuning, and reinforcement learning for long-horizon TravelPlanner agents.The stages construct queries, initialize task-aware policies, and strengthen planning through environmental feedback.
  • Data Synthesis: Data synthesis validates feasible travel constraints and varies constraint number and type to create easy, medium, and hard queries.Validated elements and dynamically estimated budgets support natural-language query generation with controllable difficulty.
  • SFT: SFT filters teacher-generated ReAct trajectories for Success and uses the retained high-quality trajectories as supervision.This provides task-specialized initial checkpoints before RL.
  • RL: RL uses environmental feedback with reward signals ranging from dense SUM and semi-sparse MACRO to sparse SUCCESS.These rewards correspond to progressively narrower levels of constraint satisfaction.
  • RL: CURRICULUM transitions from rsum to rsuccess during training to guide exploration.The staged reward is an explicit curriculum-style alternative within the reward design space.
  • Optimization: GRPO samples trajectory groups from the old policy and maximizes a clipped surrogate advantage objective.Advantages are normalized within each sampled group, while asymmetric clipping bounds control the importance-ratio update.
  • Experimental Design: The modular RL setup varies data, rewards, algorithms, and environmental dynamics to isolate their effects empirically.This design enables controlled study of the broader agentic RL design space.
  • Experimental Design: Table 1 compares in-domain TravelPlanner performance across reward designs and model scales.Its stated pattern is that smaller models benefit most from CURRICULUM, while the 7B model favors dense SUM.

4 Experiments

Controlled TravelPlanner experiments isolate how reward shaping, model scale, data composition, algorithm choice, and environmental stability affect long-horizon RL. The results support scale-aware rewards and exploration, a balanced data mixture near 1K prompts, and stable environments.

  • Reward Shaping: CURRICULUM rewards achieve the highest success rates for smaller models, while dense SUM rewards best exploit the 7B model; sparse SUCCESS is never best.Smaller models struggle with long-horizon credit assignment, whereas the 7B model can leverage fine-grained dense feedback without staged transitions.
  • Reward Shaping: Overly dense SUM rewards maximize 7B in-domain performance but substantially reduce OOD accuracy relative to SFT, whereas semi-sparse MACRO better balances transfer and in-domain results.The reported alignment tax is attributed to overfitting to the TravelPlanner format and degradation of general information-seeking abilities.
  • Model Scaling: 62.8% success under SUM at 7B versus 33.1% at 1.5B shows that scaling improves performance across reward signals, with gains varying by reward design.The 3B-to-7B gain is 15.8% under SUM but 7.1% under CURRICULUM; larger models also converge faster and reach higher asymptotes.
  • Data Composition: 49.9% in-domain success and 35.0% average OOD score at 1K prompts mark a data-scaling sweet spot, while 2K prompts raise in-domain success to 50.8% but lower OOD performance to 32.2%.Increasing data from 100 to 1K prompts raises in-domain success from 37.5% to 49.9%, but further scaling harms transferability.
  • Data Composition: A 4:3:3 easy:medium:hard mixture reaches 49.9% overall success by combining dense learning signals from simple tasks with complex constraint coverage.Easy-only training reaches 79.7% Commonsense Macro but misses complex constraints, while hard-only training collapses under reward sparsity.
  • Algorithm Selection: At 1.5B, ARPO and DAPO reach 37.5% and 36.9% success versus 30.1% for GRPO, but at 7B GRPO reaches 62.8% and sophisticated exploration adds computational overhead.The exploration advantage narrows at 3B and reverses at 7B, indicating that algorithmic sophistication is most useful for smaller models.
  • Environmental Stability: Training with failure rates at or below 5% preserves relatively stable test performance, whereas 10% failures slow convergence, increase variance, and degrade all reported metrics.High instability reduces successful trajectories during exploration and therefore limits reliable reward signals for optimizing complex constraints.

5 Conclusion

The paper presents STAR as a systematic, scale-aware recipe for training long-horizon tool-using agents and reports strong TravelPlanner performance. It also identifies limitations involving simulation, restricted OOD evaluation, model scale, and isolated factor analysis.

  • Conclusion: STAR decomposes long-horizon agent post-training across reward shaping, model scaling, data composition, algorithm selection, and environmental stability.The pipeline integrates data synthesis, supervised fine-tuning, and reinforcement learning.
  • Conclusion: Smaller models benefit from staged curriculum rewards and sophisticated exploration, whereas larger models learn efficiently with simpler dense rewards and standard GRPO.The recipe is explicitly scale-aware rather than uniform across model sizes.
  • Conclusion: A data sweet spot balances in-domain mastery with out-of-domain generalization, and STAR achieves new state-of-the-art TravelPlanner performance with much smaller models.The reported result significantly outperforms leading proprietary LLMs.
  • Conclusion: The study provides actionable training guidelines while leaving simultaneous interactions among multiple design factors as an open challenge.The authors position STAR as a toolkit for future agentic RL research.
  • Conclusion: The evidence is limited by TravelPlanner’s simulated setting, restricted single-domain OOD evaluation, model sizes up to 7B, and task-specific single-factor analysis.These boundaries leave real-world dynamics, cross-domain robustness, larger-model behavior, and factor interactions unresolved.

B.3 Evaluation Rules

TravelPlanner evaluates plans against commonsense and hard constraints, converting natural-language outputs into structured representations for automated scoring. The formatting pipeline uses a consistent model across evaluations and was validated against human annotations.

  • Evaluation Rules: A trajectory is successful only when all commonsense and hard constraints are fully satisfied.Micro scores measure the percentage of satisfied rules within each dimension, while fully satisfied dimensions receive macro score 1.
  • Evaluation Rules: The agent’s natural-language travel plan is converted into structured JSON containing daily transportation, accommodation, and attraction elements for automated evaluation.The conversion avoids requiring the planning agent to produce strict JSON directly.
  • Evaluation Rules: DeepSeek-V3.2-Exp replaces GPT-4o as the formatting model because large-scale trajectory generation makes proprietary API calls prohibitively expensive.All checkpoints and comparison models use the same formatting pipeline.
  • Evaluation Rules: DeepSeek-V3.2-Exp achieved human-annotation alignment comparable to, or marginally better than, GPT-4o during offline validation.The validation particularly examined information loss in complex natural-language-to-JSON conversion.

C Implementation Details

The implementation section summarizes the experimental pipeline and separates default setup from study-specific ablations. Detailed configurations are deferred to the corresponding analysis sections.

  • Implementation Details: The implementation covers data synthesis, default supervised fine-tuning and reinforcement-learning setups, and inference.These components define the main experimental protocol.
  • Implementation Details: Configurations specific to individual ablation studies are deferred to their respective analysis sections.The section therefore provides the default setup rather than every experimental variation.
  • Implementation Details: The section organizes implementation details around training and inference rather than introducing a separate experimental finding.Its role is procedural and configurational.

C.1 Data Synthesis

The data-synthesis process balances query difficulty and uses multiple strong open-weight models to create diverse, feasible travel-planning queries. The resulting synthetic pool is large and empirically calibrated against TravelPlanner validation performance.

  • Data Synthesis: Easy, medium, and hard element combinations are sampled in balanced proportions during query construction.Difficulty is controlled through the sampled combinations of travel constraints.
  • Data Synthesis: GPT-OSS-120B and DeepSeek-V3.2-Exp-671B generate queries with equal probability to diversify travel-intent expression.Sandbox verification confirms that sampled dates and constraints admit feasible solutions.
  • Data Synthesis: Over 10K queries were curated with balanced difficulty levels for subsequent training use.The synthesis process iteratively filters and validates candidate queries.
  • Data Synthesis: 21.9% success on a random 200-case sample closely matched 21.1% on the 180-instance TravelPlanner validation set.This comparison supports the reliability of the curated synthetic pool.

C.2 Training Hyperparameters

The pipeline uses filtered supervised trajectories to initialize models, followed by controlled GRPO-based RL with a balanced synthetic dataset and fixed training settings.

  • SFT: 1,198 valid trajectories from 5K prompted cases support full-parameter SFT for task initialization.The 3B and 7B models train for 4 epochs, while the 1.5B model trains for 6 epochs.
  • RL: The default RL setup uses GRPO on 1K synthetic samples with a 4:3:3 easy-to-medium-to-hard difficulty ratio.The RL configuration excludes SFT data and uses a group size of 8, 30K-token contexts, and 60 tool calls.
  • RL: RL training runs for 5 epochs with batch size 32, learning rate 2 × 10^-6, and sampling temperature 1.0.These settings define the default optimization configuration for the experiments.

C.3 Evaluation Setup

Evaluation combines TravelPlanner testing with out-of-domain knowledge-intensive question answering, using structured itinerary parsing and constrained tool-based inference.

  • Evaluation coverage: Performance is evaluated in-domain on 1,000 TravelPlanner test instances and out-of-domain on 7 knowledge-intensive QA benchmarks.The OOD benchmarks include NQ, TriviaQA, PopQA, HotpotQA, 2Wiki, Musique, and Bamboogle.
  • In-domain evaluation: TravelPlanner inference follows ReAct interaction, and a formatting model converts final itineraries into JSON for automated leaderboard evaluation.All models use the identical evaluation pipeline and codebase for comparison.
  • OOD evaluation: OOD inference uses one Search tool over a local Wikipedia corpus with E5 retrieving the top-5 text snippets.Trajectories exceeding context, tool-call, or output-format limits are marked as failures.
  • Training-dynamics analysis: Figure 7 compares success-rate training curves for different reward strategies across model scales.The figure provides a training-dynamics view of reward effects rather than an evaluation protocol.

D Supplementary Materials for Experiments

Supplementary experiments isolate reward, scale, data, and algorithm effects through controlled training-dynamics analyses, revealing scale-dependent optimization and generalization trade-offs.

  • D.1 Reward Shaping: Reward comparisons change only reward computation, showing CURRICULUM benefits smaller models while dense rewards suit the 7B model.CURRICULUM accelerates convergence and reaches higher peak performance for smaller models, whereas dense rewards optimize the 7B model effectively.
  • D.1 Reward Shaping: For the 7B model, dense SUM reaches 36.7% OOD average accuracy versus 41.9% for its SFT starting point.The passage attributes this gap to overfitting to the TravelPlanner format, while semi-sparse MACRO mitigates the alignment tax.
  • D.2 Model Scaling: Increasing model capacity from 1.5B to 7B accelerates convergence, improves training stability, and raises performance asymptotes across reward designs.The training curves indicate that smaller-model bottlenecks reflect fundamental capacity limits.
  • D.3 Data Composition: The 1K and Mixed configurations show gradual entropy decline, whereas suboptimal data settings exhibit premature entropy collapse or severe instability.Entropy is used to track exploration behavior during training.

D.3 Data Composition

Data-composition experiments compare controlled dataset sizes and difficulty mixtures, while supplementary analyses connect stable exploration and model-scale-specific algorithms to the final training recipes.

  • Data construction: Data experiments compare 100, 200, 500, 1K, and 2K samples plus Easy-1K, Medium-1K, Hard-1K, and Mixed-1K datasets.The baseline uses a 4:3:3 easy-medium-hard mixture, while single-difficulty datasets contain 1K examples each.
  • Experimental control: All dataset-size comparisons use approximately 155 gradient updates to isolate data effects from differing updates per epoch.This equals 5 epochs on the 1K dataset with batch size 32.
  • Training dynamics: The optimal 1K and Mixed-1K settings maintain stable entropy descent, unlike 0.5K and Hard-1K configurations with collapse or severe instability.The entropy patterns reflect differences in exploration behavior during RL training.
  • Algorithm selection: Exploration-heavy algorithms outperform standard GRPO for smaller models, but their advantage diminishes as capacity reaches 3B and 7B.The algorithm comparison holds training data and hyperparameters fixed while using scale-appropriate rewards.
  • Final recipe: The distilled recipe uses Mixed-1K for all scales, ARPO at 1.5B, GRPO with CURRICULUM at 3B, and GRPO with the larger-model reward configuration at 7B.The recipe matches data composition and algorithm choices to model scale.

F Cases

The cases show successful tool use for building constraint-aware itineraries, alongside failures on dense constraints and global replanning. Successful agents can locally adapt when transportation becomes infeasible, but failures reveal persistent long-horizon weaknesses.

  • Successful Cases: Successful trajectories balance transportation, accommodation, meals, and budget while satisfying user requirements.The cases include tool-supported flight selection, accommodation search, dining, attractions, and a total budget of $1,352.
  • Successful Cases: When ground transportation is infeasible, the agent locally adapts by switching to flight search.After unsuccessful distance searches, the agent searches flights from St. Petersburg to Appleton and finds a $542 flight.
  • Failure Cases: Dense constraints can cause instruction-following degradation, such as omitting one of four required cuisines.The failure case attributes this difficulty to high cognitive load.
  • Failure Cases: Lack of global backtracking causes the agent to retain an infeasible destination and violate accommodation requirements.After discovering no matching private room that allows parties, the agent selects an invalid room type instead of revising the city choice.
  • Failure Cases: The contrast between local correction and failed global replanning exposes difficulty revising upstream decisions after downstream observations.The paper identifies long-horizon dependencies requiring upstream decisions to be revised as a future research bottleneck.
Loading 2603.21972v1…