acceptodds
Under review as a conference paper at ICLR 2027

Exploration and Exploitation Are Measurable for Language Model Agents

14 views

Abstract

Language Model (LM) agents are increasingly used in complex open-ended decision-making tasks, from AI coding to physical AI, where they must both explore the problem space and exploit acquired knowledge effectively. However, it remains challenging to systematically distinguish exploration and exploitation using observed actions without access to the agent's internal policy, and to determine when either constitutes an error. To address this, we design partially observable 2D grid maps paired with an unknown symbolic task directed acyclic graph (DAG), abstracting the structure of practical agentic AI scenarios. We then propose a metric that detects unproductive traversals using redundancy criteria grounded in classical graph exploration bounds, while permitting necessary backtracking. We attribute each error to exploration or exploitation based on whether the current state admits productive exploration, exploitation, or both, making the metric policy-agnostic. Using programmatically generated maps and task DAGs with controllable difficulty, we evaluate 35 frontier LM agents and find that even state-of-the-art models struggle to reach the goal within the step budget. Log exploration and exploitation errors exhibit strong linear relationships with task success ( and , respectively), providing empirical evidence that the metric captures behavior relevant to task success. Beyond success rate, the metric reveals distinct exploration and exploitation behaviors among models with similar success rates. We further find that a compact memory harness achieves higher task success than a reasoning baseline that retains the model's own reasoning traces. Finally, we extend our metric to an iconic video game, Minecraft Clone, beyond our synthetic environment.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Language model agents, Exploration, Exploitation, Metric for exploration and exploitation errors

Reviews

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

The paper proposes a framework for measuring exploration and exploitation errors in language model agents using partially observable grids with initially unknown symbolic task dependencies. It detects unproductive actions through distance-based progress and structural redundancy, then assigns errors according to the opportunities available in the current state. Experiments cover 35 models and examine relationships with task success, prompting, memory, semantic task labels, and an extension to Minecraft Clone. The intended contribution is a behavioral diagnostic that reveals information beyond binary task success.

Critical strengths
  1. The controlled environment is well suited to studying sequential agent behavior. Partial observability and symbolic task dependencies require agents to acquire information, maintain state, and revisit actionable tasks while reducing dependence on prior semantic knowledge. This makes the setting useful for investigating failures that are difficult to isolate in less controlled benchmarks.

  2. The broad model coverage and trajectory analyses provide useful descriptive evidence. The examples show how agents with similar task outcomes can behave differently, and the reported correlations are numerically consistent with Table 10. The framework could therefore become a valuable diagnostic tool if the interpretation of its two error measures is validated.

Critical weaknesses
  1. The evidence does not yet establish that the metric distinguishes exploration failures from exploitation failures. The method first detects an error using a shared rule and then assigns it according to the opportunities available; in Case 4, the same error contributes to both metrics. This describes the circumstances in which an error occurs, but the connection to distinct failure mechanisms needs validation. Correlation with success is insufficient on its own because repetition and lack of progress can also predict failure under a fixed step budget. The paper does not establish incremental diagnostic value over these simpler measures or validate the attribution on policies with known failure modes. Since measurement is the central contribution, this is my main reason for weak rejection and the primary basis for my soundness concern.

  2. The relationship between the written metric, the supplied implementation, and the reported results is unresolved. Section 4 describes entering an unobserved cell as a progress event. However, src/symbolic_benchmark/metrics_upd.py uses membership in the current target set, and when the goal is pending that set contains only the goal. Its default partially observed branch also computes distances over visited cells and their frontier. These details address part of the implementation question, but differ from the broad written progress rule. Separately, Table 16 uses an exploration denominator of 188 even though the final 110 steps are described as Case 2, while Section 5 restricts that denominator to Cases 1 and 4. The supplied files alone do not establish which implementation produced the reported numbers. Appendix I also leaves the mapping from heterogeneous Minecraft actions to the metric's targets, progress, and redundancy quantities unclear. These gaps limit reproducibility and interpretation across environments.

Questions for authors
  1. Which implementation and configuration produced the main results and Table 16? Please reconcile the paper's progress definition with the target-based rule in metrics_upd.py, and clarify the exploration denominator, including episodes with no eligible opportunities. For Minecraft, please provide the action-to-metric definitions and the scored opportunity counts underlying Figure 6. These clarifications would establish whether the discrepancies are confined to exposition or affect the reported calculations.

  2. Using existing trajectories where possible, can you compare the proposed measures with simple repetition/no-progress baselines and report Case 4 errors separately? A small diagnostic using policies with a known exploration or exploitation failure would also help assess the attribution. Evidence that the two measures identify distinct failures beyond general inefficiency would materially improve my assessment; a comprehensive new benchmark study is not required.

