Exploration and Exploitation Errors Are Measurable for Language Model Agents

This paper introduces controllable environments and a policy-agnostic metric to quantify exploration and exploitation errors in language model agents, revealing that while state-of-the-art models struggle with these tasks, reasoning models and minimal harness engineering can significantly improve performance.

The Gist

Imagine you are trying to teach a very smart, but slightly naive, robot how to solve a giant, invisible maze to find a hidden treasure. The robot has a massive library of knowledge (it knows what a "key" or a "door" usually looks like in real life), but in this specific game, the rules are different, and the objects have made-up names like "Z7X9" instead of "Key."

This paper is about a new way to test how well these AI robots can figure out the maze on their own, without us peeking inside their "brain" to see how they think.

Here is the breakdown of the paper using simple analogies:

1. The Two Big Problems: "Wandering" vs. "Stuck in a Loop"

When an AI tries to solve a complex task, it has to balance two things:

• Exploration (Wandering): Going into new, unknown areas to find clues. It's like walking into a dark room and turning on the lights to see what's there.
• Exploitation (Using What You Know): Using the clues you've already found to solve the puzzle. It's like realizing, "Oh, I found the key in the kitchen, so I should go back to the locked door."

The Problem: Until now, we could only tell if the AI succeeded or failed at the very end. We couldn't tell why it failed. Did it fail because it was too lazy to look around (bad exploration)? Or did it find the key but keep walking in circles around the door instead of opening it (bad exploitation)?

2. The New "Scorecard" (The Metric)

The authors built a special test environment—a digital grid map with invisible walls and hidden tasks. They created a new "scorecard" that watches the AI's moves in real-time.

Think of it like a referee in a video game who doesn't just look at the final score, but watches every step:

• The "Stale Score": If the AI walks in a circle, goes back and forth over the same spot too many times, or enters a dead end it already knows is empty, the referee gives it a "Stale Point."
• The Goal: The referee tries to guess: "Is this move a smart exploration, or is it a stupid mistake?"
  • If the AI walks into a new, unexplored area, that's Exploration.
  • If the AI walks toward a task it already knows about but hasn't finished, that's Exploitation.

The paper found something surprising: Exploration is the most important part. If an AI fails to explore enough, it almost never wins, no matter how smart it is. But if it explores well, it has a good chance of winning, even if it makes some small mistakes later.

3. The "Secret Cheat Sheet" (Harness Engineering)

The researchers noticed that some AIs were getting confused because they had to remember everything from the start of the game just by reading the chat history. It's like trying to solve a mystery while reading a 500-page book where the clues are scattered randomly.

They tried giving the AI a "Cheat Sheet" (Harness Engineering). Instead of just saying "You are at [2,3]," they gave the AI a structured summary:

• "You have visited these rooms."
• "You found these clues."
• "Here are the rooms you haven't checked yet."

