# Environment Maps: Structured Environmental Representations for Long-Horizon Agents

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 10 of its 14 references that are in the map.
- First posted on arXiv 24 Mar 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

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

- [SkillWeaver: Web Agents can Self-Improve by Discovering and Honing Skills](https://mlsanity.com/paper/2504.07079/) (2025)
- [AutoDroid: LLM-powered Task Automation in Android](https://mlsanity.com/paper/2308.15272/) (2023)
- [Is Your LLM Secretly a World Model of the Internet? Model-Based Planning for Web Agents](https://mlsanity.com/paper/2411.06559/) (2024)
- [Web Agents with World Models: Learning and Leveraging Environment Dynamics in Web Navigation](https://mlsanity.com/paper/2410.13232/) (2024)
- [Inducing Programmatic Skills for Agentic Tasks](https://mlsanity.com/paper/2504.06821/) (2025)
- [WebEvolver: Enhancing Web Agent Self-Improvement with Coevolving World Model](https://mlsanity.com/paper/2504.21024/) (2025)
- [GUI-explorer: Autonomous Exploration and Mining of Transition-aware Knowledge for GUI Agent](https://mlsanity.com/paper/2505.16827/) (2025)
- [Learning on the Job: An Experience-Driven Self-Evolving Agent for Long-Horizon Tasks](https://mlsanity.com/paper/2510.08002/) (2025)
- [Mirage-1: Augmenting and Updating GUI Agent with Hierarchical Multimodal Skills](https://mlsanity.com/paper/2506.10387/) (2025)
- [WebCoach: Self-Evolving Web Agents with Cross-Session Memory Guidance](https://mlsanity.com/paper/2511.12997/) (2025)

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

- [RubricEM: Meta-RL with Rubric-guided Policy Decomposition beyond Verifiable Rewards](https://mlsanity.com/paper/2605.10899/) (2026)

## Abstract (arXiv)

Although large language models (LLMs) have advanced rapidly, robust automation of complex software workflows remains an open problem. In long-horizon settings, agents frequently suffer from cascading errors and environmental stochasticity; a single misstep in a dynamic interface can lead to task failure, resulting in hallucinations or trial-and-error. This paper introduces textitEnvironment Maps: a persistent, agent-agnostic representation that mitigates these failures by consolidating heterogeneous evidence, such as screen recordings and execution traces, into a structured graph. The representation consists of four core components: (1) Contexts (abstracted locations), (2) Actions (parameterized affordances), (3) Workflows (observed trajectories), and (4) Tacit Knowledge (domain definitions and reusable procedures). We evaluate this framework on the WebArena benchmark across five domains. Agents equipped with environment maps achieve a 28.2% success rate, nearly doubling the performance of baselines limited to session-bound context (14.2%) and outperforming agents that have access to the raw trajectory data used to generate the environment maps (23.3%). By providing a structured interface between the model and the environment, Environment Maps establish a persistent foundation for long-horizon planning that is human-interpretable, editable, and incrementally refinable.