PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploration and Exploitation Errors Are Measurable for Language Model Agents

Jaden Park, Jungtaek Kim, Jongwon Jeong, Robert D. Nowak, Kangwook Lee, Yong Jae Lee

arXiv:2604.13151v1cs.AI

TL;DR

Evaluating how language-model agents balance exploration and exploitation from behavior alone remains difficult. This paper introduces policy-agnostic environments and error metrics, finding that low exploration error predicts success, while similarly successful agents can behave differently.

  • Problem

    A systematic framework is missing for distinguishing and quantifying language-model agents’ exploration and exploitation from observed actions without access to internal policies.

  • Method

    The paper combines partially observable grid maps with unknown symbolic task DAGs and measures structurally redundant trajectory behavior to assign exploration and exploitation errors.

  • Results

    Low exploration error strongly predicts success, while agents with similar success rates exhibit qualitatively different behaviors and both error types improve through minimal harness engineering.

  • Takeaways & Limitations

    The framework offers a behavioral lens beyond success rate for evaluating and improving language-model agents in complex open-ended tasks.

  • Takeaways & Limitations

    Because the environments remove semantic information, they do not fully represent real-world tasks where agents use domain knowledge and pretrained knowledge.

Abstract

from arXiv · show

Language Model (LM) agents are increasingly used in complex open-ended decision-making tasks, from AI coding to physical AI. A core requirement in these settings is the ability to both explore the problem space and exploit acquired knowledge effectively. However, systematically distinguishing and quantifying exploration and exploitation from observed actions without access to the agent's internal policy remains challenging. To address this, we design controllable environments inspired by practical embodied AI scenarios. Each environment consists of a partially observable 2D grid map and an unknown task Directed Acyclic Graph (DAG). The map generation can be programmatically adjusted to emphasize exploration or exploitation difficulty. To enable policy-agnostic evaluation, we design a metric to quantify exploration and exploitation errors from agent's actions. We evaluate a variety of frontier LM agents and find that even state-of-the-art models struggle on our task, with different models exhibiting distinct failure modes. We further observe that reasoning models solve the task more effectively and show both exploration and exploitation can be significantly improved through minimal harness engineering. We release our code \href{https://github.com/jjj-madison/measurable-explore-exploit}{here}.

1 Introduction

The paper addresses the lack of a systematic, policy-independent way to assess how LM agents explore and exploit in open-ended tasks. It introduces controllable grid-map/DAG environments and an action-trajectory metric for measuring exploration and exploitation errors.

  • Introduction: LM agents face open-ended tasks requiring both exploration of unseen problem regions and effective exploitation of acquired knowledge.
  • Introduction: A systematic framework for quantifying exploration and exploitation remains unavailable because LM-agent evaluations typically expose observed actions, not internal policies or value functions.
  • Introduction: The authors introduce a policy-agnostic framework that evaluates exploration and exploitation from action trajectories in partially observable 2D grid maps paired with unknown task DAGs.
  • Introduction: The error metric flags structurally redundant actions during trajectory segments that make no task progress, without prescribing an optimal policy.
  • Introduction: Programmatically varying map topology and task-DAG complexity creates different exploration or exploitation demands, while frontier-agent evaluations reveal frequent struggles and distinct failure modes.More exploration can involve wider maps or sparser task-node placement, whereas more exploitation can involve shallow paths or denser task dependencies.

2 Related Work

Related work studies LM agents’ exploration and exploitation in embodied, software, and tool-use environments, but existing evaluations often conflate pretrained knowledge with in-environment reasoning and rely primarily on task success. This work addresses these limitations with symbolic, controllable task structures and trajectory-based metrics for separating exploration and exploitation errors.

  • Language Model Agents: LM agents interact with external environments over multiple turns and must explore for information while exploiting it to achieve goals.This has motivated benchmarks spanning embodied interaction, software tasks, and tool-use settings.
  • Language Model Agents: Recent work evaluates whether LM agents can construct and exploit spatial beliefs through exploration.Zhang et al. (2026) specifically assess spatial-belief construction and exploitation.
  • Language Model Agents: Existing environments rely on semantic information, lack systematic control over task dependencies, and do not separate or quantify exploration and exploitation errors from trajectories.The paper responds with symbolic task DAGs, controllable dependency structures, and a metric for exploration and exploitation errors.
  • Evaluation Metrics for LM Agents’ Behavior: Current LM-agent evaluations predominantly use task success rates, while finer-grained metrics assume annotated reference trajectories and a fixed optimal strategy.These methods include stepwise alignment with expected tool calls and progress relative to reference trajectories.

3 Task Formulation

The framework models an agent navigating a partially observable 2D grid to discover task nodes, satisfy their prerequisites, and achieve a unique goal node. Its information-revelation design enables exploration and exploitation to be distinguished and quantified from actions.

  • Framework objective: The agent traverses a 2D grid map to discover relevant task nodes, use accumulated knowledge to satisfy prerequisites, and ultimately achieve the goal node.The framework is designed to distinguish and quantify exploration and exploitation from the agent’s actions.
  • 2D Grid Map: The partially observable map consists of traversable cells in N^2, with up, down, left, and right movements.Obstacles are excluded from the map, and movement reveals local spatial information and task-relevant entities.
  • 2D Grid Map: Visiting cells reveals admissible neighboring moves, while task-DAG information is revealed only when cells are observed, requiring travel to unobserved cells for discovery.A cell is observed after the agent has visited it; previously unseen neighboring cells remain unobserved.
  • Task DAG: The task DAG represents sub-tasks as nodes and precedence constraints as edges, with a unique goal node assumed without loss of generality.Upon discovering a node, the environment reveals its parent and child nodes, but the revealed nodes’ locations must still be found.
  • Task DAG: Each task node is undiscovered, discovered, or achieved, and the task completes only when the agent achieves the goal node.A node is discovered when found but its preconditions are unmet; it is achieved only after visiting it with satisfied preconditions.

4 Measuring Exploration and Exploitation Errors

The section defines a policy-agnostic metric that distinguishes exploration from exploitation errors using task readiness, unobserved cells, target-directed gains, and structurally stale trajectories.

  • Action requirements: Pending tasks P(t) represent ready-to-achieve DAG nodes with known locations, while unobserved cells U(t) represent exploration opportunities.The agent exploits by returning to locations of pending tasks and explores unobserved cells.
  • Action requirements: The agent must explore when U(t) ≠ ∅ and exploit when P(t) ≠ ∅, except that a pending goal task permits exploitation only.These conditions determine whether errors are attributed to exploration, exploitation, or both.
  • Progress and errors: An action gains progress if it enters a target cell or reduces minimum distance to a target; otherwise it is initially classified as an error.Gain alone cannot detect indefinite oscillation between symmetric targets.
  • Stale trajectories: No-progress trajectories track traversed nodes and edges since the latest task achievement or unobserved-cell entry, capturing repeated movement after progress stalls.The trajectory statistics include cyclomatic number ct and excess edge and node reuse, et and nt.
  • Error metric: The stale score St = ct + et + nt flags an error when it increases, while progress events receive zero error.The stale score is needed only when multiple target cells exist; single-target gains are not stale-score errors.
  • Error attribution: When an error occurs, Case 1 increments exploration error, Cases 2–3 increment exploitation error, and Case 4 increments both.This attribution follows the required action determined by the environment state.

5 Experimental Setup

The experiments generate task DAGs and 2D grid maps whose structural parameters and obstacles control exploration and exploitation difficulty, then evaluate 13 language models under four ReAct prompt variants using success and normalized error metrics.

  • Models: The study evaluates 13 language models spanning OpenAI ChatGPT, Google Gemini, Anthropic Claude, and GPT-OSS-120.The listed models include GPT-4.1, GPT-5.4, Gemini 3.1 pro, Claude Opus 4.6, and other family variants.
  • Prompts: The default ReAct setup uses base, exploration, exploitation, and balance prompts that share the same environment description and action format.Variants differ only in one strategy sentence, while the base prompt gives no strategic guidance.
  • Evaluation: Evaluation reports success rate, exploration error, and exploitation error, with errors normalized by timesteps requiring the corresponding action type.Exploration error covers Cases 1 and 4, whereas exploitation error covers Cases 2, 3, and 4.

6 Experimental Results

Stronger reasoning models achieve higher success, with success strongly tied to low exploration error but only weakly to exploitation error. Prompting, harness engineering, and semantic information affect exploration, exploitation, and performance, while similarly successful agents can behave differently.

  • Stronger reasoning models consistently achieve higher performance, with the best models reaching up to 100% success rate.
  • Low exploration error strongly predicts success, whereas exploitation error has only a weak relationship with success.Agents must discover relevant task nodes before achieving the goal, so persistent exploration failures directly limit completion.
  • Agents with similar success rates can exhibit qualitatively different exploration behaviors.Claude Opus 4.6 and Gemini 3.1 Pro both achieve 100% success but diverge after roughly 50% of episode progress, with Gemini exploring more.
  • Exploration-focused and exploitation-focused prompts reduce exploration and exploitation errors, respectively, while exploration-focused prompts achieve the highest success rate.For GPT-4.1, the exploration-focused prompt has the lowest exploration error and highest success, whereas the exploitation-focused prompt has the lowest exploitation error.
  • Structured harness engineering significantly improves success rates, exploration and exploitation errors, and average steps taken in successful trajectories.The reported improvements apply to agents using historical outcomes, including Gemini 3.1 Flash Lite and GPT-4.1.
  • Reintroducing semantic information affects models differently: GPT-4.1’s success rate increases by roughly 3× with lower exploration error, while other models may favor myopic exploitation.These results indicate that semantic priors can guide exploration or bias behavior toward exploitation.

7 Discussion and Limitations

The study’s symbolic, semantics-free environments isolate exploration, memory, and exploitation behaviors but do not fully represent real-world tasks, where semantic priors can substantially change agent behavior. Its error metrics are trajectory-dependent and vary across agents, runs, and map difficulties, complicating comparisons despite observed cross-model strategy and success trends.

  • On the use of symbolic abstraction: The symbolic abstraction isolates raw exploration and exploitation capabilities by removing semantic information and representing tasks as symbolic DAGs, but it does not fully reproduce real-world scenarios.Many practical tasks include semantic information and priors that are absent from this setup.
  • On the use of symbolic abstraction: Semantic reintroduction can substantially affect agent behavior, while the abstraction tests exploration, relevant memory and state maintenance, and action on newly actionable knowledge without semantic shortcuts.These behaviors must be inferred from interaction history alone in the symbolic setting.
  • Per-model variance and the error metric: Exploration and exploitation errors are inherently trajectory-dependent because per-case normalization depends on timestep counts shaped by each agent’s chosen path.Different success rates and average successful-trajectory lengths also directly influence the normalization.
  • Per-run variance and map difficulty: Different runs of the same agent can produce substantially different trajectories and local scenarios, yielding different aggregated error values despite clear cross-model trends in strategies and success rates.Some experiments nevertheless show weaker correlations across models.

8 Conclusion

The paper introduces a policy-agnostic metric for quantifying exploration and exploitation errors from LM-agent action trajectories. Experiments in partially observable grid-map environments with task DAGs link low exploration error to success while revealing qualitatively different behaviors among agents with similar success rates.

  • Contributions: The work introduces a policy-agnostic metric that quantifies exploration and exploitation errors from LM-agent action trajectories.The metric is evaluated in partially observable grid-map environments with task DAGs.
  • Findings: Low exploration error is strongly associated with success across the evaluated frontier LM agents.
  • Findings: Agents with similar success rates can nevertheless exhibit qualitatively different behaviors.

Ethics Statement

The paper notes that its synthetic-task findings may inform real systems but warns that the environments and errors could also make unsafe agents appear better when used alone. It therefore emphasizes reproducibility and recommends human review, task-specific safety checks, and hard action limits before deployment.

  • Risks and limitations: The environments and error metrics can help identify weak behavior before deployment, but may make unsafe agents look better if used alone.The authors explicitly caution against treating these evaluations as sufficient safeguards for real-world use.
  • Mitigations: The authors will release full prompts, task-generation settings, and evaluation code to support reproducibility.These materials are intended to make the evaluation process inspectable and repeatable.
  • Mitigations: Before real-world deployment, the paper recommends human review, task-specific safety checks, and hard action limits.These safeguards are proposed because the environments are synthetic and the evaluation should not be used alone.

Appendices · A Additional Related Work

The appendices provide additional details omitted because of limited space, including related work on exploration–exploitation in reinforcement learning and LM agents. The section highlights a gap: existing frameworks do not quantitatively separate exploration and exploitation errors when prior actions affect observations and achievable outcomes.

  • Appendices: The appendices add details that were omitted because of limited space.
  • A Additional Related Work: Exploration–exploitation has been extensively studied in reinforcement learning.
  • A Additional Related Work: The exploration–exploitation tradeoff has recently gained attention for language-model agents.
  • A Additional Related Work: Several studies find that language models explore inefficiently and propose improving exploration through in-context learning.
  • A Additional Related Work: Prior work has targeted exploration or exploitation and analyzed their tradeoffs in fixed environments with environment-independent actions.
  • A Additional Related Work: In real-world tasks, prior actions often determine what a language-model agent can observe and achieve.
  • A Additional Related Work: No existing framework quantitatively separates and measures exploration and exploitation errors in environments where actions affect observations and outcomes.
  • A Additional Related Work: This work addresses the gap through proposed 2D grid-map environments.

B Details of Task Formulation and Exploration and Exploitation Metric … F Examples of LM Agent’s Runs in Our Environments

The appendix formalizes partially observed grid-and-DAG tasks and a policy-agnostic gain metric that distinguishes productive exploration and exploitation from erroneous actions. It also details task generation, harness engineering, semantic-information experiments, and trajectory visualizations illustrating agent behavior.

  • B Details of Task Formulation and Exploration and Exploitation Metric: Each visited cell reveals admissible neighboring moves, while task-DAG information is revealed only when the agent reaches previously unobserved cells.The agent must traverse to unobserved cells to discover whether task nodes are present.
  • B Details of Task Formulation and Exploration and Exploitation Metric: The task DAG has a unique goal sink, injectively mapped task nodes, and AND/OR prerequisites governing when visited nodes become achieved.A node is achieved only when visited with either all or at least one parent achieved, depending on its type.
  • B Details of Task Formulation and Exploration and Exploitation Metric: A move is a gain when it enters a productive target cell or reduces shortest distance to at least one target; otherwise, it is an error.The existential condition makes the metric policy-agnostic, while target cells vary with the agent’s current state.
  • B Details of Task Formulation and Exploration and Exploitation Metric: When pending tasks and unseen cells coexist, the metric permits either exploration or exploitation because the optimal tradeoff depends on unavailable full map and DAG knowledge.A longer path through unseen cells can be more task-efficient than a shorter path through seen cells.
  • C.1 Task Generation: Task instances vary DAG size and exploitation demand, with map density and corridor width controlling spatial sparsity, distances, and admissible moves.DAG sizes include 4, 6, and 8 nodes for small, medium, and large settings, respectively.
  • D Harness Engineering: The harness injects a rule-based structured memory summary containing only information derivable from observation history, including visited cells, frontier, discovered states, and activation status.The summary explicitly supports exploration through frontier cells and exploitation through activatable states.
  • E Semantic Experiment: Semantic experiments preserve the grid, DAG, and observation format while replacing symbolic identifiers with meaningful cooking-task names that may invite semantic priors.The experiments use pasta-cooking scenarios requiring visits to ingredient and intermediate-step cells.
  • F Examples of LM Agent’s Runs in Our Environments: Trajectory visualizations report action paths and metric values over time for Gemini 3.1 Flash Lite, GPT-4.1, Claude Opus 4.6, and Claude Haiku 4.5.Figure 8 specifically presents trajectory and metric results for Claude Haiku 4.5.

G Additional Experimental Results

Additional experiments with GPT-4.1 vary exploration demand and task DAG size on fixed 8×8 maps. Exploration error rises with exploration demand and DAG size, while exploitation error shows weaker demand correlation and declines as DAG size increases.

  • Experimental setup: Figure 20 evaluates GPT-4.1 across exploration demands and task DAG sizes using 96 runs on 32 maps with three random seeds.The map remains a full 8×8 grid while task DAG size and map design vary.
  • Experimental setup: Exploration demand is controlled by task-node density and corridor width, while low exploration demand implies high exploitation demand.Task DAG sizes vary by changing task-node count while keeping the 8×8 map configuration fixed.
  • Demand analysis: Exploration error is positively correlated with exploration demand, whereas exploitation error shows no similarly strong correlation with exploitation demand.The authors hypothesize that trajectory dependence obscures exploitation-demand trends because a few divergent actions can produce substantially different trajectories and metrics.
  • DAG-size analysis: With larger task DAGs, exploration error increases while exploitation error decreases.Because map size is fixed, more task nodes expand the effective area requiring traversal; expected inter-node distances also decrease.
Loading 2604.13151v1…