{"id":"0ca2c43d-8979-4eff-8cee-dbb5f8422fd6","arxiv_id":"2501.08925","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Exploration by LLM agents can be measured separately from exploitation using an optimal exploitation oracle, and most models explore poorly, with exploration performance correlated to reasoning ability.","lead":"This paper introduces a way to measure how well large language models explore unfamiliar environments, separate from how well they exploit what they have found. It tests popular open and closed models and finds most explore poorly, with stronger reasoning models generally exploring more thoroughly.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Oracle optimality is unvalidated and the §3.2 definition conflicts with the §3.3 implementation; the exploration gap may include exploitation suboptimality.","rationale":"The framework is clever and the empirical findings are plausible, but the central metric is a difference between two quantities, and the subtrahend (R^σ) is asserted rather than verified. The internal inconsistency between the 'locally reward-maximizing' definition in §3.2 and the global orienteering statement in §3.3 is not cosmetic: the two definitions yield different returns whenever the optimal path to a high-reward ball passes a lower-reward ball, which is exactly the situation these environments are designed to create. The paper's own text acknowledges that 'finding the optimal exploitation is intractable in many environments' (§3.2), yet no argument is given that the implemented oracle is exact for these specific small grids and mazes. If the oracle is approximate, all reported exploration gaps contain an unknown exploitation suboptimality component, so the headline conclusion ('most models struggle to explore') and the MMLU-Pro correlation could be artifacts. The proposed test settles the issue directly by checking whether a fully informed memory yields a zero exploration gap. If the oracle passes on all tested layouts, the framework is sound; if not, the decomposition needs an additional correction term for oracle suboptimality. This is exactly the kind of condition a conditional acceptance should require, so the reader's verdict stands.","tokens_in":13888,"tokens_out":6855,"duration_ms":68068,"concrete_test":"Take one small Treasure Rooms map (e.g., the 4×4) and one maze layout. Construct a fully explored memory: all cells visited and all ball rewards observed. Run the implemented oracle (Appendix A.6) on this memory and compare its return to the true R* obtained by exhaustive search over all valid action sequences or dynamic programming over the deterministic MDP. If R^σ < R*, then Δ_explore > 0 even with complete exploration, directly falsifying the claim that the gap measures only missing exploration. Also run a leakage check: remove the observation of a specific high-reward ball from the memory and verify the oracle's plan never enters that ball's cell; if it does, the oracle uses privileged information.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Δ_explore = R* − R^σ isolates exploration, i.e., the only cause of a nonzero gap is missing information. This requires σ to be exactly optimal given the agent's memory. Section 3.2 defines σ as 'optimally select[ing] the locally reward-maximizing action ... at every time step,' corresponding to a greedy policy, while Section 3.3 states the oracle is implemented by 'search[ing] for the path between balls with the highest reward' (orienteering). A local greedy policy and a global orienteering oracle are not the same: on a grid or maze, optimal routes often pass low-reward balls to reach high-reward balls, and greedy lookahead can fail. If the implemented oracle is greedy or approximate, then even with complete state coverage R^σ < R*, so Δ_explore > 0 despite full exploration, breaking the disentanglement. No proof of optimality, complexity bound, or validation appears in the main text; details are deferred to a self-cited appendix, and the LLM ablation in §A.7 tests a substitute, not the oracle's correctness. All model comparisons in Tables 1–2 and Figure 5 therefore depend on this unvalidated oracle.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an evaluation framework for disentangling exploration from exploitation in LLM-based agents operating in deterministic, partially observable environments. The central idea is to define an optimal exploitation oracle σ_exploit that, given the agent's accumulated memory, computes the best possible return from the information gathered. The exploration gap Δ_explore is then defined as R* − R^σ, where R* is the maximal achievable return, and the exploitation gap as R^σ − R_agent, so that cumulative regret decomposes exactly as Δ_explore + Δ_exploit. The authors apply this decomposition to Treasure Rooms and Maze environments, compare eleven LLMs plus a random baseline, report that most models leave large exploration gaps, and correlate exploration performance with MMLU-Pro scores. They also use the decomposition to analyze how different prompting instructions change exploration versus exploitation behavior. The manuscript is an arXiv preprint that defers several details, including the oracle implementation and an ablation, to a self-cited 'full version' reference.","tokens_in":14170,"tokens_out":3019,"duration_ms":34891,"significance":"If the optimal exploitation oracle is valid, the proposed decomposition is a conceptually clean and useful diagnostic tool: it gives a scalar measure of exploration progress that is not confounded by the agent's ability to exploit known information, and the empirical study provides one of the first systematic LLM evaluations with exploration isolated from exploitation. The paper honestly acknowledges that the oracle is a strong assumption, and it includes a useful set of controlled environments, a broad model comparison, and a prompt-engineering case study. The main contribution is therefore a measurement methodology rather than a new learning algorithm, and its value depends entirely on whether the oracle can be computed exactly and without using information the agent has not actually gathered.","major_comments":[{"comment":"The definition of the oracle is internally inconsistent. Section 3.2 defines σ_exploit as 'optimally select[ing] the locally reward-maximizing action at every time step,' which describes a greedy policy, whereas Section 3.3 states the oracle is implemented by 'search[ing] for the path between balls with the highest reward,' which is a global orienteering problem. A local greedy policy and a globally optimal route are not the same: in the maze and Treasure Rooms environments, an optimal path may pass through low-reward balls to reach a high-reward ball, and greedy per-step maximization can fail. This distinction is load-bearing because Δ_explore = R* − R^σ isolates exploration only if σ is exactly optimal given the agent's memory. If the implemented oracle is greedy or approximate, then R^σ < R* even with complete state coverage, and the exploration gap is contaminated by exploitation suboptimality. The main text must specify the exact optimization problem solved, prove or empirically validate that the implementation attains the optimum, and demonstrate that the oracle uses only the agent's observed memory rather than the unvisited reward layout.","section":"Section 3.2 and Section 3.3"},{"comment":"The central implementation is not actually contained in the manuscript. The text says 'See more details in Appendix A.6 [15]' and reference [15] is the authors' own arXiv full version of this same paper, so the main text is not self-contained. There is no pseudocode, no correctness statement, no complexity bound, and no validation of the oracle in the main text. The ablation in Appendix A.7 tests whether an LLM can serve as a replacement for the oracle, but it does not test whether the actual oracle is exact. Since Tables 1-2 and Figure 5 are all computed through this oracle, the main empirical claims rest on an unverified component that the reader cannot inspect in the submitted manuscript. The authors should provide the oracle algorithm and a validation study (for example, comparison against brute-force optimal solutions on small instances) directly in the main text or in an accessible appendix.","section":"Appendix A.6 / reference [15]"},{"comment":"The paper admits that the optimal exploitation assumption is 'strong' and that 'approximators are an option, but should be consistent; otherwise, they might introduce ambiguity.' This is an explicit acknowledgement that the framework's accuracy depends on oracle correctness, but no sensitivity analysis is provided. A concrete test would be to compute R^σ with an exact solver on the smallest environments and compare it against the oracle used for the reported results, or to perturb the oracle's optimality and show that model rankings are stable. Without such a test, the reader cannot know whether the reported differences between models (for example, o1-mini versus Gemini 1.5 Pro in Table 1) are due to exploration ability or to differential sensitivity to a suboptimal oracle.","section":"Section 3.2, 'On the complexity of defining an optimal exploitation'"}],"minor_comments":[{"comment":"In the Claude 3.5 Sonnet row, the Regret value for the 'Last Episode' column is printed as '41%' while all other Regret entries are decimals; this should be '0.41' for consistency.","section":"Table 1"},{"comment":"The sentence 'The optimal exploitation oracle is fastest by solving an instance of the orienteering optimization problem' appears to contain a typo; it should likely read 'is implemented by solving' or 'is obtained by solving.'","section":"Section 3.3"},{"comment":"The vertical axis label 'Optimal Return − Δ explore' is confusing because the text says the figure regresses exploration gaps against MMLU-Pro; please clarify what is plotted (for example, 'R* − Δ_explore' or 'normalized exploration gap').","section":"Figure 4"},{"comment":"The definition of sample efficiency as 'converge to the 90% equilibrium of the maximum achieved exploitation return' is vague; please define 'equilibrium' precisely and state how the 90% threshold is computed over episodes.","section":"Section 4.2"},{"comment":"The paper cites its own full version as reference [15] with the same arXiv identifier as the manuscript itself; this self-reference is unusual and should be explained or the relevant content should be included in the submission.","section":"Reference [15]"}],"recommendation":"major_revision","confidential_remarks":"The central methodological contribution is potentially useful, but the manuscript currently defers the load-bearing oracle implementation to a self-citation and contains two incompatible descriptions of the oracle. This is fixable in revision, but not by local edits alone: the authors need to supply the oracle algorithm, prove or verify its optimality, and add a sensitivity analysis. I would also flag to the editor that reference [15] pointing to the same arXiv ID as the submitted manuscript is an unusual self-citation practice; while not necessarily improper, it makes the submission non-self-contained and should be resolved before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the regret decomposition here is a genuinely useful measurement tool for the LLM-agent crowd, and the first broad multi-model comparison under that protocol is a solid contribution. But the load-bearing oracle is under-validated and described two incompatible ways in the main text; that needs to be fixed before the numbers in Tables 1 and 2 can be trusted.\n\nWhat's new and good. The decomposition Regret = Δ_explore + Δ_exploit is a definition, not a theorem, but operationalizing it with a deterministic environment and an optimal exploitation oracle is a good move. The environments (Treasure Rooms, mazes) are small but well-chosen; the dense-reward, symbolic-action design makes exploration complexity non-trivial without dragging in low-level motor noise. The coverage, redundancy, and sample-efficiency statistics are sensible complements. The MMLU-Pro correlation is suggestive: a strong, statistically significant slope across 11 models, with the explicit caveat that it's not causal. The prompt-engineering comparison in Figure 5 shows the tool can distinguish instruction effects that agent return alone can't. That's a real, field-usable contribution.\n\nSoft spots. The paper's central claim rests on the oracle being exactly optimal with respect to the agent's memory. Section 3.2 defines it as 'locally reward-maximizing action at every time step,' which reads as greedy. Section 3.3 says it's implemented by solving an orienteering problem, which is global. Greedy and global optimality are not the same. If the implemented oracle is greedy, the exploration gap includes exploitation suboptimality even with full coverage, breaking the disentanglement. If it's global, the writeup is sloppy and should say so. The paper acknowledges the 'strong assumption' but defers all implementation details to a self-cited full version (ref [15]) and provides no proof of optimality or validation experiment in the main text. The LLM ablation in A.7 tests a substitute for the oracle, not the oracle's correctness. That's a genuine hole, though a fixable one: give the exact dynamic program for the orienteering instance, show it returns optimal paths for the small maps, and publish the code. The criticism is not that the decomposition is circular—it isn't—but that the instrument used to compute one side of it is unverified. Also, no code or data is released; for a measurement paper that's a real barrier.\n\nWho benefits. Anyone evaluating LLM agents on exploration-heavy tasks. It deserves a serious referee and probably major revision, not rejection. The framework is sound in principle; the missing validation is the kind of thing a careful revision can supply.","headline":"A clean, useful regret decomposition for isolating LLM exploration, but the oracle it rests on is under-validated and its description is internally inconsistent.","tokens_in":14625,"tokens_out":3158,"would_cite":true,"duration_ms":33194,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that comparing an LLM agent's return with the return of an optimal exploitation oracle isolates how much of its shortfall comes from missing exploration rather than weak exploitation.","keywords":["exploration","exploitation","regret decomposition","large language models","in-context reinforcement learning","optimal exploitation oracle","LLM agents","state space coverage"],"falsifier":"Find any environment instance where the oracle's optimal exploitation path, computed from the agent's memory, is beaten by a different path using the same memory: that would show the oracle is not exact, and the decomposition would misattribute exploitation error to exploration. Concretely, enumerate all reachable paths from the agent's observations in a small maze and compare the oracle's return to the true maximum; a single mismatch invalidates the decomposition's interpretation.","tokens_in":1448,"feed_emoji":"🧭","tokens_out":1883,"duration_ms":57295,"temperature":0.7,"pith_summary":"The paper tries to establish that exploration by LLM agents can be evaluated on its own, without being tangled up with exploitation. It proposes decomposing an agent's cumulative regret into an exploration gap and an exploitation gap using the return of an optimal exploitation oracle that acts only on the agent's memory. In deterministic grid and maze environments, the exploration gap is zero exactly when the agent has gathered the information needed for maximal return, so any remaining gap is attributed purely to missing exploration. Experiments with several open and closed LLMs show that most models explore worse than a random policy and that exploration gaps shrink as general reasoning ability, measured by MMLU-Pro score, rises. The authors argue this decomposition is needed because agent returns and LLM-based exploitation estimates do not reliably reflect exploration progress.","feed_headline":"Regret split isolates how well LLM agents explore","feed_subtitle":"Scoring agents against an optimal exploitation oracle separates missing information from weak exploitation, and most LLMs fall short.","key_machinery":"The central object is the optimal exploitation oracle $\\sigma_{\\text{exploit}}$, a predefined policy that, given the agent's history, selects the locally reward-maximizing action at every step and is used as a diagnostic tool rather than as a trainable policy. In the authors' environments the oracle is implemented by solving an orienteering problem over the reward locations the agent has seen. The identity that carries the argument is the regret decomposition $\\text{Regret} = \\Delta_{\\text{explore}} + \\Delta_{\\text{exploit}}$, which turns the exploration gap into a direct measure of missing information about the environment.","core_discovery":"The central claim is that the optimal exploitation return provides an accurate disentanglement: by calculating how much an optimal exploiter could earn from the agent's memory, one can measure exploration without conflating it with exploitation. Formally, letting $R^*$ be the maximal achievable return, $R^{\\sigma_{\\text{exploit}}}$ be the return of the optimal exploitation oracle, and $R$ be the agent's return, the regret decomposes as $R^* - R = (R^* - R^{\\sigma_{\\text{exploit}}}) + (R^{\\sigma_{\\text{exploit}}} - R)$, where the first parenthesized term is the exploration gap and the second is the exploitation gap. Because the oracle uses only gathered information, a positive exploration gap indicates that the agent did not explore enough, and a gap of zero proves that its information suffices for optimal return. The paper then applies this metric to LLM agents in symbolic Treasure Rooms and maze environments and finds that most models fail to reach full coverage or near-zero exploration gaps.","pith_inferences":["The exactness of the decomposition hangs on the oracle being truly optimal with only the agent's observations; if the implemented orienteering solver is approximate, the reported exploration gaps would be overestimates and the exploitation gaps underestimates.","The MMLU-Pro correlation suggests exploration is mediated by general planning and reasoning ability, but the paper does not establish a causal direction; controlled manipulation of reasoning traces could test this.","The same decomposition could be extended to stochastic environments by replacing the deterministic maximal return with an expected optimal return, though the identity would then require probability-aware treatment.","The metric offers a direct testbed for memory design, such as comparing reflection-based or compressed histories, to see whether reducing memory redundancy improves the exploration gap."],"forward_implications":["Agent return alone cannot rank exploration: models with similar returns can have significantly different exploration gaps, and lower-return agents can be exploring more effectively.","Model comparisons should be based on optimal exploitation return rather than raw return or LLM-based exploitation estimates, because those measures conflate the two skills.","Weak LLMs are not sufficient for exploration; stronger reasoning models explore better, so exploration-heavy agent design should allocate the task to stronger models.","Prompt engineering effects on exploration can be measured directly, as task-oriented, undirected, and exploitation-prompts change the balance between the exploration and exploitation gaps.","Exploration performance degrades in longer-horizon environments, so long-horizon planning is a key bottleneck for LLM exploration."],"supporting_citations":[{"why":"Supplies the earlier claim that weak exploration models can support strong exploitation, which the paper's contrary finding about weak LLMs is framed against.","marker":"[21]"},{"why":"Provides the prior study of LLMs balancing exploration and exploitation in bandit settings and the trade-off findings the paper aligns with.","marker":"[27]"},{"why":"Contributes prior evidence that finetuning on exploration trajectories can improve exploration, motivating the paper's exploration-training discussion.","marker":"[37]"},{"why":"Provides the First-Explore, then Exploit approach and the Dark Treasure Room environment that the paper adapts for its experiments.","marker":"[38]"},{"why":"Documents aimless and redundant LLM behavior in game environments, supporting the paper's interpretation of redundant state revisits.","marker":"[40]"},{"why":"Supplies the MMLU-Pro benchmark used to correlate general reasoning and language understanding with exploration capability.","marker":"[55]"},{"why":"Provides the symbolic action-space environment design, similar to TextWorld, that the paper uses to reduce low-level spatial navigation demands.","marker":"[12]"}],"fun_headline_variants":["Optimal-exploitation oracle exposes LLM exploration gaps","Most LLM agents can't explore: regret split proves it","How to measure exploration: oracle separates info from action","LLM exploration deficit: optimal exploitation oracle reveals it","Exploration not exploitation: why LLM agents fall short"],"cache_read_input_tokens":16896,"weakest_assumption_plain":"The framework assumes the optimal exploitation oracle is truly optimal and uses only the information the agent actually gathered, so the exploration gap is exactly the return lost to missing information; if the oracle is approximate or leaks knowledge of unvisited rewards, the gap is biased.","fun_headline_variants_meta":{"raw":{"variants":["Optimal-exploitation oracle exposes LLM exploration gaps","Most LLM agents can't explore: regret split proves it","How to measure exploration: oracle separates info from action","LLM exploration deficit: optimal exploitation oracle reveals it","Exploration not exploitation: why LLM agents fall short"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000581,"raw_usage":{"total_tokens":2698,"prompt_tokens":872,"completion_tokens":1826,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":488,"completion_tokens_details":{"reasoning_tokens":1747}},"tokens_in":488,"tokens_out":1826,"duration_ms":11447,"temperature":1.0,"reasoning_tokens":1747,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:14:18.144432+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find any environment instance where the oracle's optimal exploitation path, computed from the agent's memory, is beaten by a different path using the same memory: that would show the oracle is not exact, and the decomposition would misattribute exploitation error to exploration. Concretely, enumerate all reachable paths from the agent's observations in a small maze and compare the oracle's return to the true maximum; a single mismatch invalidates the decomposition's interpretation.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the MMLU-Pro benchmark used to correlate general reasoning and language understanding with exploration capability."}],"review_version":1}