AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling

Liang Ding

cs.AIMar 22, 2026

AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling

Authors: Liang Ding

Organizations: The University of Sydney

Abstract

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

Figures & tables

Panel of Figure 1 — Figure 1: AgentHER vs. conventional pipelines. Standard training retains only successes ( $\checkmark$ ), discarding 60–75% of data. AgentHER relabels failures ( $\circlearrowleft$ ) with achievable hindsight goals, expanding the effective training corpus ${\approx}3.7\times$ at a cost of ${\approx}\$ 1.4!\cdot!10^{-3}$ per accepted pair (Section 4.3 ).

Panel of Figure 2 — Figure 2: AgentHER four-stage pipeline. Stage 1 classifies failures and discards irrecoverable runs (dashed downward arrow). Stage 3 retries up to three times if the relabeling confidence $c<\theta$ . Stage 3 uses two independently trained LLMs (gpt-4o-mini and Qwen2.5-72B-Instruct) for relabeling and verification; both must agree (Section 3.5 ). Stages 1–2 offer zero-cost rule-based variants; Stage 4 is deterministic.

	WebArena WA-HeldOut (%)				ToolBench pass@1 (%)
Method	GPT-4o	Qwen-72B	Qwen-7B	LLaMA-8B	GPT-4o	Qwen-72B	Qwen-7B	LLaMA-8B
Base	13.7	20.9	8.2	6.5	53.2	60.1	44.6	42.1
SFT-Random ‡	18.0	25.6	13.9	12.7	61.4	68.9	54.8	52.9
SFT-Negative	18.6	26.1	14.5	13.1	62.1	69.5	55.6	53.7
Rejection-Sampling	20.7	28.6	16.9	15.5	66.2	73.7	59.8	57.4
SFT-Success	22.3	29.9	17.8	16.4	67.8	75.4	61.2	58.3

Table 1: Main results. WebArena: success rate (%) on the strict task-disjoint WA-HeldOut split. ToolBench: pass@1 (%) on official test splits. Best per column in bold ; second-best underlined .

\Delta

vs. SFT-Success;

\Delta_{b}

vs. best training-time baseline (AWM). All fine-tuned results averaged over 3 seeds; std

<

0.5 pts (Appendix E ). † Inference-time, online; reference only. ‡ Same 3,000 failed trajectories as AgentHER (equal-volume control). ICL = 8-shot in-context, no fine-tuning.

Stage	Calls /tr.	Cost ($)	Wall (m)
S1 detector	1.00	0.39	4.1
S2 extractor	1.00	0.55	4.6
S3a relabeler	1.27	0.84	6.7
S3b verifier (MJ-X only)	1.00	1.20	10.1
S4 augmenter (det.)	—	0.00	0.4
SJ total	3.27	1.78	15.8

Table 2: System-cost audit on 3,000 WebArena failures. S1–S3a shared by SJ/MJ-X; only S3b verifier is added in MJ-X. Pricing assumes gpt-4o-mini Batch API + prompt caching; Qwen-72B amortised on 8

\times

A100. Per-stage I/O token sizes are in App. F . ∗ LoRA cost: 4.4 h

\times

8 GPUs

\times

$1.05/h.

Panel of Figure 3 — Figure 3: Data efficiency and scaling (Qwen2.5-7B, WA-HeldOut ). (a) AgentHER-SJ at 50% successful demos matches SFT-Success at 100%; AgentHER-MJ-X exceeds it. (b) Both AgentHER variants scale log-linearly with failure volume; SFT-Success cannot benefit from additional failures. (c) Both variants peak near $\theta^{*}{=}0.5$ ; MJ-X is uniformly better and slightly more robust at low $\theta$ .

Panel of Figure 4 — Figure 4: Model-size scaling on WA-HeldOut (Qwen2.5 family). Labels above AgentHER-MJ-X points show $\Delta$ over SFT-Success. Gains are consistent at every scale (1.5B–72B), peaking at 14B (+9.0%). Even the 1.5B model nearly doubles in performance with AgentHER-MJ-X (6.4% $\to$ 12.0%).