8 comments

We thank the reviewer for recognizing the value of our controlled environment for studying sequential agent behavior and for highlighting how our trajectory analyses reveal differences in behavior among agents with similar task outcomes. We address the reviewer’s concerns below.

(W1 & Q2)

Distinguishing exploration and exploitation failures

We agree with the reviewer that correlation with task success is not a direct validation of error attribution. First, we kindly remind the reviewer that Appendix B (Lines 923–1016) includes challenging edge cases where we validate the error metrics against human annotation of the errors.

To further test our metric, we generate four scripted policies with known stalling behaviors. We first fix a small map consisting of a five-cell corridor and a two-cell side branch. We design four policies: "Efficient return" returns to the activated goal node directly. "Stall before discovering prerequisite" and "Stall after goal becomes actionable" add 12 alternating moves before discovering the prerequisite or after the goal becomes actionable, respectively. "Enter new side branch after goal becomes actionable" makes the agent perform unnecessary exploration after goal is pending. The results are reported below:

Scripted policyActionsRepeated visitsNo-progress actionsExploration errorsExploitation errors
Efficient return73200
Stall before discovering prerequisite19151460
Stall after goal becomes actionable19151406
Enter new side branch after goal becomes actionable115402

While all four policies succeed, "Efficient return" incurs no errors, while the two stalling policies receive different exploration and exploitation errors despite having the same counts for repetition and no-progress threads. The metric also flags two moves into unseen side-branch cells after the goal becomes actionable as an exploitation error as desired.

Comparison with simpler measures

We would like to emphasize that the purpose of our metric is to quantify exploration and exploitation errors, and not to use it as a predictor of success. The reported R2R^2 values simply are empirical findings that add to the validity and soundness of our metric. We show below that repetition and lack of progress are both strong predictors of success. However, repetition and lack of progress are entities defined in our paper towards the error metric, and these alone cannot measure exploration and exploitation errors.

We perform leave-one-model-out evaluation with repetition and no-progress rates alongside our error rates. We trained logistic regression on episodes from 34 models and tested on the held out model, repeating 35 times. We report AUROC and Brier scores, and the results are shown below.

InputsAUROC ↑Brier score ↓
Repetition0.97320.0534
No-progress0.97290.0622
Repetition + no-progress0.98280.0464
Exploration and exploitation error rates0.97600.0602

The results show that both repetition and no-progress threads are also strong predictors of episode success, showing comparable AUROC and Brier scores to our exploration and exploitation errors. However, repetition and no-progress threads cannot be used to attribute actions as errors.

Case 4 attribution

We report the breakdown of the errors into four cases:

CaseCase descriptionErrors / TotalRate
1Exploration: no pending tasks276,499 / 625,25644.22%
2Exploitation: goal pending2,605 / 17,45914.92%
3Exploitation: pending tasks, no exploration frontier483 / 3,57313.52%
4Both: non-goal pending tasks and exploration frontier13,682 / 55,16524.80%

Case 4 contributes 4.71% of exploration-error events and 81.59% of exploitation-error events.

(W2 & Q1)

Exploration denominator

Thank you for identifying this discrepancy. We audited the scoring code and confirmed that the exploration denominator incorrectly included Case 2 steps, where the goal is pending and only exploitation is eligible. We corrected the denominator to count only Cases 1 and 4, as specified in Section 5. Our audit found no other error in our code.

We recomputed the affected exploration-error rates and the corresponding R2R^2 values for their relationship with task success. The strong negative relationship between log exploration error and task success persists across all three settings.

SettingOriginal R2R^2Corrected R2R^2
Default0.8970.893
Reasoning0.8020.796
Combined0.8850.881

For the example in Table 16, the correction excludes the final 110 Case 2 steps, giving 78 eligible exploration steps for GPT-OSS-120B, and the final 6 Case 2 steps are removed for Hy3.

ModelOriginal (errors / eligible steps)Corrected (errors / eligible steps)
Hy312/148 (8.1%)12/142 (8.5%)
GPT-OSS-120B0/188 (0%)0/78 (0%)

We also updated the exploration-error rates in the harness and semantic ablations and in the sensitivity analyses for k∈{1,2,3}k \in \{1,2,3\} and α∈{1,2,3}\alpha \in \{1,2,3\}, and the corresponding figures.

Minecraft Clone setting

