Clearing the Fog: Towards Installing and Refining Proactive Exploration Capabilities in LLM Agents

Motivation

• Proactive exploration expands an agent’s trajectory beyond immediate local optima to acquire information for decisions that cannot be made from current observations alone.The shopping example illustrates strategic backtracking and pagination to find a better-priced product rather than settling for a satisfactory item.Source: §1 · p. 1, Figure 1 · p. 1

Bottlenecks

• Standard SFT-RL agents suffer from SFT data’s hindsight bias and RL exploration collapse, leading to premature choices and weak long-horizon strategies.Expert trajectories omit exploratory steps, while SFT-initialized agents rarely sample exploratory behaviors during RL rollouts, leaving their long-term benefits undiscovered and unrewarded.Source: §1 · pp. 1–2

SAFARI

• SAFARI uses exploration-rich SFT data and contrastive RL guidance to address the two bottlenecks and refine agents’ decision-making.Exploratory Data Construction distills diverse paths from a powerful LLM using tree-structured context modeling and screening; RL compares candidate and reference actions at identical states using Monte Carlo estimates of future returns.Source: §1 · p. 2

Results

• ∼10%-15% average task-success gains and ∼8%-18% exploration-efficiency gains over competitive baselines are reported for SAFARI across diverse benchmarks.The analysis attributes performance gains to gathering task-relevant information while avoiding redundant interactions; exploration benefits grow with task difficulty, with the largest gains on tasks requiring substantial information gathering.Source: §1 · p. 2

2 Related Work

• Prompt-based planning and imitation learning kept early agents near observed state–action distributions, while later exploration-driven RL and self-improvement faced hindsight bias and exploration collapse.These limitations often yield insufficient proactive exploration and suboptimal solutions.Source: §2 · p. 2
• Failure-triggered corrective trajectories and MCTS-based self-improvement address errors only after failure, discouraging exploration beyond reward-sufficient trajectories and risking local optima.The cited approaches include corrective trajectories (Wang et al., 2025; Chen et al., 2025) and MCTS-based self-improvement (Yuan et al., 2025).Source: §2 · p. 2
• Tree-based reasoning, interaction graphs, and webpage hierarchies support state visibility, search, and navigation, but remain external tools designed for web environments rather than broad policy-level mechanisms.This limits their applicability to domains such as database manipulation and scientific environments.Source: §2 · p. 2

3.1 Evaluation Setup

• The WebShop setup separates task-oriented Search, Open, Select, and Buy from exploratory Next, Back, and Home, and compares SFT-Only, SFT-RL (ETO/IPR), and correction-based STeCa.All baselines use Meta-Llama-3.1-8B-Instruct; WebShop is selected to isolate exploratory behavior from terminal task execution.Source: §3.1 · pp. 2–3

3.2 Main Findings

• Expert trajectories devote just 0.10% of actions to exploration, SFT-Only remains near-zero, and SFT-RL or correction yields no qualitative shift, only ∼20% item-selection gains within current observations.The action-distribution analysis finds that existing methods refine item selection without developing exploratory behavior.Source: Table 1 · p. 3, §3.2 · p. 3
• Hindsight-biased SFT strips exploratory steps, while their rarity in RL rollouts prevents discovery of long-term rewards and contributes to degradation on complex tasks.The authors argue for exploration-rich SFT data and RL mechanisms that shift behavior from reactive execution to proactive exploration.Source: §3.2 · p. 3

4 SAFARI: The Method

• SAFARI pairs exploration-rich data construction with contrastive RL to calibrate the agent’s choice between information gathering and direct execution.The method treats task success as the reward for a completed interaction trajectory.Source: §4 · p. 3

4.1 Exploratory Data Construction

• Exploratory Data Construction elicits diverse paths from an LLM expert and filters them into high-quality, exploration-oriented trajectories for student initialization.Source: §4.1 · p. 3

4.1.1 Data Distillation

• Tree-structured context lets the teacher branch, backtrack, and annotate interaction histories, distilling trial-and-error reasoning rather than only successful paths.Cognitive notes record feedback and insights; backtracking can preserve a viable partial-reward path when the step limit approaches.Source: §4.1.1 · pp. 4–5

4.1.2 Data Screening

• For each task, SAFARI selects the best of m sampled trajectories using a length-penalized reward, then retains only successful trajectories in Dbase for SFT.The length penalty discourages redundant wandering while preserving meaningful exploration; SFT is intentionally brief to limit overfitting and preserve foundational capabilities.Source: §4.1.2 · p. 5

4.2 RL with Contrastive Signal Guidance