Configuration	Success (%)	$\Delta$	Noise (%)
Full AgentHER-MJ-X (cross-model judge $+$ severity)	26.5	—	2.9
w/ Same-model multi-judge (MJ-S, two temps)	26.0	$-$ 0.5	4.4
w/o Multi-judge (single judge only, AgentHER-SJ)	25.7	$-$ 0.8	5.9
w/o Severity weighting ( $w{=}1$ for all)	25.0	$-$ 1.5	4.3
w/ Rule-based Extractor (Stage 2 degraded)	24.6	$-$ 1.9	6.0
w/ LLM Detector (Stage 1 upgraded)	27.4	$+$ 0.9	2.4

Table 3: Component ablation on WA-HeldOut (Qwen2.5-7B).

\Delta

relative to Full AgentHER-MJ-X; noise = fraction of accepted relabelings rated invalid by human annotators (Section 5.3 ). “MJ-S” = same-model multi-judge (Qwen-72B used twice with different temperatures, an analogue of self-consistency). “MJ-X” = cross-model multi-judge (gpt-4o-mini + Qwen-72B-Instruct), our default.

Failure type	WebArena	ToolBench
Incomplete	32.4%	21.0%
of which looping	12.1%	4.5%
Constraint_Violation	30.7%	17.6%
Wrong_Result	17.6%	23.7%
Tool_Error	4.2%	25.4%
Hallucination	7.0%	8.5%

Table 4: Failure-type distribution of collected failed trajectories. WebArena (3,000 trajectories) and ToolBench (5,000 trajectories), classified by Stage 1. “Looping” is a sub-mode of Incomplete where the agent repeats one action

\geq 3

times; reported separately given its distinct recoverability profile.

Panel of Figure 5 — Figure 5: Per-failure-type gain on both benchmarks (Qwen2.5-7B, AgentHER-SJ). Incomplete and Constraint_Violation dominate both benchmarks; Tool_Error yields the least. The ranking is consistent across benchmarks even though failure-mode prevalences differ (Table 4 ).

	WebArena		ToolBench
Group	n	Valid (%)	n	Valid (%)
SJ accepted	169	94.1	168	92.3
MJ-S accepted	142	95.6	138	94.0
MJ-X accepted	137	97.1	132	96.0
Filter-rejected	31	38.7	32	35.8
Fleiss’ $\kappa$	—	0.82	—	0.79

Table 5: Human evaluation of relabeling precision on both benchmarks. 200 sampled pairs per benchmark; three NLP-PhD annotators blind to scores; majority vote. Filtered = pairs rejected by the confidence filter; their human validity is reported to gauge the false-rejection rate.

Round	Src.	New fails	Accepted	Suc. (%)
0 (SFT-Only)	—	—	—	17.8
1 (MJ-X)	GPT-3.5	3,000	2,144	26.5
2 (Iter. +1)	Q-R1	2,500	1,710	27.9
3 (Iter. +2)	Q-R2	2,000	1,320	28.2

Table 6: Iterative AgentHER (Qwen2.5-7B, WA-HeldOut ). Each round collects new failures, relabels, and retrains on the full accumulated corpus. Q-R1/R2 = Qwen-7B Round 1/2.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Role	Stage	Model	Notes
Collection agent	—	gpt-3.5-turbo-0125	Intentionally weak.
Failure detector	1 (LLM)	gpt-4o-mini	$T{=}0$ , JSON schema.
Outcome extractor	2 (LLM)	gpt-4o-mini	$T{=}0$ , factuality-only.
Relabeler $\mathcal{J}_{1}$	3	gpt-4o-mini	$T{=}0.3$ ; $T{=}0.7$ on retry.
Verifier $\mathcal{J}_{2}$ (MJ-X)	3	Qwen2.5-72B-Instruct	$T{=}0$ , vLLM, schema-constrained.
Verifier $\mathcal{J}_{2}$ (MJ-S)	3	Qwen2.5-72B-Instruct	Ablation only; same as $\mathcal{J}_{1}$ at $T{=}0.7$ .

Appendix

Table 7: LLM roles in the AgentHER pipeline. Collection uses a weak model (to produce diverse failures); judging uses strong, architecturally independent models.