Appendix H of the revised manuscript clarifies how we score the actions (Figure 7; Figure 6 in the submitted version). Since Minecraft Clone allows 3D continuous actions, we discretize the actions the agents can take into 21 predefined actions: movement in four directions, camera adjustment in four directions, jumping, mining, block placement, selection of one of nine inventory slots, and waiting. Movements last for 1 second, jumping lasts 0.4 seconds and mining holds the left mouse button for 2 seconds. Camera adjustment applies a fixed mouse displacement with a 0.2 second action budget. The simulation advances only within these action budgets and remains frozen between actions, preventing model inference time from affecting execution.

The goal of the agent is to find two iron-ores. An iron-ore block becomes a known target once the agent aims at it. Exploration remains active when the known number of ores is insufficient to meet the goal, and exploitation is active whenever known ore remains to be mined. Moving to new positions, changing the viewpoint, and discovering ores are gainful exploration. Approaching known ore, productively reorienting toward it, mining, or collecting iron contribute to gainful exploitation. Discovering an ore or collecting it resets the no-progress thread. Within a no-progress thread, staleness tracks cycles and node/edge reuse beyond two visits/traversals, with stationary actions counting towards node visits (since we do not have a self-edge). Actions without active gain are errors; gainful actions with increase in staleness score are also errors.

As requested by the reviewer, the scored opportunity counts underlying Figure 6 of the submitted version are provided below.

Model / visual memoryExploration errors / opportunitiesExploitation errors / opportunities
Gemini 3.1 Flash Lite / with390 / 4830 / 8
Gemini 3.1 Flash Lite / without845 / 8910 / 1
GPT-4.1 / with438 / 59210 / 18
GPT-4.1 / without733 / 8360 / 0

We hope the response addresses your concerns. We would be happy to answer any further questions.

Thank you for the detailed rebuttal. I appreciate the correction to the exploration denominator, the reference-policy experiments, and the clearer Minecraft definitions. I also understand that the two rates describe errors under available opportunities rather than infer an agent’s intention.

My central concern is whether the rates identify distinct failures in LM trajectories. The scripted policies show that the rates can differ in constructed cases, but 81.59% of exploitation-error events in the main analysis are Case 4 events counted in both metrics. In the Terminal-Bench extension, all 29 identified faults contribute to both numerators. The repetition and no-progress baseline also predicts success at least as well, so success correlation does not independently validate the attribution.

I would also appreciate clarification of a possible inconsistency: Equation (1) assigns zero error to entering an unobserved cell, while the new example counts moves into unseen side-branch cells after the goal becomes actionable as exploitation errors. An action-level scoring trace and the scorer version used for the main results would help resolve this. For now, I am keeping my rating at 2.

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

This paper proposes a policy agnostic metric to quantify Exploration and Exploitation Errors from action trajectories of LM agents. The authors construct partially observable 2D grid maps with unknown symbolic task DAGs. The metric identifies ineffective actions using gain and trajectory redundancy. The authors evaluate 35 LMs. They also analyze prompt strategies, harness engineering, semantic information, and an extension to Minecraft Clone.

Critical strengths
  1. The paper studies a problem that has received limited systematic evaluation. It aims to distinguish Exploration failures from Exploitation failures using only observed trajectories of LM agents.

  2. The experimental evaluation is comprehensive. The authors evaluate 35 LMs. They systematically analyze Prompt Strategy, Harness Engineering, Semantic Information, task difficulty, and different Exploration or Exploitation demands.

Critical weaknesses
  1. The proposed policy agnostic metric still relies on several strong design assumptions. These assumptions include shortest distance Gain, a fixed revisit budget, and hand crafted target set construction rules. Therefore, the Error criteria still depend on predefined rational behavior assumptions.

  2. The authors mainly validate the metric through correlations with Success Rate, prompt interventions, and synthetic edge cases. However, the evaluation lacks human annotation, an oracle policy, or other independent ground truth. Such evidence is necessary to directly verify the correctness of each Exploration or Exploitation Error classification.

  3. In Case 4, both Exploration and Exploitation are valid strategies. However, once an error occurs, the same action is counted in both error categories. Therefore, this attribution rule cannot determine whether the failure more specifically arises from Exploration or Exploitation.

  4. The paper further evaluates the metric in Minecraft Clone. However, the formalization and large scale experiments still mainly rely on discrete symbolic grid settings. Its effectiveness under stochastic transitions, continuous states, or more complex action spaces remains insufficiently validated.

Questions for authors

Please refer to the Critical Weaknesses.

4 comments

We thank the reviewer for highlighting the need to systematically distinguish exploration and exploitation errors from observed agent trajectories and for recognizing the breadth of our evaluation. We address the reviewer’s concerns below.

(W1 – Task design assumptions)

We would like to clarify that shortest distance gain and target set are defined canonically from the 2D grid setting, and are not hand-crafted assumptions. The target sets are structurally defined from the map configuration, and since the LM agent can only take one step per action, we do not penalize an action towards any element in the target set, hence defining it as a gainful action.

