AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling

1. Problem Statement

Current Large Language Model (LLM) agent training pipelines suffer from a critical data waste problem. Despite the high failure rates of agents on real-world tasks (e.g., GPT-4o succeeds on only ~14% of WebArena tasks and <55% of ToolBench tasks), standard training protocols discard all failed trajectories.

• The Issue: These failures are not random noise; they often contain coherent, correct intermediate steps and factual observations that simply failed to meet the original specific goal.
• The Opportunity: A trajectory that fails to achieve Goal A might be a perfect demonstration for a different, achievable Goal B. Current methods fail to leverage this "hindsight" potential, relying solely on scarce successful demonstrations for Supervised Fine-Tuning (SFT).

2. Methodology: The AgentHER Framework

AgentHER adapts the Hindsight Experience Replay (HER) principle from Reinforcement Learning to natural-language LLM agents. It proposes a four-stage pipeline to convert failed trajectories into high-quality training data (SFT, DPO, and ShareGPT formats) without requiring new environment interactions.

The Four-Stage Pipeline

1. Failure Detector (Stage 1):
   • Function: Classifies the failure type (e.g., Incomplete, Constraint Violation, Wrong Result, Tool Error, Hallucination) and assigns a severity weight ($w$).
   • Mechanism: Uses rule-based keyword lexicons or an LLM judge. Trajectories with severe flaws (e.g., hallucinations, catastrophic tool misuse) are discarded ($w < 0.3$). Recoverable failures are passed downstream with a weight to scale the training loss.
2. Outcome Extractor (Stage 2):
   • Function: Extracts a REPLAYOUTCOME—a list of actual achievements, numeric data, and factual observations from the trajectory.
   • Purpose: Anchors the subsequent relabeling step in factual evidence to prevent the generation of hallucinated goals.
3. Prompt Relabeler (Stage 3):
   • Function: An LLM synthesizes a new natural-language goal ($\hat{g}$) that the trajectory $\tau$ actually satisfies, based on the REPLAYOUTCOME.
   • Constraints: The new goal must be a natural user request, factually supported by observations, independent of the original failed prompt, and match the original complexity.
   • Multi-Judge Verification: To ensure quality, a second independent LLM judge verifies the relabeling. A relabeling is accepted only if both judges agree with high confidence ($c \ge \theta$). This reduces label noise from 5.9% to 2.3%.
4. Data Augmenter (Stage 4):
   • Function: Packages the validated $(\hat{g}, \tau)$ pairs into training datasets.
   • Formats:
     • SFT: Reconstructs the chain of thought as a conversation.
     • DPO: Creates a preference pair where the relabeled goal is "chosen" and the original failed goal is "rejected," teaching the model that the trajectory is valid for the new goal.
     • ShareGPT: Formats for multi-turn compatibility.

Key Mechanisms

• Failure-Severity Weighting: Down-weights trajectories with minor reasoning flaws during training to reduce noise.
• Multi-Judge Verification: Requires consensus between two judges, significantly increasing precision (97.7%) compared to single-judge approaches (94.1%).

3. Key Contributions

1. Novel Formulation: The first systematic pipeline bridging goal-conditioned HER to natural-language agent data synthesis. Unlike prior work that reuses failures for inference-time memory (e.g., ECHO), AgentHER focuses on offline training data augmentation by relabeling goals while keeping trajectories fixed.
2. Robustness Engineering: Introduction of failure-severity weighting and multi-judge verification, which are engineering best practices that raise pipeline precision and reduce label noise, making the system production-ready.
3. Theoretical Guarantee: Provides a proposition that under a perfect judge, the relabeled data is an unbiased sample from the oracle goal-conditioned policy. It also derives a lower bound on performance gains based on judge precision.

4. Experimental Results

The authors evaluated AgentHER on WebArena (web navigation) and ToolBench (API orchestration) across four model families (GPT-4o, Qwen2.5-72B/7B, LLaMA-3.1-8B).

• Performance Gains:
  • AgentHER-MJ (Multi-Judge) improved over standard SFT-Success (training only on successes) by +7.1 to +11.7 percentage points (pp) across all models and benchmarks.
  • Example: On WebArena with Qwen2.5-7B, performance jumped from 18.9% (SFT-Success) to 27.8% (AgentHER-MJ).
• Data Efficiency:
  • AgentHER achieves the same performance as SFT-Success using only 50% of the successful demonstrations, effectively doubling data efficiency.
  • It scales log-linearly with the volume of failed trajectories, whereas SFT-Success cannot utilize additional failures.
• Model Scaling:
  • Gains are consistent across model sizes (1.5B to 72B). Smaller models (7B/8B) benefit most, with gains up to +11.7 pp on ToolBench, suggesting they lack the world knowledge to self-correct and benefit more from diverse relabeled examples.
• Iterative Redeployment:
  • Using AgentHER in an iterative loop (collecting new failures from the improved model, relabeling, and retraining) yields compound gains, adding +2.1 pp over additional rounds.
• Generalization:
  • Models trained on WebArena failures via AgentHER showed a +9.5 pp transfer advantage when evaluated zero-shot on ToolBench, proving the model learns general planning behaviors rather than memorizing specific task patterns.

5. Significance and Conclusion

• Paradigm Shift: AgentHER challenges the industry standard of discarding failures. It posits that the distinction between success and failure is task-relative, not trajectory-absolute.
• Cost-Effectiveness: It transforms the "dominant source of collected experience" (failures) into high-value training data without requiring human annotation or additional environment rollouts.
• Practical Impact: By converting discarded data into SFT and DPO datasets, AgentHER offers a scalable, automated method to improve agent capabilities, particularly for smaller models and in data-scarce scenarios.

The paper concludes that recognizing the potential in failed trajectories transforms every failed deployment into a curriculum for the next iteration of the agent.