# APEX: Autonomous Policy Exploration for Self-Evolving LLM Agents

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 20 of its 26 references that are in the map.
- First posted on arXiv 20 May 2026.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)
- Synthetic data and self-improvement for LLMs / [Self-evolving LLM agents](https://mlsanity.com/synth/self-evolving-llm-agents/)

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments](https://mlsanity.com/paper/2404.07972/) (2024)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models](https://mlsanity.com/paper/2505.22617/) (2025)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Agentic Context Engineering: Evolving Contexts for Self-Improving Language Models](https://mlsanity.com/paper/2510.04618/) (2025)
- [Agent Workflow Memory](https://mlsanity.com/paper/2409.07429/) (2024)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [ReasoningBank: Scaling Agent Self-Evolving with Reasoning Memory](https://mlsanity.com/paper/2509.25140/) (2025)
- [Never Give Up: Learning Directed Exploration Strategies](https://mlsanity.com/paper/2002.06038/) (2020)
- [Interactive Fiction Games: A Colossal Adventure](https://mlsanity.com/paper/1909.05398/) (2019)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [EvoTest: Evolutionary Test-Time Learning for Self-Improving Agentic Systems](https://mlsanity.com/paper/2510.13220/) (2025)
- [Contingency-Aware Exploration in Reinforcement Learning](https://mlsanity.com/paper/1811.01483/) (2018)
- [Just-In-Time Reinforcement Learning: Continual Learning in LLM Agents Without Gradient Updates](https://mlsanity.com/paper/2601.18510/) (2026)

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

- [The Last AI Built by Humans: Toward Genuine Recursive Self-Improvement](https://mlsanity.com/paper/2609.11873/) (2026)
- [Success Leaves Detours: Learning Executable Walkthroughs for Long-Horizon Agents](https://mlsanity.com/paper/2609.22120/) (2026)

## Abstract (arXiv)

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 Autonomous Policy EXploration (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.