Source-linked AI summary
Sample-Efficient Online Learning in LM Agents via Hindsight Trajectory Rewriting
Michael Y. Hu, Benjamin Van Durme, Jacob Andreas, Harsh Jhamtani
TL;DR
Language-model agents can learn inefficiently from limited interactions in unfamiliar environments, where interactions may be costly. ECHO adapts hindsight experience replay by using language models to rewrite failed trajectories into optimized counterfactual examples. It outperforms ReAct substantially on XMiniGrid-Stateful, while on PeopleJoinQA-Stateful it beats ReAct but is slightly behind the best baseline in accuracy.
Problem
Language-model agents often have poor sample efficiency in unfamiliar interactive environments, where interactions can be costly and existing methods make limited use of counterfactual trajectory reasoning.
Source: §1 · pp. 1–2Method
ECHO adapts hindsight experience replay by having a language model identify alternative goals and rewrite failed trajectories into optimized counterfactual trajectories.
Source: §1 · p. 2, §3.1 · p. 3Results
On XMiniGrid-Stateful, ECHO outperforms ReAct by 80% in average reward and the next-best baseline by 42%; on PeopleJoinQA-Stateful, it beats ReAct in accuracy and efficiency but trails the best baseline in accuracy by 4.6% and ties it in efficiency.
Source: §1 · p. 2Takeaways & Limitations
ECHO offers a promising approach to improving sample efficiency, particularly in partially observable environments with sparse feedback.
Source: §6 · p. 8The work primarily uses natural-language trajectory representations, and its shorter-trajectory update heuristic may be improved with a more sophisticated compression-biased rule.
Source: §5.3 · pp. 7–8
Abstract
from arXiv · showhide
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.
1 Introduction
ECHO addresses the limits of online learning from costly interactions by using language models to rewrite failed trajectories into counterfactual examples. On XMiniGrid-Stateful, it outperforms ReAct and the next-best baseline; on PeopleJoinQA-Stateful, it improves on ReAct but falls short of the best baseline in accuracy.
1 Introduction
- Existing online-learning frameworks use reflection, memory, or replay, but make limited use of language models’ ability to reason about counterfactuals from failures.The motivating setting includes costly interactions, such as with humans or physical systems.Source: §1 · pp. 1–2
- From a failed XMiniGrid trajectory, ECHO identifies other reachable objects and generates optimized trajectories that can help complete unseen goals later.The evaluation varies the queries or tasks while resetting the environment to the same initial position or state.Source: Figure 1 · p. 2, §1 · p. 2
- ECHO adapts hindsight experience replay to language models, generating counterfactual trajectories for more sample-efficient learning.Unlike relabeling a goal alone, ECHO can rewrite both a failed trajectory’s goal and its intermediate steps.Source: §1 · p. 2
- On XMiniGrid-Stateful, ECHO outperforms ReAct by 80% in average reward and the next-best baseline by 42%; on PeopleJoinQA-Stateful, it beats ReAct on accuracy and efficiency but trails the best baseline in accuracy by 4.6% and ties it in efficiency.The evaluation uses stateful environments with persistent scratchpad memory and repeated tasks from the same initial state.Source: §1 · p. 2
2 Related Work
Related work frames language-model agents as interactive systems that need to adapt beyond static pretrained knowledge. The paper situates ECHO among memory and experience-replay approaches, emphasizing its extension of hindsight relabeling to synthetic trajectories.
Language Model Agents
- Language-model agents use a perception–action loop to interact with environments, but reliance on static pretrained knowledge can limit adaptation in novel settings.The cited examples span web navigation, tool use, collaboration, and code generation.Source: §2 · p. 3
Offline Reasoning and Memory
- Reflexion builds semantic memory through trajectory reflection, while Agent Workflow Memory stores successful workflows as episodic memory.The paper presents these as baselines for manipulating the two memory types.Source: §2 · p. 3
Experience Replay
- Experience replay reuses informative trajectories, and hindsight experience replay relabels past trajectories with goals achieved during execution.ECHO generalizes HER by editing arbitrary trajectory aspects and inducing synthetic trajectories.Source: §2 · p. 3
3 Approach
ECHO uses an LM to identify goals achievable from past trajectories and rewrite them as optimized workflows, then retains concise goal-specific descriptions in memory. The section also contrasts this approach with Reflexion and AWM using a shared failed XMiniGrid trajectory.
3.1 ECHO: Experience Consolidation via Hindsight Optimization
- ECHO prompts an LM to infer goals achievable from a trajectory and generate optimized natural-language workflows for them.Unlike relabeling alone, its hindsight rule can revise both goals and intermediate steps.Source: §3.1 · pp. 3–4
- For each goal, ECHO keeps the shorter of the newly generated descriptor and its predecessor to favor compact replay-buffer descriptions.The online setting processes queries sequentially without ground-truth rewards or demonstrations.Source: §3.1 · pp. 3–4
3.2 Baselines
- Reflexion and AWM are recast in the hindsight-update framework, with baseline updates appending hindsight edits to memory.The section presents their hindsight rules as the important algorithmic difference.Source: §3.2 · p. 4, §3.3 · p. 4
3.3 Qualitative Example
- After the agent fails to pick up a grey key, the example compares Reflexion, AWM, and ECHO on the same trajectory.The shared episode makes their different memory outputs directly comparable.Source: §3.3 · p. 4
Reflexion
- Reflexion gives generic failure feedback that does not change XMiniGrid-Stateful performance, while AWM declines a workflow after failure and ECHO produces a correct grey-star workflow.ECHO uses the observed but uncollected star as an alternative goal.Source: Reflexion · p. 5
4 Results
The section evaluates ECHO on stateful XMiniGrid and PeopleJoinQA benchmarks, using final reward or accuracy alongside cumulative average reward to track performance over successive queries.
4 Results
- The evaluation tests stateful versions of XMiniGrid and PeopleJoinQA, where exploration is important for solving queries.The experiments use GPT-4o.Source: §4 · p. 5
4.1 Evaluation
- Cumulative average reward tracks sample efficiency as the average of rewards through an episode, with rewards reported as gains over ReAct.The evaluation also reports final average reward or accuracy.Source: §4.1 · p. 5
4.2 XMiniGrid-Stateful
- ECHO strictly outperforms the other methods on XMiniGrid, and Figure 2 shows its cumulative reward exceeding ReAct’s after three interactions.XMiniGrid-Stateful repeats object-pickup queries in fixed procedurally generated environments, allowing agents to learn unseen object locations over time.Source: §4.2 · pp. 5–6, Figure 2 · p. 6
- In XMiniGrid trajectory-validity tests, agents reached 34 of 40 hindsight-imputed goals; two remaining failures involved infeasible synthesized steps.The other four failures arose from agent deviations from execution instructions.Source: §4.2 · p. 6
4.3 PeopleJoinQA-Stateful
- On PeopleJoinQA-Stateful, Reflexion is most accurate, while ECHO and AWM complete tasks in around 1.6 fewer messages on average.The benchmark fixes each organization between queries, allowing agents to reflect on how information is distributed.Source: §4.3 · p. 6, Figure 3 · p. 7
- Across PeopleJoinQA organizations, no method dominates accuracy or efficiency; ECHO becomes the most efficient after around 15 queries in one department-store organization.The authors identify improving robustness across settings as future work.Source: §4.3 · p. 7
5 Discussion
ECHO uses an LM’s pretrained knowledge to improve past trajectories without requiring a complete world model, and treats language as a flexible medium for experience replay. The discussion identifies natural-language representations and the trajectory-update heuristic as areas for further development.
5.1 Language Models as Incomplete World Models
- ECHO uses pretrained knowledge to propose local improvements to past trajectories, which can help in partially observable settings where building a complete world model is infeasible.After a single trajectory, the LM may lack enough information to infer a full internal world model.Source: §5.1 · p. 7
5.2 Connections between RL and Prompting
- Unlike traditional hindsight replay based on numerical rewards and states, ECHO lets LMs edit experiences in natural language and act as both world models and policy generators.The discussion frames this as a bridge between experience-based learning and symbolic reasoning.Source: §5.2 · p. 7
5.3 Limitations and Future Work
- The paper primarily uses natural-language representations; future work could explore programmatic representations and an update heuristic that combines new and old information while preserving compression.It also suggests retrieval-based memory for more targeted reuse of relevant experiences.Source: §5.3 · pp. 7–8
6 Conclusion
The conclusion presents ECHO as an approach to improving LM-agent sample efficiency by using LMs to edit and optimize past trajectories. It evaluates the approach in two stateful benchmarks requiring exploration and multi-step reasoning.
6 Conclusion
- ECHO adapts hindsight experience replay from off-policy reinforcement learning to improve LM-agent sample efficiency.The framework uses agents as incomplete world models to edit and optimize earlier trajectories.Source: §6 · p. 8
- The evaluation introduces XMiniGrid-Stateful and PeopleJoinQA-Stateful, adaptations of existing benchmarks that require exploration and multi-step reasoning.Source: §6 · p. 8
- The conclusion identifies partially observable environments with sparse feedback as settings where ECHO may support more sample-efficient and adaptable agents.Source: §6 · p. 8
A Prompts
Offline proactive reasoning methods are paired with a ReAct agent for action execution. In PeopleJoinQA-Stateful, the decision policy uses prompts from Jhamtani et al. (2025).
A Prompts
- Reflexion, AWM, ECHO, and their variants are each paired with a ReAct agent that performs actions.This pairing applies to all offline proactive reasoning methods studied.Source: A Prompts · p. 10
A.2 PeopleJoinQA-Stateful
- PeopleJoinQA-Stateful decision-policy prompts come from Jhamtani et al. (2025).The passage points to the PeopleJoin repository for those prompts.Source: §A.2 · p. 12
B Hyperparameters
The appendix labels the agent and offline reasoning settings and identifies tables for ReAct and offline results in XMiniGrid-Stateful and PeopleJoin. Figure 4 reports organization-level variation in whether offline methods outperform the baseline.
B Hyperparameters
- The appendix labels the agent setting “ReACT” and the offline proactive-reasoning setting “Offline,” whose GPT-4o hyperparameters differ slightly.Source: B Hyperparameters · p. 14
- Tables 1 and 2 are labeled for XMiniGrid-Stateful ReACT and Offline, while Tables 3 and 4 are labeled for PeopleJoin ReACT and Offline.Source: Table 1 · p. 14, Table 2 · p. 14, Table 3 · p. 14
- Figure 4 samples five PeopleJoinQA organizations for variation in organization size and query count; no offline method consistently beats the baseline on both accuracy and efficiency across all five.Source: Figure 4 · p. 15