The Result: This was a game-changer. By organizing the information clearly (like a detective's whiteboard), the AI's performance skyrocketed. It made fewer mistakes and finished the task much faster. It proved that sometimes, the AI isn't "dumb"; it just needs better organization of the information it already has.

4. The "Meaning" Trap (Semantic vs. Symbolic)

The researchers also tested what happens when they give the AI real-world names (like "Pasta" and "Tomato Sauce") versus fake names (like "A1" and "B2").

• The Good: For some AIs, real names helped them guess the right path because they knew how pasta is made.
• The Bad: For other AIs, real names were a trap! They got so distracted by their "real world" knowledge that they ignored the actual rules of the game. They assumed the cheese must be next to the pasta, even if the game map said otherwise.

The Big Takeaway

This paper teaches us that to make AI agents better at complex jobs (like coding, robot control, or planning), we can't just look at whether they finished the task. We need to measure how they got there.

1. Exploration is King: An AI that isn't brave enough to look around will fail.
2. Organization Matters: Giving AI a clear, structured summary of what it knows (a "harness") helps it think much better than just dumping raw data on it.
3. Context is a Double-Edged Sword: Real-world knowledge helps, but it can also trick the AI into making bad assumptions if the situation is unusual.

In short: To build better AI, we need to stop just asking "Did you win?" and start asking "Did you look around enough, and did you use your notes correctly?"

Technical Summary

1. Problem Statement

Language Model (LM) agents are increasingly deployed in complex, open-ended decision-making tasks (e.g., AI coding, embodied AI, workflow automation). These tasks inherently require a balance between exploration (gathering new information about the environment) and exploitation (using known information to achieve goals).

However, a critical gap exists in evaluating these agents:

• Lack of Policy-Agnostic Metrics: Existing evaluation methods rely heavily on success rates or assume access to an agent's internal policy/value function. In practice, evaluators often only have access to observed action trajectories.
• Inability to Distinguish Error Types: It is difficult to systematically distinguish whether a failure stems from poor exploration (failing to find necessary nodes) or poor exploitation (failing to utilize known paths efficiently) without a ground-truth optimal policy.
• Semantic Confounding: Many existing benchmarks use semantic information (e.g., "cook pasta"), which allows agents to rely on pretrained priors rather than genuine reasoning about the specific environment structure.

2. Methodology

The authors propose a policy-agnostic framework to quantify exploration and exploitation errors solely from action trajectories.

A. Environment Design

The authors designed a controllable, partially observable 2D grid map environment paired with an unknown Task Directed Acyclic Graph (DAG).

• 2D Grid Map: A partially observable grid where the agent reveals cells by visiting them. Obstacles and unobserved cells are hidden.
• Task DAG: Represents the task structure where nodes are sub-tasks and edges define precedence constraints (AND/OR logic).
  • Symbolic Abstraction: Crucially, all node names are replaced with random alphanumeric tokens (e.g., "A7X9") to strip semantic meaning. This forces the agent to rely entirely on observed state and memory rather than pretrained knowledge.
  • State States: Nodes transition from Undiscovered $\to$ Discovered (seen but prerequisites unmet) $\to$ Achieved (prerequisites met and visited).
• Controllability: Map generation parameters (node density, corridor width, DAG complexity) allow the authors to programmatically emphasize exploration difficulty (sparse nodes, wide maps) or exploitation difficulty (dense dependencies, shallow paths).

B. The Error Metric

The core contribution is a metric that flags actions as errors based on structural redundancy and lack of progress, without assuming a specific optimal policy.

1. Target Set $T(t)$: At any timestep $t$, the agent must either explore (visit unobserved cells $U(t)$) or exploit (visit pending tasks $P(t)$). The target set $T(t)$ is defined based on the current state of the map and DAG (Table 1 in the paper).
2. Gain Definition: An action is a "gain" if it moves the agent into a target cell or reduces the distance to a target cell.
3. Stale Score ($S_t$): To handle cases where gain is ambiguous (e.g., symmetric targets), the authors track no-progress trajectories ($\tau_{np}$). They compute a "stale score" based on graph theory concepts:
   • $c_t$: Cyclomatic number (new loops formed).
   • $e_t$: Excess edge traversals (edges traversed $>2$ times).
   • $n_t$: Excess node visits (nodes visited $>2$ times).
   • Rationale: Optimal graph exploration traverses edges at most twice. Reusing edges/nodes beyond this without progress indicates a failure.
4. Error Classification: An error is flagged if:
   • The action yields no gain ($Gain=0$).
   • The action yields gain but increases the stale score (redundant movement).
   • Errors are attributed to Exploration, Exploitation, or Both based on the required action type at that timestep.

C. Experimental Setup

• Models Evaluated: 13 frontier LMs (GPT-4.1/5.4 series, Gemini 3.1 series, Claude 4.5/4.6 series, and GPT-OSS-120B).
• Variables:
  • Prompt Variants: Base, Exploration-focused, Exploitation-focused, and Balanced.
  • Harness Engineering: Explicitly providing structured summaries of visited cells, frontiers, and task states to the agent (simulating external memory) vs. relying on raw context.
  • Semantic Injection: A secondary experiment reintroducing semantic names (e.g., "Pasta") to test the impact of priors.

3. Key Contributions

1. Policy-Agnostic Metric: Introduced the first metric to quantify exploration and exploitation errors from action trajectories alone, grounded in graph theory (redundancy and reuse) rather than a fixed optimal policy.
2. Controllable Benchmark: Designed a symbolic, partially observable grid-world environment with task DAGs that isolates reasoning capabilities from semantic priors, allowing systematic control over exploration/exploitation demands.
3. Empirical Insights:
   • Finding 1: Low exploration error is a strong predictor of success ($R^2 = 0.947$), whereas exploitation error correlates weakly with success.
   • Finding 2: Agents with identical success rates exhibit qualitatively different behaviors (e.g., some over-exploit known paths while others continue exploring).
   • Finding 3: Prompt engineering (explicitly instructing "prioritize exploration") significantly reduces specific error types.
   • Finding 4: Harness Engineering (providing structured memory summaries) dramatically improves performance, reducing errors and step counts for all models.
   • Finding 5: Reintroducing semantic information affects models differently; it can aid exploration for some (GPT-4.1) but bias others toward myopic exploitation (Gemini 3.1 Flash Lite).

4. Key Results

• Success vs. Error Correlation: There is a strong negative linear relationship between Exploration Error and Success Rate. Models that fail to explore effectively rarely succeed. Conversely, low exploitation error does not guarantee success if the agent fails to explore enough to find the goal.
• Model Performance: Even state-of-the-art models struggle, often exhibiting distinct failure modes (e.g., getting stuck in loops, failing to backtrack correctly). Reasoning models generally perform better.
• Impact of Harness Engineering: Providing explicit structured summaries (Harness) improved success rates from ~50-60% to ~88-92% for models like GPT-4.1 and Gemini 3.1 Flash Lite, while simultaneously reducing both exploration and exploitation errors.
• Semantic Impact: In the semantic experiment, GPT-4.1 leveraged priors to improve exploration (3x success rate increase), while Gemini 3.1 Flash Lite showed a 6x decrease in exploitation error but a higher exploration rate, suggesting semantic priors can sometimes interfere with logical reasoning in complex dependency graphs.

5. Significance

• Beyond Success Rate: This work moves the field beyond binary success/failure metrics, offering a granular lens to diagnose why an agent fails (did it get lost, or did it fail to use what it knew?).
• Diagnostic Tool for Agent Design: The metric allows developers to identify specific weaknesses in an agent's reasoning loop, guiding improvements in prompt engineering, memory management (harnesses), and architecture.
• Foundation for Future Research: By isolating symbolic reasoning from semantic priors, the framework provides a rigorous testbed for evaluating the raw capabilities of LM agents in planning and memory management, which is essential for deploying them in real-world, high-stakes environments where hallucination and poor planning are critical risks.
• Practical Implications: The findings suggest that harness engineering (structuring external memory) is a highly effective, low-cost intervention to improve agent performance, potentially more so than simply scaling model size or changing prompts.