Exploration and Exploitation Errors Are Measurable for Language Model Agents

Abstract

Language Model (LM) agents are increasingly used in complex decision-making tasks, from AI coding to physical AI, where they must both explore a search space and exploit acquired knowledge effectively. Although exploration and exploitation play different roles in decision-making, it remains challenging to systematically distinguish exploration and exploitation 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 practical agentic AI scenarios. We then propose a policy-agnostic metric that detects unproductive traversals, while permitting necessary backtracking. We attribute each error to exploration or exploitation based on whether the current state admits productive exploration, exploitation, or both. Using 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 relationships with task success ($R^2 = 0.885$ and $0.875$, 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 its own reasoning traces. Finally, we extend our metric to an iconic video game, Minecraft Clone, beyond our synthetic environment. We release our code at https://github.com/jjj-madison/measurable-explore-exploit.