• Contrastive Signal Guidance compares student and reference actions from shared contexts, estimates their future returns with forward-only MC rollouts, and applies DPO to favor higher-reward choices.An SFT regularization term mitigates catastrophic forgetting, and pairs are retained only when their reward gap exceeds a margin threshold.Source: §4.2 · pp. 5–6

5.1 Experimental Settings

• Experiments use two 7B–8B instruction backbones across WebShop, InterCode-SQL, and ScienceWorld, measuring final-reward task performance and five-rollout maximum-reward exploration score.The backbones are Meta-Llama-3.1-8B-Instruct and Mistral-7B-Instruct-v0.3; GPT-4o serves as the data-distillation teacher.Source: §5.1 · p. 6

5.2 Main Results

• SAFARI gains approximately 10%–15% in task success and 8%–18% in exploration score over the best baselines, while its 8B model is comparable to or better than enhanced GPT-4o.Tree-structured context modeling also improves GPT-4o, supporting the value of structured history for resolving uncertainty and systematic exploration.Source: §5.2 · p. 6, Table 2 · p. 7

5.3.1 Exploration Efficiency

• SAFARI’s efficiency metric is effective exploration minus wasted exploration; on WebShop, ETO and IPR show near-zero levels of both, while STeCa’s wasteful exploration overwhelms its effective exploration.Effective exploration is task reward multiplied by exploration extent; wasted exploration is one minus task reward, multiplied by exploration extent. Together, the results indicate that productive exploration depends on useful information gathering, not merely more exploratory actions.Source: §5.3.1 · p. 7
• RL1 sharply reduces wasted exploration and makes net efficiency positive; through RL2 and RL3, the effective-versus-wasted exploration gap widens.SFT first raises both effective and wasted exploration, while later RL calibration reduces waste and sustains gains in task-relevant information seeking.Source: Figure 3 · p. 6, §5.3.1 · p. 7

5.3.2 Exploration Scales with Task Difficulty

• On hard WebShop tasks, SAFARI raises average reward from 0.23 to 0.45 alongside effective exploration of 0.11; on easy tasks, reward falls from 1.00 to 0.89.As difficulty increases from Easy to Hard, exploration extent rises from 0.16 to 0.20 to 0.35, and trajectory length from 4.95 to 5.41 to 6.20; easy-task exploration has effective exploration 0.12 and wasted exploration 0.04.Source: §5.3.2 · p. 8

5.3.3 Ablation Studies

• Structured histories yield larger gains than explicit exploration prompting: list histories add +12.24% TP and +13.28% ES, while tree histories add +16.63% TP and +12.83% ES.Explicit prompting adds +3.14% TP and +7.53% ES; cognitive notes add +5.03% TP and +2.23% ES. Tree-structured prompts with data screening improve downstream SFT by +9.66% TP and +5.61% ES, and RL gains depend on prior SFT initialization.Source: Table 4 · p. 8, §5.3.3 · p. 8

• Proactive exploration lets agents acquire information at short-term cost when it can improve future decision-making.It requires reasoning about whether current knowledge is sufficient for reliable planning.Source: §6 · p. 8
• Effective agents must reason about whether their current knowledge supports reliable planning, not only which action to take.Source: §6 · p. 8
• Proactive exploration is a foundational capability for next-generation agents in complex open-world environments.Optimal actions in these environments may depend on actively expanding and refining environmental understanding.Source: §6 · p. 9

Heuristic Exploration Metrics

• Eff(τ) is only a proxy for exploration utility: terminal-reward anchoring can inflate successful-trajectory scores even when exploration did not cause success.More rigorous metrics that isolate exploration’s causal impact remain future work.Source: Limitations · p. 10
• Eff(τ) nevertheless exhibits a meaningful macroscopic correlation with exploration behavior.Source: Limitations · p. 10

SFT Dependency

• SAFARI currently depends on SFT using exploration-aware trajectories distilled from a powerful LLM; removing SFT leads to severe hindsight bias, and teacher knowledge may bound behavior.Source: Limitations · p. 10
• Existing agents still cannot efficiently acquire environmental knowledge entirely from scratch; fully autonomous proactive exploration from scratch remains future work.Source: Limitations · p. 10

LLM Usage

• LLMs serve as backbone models and teacher models for trajectory-data construction, and are used only for language polishing during paper writing.Source: LLM Usage · p. 10

A Details of the Interactive Tree-Structured History with Cognitive Notes

• The appendix covers the Tree-Structured History’s formalization, algorithmic conversion, operational mechanisms, and environment-specific implementations.Source: A Details of the Interactive… · p. 11

A.1 Formalization and Algorithmic Conversion

