acceptodds
Under review as a conference paper at ICLR 2027

Beyond Action Diversity: Effect-Class Exploration for LLM Agents

Abstract

Reinforcement learning can improve language model agents on interactive tasks, but limited training budgets are often spent continuing rollouts from different actions that produce the same immediate environmental outcome. We aim to convert repeated environmental outcomes into more effective exploration without treating distinct language histories as interchangeable. We introduce Effect-Class Exploration (ECE), which probes candidate actions in deterministic environments with restorable states, groups identical complete one-step outcomes, and continues one uniformly sampled representative per group. Each representative keeps its own history and receives a weight equal to its group size, preserving the expected additive policy gradient; our fixed-policy analysis identifies when interaction savings outweigh the additional sampling variance. Under matched interaction budgets, a fixed node bank, and a shared training update, ECE improves Qwen2.5-7B-Instruct success rates over development-selected direct sampling by 3.2 percentage points on unseen ALFWorld tasks and 5.1 points on WebShop, and exceeds optimized parsed-action grouping by 1.9 percentage points in WebShop success rate. ECE allocates exploration by observed effects under explicit efficiency conditions, with ordinary single-trajectory evaluation.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language model agents, reinforcement learning, budgeted exploration, rollout allocation

Reviews

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

The paper proposes a new rollout allocation method for exploration under budget constraints, specifically aimed at multi-interaction agentic tasks. The idea is to group actions from a state based on the one-step effect of the immediate next action and then continue only one uniformly sampled trajectory from the group. The unbiased estimator of the REINFORCE-style gradient is obtained simply by reweighing trajectories by the group size. The paper designs a controlled experimental protocol that aims to isolate the impact of the proposed exploration method under exact budget constraints. Under this protocol, the method improves task success over direct sampling on ALFWorld and WebShop. Additional experiments also show gains in an online task-start setting and across different policy-optimization algorithms.

Critical strengths

The critical strength of the paper is the choice of experimental protocol and baselines. The first set of experiments isolates the impact of the proposed roll-out selection method under a budget cap, comparing it against direct sampling and parser grouping. Then the second set of experiments shows that the approach also works across tasks and different training algorithms. These two stages separate the effect of the proposed method from simple direct sampling and other complementary methods of rollout selection.

Critical weaknesses

Writing: As a human reviewer, I find the paper extremely difficult to read, especially the experiments section.

  1. The writing does not distinguish between minor details and critical points. Moreover, the discussion of results merely reads the table without any added narrative or interpretive commentary. For example, the following discussion should be split into several longer sentences, and there should be an attempt to explain why on ALFWorld, the parse-based grouping works well: "The four primary Holm-corrected 7B tests support ECE over tuned direct sampling in both environments and over the parser on WebShop; the ALFWorld parser-relative interval includes zero, leaving that comparison inconclusive (Table 9, Appendix C.3). These controls fix continuation states and evaluate policies from task starts. Online validation uses current-policy prefixes: ECE gains 2.9/5.2 points over direct sampling and 1.3/2.2 over the parser on ALFWorld unseen/WebShop SR (Appendix C.2)."

Many similar instances appear in the results section.

Empirical advantage reduces in more general setup of Table 2: When compared across base host methods, the advantage of ECE is much smaller compared to other roll-out selection methods. This raises the question of significance: whether the added complexity of state restoration during training is justified when other arguably simpler rollout-selection methods also provide substantial performance gains.

Questions for authors
  1. My interpretation of the rows named +selection_method in Table 2 is that each row applied the "selection_method" in the base host algorithm. In that case, why were the other collector methods used in Table 2 not included in Table 1 as baselines?
  2. On a similar note, does ECE add value when combined with adaptive branching or prefix reuse? Specifically, since ECE addresses which candidate continuations to retain, whereas ARPO and Tree-GRPO address branching and prefix sharing, could you use ECE at branching points selected by ARPO? This will help understand if ECE retains its advantage on top of an optimized state selection method.
  3. How much efficiency is gained simply by consolidating parse-error and no-state-change into a group and retaining all other trajectories that don't fall into these two groups?
1 comment

The authors have posted their responses to your comments. Could you please take a look and let us know whether your concerns have been addressed? We encourage active discussion between reviewers and authors during this period.

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

This paper presents Effect-Class Exploration (ECE), a method for improving exploration efficiency in RL for LLM agents. The authors first present a motivating study showing that different actions can produce identical environmental effects, leading to redundant exploration and unnecessary interaction costs. To address this issue, ECE groups candidate actions based on their one-step effect in the environment and continues the rollout of only one example from each group. The authors further introduce a class-size-weighted policy gradient estimator to preserve unbiasedness under an additive policy gradient objective. Experiments across ALFWorld, WebShop, ScienceWorld, and search-based QA tasks demonstrate improvements over existing rollout sampling strategies under matched interaction budgets.

Critical strengths

The paper is well motivated by the observation that different actions can produce identical environmental effects, leading to redundant exploration. The idea of using one-step environmental effects to guide exploration is interesting and intuitive. The empirical evaluation is also comprehensive, demonstrating consistent improvements across multiple benchmarks and RL algorithms under matched interaction budgets.

