StraTA: Incentivizing Agentic Reinforcement Learning with Strategic Trajectory Abstraction

Paper: 2605.06642 Authors: Xiangyuan Xue, Yifan Zhou, Zidong Wang, Shengji Tang, Philip Torr, Wanli Ouyang, Lei Bai, Zhenfei Yin Institutions: CUHK, Shanghai AI Lab, University of Georgia, University of Oxford Categories: cs.CL Code: github.com/xxyQwQ/StraTA Models: huggingface.co/collections/xxyQwQ/strata

Abstract

Large language models (LLMs) are increasingly used as interactive agents, but optimizing them for long-horizon decision making remains difficult because current methods are largely purely reactive, which weakens both exploration and credit assignment over extended trajectories. This paper presents Strategic Trajectory Abstraction (StraTA), a framework that introduces an explicit trajectory-level strategy into agentic reinforcement learning. StraTA samples a compact strategy from the initial task state, conditions subsequent actions on that strategy, and trains strategy generation and action execution jointly with a hierarchical GRPO-style rollout design, enhanced by diverse strategy rollout and critical self-judgment. Experiments show that StraTA consistently improves both sample efficiency and final performance, reaching 93.1% success on ALFWorld, 84.2% on WebShop, and 63.5% on SciWorld—outperforming frontier closed-source models.

Key Contributions

• Strategic Trajectory Abstraction: Introduces an explicit trajectory-level strategy that decomposes long-horizon decision making into two objectives: generating a good strategy and executing actions that faithfully follow it.

• Hierarchical GRPO Training: Develops a hierarchical rollout structure that samples multiple strategies per task and multiple rollouts per strategy, enabling both strategy-level and action-level comparisons.

• Top-Performing Strategy Rewards: Assigns each strategy a reward based on the top-performing fraction of its rollouts, providing a reliable estimate of strategy quality beyond trajectory-level outcome rewards.

• Diverse Strategy Rollout: Uses farthest-point sampling to broaden semantic exploration over candidate strategies, preventing collapse to similar plans.

• Critical Self-Judgment: Introduces step-level auxiliary rewards that penalize actions that neither follow the strategy nor advance task progress, improving credit assignment.

• State-of-the-Art Performance: Achieves 93.1% on ALFWorld, 84.2% on WebShop, and 63.5% on SciWorld (with 100% on the Lifespan subset), outperforming both prompting-based agents and prior RL methods.

Methodology

The Problem with Reactive Agents

Current agentic RL methods are purely reactive:

• At each step, the agent predicts the next action solely from the current state
• The policy must decide both the immediate next move and the overall course of action simultaneously
• This coupling yields:
  • Short-sighted exploration
  • Unnecessary backtracking
  • Internally inconsistent behavior
  • Difficult credit assignment over long trajectories

StraTA Framework

Core Idea: Introduce an explicit trajectory-level strategy that guides the entire episode.

Process:

1. Strategy Generation: At the beginning of each episode, sample a compact strategy from the initial task state
2. Strategy Conditioning: Fix the strategy and prepend it to every subsequent decision
3. Action Execution: Generate each action from both the global strategy and the local state
4. Joint Optimization: Train strategy generation and action execution together

This decomposition separates high-level planning from low-level execution, enabling more coherent and consistent behavior.

Hierarchical GRPO Training

StraTA builds a hierarchical rollout structure:

Two-Level Rollouts:

• Strategy Level: For each task, sample multiple strategies (e.g., 4 strategies)
• Action Level: For each strategy, perform multiple rollouts (e.g., 4 trajectories per strategy)

Two-Level Comparisons:

• Strategy-Level: Compare different plans for the same task
• Action-Level: Compare trajectories generated under the same plan

Strategy Quality Estimation:

• Assign each strategy a reward based on the top-performing fraction of its rollouts
• This provides a more reliable signal than averaging all rollouts
• Helps identify strategies that have high potential even if some executions fail

Enhanced Training Techniques

1. Diverse Strategy Rollout:

• Use farthest-point sampling in embedding space to select diverse strategies
• Prevents the model from generating semantically similar plans
• Broadens exploration over the strategy space

2. Critical Self-Judgment:

• Introduce step-level auxiliary rewards
• Penalize actions that:
  • Don’t follow the stated strategy
  • Don’t advance task progress
• Improves fine-grained credit assignment
• Helps the model learn to execute strategies faithfully

Results

ALFWorld (Household Tasks)

Model	Success Rate
Prompting Baselines	~70-80%
Prior RL Methods (GiGPO)	86.7% (1.5B)
StraTA (1.5B)	90.7%
StraTA (7B)	93.1%

Improvements:

• +4.0% over GiGPO at 1.5B scale
• Consistent gains across model scales

WebShop (E-commerce Tasks)

Model	Success Rate
Prompting Baselines	~60-70%
Prior RL Methods (GiGPO)	65.0% (1.5B)
StraTA (1.5B)	82.5%
StraTA (7B)	84.2%

Improvements:

• +17.5% over GiGPO at 1.5B scale
• Dramatic improvement on this challenging benchmark

SciWorld (Scientific Discovery)

Model	Overall Score
Frontier Closed-Source Models	57.4%
Prior RL Baselines	57.0%
StraTA	63.5%

Subset Performance:

• Lifespan: 100.0% (perfect score)
• Outperforms GPT-4 and other frontier models
• +6.1% over closed-source models
• +6.5% over prior RL baselines

Sample Efficiency

StraTA demonstrates improved sample efficiency across all benchmarks:

• Faster convergence during training
• Better performance with fewer environment interactions
• More stable learning curves

Takeaways

• Strategy Matters: Introducing explicit trajectory-level strategies significantly improves long-horizon agent performance, validating the intuition that planning and execution should be separated.

• Hierarchical Optimization Works: The two-level rollout structure enables effective joint optimization of strategy generation and action execution, addressing both exploration and credit assignment challenges.

• Beyond Reactive Agents: StraTA demonstrates that purely reactive approaches are suboptimal for long-horizon tasks—agents benefit from forming high-level plans before executing actions.

• Practical Impact: The dramatic improvements on WebShop (+17.5%) and SciWorld (outperforming GPT-4) show that StraTA has immediate practical value for real-world agentic applications.

• Scalability: Consistent improvements across model scales (1.5B to 7B) suggest the approach scales well and could benefit even larger models.

• Generalization: Strong performance across diverse domains (household tasks, e-commerce, scientific discovery) demonstrates the framework’s generality.

• Human-Like Problem Solving: StraTA’s approach mirrors human problem-solving patterns—form a plan, execute under that plan, reflect on results—suggesting alignment with cognitive principles.

• Credit Assignment: The combination of top-performing strategy rewards and critical self-judgment provides more accurate credit assignment than standard RL approaches.

• Future Directions: The framework opens possibilities for:

  • Multi-level hierarchies (strategies, sub-strategies, actions)
  • Strategy refinement and adaptation during execution
  • Transfer learning of strategies across tasks
  • Interpretable agent behavior through explicit strategies