• A conventional multi-turn trajectory is a flat chronological sequence of instruction and action-observation pairs, conflating productive forward execution with exploratory detours.Source: §A.1 · p. 11
• After a failed attempt, a flat history leaves the abandoned branch in sequence and can mislead the agent into treating a discarded state as active context.Source: §A.1 · p. 12
• The method converts trajectories into a topological action tree, with nodes carrying unique identifiers, actions, parent links to branch origins, and child-branch tracking IDs.Source: §A.1 · p. 12
• Agent-managed notes can mark milestones, errors, exhausted paths, or imperfect backups, while plain text records valuable state information or serves as a self-reminder.Source: §A.1 · p. 12
• A global active-position pointer tracks the agent’s current state outside the nodes, and Algorithm 1 formalizes the sequence-to-tree conversion pipeline.Source: §A.1 · p. 12

A.2 Dual Relocation Mechanisms Across Different Target Domains

• In WebShop, physical backtracking synchronizes tree relocation with environmental state changes and isolates unproductive paths in parallel branches.This approach applies where the environment provides an explicit backward action, such as a <Back> button.Source: §A.2 · p. 12
• In InterCode-SQL and ScienceWorld, direct pointer modification supports target-node relocation or assigning a historical node as the next action’s parent.Relocation resumes from a past checkpoint without creating a node; parent assignment creates a new parallel branch.Source: §A.2 · p. 12

A.3 Operational Roles of Cognitive Notes with Concrete Case Study

• Cognitive notes cache verified environmental facts, preserving a snapshot of kitchen appliances after the agent leaves and avoiding repeated look-around actions.In the “freeze orange juice” task, node 2 retains information about the freezer and fridge.Source: §A.3 · p. 13
• A [DEAD END] note marks the workshop branch as unpromising and signals the policy to stop forward execution there.The agent adds the tag after finding no juicing utilities in the workshop.Source: §A.3 · p. 13
• A RULE LEARNED note records that picking requires an index, helping prevent repeated syntactical or mechanical errors.The agent records the rule after the environment rejects a vague picking action.Source: §A.3 · p. 13
• After the workshop hypothesis fails, the agent records why, revises its hypothesis toward pre-made juice, and relocates to the kitchen checkpoint to explore a new branch.Cached kitchen facts guide the agent toward the fridge or freezer, combining note-based reasoning with pointer recovery.Source: §A.3 · p. 13

Implementation Details

• Experiments were conducted on 3 NVIDIA A100 (80GB) GPUs, and the core prompt templates are provided in Appendix F.Source: B Hyperparameters and Implementation… · pp. 13–14

Data Synthesis via Teacher Model

• GPT-4o generated 5 candidate trajectories per task at T = 1.0 and top_p = 0.85, using γ = 0.1 for WebShop and InterCode-SQL and 0.01 for ScienceWorld.Source: B Hyperparameters and Implementation… · p. 14

Supervised Fine-Tuning (SFT) Phase

• The proactive agent received 1 SFT epoch at 3 × 10^-6 learning rate, while πMC received 3 epochs at 2 × 10^-5 on the Forward-Pure Set (Dscore).Source: B Hyperparameters and Implementation… · p. 14

Exploration Mechanics

• Active exploration used greedy decoding at T = 0, while step-wise reward estimation used stochastic MC rollouts at T = 1.0, with 5 rollouts per candidate action.Source: B Hyperparameters and Implementation… · p. 14

Contrastive Data Construction and Policy Optimization

• The contrastive margin threshold τm was 0.01 for WebShop and ScienceWorld and 0.1 for InterCode-SQL; policy updates used a 5×10^-7 learning rate, β = 0.1, and 3 epochs per iteration.Source: B Hyperparameters and Implementation… · p. 14

Global Pipeline Iterations

• The closed-loop pipeline ran for 3 global iterations on WebShop and InterCode-SQL, and 1 on ScienceWorld.Source: B Hyperparameters and Implementation… · p. 14

C Information-Theoretic Exploration Metrics

