acceptodds
Under review as a conference paper at ICLR 2027

Autonomous Strategy Exploration for Self-Evolving LLM Agents

Abstract

LLM agents have achieved impressive performance on complex tasks, including interactive environments involving long-horizon decision making. Nevertheless, most agents are unable to continually improve their behavior from experience at test time. Self-evolving agents offer a promising alternative by retaining memories and reflections across episodes, enabling behavioral adaptation without modifying model parameters. A key challenge, however, is that accumulated experience can progressively narrow an agent's behavioral diversity: successful strategies are repeatedly reused, while potentially better but unexplored alternatives become increasingly unlikely to be attempted. We refer to this phenomenon as exploration collapse. To mitigate this issue, we introduce an approach that explicitly organizes the agent's strategy space as a directed acyclic graph, where nodes represent milestones and edges capture prerequisite relationships. The strategy space is continually expanded by identifying evidence-supported yet unexplored directions, while a dedicated selection mechanism balances pursuing promising known strategies with exploring new ones during planning. The proposed approach consistently outperforms all evaluated baselines. Extensive ablation studies further confirm the importance of its individual components and demonstrate robust performance across diverse settings, showing that explicitly maintaining and exploring a structured strategy space can support sustained exploration in self-evolving agents.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, continual learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_AARcOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes APEX, a self-evolving LLM agent framework designed to mitigate exploration collapse, where agents repeatedly exploit familiar strategies and fail to discover better alternatives. APEX maintains an explicit DAG-based strategy map and introduces Fork Discovery to identify unexplored opportunities, Policy Selection to balance exploration and exploitation, and graph-based reward propagation to guide future decisions. Experiments on nine Jericho games and WebArena demonstrate consistent improvements over existing memory-based and self-evolving agent baselines.

Critical strengths
  1. The paper identifies exploration collapse as a practical limitation of self-evolving LLM agents, highlighting that accumulating successful experiences does not necessarily lead to better exploration.

  2. The combination of strategy maps, Fork Discovery, and uncertainty-aware Policy Selection provides a coherent mechanism for maintaining and expanding the exploration space.

Critical weaknesses
  1. The core components largely build upon established ideas, including graph-based planning, frontier exploration, Thompson Sampling, and reward propagation. The main contribution appears to be their integration rather than a fundamentally new algorithm.

  2. Prior methods such as Voyager, Go-Explore, and recent graph-based skill planning frameworks share similar motivations or mechanisms. The paper does not sufficiently clarify its unique technical contributions relative to these approaches.

  3. Most experiments emphasize final task performance rather than systematically measuring strategy diversity, exploration coverage, or the discovery rate of novel high-reward strategies over extended interactions.

  4. The framework relies on LLM-generated milestones and prerequisite dependencies, but provides limited evaluation of incorrect dependencies, redundant milestones, and error propagation as the strategy map grows.

Questions for authors

Can the authors provide direct quantitative evidence that APEX mitigates exploration collapse, such as strategy diversity, exploration coverage, or novel strategy discovery rates over longer interaction horizons?

Reviewer_D6dNOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

Motivated by the well-known exploration collapse problem in LLM agents, this work proposes a novel systematic strategy exploration strategy for self-evolving LLM agents. The proposed method builds a DAG-based strategy map, representing milestones and their dependencies, for better exploration and exploitation of policies. The map is refined as episodes progress, with returns propagated and unexplored strategies identified. The experimental results support that the agents benefit from this exploration boost, outperforming the baselines.

Critical strengths
  • The work addresses an important research problem with clearly motivated research questions: systematic exploration for self-evolving LLM agents.
  • Fork Discovery is a particularly interesting component, enabling agents to explicitly identify and pursue previously unexplored strategies.
  • The experiments are well-structured and promising. The cross-task generalization results are particularly interesting. The ablation studies in Tables 4 and 5 also support the contributions of the proposed components.
Critical weaknesses

1. Abstract

1.1. The statement “these agents cannot learn on the fly at test time” (Line 13) is overly strong and not necessarily true. Please modify or qualify this claim.

1.2. Why do the authors distinguish self-evolving agents that learn through memory updates from those that learn through model-weight updates? (Line 14) The motivation for emphasizing learning “rather than requiring model-weight updates” is unclear.

1.3. The performance improvements of APEX should be described more concretely, including the baselines used for comparison and specific numerical results.

2. Introduction

2.1. The citations appear to be improperly formatted. Please follow the ICLR submission guidelines for citation formatting.

3. Exploration Collapse

3.1. Please elaborate on the Static baseline, although this is included in the later section (at least, refer to the section).

3.2. What differences in its behavior or design enable it to reach the +80 reward, whereas Reflexion fails to do so?

3.3. APEX is not included in Figure 2. Which experimental evidence supports the corresponding description of APEX?

4. Method

Strategy Map and Abstract MDP

4.1. How are the dependencies between nodes established and validated when the strategy map is constructed using an LLM?

4.2. What justifies the Markovian assumption underlying the Milestone Abstract MDP?

4.3. How are the “key actions” associated with each milestone defined?

4.4. Including a concrete example of the Abstract MDP would help readers better understand its definition and formulation.

Milestone Verification and Reward Attribution

4.5. How is milestone completion determined and verified in the LLM-based implementation?

4.6. What mechanisms prevent hallucinated or incorrectly identified milestone completions?

4.7. How reliable are the LLM-attributed reward scores?

4.8. Could the authors further validate them by comparing LLM-assigned rewards against ground-truth environment rewards at the individual, non-abstract state level?

