APEX: Autonomous Policy Exploration for Self-Evolving LLM Agents
Yibo Li, Jiashuo Yang, Zhi Zheng, Zhiyuan Hu, Yuan Sui, Shizun Wang, Yufei He, Bryan Hooi · 2026
Read APEX: Autonomous Policy Exploration for Self-Evolving LLM Agents by Yibo Li, Jiashuo Yang, Zhi Zheng, Zhiyuan Hu, Yuan Sui, Shizun Wang, Yufei He, Bryan Hooi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21240.txt.
Introduction
Yibo Li and colleagues present APEX, a tool for self-evolving language-model agents. Such agents learn across episodes from memory and reflection, not weight updates. But growing memory can trap them in familiar high-reward routines, a flaw called exploration collapse. APEX builds a strategy map, a graph of milestones with prerequisite links. Fork Discovery adds new, evidence-backed directions, while Policy Selection weighs exploring against exploiting. Tests on nine text-adventure games and a web benchmark show APEX ahead of prior tools.
Catalog record
| CREATOR | Yibo Li, Jiashuo Yang, Zhi Zheng, Zhiyuan Hu, Yuan Sui, Shizun Wang, Yufei He, Bryan Hooi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54516 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21240
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
APEX: Autonomous Policy Exploration for Self-Evolving LLM Agents Yibo Li, Jiashuo Yang, Zhi Zheng, Zhiyuan Hu, Yuan Sui, Shizun Wang, Yufei He, Bryan Hooi Abstract LLM agents have shown strong performance across a wide range of complex tasks, including interactive environments that require long-horizon decision making. But these agents cannot learn on the fly at test time. Self-evolving agents address this by accumulating memory and reflection across episodes rather than requiring model-weight updates. However, these agents often suffer from exploration collapse : as memory grows, behavior concentrates around familiar high-reward routines, reducing the chance of discovering better alternatives. To address this problem, we propose A utonomous P olicy EX ploration ( APEX ), which builds and maintains an explicit strategy space through a strategy map—a directed acyclic graph of milestones with prerequisite dependency edges. In APEX, Fork Discovery expands the map with evidence-grounded unexplored directions, while Policy Selection balances exploration and exploitation during planning. Evaluated on nine Jericho text-adventure games and WebArena, a realistic web interaction benchmark, APEX outperforms all baselines. Extensive ablations validate each component’s contribution and demonstrate robustness across diverse settings, demonstrating APEX’s effectiveness for sustained exploration in self-evolving agents. Code is available at https://github.com/liushiliushi/APEX1 . 1 Introduction LLM agents can solve many complex tasks, such as software engineering [ 10 ] , scientific research automation [ 13 ] , and autonomous computer use [ 22 ] . Yet agents that start from scratch each time have a fundamental bottleneck: they do not keep useful experience across runs. As a result, they often repeat similar mistakes and fail to improve. To overcome this limitation, researchers have developed self-evolving agents [ 21 , 9 , 12 ] , which systematically internalize experience through memory and reflection to ensure continuous improvement over time. Figure 1 : Illustration of exploration collapse in a maze experiment (5 \times 5 grid, 20 episodes, 10 steps each). Room visitation heatmaps (color intensity shows visit proportion; reward cells ( \star ) indicate bonus locations). Static explores broadly but inconsistently. Reflexion locks into a narrow corridor and achieves a higher average while missing high-value rooms. APEX maintains broad coverage and consistently reaches high-reward cells. APEX avoids collapse by explicitly tracking which strategies have been tried and which remain unexplored, and actively directing the agent toward unexplored directions rather than refining familiar ones. Despite these gains, we observe exploration collapse, i.e., agents improve early, then settle into narrow behavioral patterns and stop discovering qualitatively different strategies. Figure 1 illustrates this behavior in a toy maze: a Reflexion agent achieves stable average returns but repeatedly traverses a narrow corridor and misses high-reward regions that require broader exploration. Notably, its maximum score even falls short of a static, non-learning model. Such collapse can be difficult to detect: average returns may remain high even as exploratory diversity decreases, and the agent repeatedly follows a narrow routine, foreclosing the discovery of better alternatives. The problem is not that agents make bad choices; they never know what choices they are missing. LLM agents face an implicit, unbounded strategy space: unlike RL, there is no predefined action set, and the agent has no natural view of what it has not tried. Discovering unexplored directions requires actively constructing and maintaining an explicit map of what has been tried and what plausible alternatives remain. Two questions follow: (1) how should the strategy space be constructed? and (2) which strategy should be explored next? Existing memory and reflection mechanisms provide useful local guidance but do not maintain a persistent, explicit strategy space for decision, making it difficult to sustain broad exploration while still exploiting what has already been learned. To address this issue, we propose APEX (Autonomous Policy Exploration), a framework centered on an explicit strategy map , a directed acyclic graph (DAG) where nodes are milestones and edges encode prerequisite dependencies. The strategy map serves as shared infrastructure for two complementary exploration mechanisms. Fork Discovery drives exploration at the map level: it mines past episodes for directions the agent observed but never pursued, and expands the map’s frontier with new milestones. Policy Selection drives exploration at the episode level: it scores milestones via principled uncertainty estimates, ensuring the agent visits under-explored directions rather than repeatedly exploiting familiar ones. Together, they turn exploration into a closed loop—Fork Discovery continuously opens new territory, and Policy Selection ensures the agent visits it. We evaluate APEX on nine text adventure games from the Jericho benchmark [ 8 ] and on WebArena [ 26 ] , a realistic web interaction benchmark. APEX consistently outperforms all baselines across both settings, with the largest gains on tasks that require discovering qualitatively different strategies—exactly the regime where exploration collapse is most harmful. Ablations and case studies trace these gains to the strategy map: Fork Discovery uncovers directions that reflection-based methods never consider, and Policy Selection ensures they are systematically visited. The results hold robustly across hyperparameter choices and backbone LLMs, underscoring the generality of APEX. 2 Related Work Self-Evolving LLM Agents. Self-evolving agents improve through accumulated experience across episodes rather than updating model weights. Early work introduced verbal self-reflection [ 16 ] , experience distillation [ 21 ] , and growing skill libraries [ 20 ] . More recent work scales these ideas further. ReasoningBank [ 14 ] distills reasoning strategies from both successful and failed experiences into structured memory. EvoTest [ 9 ] introduces a gradient-free evolutionary framework that revises an agent’s prompt, memory, and tools between episodes. JitRL [ 12 ] adjusts the action logits of the current episode by retrieving relevant historical trajectories from memory, enabling continual improvement without gradient updates. However, none of these systems builds an explicit strategy space to guide exploration; this is the gap APEX addresses. Exploration in Fixed Action Spaces. Classical exploration methods assume a predefined primitive action space. They fall into two broad families: intrinsic motivation , which rewards agents for visiting novel states or exhibiting diverse behaviors, including count-based bonuses [ 18 , 4 ] , curiosity-driven rewards [ 11 , 3 ] , episodic curiosity [ 2 ] , and diversity-maximizing skill discovery [ 6 ] ; and planning under uncertainty , which models the agent’s uncertainty to guide exploration, including UCB [ 1 , 25 ] , Thompson Sampling [ 19 , 15 ] , and maximum entropy objectives [ 7 ] . Despite their variety, all share a fundamental assumption: the primitive action space is fixed and given. They answer the question of which known option to try next, but never ask what options should exist in the first place. APEX addresses this complementary question: Fork Discovery actively constructs the strategy space from trajectory evidence, while Policy Selection operates over it. Entropy Bottleneck in LLM Reinforcement Learning. Recent work identifies entropy collapse in LLM Reinforcement Learning (RL). 5 show that RL training systematically reduces policy entropy, causing the agent to concentrate probability mass on familiar high-reward actions and progressively lose behavioral diversity. 23 show that RLVR improves average performance but narrows the reasoning boundary, as RL sharpens the distribution over existing paths rather than discovering new ones. These works focus on the weight-update regime, while APEX addresses the analogous collapse in test-time self-evolving agents. 3 Exploration Collapse: An Empirical Study