We set the fixed revisit budget k=2k=2 based on classical graph exploration literature as described in Section 4. To further verify that our metric is robust to this hyperparameter choice, we sweep k=1,2,3k=1,2,3 and measure the R2R^2 values:

kExploration error R2R^2Exploitation error R2R^2
10.8680.874
20.8810.875
30.8890.876

We included this result in the revised manuscript.

(W2 – Comparison with oracle policies)

First, we kindly remind the reviewer that Appendix B (Lines 923–1016) includes challenging edge cases where we validate the error metrics against human annotation of the errors.

To further provide the evidence of the correctness of our metric, we evaluate five reference policies.

  • DAG-sweep-then-exploit: explore the map until every task DAG nodes are discovered, and exploit in order to achieve the goal.
  • Sweep-then-exploit: explore the whole map first, and exploit in order to achieve the goal.
  • DFS-based: explore the map using DFS-search; when a task is ready to be achieved, prioritize exploitation
  • ϵ\epsilon-DFS: DFS-based but with probability ϵ=0.2\epsilon=0.2, take a random action.
  • Random walk: sample actions uniformly at random among legal neighboring moves.

Exploring the map and exploiting the task DAGs are done optimally to avoid inducing errors.

We use three exploration settings ×\times three task-DAG settings ×\times three map seeds, resulting in 27 maps. Deterministic policies are run once while stochastic policies are run 10 times. The results are reported below:

PolicyExploration errorExploitation errorSuccess
DAG-sweep-then-exploit0.00%0.00%100.00%
Sweep-then-exploit0.00%1.87%100.00%
DFS-based3.24%0.32%100.00%
ϵ\epsilon-DFS9.74%8.53%93.70%
Random walk26.44%27.36%1.85%

The five policies produce distinct aggregate error profiles. DAG-sweep-then-exploit achieves zero measured errors and 100% success on this benchmark as expected. Sweep-then-exploit has non-zero exploitation error as the algorithm may still proceed to explore the rest of the map even when the goal is pending. DFS-based approach shows non-zero errors which increase as we add randomization to the actions. Finally, random walk induces the highest errors and lowest success. See Appendix I for details.

(W3 – Classifying the action as exploration or exploitation)

The reviewer is correct that if an error occurs in Case 4, both exploration and exploitation errors accumulate (Section 4). We emphasize that we do not attempt to classify the agent’s action as exploration or exploitation. Rather, we determine whether an action is an error and attribute the error based on the opportunities available in the current map state. This is for two reasons. First, we do not have access to the policy of a black-box model and cannot directly identify the agent’s intention. Second, as illustrated in Figure 3, the outcome of an action may differ from the agent’s intention. Counting the error in both categories therefore indicates that it occurred when both exploration and exploitation were viable.

(W4 – Extension more complex settings)

We would like to first clarify that the Minecraft Clone experiment was to demonstrate the applicability of our metric to 3D continuous maps. By discretizing the 3D continuous space, our metric can be applied to analyze the agent trajectories.

To further demonstrate the applicability of our metric to different tasks such as coding, we analyze the released trajectories of Terminal-Bench 4.1 [1]. Terminal-Bench evaluates AI agents on practical tasks performed in terminal environments. We select the top five and bottom five leaderboard entries from Terminal-Bench 4.1 to examine how our exploration and exploitation errors can be applied to a less structured problem beyond our 2D grid map and task DAG. We choose telecom-entity-resolution, which requires grouping approximately 93,000 customer records into person-level clusters while distinguishing people who share household information. We collect one trajectory per model, totaling ten logs.

We represent each agent's log as a sequence of parameterized actions, τ=(a1,…,aT)\tau=(a_1,\ldots,a_T), where at=(ot,θt)a_t=(o_t,\theta_t): oto_t belongs to the same seven-operator vocabulary, and θt\theta_t specifies arguments such as files, programs, or process identifiers. The operator set is fixed, while invocation validity depends on the current state and parameters. Before each recorded step, we annotated whether exploration could answer a concrete unresolved question (EtE_t) and whether exploitation could perform an established, ready operation (XtX_t). A localized, evidence-supported operational fault receives wt=1w_t=1; otherwise, wt=0w_t=0 means that no qualifying witness was identified. For each trajectory, we calculated exploration and exploitation error rates as rexploration=∑t=1TwtEt∑t=1TEtr_{\mathrm{exploration}}=\frac{\sum_{t=1}^{T}w_tE_t}{\sum_{t=1}^{T}E_t} and rexploitation=∑t=1TwtXt∑t=1TXtr_{\mathrm{exploitation}}=\frac{\sum_{t=1}^{T}w_tX_t}{\sum_{t=1}^{T}X_t}, respectively. This is an operational-validity adaptation of the paper’s framework.