Fork Discovery 4.9. What prompting strategies or reasoning mechanisms are required to achieve high-quality Fork Discovery?

4.10. Further implementation details would help clarify how reliably unexplored strategies can be identified.

5. Experiments

Evaluation Protocol and Generalization

5.1. In WebArena, there is no explicit separation between training and test tasks. Since the method uses ground-truth environment rewards and repeatedly attempts tasks after resetting the environment, separating training and test tasks would provide a more rigorous assessment of generalization.

5.2. The cross-task generalization setting is described ambiguously. Please clarify the inputs and outputs of each episode, particularly which information is retained, transferred, or excluded across tasks.

Statistical Robustness

5.3. Given the substantial fluctuations in Figure 4, evaluating more episodes or conducting additional independent runs (e.g., with multiple random seeds) would strengthen the evidence for the robustness of APEX.

5.4. The expression “clear margin” (Line 349)seems overly strong without accompanying statistical evidence. Please provide statistical support or moderate the claim.

Computational Cost and Fairness

5.5. In the cost analysis, are all baselines evaluated over five episodes per task? If so, what motivates applying the same repeated-episode protocol to methods that do not require cross-episode learning, such as Static? If not, why is the reported computational cost of Static relatively high?

Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Official Comment by Authors

Dear Reviewer D6dN,

Thank you again for your thoughtful review and constructive feedback. In our responses, we clarified how APEX constructs and refines dependencies, verifies milestones, and transfers knowledge across tasks. We also provided analyses of dependency correction and milestone outcomes, step-level comparisons between LLM-assigned and environment rewards, and three-seed results to further address your concerns about reliability and robustness.

With around one day remaining in the discussion period, we would greatly appreciate it if you could revisit our responses and let us know whether these clarifications and supplementary results address your concerns. If any questions remain, we would be happy to discuss them before the discussion closes.

Thank you again for your time and consideration.

AuthorsOpenReview ↗

Official Comment by Authors

Dear Reviewer D6dN,

Thank you again for your time and thoughtful feedback. As the rebuttal period ends today, we would greatly appreciate even a brief reply on whether our responses have addressed your concerns. If anything remains unclear, we would be happy to provide further clarification before the deadline.

Thank you for your consideration!

Reviewer_9WYYOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Within the paper, the authors introduce a strategic exploration approach for LLMs using directed cyclic graph where node are milestones and edges express the dependencies between nodes. The authors make use and evaluate non-greedy policy selection approaches (epsilon greedy, upper confidence bound and Thompson sampling to push the agent to more under-explored nodes and a proposed fork discovery approach to expand the frontier of the DAG graph introducing new milestones as nodes. The proposed method APEX is compared against relevant baselines across Jericho and WebArena domains.

Critical strengths

The proposal of Fork Discovery to push the agent toward new frontiers by mining directions the agent observed but never pursued is well justified.

Critical weaknesses

I have a concern on results selectivity. Table 1 shows the proposed approach APEX performing better (in bold) than the baselines, however, by reviewing the learning plots in Figure 6 the improvement against the baselines seems significantly weaker on certain episodes prior to episode 50. For instance, if we were to have created Table 1 to reflect the results of episode 20 many of the other approaches would have the highest scores. Moreover in Temple, Detection and Balance, the reflection baseline obtains a score close to the score of APEX on episode 50 significantly earlier, (within the first 5 episodes in Detection).

Questions for authors

I have questions on results selectivity discussed in the critical weakness section. Can the authors provide areas under the curve results Table 1 instead of or as well as the score at episode 50. Are the results in Table 1 performed over a single random seed? if not can the authors also provide the multiple seed run statistics within all result table within the main paper and error bars for the plots in Figure 6 and Figure 4.

How were the nine Jericho domains selected? The Jericho domain paper provides 56 domains, could each of these also have been equally used to evaluate APEX against the baseline methods. Were the domains selected at random?

Table 6 used the writing (ours) as a suffix for the Thompson sampling method. Weren't the other methods epsilon greedy and UCB also using the proposed APEX method and would also be suitable for the suffix (ours)? what exactly does (ours) refer to here which the other approaches are not doing?

It was not completely clear to me from reading the exact functionality of the apply() function, could the authors provide a clearer formulation of this function prior to it being used on line 239.

4 comments
AuthorsOpenReview ↗

Official Comment by Authors

Dear Reviewer 9WYY,

Thank you again for your careful review and constructive feedback. In response to your concern about result selectivity, we explained the Final-5 evaluation window and the trade-off between early exploration and later performance, and provided AUC comparisons and three-seed statistics. We also clarified the selection of the Jericho games, added an evaluation on Enchanter, and explained the policy labels and the apply() operation.

With around one day remaining in the discussion period, we would greatly appreciate it if you could revisit our responses and let us know whether these clarifications and supplementary results address your concerns. If any questions remain, we would be happy to discuss them before the discussion closes.

Thank you again for your time and consideration!

AuthorsOpenReview ↗

Official Comment by Authors

Dear Reviewer 9wxy,

Thank you again for your time and thoughtful feedback! As the rebuttal period ends today, we would greatly appreciate even a brief reply on whether our responses have addressed your concerns. If anything remains unclear, we would be happy to provide further clarification before the deadline.

Thank you for your consideration!

Thank you for addressing all of my concerns. I have increase my score to weak accept in light of the reasonable explanation for varied competitiveness to baselines and my main concern of result selection being addressed.

AuthorsOpenReview ↗

Response by Authors

Thank you a lot for your thoughtful review and for taking the time to consider our responses! We are glad that our clarifications addressed your concerns, and we sincerely appreciate your constructive feedback and positive reassessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.