• Exposed entities measure information breadth, while focused entities capture information the agent explicitly inspects or manipulates.The metric combines these dimensions with task reward to quantify exploration’s net utility along a trajectory.Source: C Information-Theoretic Exploration… · p. 14
• Contextual extraction, canonicalization, and trajectory-level deduplication produce exposed and focused entity sets that are counted by task-specific category.The extraction functions and category mappings use manually customized, hard-coded rules and token-matching heuristics for each target environment.Source: C Information-Theoretic Exploration… · pp. 14–15
• Normalized gains measure surplus exploration beyond a fixed baseline pool of vanilla-SFT validation trajectories shared across evaluation methods.Categories absent from the pool receive a normalized gain of zero; negative gains are discarded, so sub-baseline exploration does not contribute.Source: C Information-Theoretic Exploration… · p. 15
• Category gains are aggregated, with mean used in the primary analysis, and an exponential saturation function limits score inflation from arbitrarily long trajectories.The fixed scaling hyperparameter is α = 1 across reported experiments.Source: C Information-Theoretic Exploration… · p. 15
• Reward coupling separates task-aligned Effective Exploration from unsuccessful Wasted Exploration, and Exploration Efficiency subtracts wasted overhead from productive gains.This distinguishes purposeful information gain from blind, ungrounded wandering.Source: C Information-Theoretic Exploration… · p. 15

D Case Study: Overcoming Hallucination via Proactive Exploration

• Qualitative case studies across distinct domains show SAFARI using tree-structured memory and cognitive notes to audit candidates, gather missing context, and address fatal decision hallucinations.Source: D Case Study: Overcoming Hallucination… · p. 16

D.1 Case 1: Webshop

• R = 1 for SAFARI, compared with R = 0.3333 for IPR/ETO and R = 0.0667 for STeCa, after SAFARI verified alternatives before purchase.SAFARI selected the chocolate flavor of B08FSC3XG3, while the baselines purchased products that mismatched the requested product type.Source: Table 5 · p. 16, §D.1 · p. 16
• IPR, ETO, and STeCa clicked the first lexically plausible product and purchased without comparative verification, terminating after three steps.IPR/ETO bought white-chocolate fruity cereal candy bars; STeCa bought Special K protein bars, which met the price constraint but not the requested product type.Source: §D.1 · p. 16
• SAFARI searched with the full constraints, inspected multiple candidate pages, and delayed purchase until the chocolate option was grounded in the environment.It rejected an assorted snack care pack and another closer candidate before selecting chocolate on B08FSC3XG3.Source: §D.1 · p. 16
• The case characterizes proactive exploration as targeted candidate auditing that compares alternatives and records product-level mismatches to reduce shopping errors.The passage contrasts this strategy with premature exploitation.Source: §D.1 · p. 16

D.2 Case 2: Intercode-Sql

• SAFARI retrieves the correct answer (R = 1), while baselines guessing “AFG” or “AF” fail (R = 0).The case study contrasts their trajectories on the question of how many official languages are spoken in Afghanistan.Source: Table 6 · p. 16, §D.2 · pp. 16–17
• By inspecting the country table schema, SAFARI acquires the Name-to-Code mapping and avoids a blind country-code assumption.Baselines inspect only the countrylanguage table, bypass semantic grounding, and hallucinate an unverified code.Source: §D.2 · pp. 16–17
• The case characterizes proactive exploration as purposeful alignment of internal beliefs with external reality, not random wandering.The passage says this strategy completely eradicates environmental hallucinations.Source: §D.2 · p. 17

E.1 Environment and Model Configurations

• WEBSHOP experiments use GPT-4o for teacher trajectory synthesis and Meta-Llama-3.1-8B-Instruct for student SFT and RL on the WEBSHOP benchmark.Source: §E.1 · p. 17

E.2 Teacher-Driven Trajectory Synthesis

• Teacher prompt variants compare direct instructions, exploration guidance, and chronological-list versus behavior-tree histories, each with or without notes.All variants use identical task-specific few-shot exemplars; exploration guidance adds hypothesis testing, proactive backtracking, and search tolerance.Source: §E.2 · p. 17

E.3 Student Downstream Policy Learning

• Student ablations remove exploration-rich SFT data, tree-structured memory, trajectory screening, or RL to isolate each component’s contribution.The alternatives use standard trajectory-agnostic SFT data, flat chronological histories, all generated trajectories, or evaluation after SFT, respectively.Source: §E.3 · p. 17

F Prompts for SAFARI Across Benchmarks

• SAFARI’s full system prompts specify runtime instructions for WEBSHOP, INTERCODE-SQL, and SCIENCEWORLD.Source: F Prompts for SAFARI Across Benchmarks · p. 17

F.1 Model Input Wrappers and Context Templates

• At each decision turn, SAFARI dynamically inserts serialized tree topology and memory metadata into the action-history slot alongside the instruction and observation.Source: §F.1 · pp. 17–18

F.2 Full Prompt for the WEBSHOP Environment

• The WEBSHOP prompt directs agents to verify hidden product attributes, configure matching options, and proactively backtrack or branch when requirements are unmet.It enforces strict exploration early, then permits a sub-optimal backup near the 10-step limit; tree notes track candidates and status tags.Source: §F.2 · p. 18