OperatorMeaningObserved actions
READRetrieve specified content or status105
SEARCHLocate resources or matches94
MODIFYChange an artifact or process state330
EXECUTERun a computation, test, or opaque program921
WAITWait for or poll a pending process16
COMMUNICATESend a message or delegate work0
FINISHSubmit the final result10

The ten trajectories contained 1,476 normalized actions from 872 tool calls, with 29 primary fault-bearing actions and nine additional disputed cases retained for sensitivity analysis. Opus 5.5 had no witnessed primary faults. Beam 1.0 had the most primary faults and the highest exploration error rate, while GPT-5.4 Mini had the highest exploitation error. Fable 5.2 and Sonnet 5.5 each succeeded despite three faults, whereas Nemotron 3.5 Super VL failed with only one identified fault.

EntryOutcomeActionsPrimary faultsExploration errorsExploitation errors
Opus 5.5Pass19400.00%0.00%
Fable 5.2Pass36630.82%0.84%
Gemini 4 CarbonPass12410.81%0.83%
Sonnet 5.5Pass33630.90%0.93%
GPT-6.1 SolPass12610.80%0.84%
Beam 1.0Fail10387.84%8.08%
GPT-5.4 MiniFail4137.50%9.38%
Inkling SmallFail4536.82%6.98%
Nemotron 3.5 Super VLFail4812.13%2.38%
InklingFail9366.52%6.59%

We believe this could be a first step towards applying our method to analyze complex coding trajectories of the agents. You can find the details of this experiment in Appendix J of the revised version.

Stochastic transitions

We interpret "stochastic transitions" as settings where the same action in the same state can produce different outcomes. Consider a stochastic cell that sends the agent to a random location with some probability. If the agent is unaware of this property, we would exempt the first visit from any error attributable to the random transition, analogous to allowing an initial revisit under the budget k=2k=2. If the environment reveals the cell’s behavior after the first visit, we could apply two versions of the gain criterion. A risk-averse criterion would flag a move toward the cell if any possible outcome yields no gain, while a risk-seeking criterion would allow the move if at least one possible outcome yields gain. If the environment does not reveal the cell’s behavior, we would assess the decision using the agent’s prior observations. For example, if those observations provide sufficient evidence that revisiting the cell cannot yield progress, we would flag the decision to revisit it regardless of the realized outcome.

We hope the response addresses your concerns. We would be happy to answer any further questions.

References

[1] Terminal-Bench 4.1. https://www.tbench.ai/. Accessed: 2026-11-15.

Thanks for the detailed response and the additional experiments. The sensitivity tests with k = 1, 2, and 3, the comparisons with reference policies, and the human annotations in Appendix B are all helpful. However, I am still not convinced that these results sufficiently validate the metric at the individual action level. In particular, as the authors acknowledge, an action in Case 4 can be counted as both an exploration and an exploitation error, making it difficult to clearly distinguish between the two. Therefore, I will keep my original score.------(Based on our manual evaluation.)

We thank the reviewer again for the thoughtful review and for raising the question of Case 4 attribution, which has helped us clarify the scope of our metric. Following up on our response to W3, we provide additional evidence on the reviewer's concern about error attribution in Case 4.

Counting a Case 4 error in both rates reflects a deliberate trade-off in our design. In Case 4, both exploring and exploiting are productive. Attributing an error to only one of them would require deciding which behavior the agent should have chosen, and that requires a reference strategy or a cost model. Such a choice would make the metric policy-dependent. Agents following different but reasonable strategies would be penalized differently, and as Figure 3(b) shows, reasonable behavior could be flagged as an error. We therefore trade finer attribution in Case 4 for a metric that remains policy-agnostic and does not penalize valid strategic differences. Finer attribution can be recovered by introducing a cost model or reference policy, which we view as a natural extension when such assumptions are justified for a given task.

How much this shared case affects each rate depends on the structure of the task. In our maps, the agent must discover task nodes before it can act on them, so tasks typically become pending while parts of the map remain unobserved. As a result, exploration errors occur mostly before any task is pending: 95.29% of exploration-error events fall in Case 1, where exploration is the only productive action. Exploitation opportunities, by contrast, mostly arise alongside an exploration frontier. Case 4 accounts for 72.4% (55,165/76,197) of exploitation-eligible steps, and correspondingly for most exploitation-error events.

This asymmetry comes from the map setting rather than the metric, and it is why we evaluate exploitation separately. In the exploitation-only setting (Appendix C.3), we remove the need for exploration by construction. The map and task DAG are fully observable, so U(t)=∅\mathcal{U}(t) = \emptyset at every step, and neither Case 1 nor Case 4 can occur:

CaseDescriptionAll modelsKimi K2.6
1Exploration: no pending tasks0 / 0 (—)0 / 0 (—)
2Exploitation: goal pending7,849 / 23,306 (33.68%)229 / 1,455 (15.74%)
3Exploitation: non-goal tasks pending, no exploration frontier241,587 / 371,262 (65.07%)2,211 / 9,144 (24.18%)
4Both: non-goal tasks pending and exploration frontier0 / 0 (—)0 / 0 (—)
Pooled249,436 / 394,568 (63.22%)2,440 / 10,599 (23.02%)

Even with exploration removed, LM agents incur a 63.22% exploitation error rate, and Kimi K2.6, the strongest model in this setting, still errs on 23.02% of its steps. Exploitation failure is therefore prevalent in LM trajectories on its own, not a by-product of the shared case.

The two rates also separate within the main setting. In Table 2, Hy3 and GPT-OSS-120B both succeed on the same map but fail in opposite ways. All 12 of Hy3's exploration errors occur in Case 1, with no exploitation errors. All 52 of GPT-OSS-120B's exploitation errors occur in Case 2, after the goal becomes pending, with no exploration errors. Neither trajectory contains a single Case 4 error.

Moreover, if the two rates only reflected general inefficiency, interventions would move them together. Instead, our existing ablations on LM agents move them independently or in opposite directions. Reintroducing semantic information substantially reduces exploitation error (0.405→0.061 for Gemini 3.1 Flash Lite; 0.456→0.219 for GPT-4.1), while exploration error stays nearly unchanged (0.309→0.296; 0.279→0.290) (Table 4). Harness engineering reduces GPT-4.1's exploration error (0.177→0.133) while increasing its exploitation error (0.227→0.293) (Table 3). Our scripted policies with known failure modes further confirm the attribution: "Stall before discovering prerequisite" and "Stall after goal becomes actionable" have identical repetition and no-progress counts, yet our metric assigns 6 exploration and 0 exploitation errors to the former, and 0 and 6 to the latter.

The same reasoning clarifies the scope of the Terminal-Bench extension. There, the structure of the task leaves both opportunities available at nearly every step (e.g., 193 and 178 of 194 steps for Opus 5.5), so every identified fault falls into the shared case. In open-ended terminal tasks, exploration and exploitation are almost always simultaneously viable, and separating them would require the stronger assumptions discussed above. We present this experiment as evidence that the opportunity-based framework can be applied to unstructured agent logs, not as evidence of separation, and we will clarify this in the revision.

We hope these additional results address the reviewer's concerns, and we would be happy to answer any further questions.

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

In this paper, the authors tackle measuring explore/exploit optimality deficiencies in LLMs. Noting that LLMs struggle with this (no surprise as it’s hard!) and that measuring / training for this is hard, the introduce some simple graph-based environments where it’s easy to measure how optimal an action is with respect to exploring or exploiting, they define a metric for this, and they evaluate various LLMs on this. The metric is based on whether the model is moving towards (in a geometric sense) a square that has exploration or exploitation value relative to the ground truth structure of the environment. They show that models of a range of strengths with various different system prompts perform differently on this benchmark, and they also include a Minecraft-based extension.

Critical strengths
  • The problems identified are indeed important problems. Training modern language agents to act Bayes-optimally (in a weak sense) is very difficult!
  • The approach of evaluating real LLMs on simple environments that expose the structure we care about is a nice one. Some of the toyness is alleviated by the models used and the prompting methods etc being realistic.
  • The metric makes a lot of sense in this particular setting.
  • The learnings about current LLMs are interesting, showing that weak LLMs struggle to do anything coherent at all and that even strong LLMs are not perfect (despite the games being quite simple).
  • There are some independently interesting findings about the helpfulness of some harness modifications (e.g. reasoning, memory) for optimal behavior in this setting, which could be extended to an interesting line of work.
  • The paper is very well-presented generally, discursively-written and readable. Props to the authors for this which is not all that common anymore.
