# AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling

arXiv: https://arxiv.org/abs/2603.21357 · HTML: https://mlsanity.com/paper/2603.21357/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use.
- Builds on 32 of its 45 references that are in the map.
- First posted on arXiv 22 Mar 2026.

## Placed in

- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 30 of 32)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [Mind2Web: Towards a Generalist Agent for the Web](https://mlsanity.com/paper/2306.06070/) (2023)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate](https://mlsanity.com/paper/2305.19118/) (2023)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [ExpeL: LLM Agents Are Experiential Learners](https://mlsanity.com/paper/2308.10144/) (2023)
- [CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing](https://mlsanity.com/paper/2305.11738/) (2023)
- [Instruction Tuning with GPT-4](https://mlsanity.com/paper/2304.03277/) (2023)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [AgentTuning: Enabling Generalized Agent Abilities for LLMs](https://mlsanity.com/paper/2310.12823/) (2023)
- [FireAct: Toward Language Agent Fine-tuning](https://mlsanity.com/paper/2310.05915/) (2023)
- [V-STaR: Training Verifiers for Self-Taught Reasoners](https://mlsanity.com/paper/2402.06457/) (2024)
- [Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents](https://mlsanity.com/paper/2408.07199/) (2024)
- [Trial and Error: Exploration-Based Trajectory Optimization for LLM Agents](https://mlsanity.com/paper/2403.02502/) (2024)
- [Error Analysis Prompting Enables Human-Like Translation Evaluation in Large Language Models](https://mlsanity.com/paper/2303.13809/) (2023)
- [SteP: Stacked LLM Policies for Web Actions](https://mlsanity.com/paper/2310.03720/) (2023)

## Built on by (most cited first, 13 of 13)

- [Off-Context GRPO: Learning to Reason on Hard Problems using Privileged Information](https://mlsanity.com/paper/2607.19313/) (2026)
- [TRCA: Transition-wise Rubric Credit Assignment for Long-horizon LLM Agents](https://mlsanity.com/paper/2608.16156/) (2026)
- [Speculate with Memory: Lossless Acceleration for LLM Agents](https://mlsanity.com/paper/2607.12236/) (2026)
- [Agent Memory Distillation: Empowering Small LLM Agents with Hierarchical Teacher Memory](https://mlsanity.com/paper/2608.07169/) (2026)
- [State2State: Environment-Derived Mid-Training for LLM Agents](https://mlsanity.com/paper/2608.04934/) (2026)
- [AgentBrew: Offline Tool-Use Agent Learning from Raw Real-World Trajectories](https://mlsanity.com/paper/2609.05837/) (2026)
- [From Cognitive Architectures to Language Agents: A Mechanism-Level Review of Lineage, Convergence, and Migration Gaps](https://mlsanity.com/paper/2607.23942/) (2026)
- [Terminal Agents: A Survey of AI Agents in Command-Line Environments](https://mlsanity.com/paper/2608.20485/) (2026)
- [Agent Error Dataset: Scaling 50,000 Error--Diagnosis Pairs for Failure Analysis and Error-Aware Post-Training](https://mlsanity.com/paper/2609.40111/) (2026)
- [Grounded Scaling: Why Agentic AI Needs Deterministic Environments](https://mlsanity.com/paper/2606.22495/) (2026)
- [HindSearch: Trajectory-Level Hindsight Critique for Search-Augmented Reinforcement Learning](https://mlsanity.com/paper/2608.01597/) (2026)
- [MemeMind: Reference-Guided Trace Construction for Offline Context Optimization](https://mlsanity.com/paper/2608.09316/) (2026)
- [One Rollout Is All You Get: Fully Test-Time Adaptation for GUI Agents](https://mlsanity.com/paper/2609.34321/) (2026)

## Abstract (arXiv)

LLM-agent training pipelines routinely discard failed trajectories even though GPT-4o achieves only 14-20% on WebArena and below 55% pass@1 on ToolBench; even specialised systems at 50-65% leave the majority of trajectories unused. We introduce AgentHER, which recovers this lost signal by adapting Hindsight Experience Replay (HER) to natural-language agent trajectories: a trajectory that fails goal A is often a correct demonstration for an achievable alternative goal B. AgentHER realises this through a four-stage pipeline (failure classification, outcome extraction, LLM-guided relabeling with confidence gating, and data packaging) that converts discarded failures into SFT, DPO, and ShareGPT training data. On WebArena and ToolBench under a strict task-disjoint held-out protocol, AgentHER improves over success-only SFT by +7.6-11.4% across four model families (GPT-4o, Qwen2.5-72B/7B, LLaMA-3.1-8B), achieves 2x sample efficiency, and beats the strongest experience-centric baseline (Agent Workflow Memory) by +3.0-6.2%. Two robustness mechanisms, failure-severity weighting and cross-model multi-judge verification (gpt-4o-mini paired with Qwen2.5-72B-Instruct), reduce label noise from 5.9% to 2.9% and raise human-rated relabeling precision to 97.1% on WebArena and 96.0% on ToolBench. A full system-cost audit shows the entire relabeling pipeline costs 2.98 and 26 wall-clock minutes for 3,000 trajectories, i.e. 1.4 x 10^-3 per accepted pair. Code: https://github.com/alphadl/AgentHER