# Sample-Efficient Online Learning in LM Agents via Hindsight Trajectory Rewriting

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in Agent memory systems, one of 16 directions in LLM agents and tool use.
- Builds on 21 of its 27 references that are in the map.
- First posted on arXiv 11 Oct 2025.

## Placed in

- LLM agents and tool use / [Agent memory systems](https://mlsanity.com/agents/agent-memory-systems/)

## Builds on (most cited first, 21 of 21)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (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)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [ChatDev: Communicative Agents for Software Development](https://mlsanity.com/paper/2307.07924/) (2023)
- [ExpeL: LLM Agents Are Experiential Learners](https://mlsanity.com/paper/2308.10144/) (2023)
- [Cognitive Architectures for Language Agents](https://mlsanity.com/paper/2309.02427/) (2023)
- [Agent Workflow Memory](https://mlsanity.com/paper/2409.07429/) (2024)
- [Can Large Language Models Transform Computational Social Science?](https://mlsanity.com/paper/2305.03514/) (2023)
- [Synapse: Trajectory-as-Exemplar Prompting with Memory for Computer Control](https://mlsanity.com/paper/2306.07863/) (2023)
- [Measuring AI Ability to Complete Long Software Tasks](https://mlsanity.com/paper/2503.14499/) (2025)
- [Inducing Programmatic Skills for Agentic Tasks](https://mlsanity.com/paper/2504.06821/) (2025)
- [Synthetic Experience Replay](https://mlsanity.com/paper/2303.06614/) (2023)
- [XLand-MiniGrid: Scalable Meta-Reinforcement Learning Environments in JAX](https://mlsanity.com/paper/2312.12044/) (2023)
- [BAGEL: Bootstrapping Agents by Guiding Exploration with Language](https://mlsanity.com/paper/2403.08140/) (2024)
- [CodeIt: Self-Improving Language Models with Prioritized Hindsight Replay](https://mlsanity.com/paper/2402.04858/) (2024)
- [Interpreting User Requests in the Context of Natural Language Standing Instructions](https://mlsanity.com/paper/2311.09796/) (2023)

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

- [Skill-SD: Skill-Conditioned Self-Distillation for Multi-turn LLM Agents](https://mlsanity.com/paper/2604.10674/) (2026)
- [AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling](https://mlsanity.com/paper/2603.21357/) (2026)
- [GRASP: Gated Regression-Aware Skill Proposer for Self-Improving LLM Agents](https://mlsanity.com/paper/2605.29668/) (2026)
- [Off-Context GRPO: Learning to Reason on Hard Problems using Privileged Information](https://mlsanity.com/paper/2607.19313/) (2026)
- [Planning with the Views](https://mlsanity.com/paper/2605.29563/) (2026)
- [Agent Memory Distillation: Empowering Small LLM Agents with Hierarchical Teacher Memory](https://mlsanity.com/paper/2608.07169/) (2026)
- [View-oriented Conversation Compiler for Agent Trace Analysis](https://mlsanity.com/paper/2603.29678/) (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)
- [My FAULT: Self-Diagnosis as Credit Assignment in Self-Evolving Agentic Reinforcement Learning](https://mlsanity.com/paper/2610.01161/) (2026)
- [TeleTune: Evolving Agent Skills From Offline Telemetry](https://mlsanity.com/paper/2610.05437/) (2026)
- [Fan Out or Relay? Ownership-Aware Routing for LLM Agents Querying Siloed Tables](https://mlsanity.com/paper/2610.18157/) (2026)
- [Co-Evolving Acting and Forecasting for Language Agents](https://mlsanity.com/paper/2610.20597/) (2026)

## Abstract (arXiv)

Language model (LM) agents deployed in novel environments often exhibit poor sample efficiency when learning from sequential interactions. This significantly hinders the usefulness of such agents in environments where interaction is costly (for example, when they interact with humans or reset physical systems). While a number of existing LM agent architectures incorporate various mechanisms for experience storage and reflection, they make limited use of LMs' abilities to directly generate or reason about full counterfactual trajectories. We introduce ECHO (Experience Consolidation via Hindsight Optimization), a prompting framework that adapts hindsight experience replay from reinforcement learning for language model agents. ECHO generates optimized trajectories for alternative goals that could have been achieved during failed attempts, effectively creating synthetic positive examples from unsuccessful interactions. Our approach consists of two components: a hindsight rule that uses the language model itself to identify relevant subgoals and generate optimized trajectories, and an update rule that maintains compressed trajectory representations in memory. We evaluate ECHO on stateful versions of XMiniGrid, a text-based navigation and planning benchmark, and PeopleJoinQA, a collaborative information-gathering enterprise simulation. Across both domains, ECHO outperforms vanilla language agent baselines by up to 80%; in XMiniGrid, it also outperforms a number of sophisticated agent architectures including Reflexion and AWM, demonstrating faster adaptation to novel environments through more effective utilization of past experiences.