Critical weaknesses
  • I think that the settings are somewhat limited. This is not just a “this is toy” claim – I understand that it is intentionally so – but there are some properties of this setting which do not transfer very well to general explore/exploit settings. Most notably, in this setting it is always optimal to either explore or exploit, and if either is admissible than the metric doesn’t care. For example, it is basically always useful to gather more information until the final goal (or sequence of states to get to the goal) is clear and then it is optimal to just take go to the goal immediately (or to that sequence). This property is not one that holds in many interesting settings, where normally there is some real trade-off between exploiting earlier and exploring to gather more information. Put simply, there is no “suboptimal exploit” possible in these settings, unless I have misunderstood.
  • The metric depends on substantial ground-truth structure (as well as geometric structure) that does not exist in most realistic settings, so it is hard to view this metric as a useful contribution in itself. (I appreciate the incremental Minecraft-based results in this direction, though.) That means that the benchmark results become the more interesting contribution for me.
  • The benchmark is, however, pretty close to saturated for frontier models, showing the simplicity of the setting. Incidentally, this does not feel in kilter with the claim in the abstract that “even state-of-the-art models struggle to reach the goal”.
  • Despite a very good discussions and limitations section, there is not much discussion of these issues and how they relate to the broader literature and future work.
Questions for authors
  1. How would this metric generalise to settings with less ground-truth structure?
  2. How would this metric generalise to settings with a real explore-exploit tradeoff?
  3. What do you view as the main takeaways from this research that help us get closer to LLMs capable of better decision-making under uncertainty in real-world environments – can you describe a path to that? Or do you think there are other important takeaways irrespective of this. (For example, some of the harness findings seem interesting to me.) Armed with a stronger understanding of the authors' views here, and possibly supporting evidence or discussion in the paper, I would feel more comfortable recommending an accept.
4 comments

We thank the reviewer for recognizing the importance of the problem, the soundness of our environment and metric design, and the interest of our empirical findings. We address the reviewer’s concerns below.

(W1 & Q2 – More realistic explore-exploit tradeoff scenarios)

The reviewer’s understanding is correct that our metric does not enforce a certain behavior between exploration and exploitation and we clarify that this is intentional.

From an agent’s perspective, the reviewer is correct that there will be many scenarios where certain actions will have cascading effects, and where certain strategies are more effective compared to others. For example, as illustrated in Figure 3(b), "Exploring Detour" would always be more optimal than directly going back to B from A by moving left three times, which would then correspond to "suboptimal exploitation." However, since the aim of the paper is to devise an error metric that flags certain actions as errors, we decided not to prescribe a certain optimal strategy and penalize the suboptimal deviations as errors, as those actions could still be making valid progress in our setting.

For this exact reason, while we set a fixed budget and report them for completeness, we do not bake in the notion of efficiency or cost in our metric, except for flagging actions that no valid policy would take as an error, reflected by the increase in stale score (Section 4 Eq. (1)). Relaxing this assumption and incorporating the notion of efficiency in our metric could be a generalization towards modeling more realistic exploration-exploitation tradeoff.

(W2 & Q1 – Relaxing the ground-truth structure)

We believe the framework could be extended to more realistic and general tasks. As acknowledged, the extension to Minecraft was an effort towards applying our metric in 3D continuous space.

To further demonstrate the applicability of our metric to different tasks such as coding, we analyze the released trajectories of Terminal-Bench 4.1 [1]. Terminal-Bench evaluates AI agents on practical tasks performed in terminal environments. We select the top five and bottom five leaderboard entries from Terminal-Bench 4.1 to examine how our exploration/exploitation errors can be applied to a less structured problem beyond our 2D grid map and task DAG. We choose telecom-entity-resolution, which requires grouping approximately 93,000 customer records into person-level clusters while distinguishing people who share household information. We collect one trajectory per model, totaling ten logs.

We represent each agent's log as a sequence of parameterized actions, τ=(a1,…,aT)\tau=(a_1,\ldots,a_T), where at=(ot,θt)a_t=(o_t,\theta_t): oto_t belongs to the same seven-operator vocabulary, and θt\theta_t specifies arguments such as files, programs, or process identifiers. The operator set is fixed, while invocation validity depends on the current state and parameters. Before each recorded step, we annotated whether exploration could answer a concrete unresolved question (EtE_t) and whether exploitation could perform an established, ready operation (XtX_t). A localized, evidence-supported operational fault receives wt=1w_t=1; otherwise, wt=0w_t=0 means that no qualifying witness was identified. For each trajectory, we calculated exploration and exploitation error rates as rexploration=∑t=1TwtEt∑t=1TEtr_{\mathrm{exploration}}=\frac{\sum_{t=1}^{T}w_tE_t}{\sum_{t=1}^{T}E_t} and rexploitation=∑t=1TwtXt∑t=1TXtr_{\mathrm{exploitation}}=\frac{\sum_{t=1}^{T}w_tX_t}{\sum_{t=1}^{T}X_t}, respectively. This is an operational-validity adaptation of the paper’s framework.