Critical weaknesses

1. Limited clarity and insufficient justification of the sampling setup.

The presentation of the method in Section 4.2-4.4 could be improved. For example, Eq. (5) defines IcI_c as the selected representative from each effect class, but Eq. (6) introduces the trajectory-level log probability ℓθ(τi∣v)\ell_\theta(\tau_i\mid v) for all candidates ii, without clearly distinguishing between observed trajectories and hypothetical continuations. Besides, the overall training process is not presented until Algorithm 1 in the appendix, making the method difficult to follow.

More importantly, the sampling setup in Eq. (1) is not well justified. The main experiments rely on a fixed node distribution μ\mu collected by a frozen reference policy before training, which is a bit limited and not scalable. The algorithm also requires the environment to be deterministic and restorable, making it challenging to be applied to real-world tasks.

2. Insufficient justification of the sampling strategy and unclear sources of performance improvements.

The choice of continuing only one representative from each effect class is not sufficiently justified. Even if two actions produce identical one-step environmental effects, their subsequent trajectories may differ, and discarding these continuations could lose useful training signals. Therefore, continuing all sampled trajectories should be at least no worse than sampling only one example per group.

This raises the question of why ECE outperforms the baseline algorithms. The experiment settings says ECE has the same interaction budget as the baseline in Section 5.1, but not necessary the same steps of gradient updates. Since ECE reduces the rollout cost per update, does it actually perform more optimization steps than the baselines? If so, is it a fair comparison?

Questions for authors
  1. Why does ECE use a fixed node distribution collected by a frozen reference policy, rather than states visited by the evolving policy? How would this affect its applicability to standard on-policy RL training?

  2. Does ECE perform more gradient updates than the baselines in Table 2 under matched interaction budgets? What's the major source of improvement of ECE compared to the baselines?

  3. Since invalid and no-op actions account for a large fraction of the interaction savings, how does ECE compare with a simpler baseline that only filters these actions?

2 comments

The authors have posted their responses to your comments. Could you please take a look and let us know whether your concerns have been addressed? We encourage active discussion between reviewers and authors during this period.

I thank the authors for the extended experiments and detailed response.

  • Presentation and clarity: I think the presentation of the paper could be improved, specially the method section. I encourage the authors to polish the text in the next version.

  • W1 sampling setup: My concerns have been addressed.

  • W2 method design and evaluation fairness: I thank the authors for the additional ablations. These results have address my concerns.

  • Q3 Comparison with simpler baseline: I appreciate the additional comparison with Simple-2group. However, the performance improvements of Full ECE are relatively small (+1.3/+1.8%). Does it mean that the major advantage of ECE comes from the diverse sampling strategy that filters out redundant invalid and no-op actions?

Reviewer_3NtBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In interactive tasks when an LLM agent explores the environment by examining the results of various actions. Some of these actions could lead to the same immediate result. However, because the exploration history plays a crucial role in the long range trajectories, immediate-step equivalent may not imply long-range equivalence: However, because identical environmental outcomes do not mean identical histories, thus, different actions produce different contexts for subsequent reasoning, which can potentially lead to different future behavior and policy-gradient contributions.

Without computational resource limitations, the agent can explore all diverse trajectories to gain comprehensive information. However, with a resource budget, it has to optimize its exploration strategy. This is the main subject of study of this largely methodology and experimental paper, which aims to reduce redundant environment interactions without assuming that actions with identical effects are interchangeable for learning.

The method developed in the paper is intuitive, but seems to be effective. Essentially, the space of actions is first partitioned based on the immediate outcome. Then, uniformly sample one action from each effect class and continue its trajectory from the saved post-action state, retaining its own language history. The learning adjustment is then realized by a version of weighted gradient contribution. The theoretical analysis shows that effect grouping may not always be beneficial, however, it improves asymptotic budget efficiency when the reduction in interaction cost outweighs the variance introduced by representative sampling.

The paper then uses experiments with onALFWorld, WebShop, and ScienceWorld, and seven search-question-answering datasets to demonstrate the effectiveness of their algorithm. It also presents some basic theory to establish that their Effect-Class Exploration (ECE) preserves the expected additive policy gradient under some sampling assumptions. ECE maintains unbiasedness of the additive gradient estimator, not equivalence of individual trajectories or identical learning dynamics.

Critical strengths

This is a solid work with balanced experimental analysis, conceptual reasoning, and basic theoretical analysis on a well motivated practical problem in LLM exploration.

Critical weaknesses

What is less clear to me is that the current theoretical analysis did not addressed what I believe could be a more central problem in ECE based exploration: when histories within a class have very different future returns, what is the best way to manage the variance of long-range trajectories? Seems like more structural information other then simplify multiplicity weighing is required.

Questions for authors

Better understanding and characterization of the variance problem due to diverging trajectories in a class may required more principled approach.

1 comment

The authors have posted their responses to your comments. Could you please take a look and let us know whether your concerns have been addressed? We encourage active discussion between reviewers and authors during this period.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.