Hyperparameter	SFT (LoRA)	DPO (LoRA)
LoRA rank $r$	16	16
LoRA $\alpha$	32	32
LoRA dropout	0.05	0.05
LoRA target modules	q,k,v,o,gate,up,down	q,k,v,o
Learning rate	$2\times 10^{-4}$	$5\times 10^{-5}$
LR schedule	cosine	cosine

Appendix

Table 8: Training hyperparameters used for all open-weight models.

Method	Full (812)	HeldOut (200)	Drop
Base	8.6	8.2	$-$ 0.4
SFT-Success	18.9	17.8	$-$ 1.1
ETO	22.1	21.0	$-$ 1.1
AWM	23.4	22.4	$-$ 1.0
AgentHER-SJ	27.0	25.7	$-$ 1.3
AgentHER-MJ-X	27.8	26.5	$-$ 1.3

Appendix

Table 9: Comparison of held-out and full-task results on WebArena (Qwen2.5-7B). “Full” = the original 812-task evaluation (used by all prior WebArena papers); “HeldOut” = our 200-task task-disjoint test split. Numbers in the main paper use the HeldOut column. The drop from Full to HeldOut quantifies the modest amount of task-overlap leakage in the standard 812-task setup; AgentHER’s advantage over baselines is preserved under the stricter protocol.

Category	Base	SFT-Random	SFT-Success	AgentHER-SJ	AgentHER-MJ-X
G1 (single-tool)	49.3	57.2	67.1	76.4	77.9
G2 (intra-category)	41.7	51.3	58.3	68.5	70.0
G3 (cross-category)	38.2	47.8	54.2	65.0	66.6
Overall	44.6	54.8	61.2	71.0	72.6

Appendix

Table 10: ToolBench pass@1 (%) by category group (Qwen2.5-7B). All numbers on the official test splits (disjoint by construction).

Failed processed	500	1,000	1,500	2,000	3,000	5,000
AgentHER-SJ	20.0	21.5	22.9	23.9	25.7	26.4
AgentHER-MJ-X	20.6	22.2	23.7	24.7	26.5	27.2

Appendix

Table 11: WA-HeldOut success rate (%) vs. number of failed trajectories, fixed 500 successful demonstrations, Qwen2.5-7B.

Method	G1	G2	G3	Overall	$\Delta$
Base (no FT)	49.3	41.7	38.2	44.6	—
SFT-Success	63.2	55.8	51.4	57.1	$+$ 12.5 (vs. Base)
AgentHER-SJ	70.1	64.3	59.8	65.0	$+$ 7.9 (vs. S-S)
AgentHER-MJ-X	71.8	65.9	61.4	66.6	$+$ 9.5 (vs. S-S)

Appendix

Table 12: Cross-benchmark transfer (Qwen2.5-7B): train on WA-Train only, zero-shot evaluation on ToolBench official test splits.

Subset	n	Recoverable (%)	Accepted (%)	Avg. $\Delta$ (%)
Looping (WebArena)	363	24.2	21.5	$+$ 3.4
Non-looping (WebArena)	2,637	81.6	78.4	$+$ 9.5
Looping (ToolBench)	225	38.7	35.1	$+$ 3.9
Non-looping (ToolBench)	4,775	84.6	81.7	$+$ 10.7

Appendix

Table 13: Looping-failure subset. Trajectories where the agent repeats a single action

\geq

3 times before termination. “Recovered” = passed Stage 1 recoverability filter and was relabeled by AgentHER-MJ-X.

Method	Mean	Std
Base	8.2	0.0 (deterministic)
SFT-Success	17.8	$\pm$ 0.3
SFT-Random	13.9	$\pm$ 0.4
SFT-Negative	14.5	$\pm$ 0.4
Rejection-Sampling	16.9	$\pm$ 0.4
ETO	21.0	$\pm$ 0.4

Appendix

Table 14: Multi-run statistics on WA-HeldOut : success rate (%), mean

\pm

std over 3 seeds (Qwen2.5-7B).