OperatorMeaningObserved actions
READRetrieve specified content or status105
SEARCHLocate resources or matches94
MODIFYChange an artifact or process state330
EXECUTERun a computation, test, or opaque program921
WAITWait for or poll a pending process16
COMMUNICATESend a message or delegate work0
FINISHSubmit the final result10

The ten trajectories contained 1,476 normalized actions from 872 tool calls, with 29 primary fault-bearing actions and nine additional disputed cases retained for sensitivity analysis. Opus 5.5 had no witnessed primary faults. Beam 1.0 had the most primary faults and the highest exploration error rate, while GPT-5.4 Mini had the highest exploitation error. Fable 5.2 and Sonnet 5.5 each succeeded despite three faults, whereas Nemotron 3.5 Super VL failed with only one identified fault.

EntryOutcomeActionsPrimary faultsExploration errorsExploitation errors
Opus 5.5Pass19400.00%0.00%
Fable 5.2Pass36630.82%0.84%
Gemini 4 CarbonPass12410.81%0.83%
Sonnet 5.5Pass33630.90%0.93%
GPT-6.1 SolPass12610.80%0.84%
Beam 1.0Fail10387.84%8.08%
GPT-5.4 MiniFail4137.50%9.38%
Inkling SmallFail4536.82%6.98%
Nemotron 3.5 Super VLFail4812.13%2.38%
InklingFail9366.52%6.59%

We believe this could be a first step towards applying our method to analyze complex coding trajectories of the agents. You can find the details of this experiment in Appendix J of the revised version.

(W3 – Performance statement)

Our intention was to point out that of the models we tested, many strong LMs show varying success rates (e.g. GPT-4.1 with 66.2%, Gemini 3.1 Flash Lite with 50.93%, in Table 10). We will tone down the sentence to reflect your feedback.

We would like to leave one remark that since the maps can be generated programmatically, we can increase the difficulty to stress test even the strongest models. We have not tested this in the paper due to API cost, but we show additional results below on strong open-source models. We evaluate two additional difficulty settings, namely Hard and Harder, with 50 maps each. The settings evaluated in the paper contain 4–8 task DAG nodes and average 34.67–56.56 total grid cells. Hard retains 8 task DAG nodes while increasing the mean grid size to 88.90 cells. Harder increases both the task DAG size to 10 nodes and the mean grid size to 113.60 cells. Both models achieve lower success rates on these more challenging settings, as shown below.

ModelPaper settingsHardHarder
Kimi K2.673.15%62%52%
Hy363.89%44%38%

This result demonstrates that as the map size and the number of task DAG nodes increase, our task becomes more challenging to even one of the strongest models.

(W4 & Q3 – Future work and takeaways)

One straightforward extension of this work towards LMs capable of better decision making in the wild would be to utilize our metric as a learning signal to penalize inefficient behaviors. The feedback can be provided either through formulating the metric into a (negative) reward function, or by structuring the feedback into an agent’s harness.

Orthogonal to this, as discussed above, we believe that canonical extension of our metric design to more complicated tasks is definitely possible, especially when the goal is to densify the reward/feedback to improve the model instead of devising a metric to compare between different models. Such extensions will be more useful under tasks where the final evaluation is costly (which is common these days for tasks like Terminal-Bench), as the learning signal from our metric could be provided regardless of the final task success/fail.

We hope the response addresses your concerns. We would be happy to answer any further questions.

References

[1] Terminal-Bench 4.1. https://www.tbench.ai/. Accessed: 2026-11-15.

Thank you for your response. I am happy enough with your comments to increase my score. Best of luck.

Comments on the paper

2 comments

We appreciate the reviewers' constructive feedback. We have revised our submission reflecting the reviewers' comments. Our revision can be summarized as below.

  • Abstract: Improved writing and clarity.
  • Experimental Results – Behavioral Comparison and Finding 2: Moved this part from the Appendix.
  • Discussion – Extension to Minecraft Clone: Improved writing and clarity.
  • AI Use Statement: Revised it more clearly.
  • Full Results – Exploration–Exploitation Setting: Added full results.
  • Full Results – Exploitation-Only Setting: Added full results.
  • Sensitivity to Budget Constants: Added results on more detailed analysis of our metric.
  • Appendix – Extension to Minecraft Clone: Improved writing and clarity.
  • Appendix – Reference Policies: Added new experiments for reference policies.
  • Appendix – Application to Terminal-Bench 4.1: Added new experiments on Terminal-Bench 4.1.

Please let us know if you have any further questions or concerns. Thank you again.

Dear Reviewers,

The authors have now submitted their rebuttal and responded to the concerns raised in the reviews. We would greatly appreciate it if you could take some time to review their responses and participate in the discussion, particularly regarding whether your concerns have been adequately addressed.

Thank you very much for your time and valuable contributions!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.