UW-Madison Exposes Why GPT-4.1 and Claude Fail Open-Ended Agent Tasks
A new policy-agnostic framework separates exploration from exploitation errors in language model agents, revealing why some frontier models fail while others succeed.
Takeaways
- New policy-agnostic framework quantifies exploration and exploitation errors from LM agent action trajectories alone.
- Partially observable 2D grid maps with hidden task DAGs let researchers isolate raw reasoning from pretrained semantic priors.
- Exploration error strongly predicts success (R²=0.947); exploitation error alone does not (R²=0.006).
- Claude Opus 4.6 and Gemini 3.1 Pro both hit 100% success but exhibit very different exploration behaviors.
- Harness engineering with structured memory summaries lifted GPT-4.1 from 63% to 92.6% success rate.
- Code and evaluation environments released at github.com/jjj-madison/measurable-explore-exploit.
Language model agents are being pushed into open-ended jobs like coding, workflow automation, and robotics, all of which require the same basic skill: knowing when to poke around for new information and when to act on what you already know. If you only see the actions an agent takes, how do you tell whether it failed because it explored badly, exploited badly, or both? A new paper from researchers at the University of Wisconsin-Madison and KRAFTON proposes a way to measure both separately, and the results expose sharp differences between frontier models that success rate alone hides.
The measurement problem
In classical reinforcement learning, exploration and exploitation are defined against an agent's internal policy or value function. For LM agents, we typically have access only to the observed actions. That makes it hard to say whether a wrong move was a failure to gather information or a failure to use what was already gathered.
Existing benchmarks mostly report task success rate, and the few that go deeper assume access to annotated reference trajectories and thus a fixed optimal strategy. That's a poor fit for LM agents, which can reason their way to a goal in many different ways.
A grid world with hidden dependencies
The paper builds a controllable test environment that captures what real agentic tasks look like: navigating a partially observed space while satisfying a chain of dependencies. Each task pairs a partially observable 2D grid with an unknown Directed Acyclic Graph (DAG) of subtasks. The agent has to walk around, discover task nodes, figure out their prerequisites, and eventually reach a goal node.

One crucial detail: all semantic information in the task DAGs is replaced with symbolic representations like random four-character codes (D7UX, 9J7T). This stops models from cheating with pretrained priors about, say, how to cook pasta, and forces reasoning purely from what they observe. The map generator can be tuned to make either exploration or exploitation harder by adjusting corridor widths, node density, and DAG depth.