F.3 Full Prompt for the INTERCODE-SQL Environment

• The INTERCODE-SQL prompt uses a behavior-tree history for schema exploration, branching to a different query after errors and simplifying queries near the 10-step limit.It also requires submitted results to match the requested quantity, order, and rows, without unrequested columns.Source: §F.3 · p. 19
• The SQL prompt requires cached schema mappings, tagged query outcomes, tree-based branching after failures, and strict adherence to requested column order.It calls for strict exploration in steps 1–6 and adaptive tolerance from step 7 onward.Source: §F.3 · p. 20

F.4 Full Prompt for the SCIENCEWORLD Environment

• The ScienceWorld prompt directs agents to close information gaps, test and revise hypotheses, verify outcomes, and treat observations as ground truth.Because past room and container details are not repeated, agents should cache discoveries in a behavior-tree history and backtrack from failed or dead-end branches.Source: §F.4 · p. 21

G Prompt Templates for Baselines and Ablation Studies on WEBSHOP

• The WebShop prompt corpus covers baseline and exploration-aware instructions plus four tracking variants across list- and tree-structured memory.The templates are used by the teacher model gpt-4o for trajectory generation and data distillation.Source: G Prompt Templates for Baselines and… · p. 22

G.1 Model Input Wrappers and Context Templates

• Vanilla WebShop inputs append raw turns chronologically, while List and Tree variants inject serialized memory metadata into the action-history slot.The unified wrapper supplies the instruction, observation, and interaction history.Source: §G.1 · p. 22

G.2 Standard Instruction Prompt.

• The standard WebShop prompt asks the agent to choose an available action from the observation and instruction, using search keywords and exact clickable values.Responses follow a Thought/Action format.Source: §G.2 · p. 22

G.3 Explore Instruction Prompt.

• The exploration prompt requires checking product pages for target attributes and configuring them before purchase, rather than rejecting results based on default titles.It also prohibits clicks on Description, Features, or Reviews and forbids doing nothing.Source: §G.3 · p. 22
• When target attributes are missing or product choices are suboptimal, the WebShop prompt instructs early backtracking under strict tolerance and requires completion within 10 steps.Agents can return to the previous page or reset the search query, then use adaptive tolerance as a fallback after exploring multiple items.Source: §G.3 · pp. 22–23
• The Explore prompt requires strict exploration through steps 1–6, then adaptive tolerance from step 7, while prioritizing attribute configuration before fallback purchases.It directs the agent to assess the current shopping observation and step number when choosing whether to pivot, configure attributes, or accept a sub-optimal option.Source: §G.3 · p. 23

G.4 List Instruction Prompt without Note.

• The no-note List prompt calls for verifying hidden product variants, configuring available attributes, backtracking on imperfect candidates early, and accepting the best available fallback later.The agent infers dead ends and backup candidates from the chronological action list, such as an item click followed by a “< Prev” click.Source: §G.4 · pp. 23–24

G.5 List Instruction Prompt with Note.

• The with-note List prompt adds step-indexed history annotations—[FAILED], [DEAD END], [SUB-OPTIMAL], and [SUCCESS]—to identify outcomes and preserve backup candidates.The agent records concise notes about price, variants, and missing attributes, then uses tagged history to select a fallback when needed.Source: §G.5 · p. 25

G.6 Tree Instruction Prompt without Note.

• The Tree prompt supplies the agent with a behavior-tree action history, its current position ID, and the current step number.These inputs accompany the instruction, observation, and available actions used to choose the next action.Source: §G.6 · p. 25
• The prompt says to click products whose search titles show the wrong variant, configure available required attributes before buying, and avoid non-actionable tabs.It also forbids “perform nothing” or “Nothing” and directs agents to buy directly when the current configuration perfectly matches requirements.Source: §G.6 · pp. 25–26
• Agents must finish within 10 steps; with doubts, they must avoid forcing forward action, maintain strict zero tolerance in steps 1–5, and return to a parent or root to backtrack or branch.If running out of steps, such as step 7 or later, they must lower their standards immediately.Source: §G.6 · pp. 25–26
• The action-history tree records exploration paths through node topology and executed actions, with forward actions creating child nodes and backward navigation returning to existing nodes.Agents infer dead ends from branch structure; they can set a historical node as the next parent or relocate the current pointer without creating an empty child.Source: §G.6 · p. 26
• The required state analysis checks the current goal, product configuration, history-tree backup paths, and step number, while action analysis identifies the next shopping or search action.It specifies strict exploration through steps 1–6 and adaptive tolerance from step 7 onward, with finalization by relocating to the best suboptimal candidate.Source: §G.6 · p. 26