Improving Language Agents through BREW: Bootstrapping expeRientially-learned Environmental knoWledge

Abstract

Large Language Model (LLM)-based agents are increasingly capable of complex, multi-step tasks such as GUI automation, tool use, and data manipulation, yet they cannot learn from experience: each new session rediscovers solutions from scratch. We introduce BREW (Bootstrapping expeRientially-learned Environmental knoWledge), a framework that distills an agent's past interaction trajectories into a structured, retrievable knowledge base (KB) of natural-language recipes, concept-level procedural documents that capture what to do, when it applies, and what to watch out for. Drawing on the principle of library learning from program synthesis, BREW decomposes agent memory into modular, concept-localized documents and formalizes KB construction as a state-space search problem. To navigate this space, we introduce Expand-and-Gather Monte Carlo Tree Search (EG-MCTS), a reward-guided algorithm that jointly optimizes recipe accuracy and retrievability across parallel, per-concept search trees. We further adapt hindsight relabeling to convert near-miss trajectories into positive demonstrations, surfacing latent agent competencies as reusable knowledge. On three domain-grounded benchmarks, OSWorld, tau^2-Bench, and SpreadSheetBench, BREW achieves 10-20% gains in task success and 10-15% fewer execution steps over base agents, while consistently outperforming existing memory-augmented baselines that can degrade below memoryless performance. The resulting KB is inspectable, modular, and extensible, providing a transparent and controllable substrate for agent optimization.