AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling

Liang Ding

TL;DR

LLM agents struggle with real-world tasks, discarding most failed attempts. AgentHER reclaims this wasted data by relabeling failed trajectories with achievable "hindsight" goals, significantly boosting LLM agent performance and data efficiency. This approach makes LLM agent training more practical and effective.

What Problem Does This Paper Address?

Modern LLM agents, despite impressive advancements, still falter on a majority of real-world tasks. For instance, GPT-4o achieves less than 15% success on WebArena and below 55% pass@1 on ToolBench. The critical issue is that current training pipelines discard nearly all failed trajectories. This is a massive waste of data, as these failures often contain valuable information about what the agent did accomplish, even if it wasn't the intended goal. The authors argue that these failures aren't just noise; they represent coherent executions that could be successful demonstrations for slightly different, achievable goals. The challenge is to systematically identify these achievable alternative goals and convert failed trajectories into useful training data without requiring new environment interactions.

Methods

AgentHER tackles this problem with a four-stage offline pipeline:

  1. Failure Classification: Identifies the type of failure (e.g., constraint violation, wrong result) and assesses its recoverability and severity. This stage can use either a fast, rule-based approach or a more sophisticated LLM-based classifier.
  2. Outcome Extraction: Extracts factual achievements and key observations from the failed trajectory. This provides the grounding for the relabeling process. Again, both rule-based and LLM-based extractors are offered.
  3. LLM-Guided Relabeling and Verification: This is the core innovation. An LLM (the "relabeler") is prompted to generate a new natural-language goal that the actual trajectory successfully achieves. Crucially, this new goal must be plausible, supported by observations, and distinct from the original failed goal. To ensure quality, a "cross-model multi-judge verification" system is employed. Two independent LLMs (GPT-4o-mini and Qwen2.5-72B-Instruct) independently verify the relabeled goal. Agreement between these diverse models is a strong signal of label quality.
  4. Data Packaging: The validated (hindsight goal, trajectory) pairs are formatted into standard training datasets like SFT (Supervised Fine-Tuning), DPO (Direct Preference Optimization), and ShareGPT.

To further refine label quality, AgentHER incorporates severity weighting (down-weighting trajectories with major reasoning flaws) and confidence gating (requiring sufficient agreement from the LLM judges).

Datasets

The paper uses two primary benchmarks:

  • WebArena: A compositional web-automation benchmark with 812 tasks. The authors use a strict task-disjoint split (WA-TRAIN and WA-HELDOUT) to ensure robust evaluation. They collected 3,000 failed and 500 successful trajectories from WA-TRAIN.
  • ToolBench: A larger benchmark with 16,464 tool-use tasks across 49 APIs. They collected 5,000 failed and 2,000 successful trajectories.

Key Insights and Ideas

  • Failures are not noise, but opportunities: The central idea that failed trajectories often represent successful demonstrations for achievable alternative goals is the foundation of AgentHER. This reframes the problem from simply discarding failures to actively leveraging them.
  • Cross-model verification is key for label quality: Relying on a single LLM for relabeling and verification can lead to self-consistency rather than true accuracy. Using two architecturally different LLMs as judges significantly boosts the reliability of the relabeled data.
  • Offline data augmentation is powerful: AgentHER demonstrates that valuable training data can be generated offline from existing failures without needing new environment interactions, making it highly practical.
  • Hindsight goals expand goal distribution: AgentHER's relabeled goals cover more semantic task clusters and introduce unique long-tail tasks, suggesting it complements rather than just duplicates existing successful demonstrations.

Key Results

  • Significant performance gains: AgentHER improves SFT-Success performance by +7.6-11.4% on WebArena and ToolBench across four model families (GPT-4o, Qwen2.5, LLaMA-3.1).
  • 2x Data Efficiency: AgentHER achieves performance comparable to success-only SFT with only 50% of the successful demonstrations, demonstrating substantial data efficiency.
  • Beats baselines: It outperforms experience-centric baselines like ETO, ECHO-offline, and AWM by +3.0-6.2%.
  • Scales well: Gains are consistent across model sizes from 1.5B to 72B parameters.
  • Compounding gains: Iterative redeployment of AgentHER leads to further improvements.
  • High relabeling precision: Human evaluation confirms 97.1% precision for relabeled data using the cross-model multi-judge system.
  • Cost-effective: The relabeling pipeline is inexpensive, costing approximately $1.4 x 10^-3 per accepted pair, making it practical for production.

Limitations and Future Work

  • Held-out split limitations: While the WA-HELDOUT split is task-disjoint, it doesn't fully address cross-environment transfer concerns.
  • Judge bias: The reliance on LLMs for judging introduces a potential for systematic bias, though this is mitigated by using diverse models and human evaluation.
  • Future Work: The authors suggest several exciting directions:
  • Online AgentHER: Integrating relabeling and training concurrently with deployment.
  • Multimodal Trajectories: Extending AgentHER to handle richer data like screenshots and GUI interactions.
  • Learned Hindsight Synthesizer: Training a dedicated model for hindsight goal synthesis.
  • Combining with Inference-Time Scaling: AgentHER's reduction in failure probability could amplify gains from inference-time techniques.
  • Active Learning: Recovering more of the "filter-rejected" pairs.

Summary updated

Abstract

LLM agents fail on the majority of real-world tasks -- GPT-4o succeeds on fewer than 15% of WebArena navigation tasks and below 55% pass@1 on ToolBench -- yet every failed trajectory is routinely discarded, wasting the dominant source of collected experience. We introduce AgentHER, a framework that recovers this lost training signal by adapting the Hindsight Experience Replay principle (HER; Andrychowicz et al., 2017) to natural-language agent trajectories for offline training data augmentation. The key insight is simple: a trajectory that fails goal A is often a correct demonstration for some achievable alternative goal B. AgentHER realises this idea through a four-stage pipeline -- failure classification, outcome extraction, LLM-guided prompt relabeling with confidence gating, and data packaging -- that converts discarded failures into high-quality SFT, DPO, and ShareGPT training data, with both zero-cost rule-based and LLM-judge implementations. On WebArena and ToolBench, AgentHER improves over success-only SFT by +7.1-11.7 pp across four model families (GPT-4o, Qwen2.5-72B/7B, LLaMA-3.1-8B), while achieving 2x data efficiency -- matching baseline performance with only 50% of successful demonstrations. Gains are consistent from 1.5B to 72B parameters (+5.8-9.2 pp) and compound under iterative redeployment (+2.1 pp over additional rounds). Human evaluation confirms 97.7% relabeling precision under multi-judge verification.
BibTeX
@misc{ding2026agenther,
  author = {Liang Ding},
  title = {{AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling}},
  year = {2026},
  eprint = {2603.21357},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.21357},
}
Figure