Technical Summary: APEX (Autonomous Policy Exploration for Self-Evolving LLM Agents)

1. Problem Statement: Exploration Collapse in Self-Evolving Agents

While Large Language Model (LLM) agents have demonstrated proficiency in complex, long-horizon tasks, a critical limitation persists: they cannot learn on the fly at test time without updating model weights. Existing self-evolving agents attempt to overcome this by accumulating memory and performing reflection across episodes. However, the authors identify a phenomenon termed exploration collapse.

As an agent accumulates experience, its behavior tends to concentrate around familiar, high-reward routines. While average returns may remain stable or even increase, the agent's exploratory diversity decreases, causing it to settle into narrow behavioral patterns. Consequently, the agent fails to discover qualitatively different, superior strategies that lie outside its current "known" space. The paper argues that existing memory and reflection mechanisms provide local guidance but fail to maintain a persistent, explicit strategy space, leaving the agent unaware of what choices it has not yet tried.

2. Methodology: The APEX Framework

To address exploration collapse, the authors propose APEX (Autonomous Policy Exploration). The core innovation is the maintenance of an explicit Strategy Map, a Directed Acyclic Graph (DAG) that structures the agent's knowledge and guides exploration.

2.1 The Strategy Map

The strategy map $G = (V, E, \theta)$ is a DAG where:

• Nodes ($V$): Represent milestones, defined as discrete sub-goals described in natural language with associated key actions (e.g., "collect the brass lantern").
• Edges ($E$): Encode prerequisite dependencies (e.g., Node $u$ must be achieved before Node $v$).
• Statistics ($\theta$): Each node tracks visit count ($n$), average reward ($\bar{r}$), and reward variance ($Var$).

This map transforms the open-ended action space into a structured planning problem, where the agent's state is the set of achieved milestones.

2.2 Core Components

APEX operates through a cycle of four distinct mechanisms:

1. Policy Selection (Episode-Level Exploration):
   During an episode, the agent selects the next milestone from the set of eligible milestones (those whose prerequisites are met). This is framed as a multi-armed bandit problem. The authors evaluate three strategies:

   • Thompson Sampling (Default): Samples from a posterior distribution based on mean and variance. It naturally favors high-uncertainty (under-explored) milestones without requiring hyperparameter tuning.
   • UCB (Upper Confidence Bound): Adds an optimism bonus based on visit counts.
   • $\epsilon$-Greedy: Randomly explores with probability $\epsilon$.
   • Mechanism: Selection is sequential; if a milestone fails, the agent re-evaluates eligible milestones rather than being locked into a pre-determined sequence.

2. Map Refinement (Knowledge Correction):
   Periodically (every $N$ episodes), an LLM analyzes structured summaries of recent episodes to update the existing map. It refines key actions, corrects erroneous dependency edges, and prunes duplicate nodes based on observed facts. This ensures the map remains accurate to the environment's mechanics.

3. Return Propagation (Credit Assignment):
   Also running periodically, this component updates the statistics ($\theta$) of the milestones. Using a reverse topological pass on the DAG, it propagates rewards from downstream milestones back to their prerequisites. This ensures that enabling milestones (e.g., "find key") receive credit for unlocking high-reward successors (e.g., "open chest"), even if the enabling milestone itself yields no immediate reward.

4. Fork Discovery (Strategy Space Expansion):
   This is the primary mechanism for preventing exploration collapse. Unlike Refinement, which corrects known paths, Fork Discovery actively expands the map's frontier. An LLM analyzes episode summaries to identify actions or directions that were observed or available but never pursued. It proposes new milestones and dependency edges to encode these unexplored possibilities, effectively forcing the agent to consider strategies it has never attempted.

3. Key Contributions

• Identification of Exploration Collapse: The paper empirically demonstrates that self-evolving agents (like Reflexion) often converge to narrow behavioral routines, missing superior strategies that static, non-learning agents occasionally stumble upon through sheer diversity.
• Explicit Strategy Space: APEX introduces the first framework for self-evolving agents that maintains an explicit, structured map of the strategy space (milestones and dependencies), rather than relying solely on unstructured memory or reflection.
• Dual-Loop Exploration: The framework separates map-level expansion (Fork Discovery) from episode-level selection (Policy Selection), creating a closed loop where new territory is continuously opened and systematically visited.
• Robust Credit Assignment: The DAG-based Return Propagation ensures that enabling actions are correctly valued, addressing the issue of sparse rewards in complex tasks.

4. Experimental Results

The authors evaluated APEX on two benchmarks: Jericho (9 text-adventure games) and WebArena (812 realistic web interaction tasks).

• Performance: APEX consistently outperformed all baselines (Static, Memory, Reflexion, EvoTest, ACE) across all environments.
  • In Jericho, APEX achieved the highest Final-5 scores on all 9 games. Notably, in games requiring diverse strategies (e.g., Ztuu), APEX significantly outperformed Reflexion, which often converged to suboptimal local maxima.
  • In WebArena, APEX led in all 5 categories (Shopping, Reddit, GitLab, CMS, Map), with particularly large gains on Reddit and GitLab where multi-step, non-obvious sequences are required.
• Ablation Studies:
  • DAG vs. Flat List: The dependency structure (DAG) was crucial; a flat list of milestones performed significantly worse, confirming that reasoning about prerequisites is key.
  • Fork Discovery: Removing Fork Discovery resulted in a significant performance drop, especially in complex games, proving that active expansion of the strategy space is necessary to avoid collapse.
  • Policy Selection: Thompson Sampling outperformed UCB and $\epsilon$-Greedy, highlighting the importance of variance-aware exploration.
  • Return Propagation: DAG-based credit propagation outperformed sequential path-based propagation, ensuring accurate value estimation for enabling milestones.
• Generalization: APEX demonstrated strong cross-task generalization on WebArena, transferring knowledge from seen tasks to unseen ones without task-specific priors.
• Cost: Despite the additional reflection components, APEX's API cost was comparable to other methods due to the concise nature of milestone-guided prompts.

5. Significance and Claims

The paper claims that APEX effectively solves the exploration collapse problem in self-evolving LLM agents by shifting from implicit, memory-based learning to explicit, map-based exploration.

• Significance: The work demonstrates that for agents to sustain improvement over time, they must not only reflect on what they have done but also actively construct and navigate a map of what they have not done.
• Modesty: The authors acknowledge limitations: the quality of the strategy map is bounded by the LLM's ability to identify milestones and infer unexplored directions. Deeply hidden game mechanics or strategies entirely outside the agent's past knowledge may still be missed. Furthermore, the current approach relies on tasks that naturally decompose into discrete milestones, suggesting that continuous or less structured environments may require adaptations to the milestone definition.

In conclusion, APEX provides a robust framework for sustained exploration, enabling self-evolving agents to discover superior strategies that traditional reflection-based methods fail to find.