Stage	Model	Calls / traj.	Inp tok	Out tok	Cost (USD)	Wall (s)
1: Failure detector	gpt-4o-mini	1.00	1,800	200	$1.30{\times}10^{-4}$	0.82
2: Outcome extractor	gpt-4o-mini	1.00	2,500	300	$1.83{\times}10^{-4}$	0.92
3a: Relabeler	gpt-4o-mini	1.27	2,700	400	$2.79{\times}10^{-4}$	1.34
3b: Verifier (MJ-X)	Qwen2.5-72B	1.00	3,000	200	$4.00{\times}10^{-4}$	1.94
4: Data augmenter	deterministic	1.00	—	—	0	0.08
SJ total	—	3.27	—	—	$5.92{\times}10^{-4}$	3.16

Appendix

Table 15: Token-level cost breakdown per stage. Token counts are means; “Calls” are the per-input-trajectory averages including retries. Pricing reflects gpt-4o-mini Batch API (50% off list) combined with prompt caching (75% off cached input) for repeated system prompts—a standard production setup; the standalone list price would be

{\approx}2{\times}

these values. Qwen2.5-72B-Instruct cost is for a vLLM deployment on a rented 8

\times

A100-80G node (

\

1.05

/GPU-hour) with 32-way request batching; the tabulated

$4.0{\times}10^{-4}$ per call represents the amortised hardware cost.

Metric	S-S	AgentHER
Task clusters covered (of 18)	11	14
Long-tail clusters (unique)	0	3
JS divergence (vs. AgentHER)	0.31	—
Avg. cluster entropy	1.83	2.47

Appendix

Table 16: Goal-distribution analysis on WA-HeldOut collection. AgentHER-MJ-X relabeled goals cover more semantic task clusters and uniquely cover three long-tail clusters absent from SFT-Success (“S-S”).

Hindsight Experience Replay

See all 9 papers

Spinning Straw into Gold: Relabeling LLM Agent Trajectories in Hindsight for Successful Demonstrations
Jul 5, 2026Zichao Li, Gang Wu, Zichao Wang +5LLM Agent Training Long-Horizon Agent Tasks
Mila, McGill University · Adobe Research
Agent^2 RL-Bench: Can LLM Agents Engineer Agentic RL Post-Training?
Apr 12, 2026Wanyi Chen, Xiao Yang, Xu Yang +7Agentic RL AI Agent Benchmarks
Soochow University · Microsoft Research Asia · Stony Brook University +2
Agent Error Dataset: Scaling 50,000 Error--Diagnosis Pairs for Failure Analysis and Error-Aware Post-Training
Sep 30, 2026Kunlun Zhu, Xuyan Ye, Yibo Li +3Agent Failure Analysis LLM Agent Training
Apodex

Jul 5, 2026J/K move · Enter open · S save

Spinning Straw into Gold: Relabeling LLM Agent Trajectories in Hindsight for Successful Demonstrations

Zichao Li, Gang Wu, Zichao Wang, Ruiyi Zhang+4

Mila, McGill University · Adobe Research

LLM Agent Training Long-Horizon Agent Tasks Long-Horizon LLM Agents

Open paper AskPDF arXiv

Large language model agents operate in partially observable, long-horizon settings where obtaining supervision remains a major bottleneck. We address this by utilizing a source of supervision overlooked in existing post-training methods: unintended yet successful goals embedded within agent rollouts. Specifically, we introduce Hindsight Supervised Learning (HSL), where an auxiliary LLM reviews each completed trajectory and relabels it with all of the natural-language goals the agent actually achieved. HSL then pairs the trajectory with its relabeled goals and uses these pairs for additional fine-tuning. To mitigate suboptimality in the relabeled data, we propose two learning techniques for HSL, irrelevant-action masking and sample reweighting. Our experiments show that HSL is flexible and compatible with existing post-training pipelines. It improves both SFT and DPO, with larger gains on long-horizon tasks with more diverse goal spaces. Moreover, HSL is sample-efficient: on ALFWorld, it surpasses baselines trained on the full dataset while using only one quarter of the ground-truth demonstrations.

Abstract

Hindsight Experience Replay

Explore similar work

Spinning Straw into Gold: Relabeling LLM Agent Trajectories in Hindsight for Successful Demonstrations

Agent^2 RL-Bench: Can LLM Agents Engineer Agentic RL Post-Training?

Agent Error Dataset: Scaling 50,000 Error--Diagnosis Pairs for Failure Analysis and Error-Aware Post-Training