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 here.
Figures & tables
Figure 1: Overall relationship between success rate and exploration/exploitation errors across various LMs. In Figure 1(a) , log exploration error and success rate show a strong negative linear relationship ( R2=0.947 ) whereas Figure 1(b) depicts a weak relationship ( R2=0.006 ) between log exploitation error and success rate. This implies that LM agents that explore the environment more effectively will have a chance of achieving the goal task.
Figure 2: Illustration of the LM agent traversing the 2D grid map to achieve the goal given by the task DAG. In each timestep, the environment returns the set of admissible moves and the information about the task node, if discovered. The LM agent must retain relevant information about the map geometry, the task DAG structure and the states of the discovered nodes to achieve the goal node.
Figure 3: Three illustrative examples demonstrating edge cases. In all three maps, node A is achieved and node B is pending, so the agent can traverse back to B, or explore to discover node C. The purple dashed line depicts the path the LM agent has taken, and the blue transparent line denotes a potentially more optimal path. In Figure 3 a, the LM agent can infer the shortest path to node A and traverse unseen nodes as part of an exploitation strategy. In contrast, in Figure 3 b, the agent has already taken the shortest path from node B to node A. Hence, it may be more optimal to make a short detour and observe 5 unseen cells at the cost of a short detour. Figure 3 c illustrates a case where target cells T(t) are placed symmetrically. Here gain will always be 1 for all four actions. A metric solely relying on gain cannot penalize the LM agent wandering indefinitely in the red dotted region.
Case
Condition
Target set T(t)
Required action
1
P(t)=∅
U(t)
Exploration
2
g∈P(t)
{l(g)}
Exploitation
3
P(t)=∅,g∈/P(t),U(t)=∅
{l(u):u∈P(t)}
Exploitation
4
P(t)=∅,g∈/P(t),U(t)=∅
U(t)∪{l(u):u∈P(t)}
Either
Table 1: Four cases determining the type of required action at timestep t .
Figure 4: Different exploration behavior between Claude Opus 4.6 and Gemini 3.1 Pro, both of which show success rate of 100%. In Figure 4(a) , until 50% of episode progress, two models show similar behaviors. Afterwards, however, Gemini 3.1 Pro performs more exploration than Claude Opus 4.6. Figure 4(b) illustrates this observation where Claude Opus 4.6 avoids stepping into unobserved cells despite the two paths incurring the same cost.
Figure 5: Effect of prompts on exploration and exploitation error, and success rate for GPT-4.1. The highlighted bar in each panel indicates lowest error or highest success rate. The exploration-focused prompt achieves the lowest exploration error and the highest overall success rate, while the exploitation-focused prompt achieves the lowest exploitation error.
Model
Method
Success (%) ↑
Exploration Error ↓
Exploitation Error ↓
Steps ↓
Gemini 3.1 Flash Lite
Baseline
51.9
0.172
0.135
94.3
+ Harness Engineering
88.9
0.030
0.071
68.0
GPT-4.1
Baseline
63.0
0.297
0.160
92.5
+ Harness Engineering
92.6
0.053
0.044
66.1
Table 2: Effect of harness engineering on success rates, exploration and exploitation errors, and the number of steps (of successful trajectories). All metrics are significantly improved for both Gemini 3.1 Flash Lite and GPT-4.1.
Model
Semantic
Success (%) ↑
Exploration Error ↓
Exploitation Error ↓
Steps ↓
Gemini 3.1 Flash Lite
✗
25.0
0.181
0.091
143.0
✓
25.0
0.241
0.015
131.5
GPT-4.1
✗
15.0
0.284
0.017
142.3
✓
45.0
0.177
0.029
131.2
Table 3: Effect of semantic information on success rates, exploration and exploitation errors, and the number steps on Gemini 3.1 Flash Lite and GPT-4.1. The number of steps reduces when semantic information is injected to our problems.
Appendix figures & tables21 assets
Supplementary material from the paper’s appendix.
Appendix
t
p(t)
ct
et
nt
St
0
(−1,0)
0
0
0
0
1
(0,0)
0
0
0
0
2
(1,0)
0
0
0
0
3
(0,0)
0
0
0
0
4
(−1,0)
0
0
0
0
Appendix
Table 4: Probe a branch and back out once.
t
p(t)
ct
et
nt
St
0
(−1,0)
0
0
0
0
1
(0,0)
0
0
0
0
2
(1,0)
0
0
0
0
3
(0,0)
0
0
0
0
4
(0,1)
0
0
0
0
Appendix
Table 5: Useful gateway revisit.
t
p(t)
ct
et
nt
St
0
(−1,0)
0
0
0
0
1
(0,0)
0
0
0
0
2
(1,0)
0
0
0
0
3
(0,0)
0
0
0
0
4
(−1,0)
0
0
0
0
5
(0,0)
0
1
1
2
Appendix
Table 6: Re-enter the same exhausted branch.
t
p(t)
ct
et
nt
St
0
(−1,−1)
0
0
0
0
1
(0,−1)
0
0
0
0
2
(0,0)
0
0
0
0
3
(−1,0)
0
0
0
0
4
(−1,−1)
1
0
0
1
5
(0,−1)
1
0
0
1
Appendix
Table 7: Repeated use of the same cycle.
t
p(t)
ct
et
nt
St
0
(0,0)
0
0
0
0
1
(0,1)
0
0
0
0
2
(0,0)
0
0
0
0
3
(0,−1)
0
0
0
0
4
(0,0)
0
0
1
1
5
(0,1)
0
1
1
2
Appendix
Table 8: Corridor oscillation.
t
p(t)
ct
et
nt
St
0
(−1,0)
0
0
0
0
1
(0,0)
0
0
0
0
2
(1,0)
0
0
0
0
3
(1,1)
0
0
0
0
4
(1,0)
0
0
0
0
5
(0,0)
0
0
0
0
Appendix
Table 9: Comb / broom graph.
Figure 6: Harness Design Comparison. (a) In the baseline, the agent harness passes observations directly to the LLM and returns actions as in Yao et al. (2023) . (b) With harness engineering, each observation is also routed through a rule-based memory manager that produces a structured summary (visited cells, frontier, activated and activatable states, …) which is injected into the LLM prompt. The information content is identical but the relevant information is highlighted explicitly through harness engineering.
Figure 7: An oracle view of the 2D grid map and the corresponding task DAG for experiments with semantic information injection. This example illustrates cooking tomato pasta with cheese. First, tomato pasta is made from pasta and tomato sauce. Second, tomato pasta with cheese is made by adding cheese to the tomato pasta. In this case, the LM agent may overly rely on semantic priors. For example, it might erroneously assume that the pasta sauce and cheese must be placed in proximity.
Figure 8: Results of action trajecotries and metric values over each timestep for Claude Haiku 4.5.
Figure 9: Results of action trajecotries and metric values over iterations using Claude Haiku 4.5.
Figure 10: Results of action trajecotries and metric values over iterations using Claude Haiku 4.5.
Figure 11: Results of action trajecotries and metric values over each timestep for Gemini 3.1 Flash Lite.
Figure 12: Results of action trajecotries and metric values over each timestep for Gemini 3.1 Flash Lite.
Figure 13: Results of action trajecotries and metric values over each timestep for Gemini 3.1 Flash Lite.
Figure 14: Results of action trajecotries and metric values over each timestep for GPT-4.1.
Figure 15: Results of action trajecotries and metric values over each timestep for GPT-4.1.
Figure 16: Results of action trajecotries and metric values over each timestep for GPT-4.1.
Figure 17: Results of action trajecotries and metric values over each timestep for Claude Opus 4.6.
Figure 18: Results of action trajecotries and metric values over iterations using Claude Opus 4.6.
Figure 19: Results of action trajecotries and metric values over iterations using Claude Opus 4.6.
Figure 20: Error analysis of GPT-4.1 with varying exploration demand by varying the map design and sizes of the task DAGs while fixing the map size to the full 8 × 8 grid. Each graph consists of 96 runs on 32 different maps with 3 random seeds.
Large language model based agents often fail in unfamiliar environments due to premature exploitation: a tendency to act on prior knowledge before acquiring sufficient environment-specific information. We identify autonomous exploration as a critical yet underexplored capability for building adaptive agents. To formalize and quantify this capability, we introduce Exploration Checkpoint Coverage, a verifiable metric that measures how broadly an agent discovers key states, objects, and affordances. Our systematic evaluation reveals that agents trained with standard task-oriented reinforcement learning consistently exhibit narrow and repetitive behaviors that impede downstream performance. To address this limitation, we develop a training strategy that interleaves task-execution rollouts and exploration rollouts, with each type of rollout optimized by its corresponding verifiable reward. Building on this training strategy, we propose the Explore-then-Act paradigm, which decouples information-gathering from task execution: agents first utilize an interaction budget to acquire grounded environmental knowledge, then leverage it for task resolution. Our results demonstrate that learning to systematically explore is imperative for building generalizable and real-world-ready agents.
Ziang Ye, Wentao Shi, Yuxin Liu +6
University of Science and Technology of China · Meituan
Recent advancements in agentic test-time scaling allow models to gather environmental feedback before committing to final actions. A key limitation of existing methods is that they typically employ undifferentiated exploration strategies, lacking the ability to adaptively distinguish when exploration is truly required. In this paper, we propose an exploration-aware reinforcement learning framework that enables LLM agents to adaptively explore only when uncertainty is high. Our method introduces a fine-grained reward function via variational inference that explicitly evaluates exploratory actions by estimating their potential to improve future decision-making, together with an exploration-aware grouping mechanism that separates exploratory actions from task-completion actions during optimization. By targeting informational gaps, this design allows agents to explore selectively and transition to execution as soon as the task context is clear. Empirically, we demonstrate that our approach achieves consistent improvements across a range of challenging text-based and GUI-based agent benchmarks. Code is available at https://github.com/HansenHua/EAPO-ICML26 and models are available at https://huggingface.co/hansenhua/EAPO-ICML26.
Xingyuan Hua, Sheng Yue, Ju Ren
Department of Computer Science and Technology, Tsinghua University, Beijing, China · State Key Laboratory of Internet Architecture, Tsinghua University, Beijing, China · School of Cyber Science and Technology, Sun Yat-sen University Shenzhen Campus, Shenzhen, China
Large Language Models (LLMs) as agents often fail to improve in new environments. We identify and characterize a failure mode we call exploration collapse: under reinforcement learning (RL) in environments whose states are unfamiliar to the policy, Pass@k, the probability that at least one of k sampled trajectories succeeds, drops markedly over training even as Pass@1 edges up, revealing increasingly brittle exploration; environments closer to the pretraining distribution show no such decline. We trace this collapse to weak grounding in environment states and dynamics, and study a simple remedy: explicitly teaching the agent to estimate the current state and predict its transitions before optimizing for reward. We instantiate it as SPA, an explore-then-exploit recipe that cold-starts the policy with a Self-Experience supervised finetuning (SFT) stage, collecting the model's own interaction trajectories and supervising state and next-state prediction, and then runs standard RL. The resulting world model serves as a grounded initialization for RL rather than an inference-time planner. Across unseen environments, SPA consistently and substantially improves over vanilla RL: for example, it raises the Sokoban success rate from 25.6% to 59.8% on Qwen2.5-1.5B-Instruct, letting sub-3B models surpass a 20B baseline on these tasks. Controlled studies indicate that the gains track four factors: grounded state representations, explicit transition modeling, self-experience trajectories from a sufficiently strong exploration policy, and adequate coverage of transition data.
Shiqi Chen, Tongyao Zhu, Zian Wang +8
City University of Hong Kong · National University of Singapore · The Hong Kong Polytechnic University +5