[2603.21357] AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling

Computer Science > Artificial Intelligence arXiv:2603.21357 (cs) [Submitted on 22 Mar 2026] Title:AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling Authors:Liang Ding View a PDF of the paper titled AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling, by Liang Ding View PDF HTML (experimental) 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 (Zhou et al., 2024; Qin et al., 2024) -- 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 (HER; Andrychowicz et al., 2017) principle to natural-language agent trajectories for offline 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 (Zhou et al., 2024) and ToolBench (Qin et al., 2024), AgentHER improves over success-only SFT by +7.1-11.7 pp across four model families (GPT-4o...