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

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Hindsight relabeling of failed agent trajectories into successful demonstrations

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Hindsight Supervised Learning (HSL) extracts additional supervision from LLM agent rollouts by using an auxiliary LLM to retroactively relabel each trajectory with all natural-language goals the agent incidentally achieved. Fine-tuning on these relabeled successes—combined with irrelevant-action masking and sample reweighting—improves both SFT and DPO baselines. With fewer than 25% of ground-truth demonstrations, HSL matches or surpasses baselines trained on the full dataset.

Problem

Post-training LLM agents is bottlenecked by supervision: SFT requires expensive expert demonstrations, RL struggles with sparse rewards and long horizons, and self-imitation methods exploit only explicitly successful on-policy rollouts. Failed or partially-successful trajectories are discarded, wasting the rich signal of unintended sub-goals the agent actually achieves during exploration.

Method

HSL frames hindsight relabeling as a three-stage loop inserted alongside any existing training pipeline:

1. Trajectory collection: The agent rolls out under sampled instructions \(I \sim D_\text{train}\), producing trajectories \(\tau_T\) including final observation \(o^*\).

2. Relabeling: An auxiliary LLM \(M\) (Llama-3.3-70B in experiments) is prompted zero-shot to identify all goals \(\{I'_1,\ldots,I'_K\}\) actually achieved in \(\tau_T\). For each achieved goal \(I'_k\), \(M\) also labels each action \(a_u\) with a binary relevance score \(z_u \in \{0,1\}\) indicating whether it was necessary for \(I'_k\).

3. Learning: Relabeled demonstrations \((τ_{S(k)}, I'_k, z_{1:S(k)})\) are stored in a rolling buffer \(D'\) of size 100. The HSL loss masks irrelevant actions and reweights samples by task difficulty and optimality:

\[\mathcal{L}^{D'}_\theta = \mathbb{E}_{d'\sim P^{w'}(\cdot)}\left[\frac{1}{T}\sum_{t=1}^T -z_t \cdot \log P_\theta(a_t|\tau_{t-1}, o_t, I')\right]\]

The full objective mixes this with a standard SFT loss on ground-truth data: \(\mathcal{L}^\text{HSL}_\theta = \lambda \mathcal{L}^{D'}_\theta + (1-\lambda)\mathcal{L}^\text{SFT}\). The buffer is continuously refreshed on-policy, aligning the hindsight distribution with the agent's current occupancy. A theoretical bound (Theorem 1) shows that SFT on relabeled demonstrations reduces the KL divergence between the agent \(\pi_\theta\) and optimal policy \(\pi^*\) as a second term alongside the standard ground-truth SFT term, with the gap shrinking as \(\kappa_{E\leftarrow H}\) (occupancy coverage ratio) improves.

Key Contributions

• HSL framework: plug-in post-training method that mines unintended achievements from any agent rollout and converts them into supervised training signal without requiring additional environment interaction or reward signals.
• Irrelevant-action masking: suppresses loss on actions irrelevant to the relabeled goal, reducing imitation of suboptimal hindsight experts (reduces \(\delta_E\)).
• Demonstration reweighting: weights \(w_d = (n_d/T_d)^\alpha \cdot n_d\) to counteract overrepresentation of easy goals and prioritize more optimal, challenging demonstrations.
• Theoretical justification: Theorem 1 provides an upper bound on expert–agent discrepancy that decreases when training on both ground-truth and relabeled demonstrations, motivating continuous on-policy buffer updates.
• Compatibility: shown to improve both SFT and DPO baselines across three diverse benchmarks.

Results

• ALFWorld (seen/unseen): SFT+HSL achieves 93.57%/97.76%, vs. SFT baseline 82.14%/78.36% — gains of +11.4% seen, +19.4% unseen; DPO+HSL achieves 92.86%/94.78% vs. DPO 85.71%/82.84%.
• PlanCraft: SFT+HSL 75.12%, DPO+HSL 75.42%, vs. SFT 70.00%, DPO 71.25%.
• WebShop: SFT+HSL 66.97 task score, DPO+HSL 70.52, vs. SFT 63.81, DPO 69.54.
• Sample efficiency: on ALFWorld, HSL using <25% of ground-truth demonstrations surpasses SFT or DPO trained on the full dataset; at 800 demonstrations, HSL nearly doubles SFT on the unseen split.
• BAGEL (offline synthesis with Llama-3.3-70B): 84.29%/91.79% seen/unseen on ALFWorld — substantially below SFT+HSL, confirming the value of on-policy, continuously updated relabeling.
• BEHAVIORCLONE (Llama-3.3-70B synthetic demos): 83.57%/88.81%, below SFT+HSL despite using a much stronger model for data generation.

Limitations

• Relies on a large auxiliary LLM (Llama-3.3-70B) for relabeling, which may be costly or unavailable in resource-constrained settings.
• Still requires some ground-truth demonstrations for stable learning; not fully unsupervised.
• HSL yields smaller gains on benchmarks with single achievable goals per trajectory (WebShop) or narrow goal spaces, limiting generality of the full benefit.
• Relabeling quality depends on the auxiliary LLM's zero-shot reasoning ability; errors in goal identification or action relevance labeling can introduce noisy training signal.
• Evaluated only on text-based simulated environments with a 1B parameter agent; scalability to larger models or real-world web/embodied settings is untested.

Relevance to Agentic AI / LLM Agents

HSL directly addresses one of the core bottlenecks in LLM agent training: the scarcity and cost of successful demonstrations in long-horizon, partially observable settings. By systematically mining unintended sub-goal achievements from rollouts, it extends the hindsight experience replay idea from goal-conditioned RL into the LLM-agent post-training paradigm, making it applicable to natural-language goal spaces where state-matching is replaced by LLM-based semantic inference. The result is a general-purpose wrapper that improves sample efficiency of both SFT and DPO pipelines without needing reward signals, which is particularly valuable for domains where environment interaction is restricted (safety, privacy). This connects directly to ongoing work on scalable agent training, data synthesis from agent experience, and reducing dependence on expensive human-curated trajectories.