PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhizhao Guan, Chen Huang, Ziming Liu, Hongru Liang, Wenqiang Lei, See-Kiong Ng, Tat-Seng Chua, Anthony G Cohn

arXiv:2608.14339v1cs.AIcs.LG

TL;DR

LLM agents need proactive exploration to acquire information for better decisions, but this capability remains limited. SAFARI synthesizes exploration-rich trajectories and refines exploration with contrastive RL, significantly improving task success and exploration efficiency across diverse benchmarks.

  • Problem

    LLM agents need proactive exploration because optimal decisions often depend on information acquired beyond the current observation.

  • Method

    SAFARI synthesizes exploration-rich trajectories and uses contrastive preference pairs during RL to install and refine proactive exploration in LLM agents.

  • Results

    10%-15% average task-success gains and 8%-18% exploration-efficiency gains show that SAFARI outperforms competitive baselines across diverse benchmarks.

  • Takeaways & Limitations

    SAFARI acquires task-relevant information while avoiding redundant interactions, with larger exploration benefits on harder information-gathering tasks.

  • Takeaways & Limitations

    The Eff(τ) metric is a heuristic proxy for exploration utility and may inflate scores in successful trajectories regardless of whether exploration caused success.

Abstract

from arXiv · show

We study proactive exploration in LLM agents, i.e., the ability to explore an environment to acquire information that improves future decision-making. In this regard, we first identify two fundamental bottlenecks that hinder this capability and then propose \ours, a novel method designed to instill and refine proactive exploration. Specifically, \ours\ consists of two components: (1) Exploratory Data Construction, which synthesizes exploration-rich trajectories to mitigate the hindsight bias of standard demonstrations; and (2) RL Optimization with Contrastive Signal Guidance, which leverages contrastive trajectory pairs to distinguish productive exploration from redundant wandering. Extensive experiments demonstrate the effectiveness of \ours\ and provide insights into the characteristics of proactive exploration. Our code is available at: https://github.com/GuanZhizhao/SAFARI.

1 Introduction

The introduction frames proactive exploration as essential for LLM agents in interactive tasks, while identifying exploration collapse as a central bottleneck. SAFARI addresses these limitations through exploratory data construction and contrastive RL guidance, improving task success and exploration efficiency.

  • Motivation: Interactive tasks require agents to decide whether to accept satisfactory options or continue exploring for better alternatives.The online-shopping example involves strategic browsing, backtracking, and pagination to locate a product with a better price.
  • Challenges: SFT-based agents lack exploratory tendencies, so RL rollouts rarely discover or reinforce the long-term benefits of proactive exploration.The introduction identifies exploration collapse during RL as a fundamental bottleneck.
  • Method: SAFARI synthesizes exploration-rich trajectories from a powerful LLM expert using tree-structured context modeling to distill diverse exploratory paths.This exploratory data construction module is designed to mitigate the limitations of standard expert trajectories.
  • Method: SAFARI uses contrastive preference pairs and Monte Carlo rollouts to provide fine-grained supervision for refining the agent’s decision boundary.Student-generated candidate actions are compared with reference actions at identical interaction states, enabling alternating strategic exploration and direct task execution.
  • Results: ∼10%-15% average task-success gains and ∼8%-18% exploration-efficiency gains show that SAFARI outperforms competitive baselines across diverse benchmarks.The analyses attribute performance improvements to acquiring task-relevant information while avoiding redundant interactions.

2 Related Work

Prior interactive agents used prompt planning or imitation learning, while newer work introduced exploration-driven RL and self-improvement to improve adaptability. Existing approaches address failures or structure search but remain limited by proactive-exploration bottlenecks and external, environment-specific mechanisms.

  • 2 Related Work: Early agents relied on prompt-based planning or imitation learning, restricting behavior to observed state–action distributions.Recent work introduced exploration-driven RL training and iterative self-improvement to improve adaptability.
  • 2 Related Work: Hindsight bias and exploration collapse can produce insufficient proactive exploration and suboptimal solutions.Error recovery methods use corrective trajectories or MCTS-based self-improvement after explicit failures.
  • 2 Related Work: Failure-triggered methods discourage exploration beyond reward-sufficient trajectories and often converge to local optimThe supplied passage ends mid-word after “local optim,” so no further claim is added.
  • 2 Related Work: Structured representations improve decision-making through tree-based reasoning, interaction graphs, or webpage hierarchies, but these methods target web environments as external search tools rather than policy-level mechanisms.Tree-based reasoning is described as improving state visibility and search efficiency.

3 Preliminary Experiments

Preliminary experiments on WebShop diagnose proactive-exploration failures through action distributions and training data. Existing methods and standard SFT trajectories largely omit exploratory actions, motivating exploration-rich data and RL mechanisms.

  • Dataset & Exploratory Actions: WebShop separates task-oriented actions from exploratory actions, enabling precise analysis of agents’ exploratory tendencies.Task-oriented actions are Search, Open, Select, and Buy; exploratory actions are Next, Back, and Home.
  • Baselines: The analysis compares agents trained with standard expert trajectories and existing SFT or SFT-RL methods against human-expert trajectories.The evaluated SFT-RL approaches include ETO and IPR.
  • Hindsight Bias in SFT Data: 0.10%: Exploratory actions comprise a negligible share of expert trajectories, revealing hindsight bias in standard SFT data.The passage states that expert trajectories strip away essential exploratory steps.
  • Exploration Bottlenecks: Existing methods and their underlying SFT data profoundly lack exploratory actions, and this deficit causes significant degradation on complex tasks.The paper links this finding to case studies and main experiments.
  • Exploration Bottlenecks: These findings motivate incorporating exploration-rich SFT data and RL mechanisms to shift agents from reactive execution toward proactive exploration.The proposed remedy directly addresses the diagnosed data and behavioral bottlenecks.

4 SAFARI: The Method

SAFARI builds exploration-aware training data by eliciting, annotating, backtracking through, and filtering diverse expert trajectories, then refines the initialized agent with contrastive preference optimization. Its method explicitly distinguishes productive exploration from redundant wandering and calibrates when to explore versus execute.

  • Exploratory Data Construction: Exploratory data construction elicits diverse paths from an LLM expert and filters them into high-quality, exploration-oriented trajectories for SFT initialization.The method addresses the cost of manually curating exploration-rich expert trajectories.
  • Exploratory Data Construction: A tree-structured context enables autonomous backtracking and active feedback digestion through cognitive notes that record environment assets and control labels.The teacher searches, annotates, and backtracks to capture complete trial-and-error trees rather than only successful paths.
  • Exploratory Data Construction: The resulting trajectories preserve authentic cognitive reasoning and complete interactions, reducing the hindsight bias inherent in standard expert datasets.The construction captures exploratory failures and subsequent recovery decisions, not merely the final success path.
  • Trajectory Refinement and SFT: SAFARI selects reference trajectories with a length-penalized reward and retains only successful candidates, penalizing redundant wandering while preserving necessary exploration.For each task, m sampled trajectories are evaluated; the candidate maximizing rfinal forms Dref, followed by a strict r(h) = 1 performance filter.
  • RL Optimization with Contrastive Signal Guidance: Contrastive pairs share a reference-set interaction context and compare a teacher reference action with a student-generated candidate action at pivotal strategic moments.MC rollouts estimate aggregate task success rewards, exposing whether an exploratory detour improves success relative to immediate execution.
  • RL Optimization with Contrastive Signal Guidance: DPO uses the higher-reward action as preferred and filters pairs by retaining only reward gaps greater than τm, reducing sensitivity to stochastic evaluation noise.The margin condition is |rstep(ˆa|st) −rstep(a∗|st)| > τm.

5 Experiment

Experiments show that SAFARI improves task success and exploration across benchmarks and backbones by combining exploration-rich data with contrastive RL optimization. Its exploration adapts to task difficulty, balances useful and wasted exploration, and benefits substantially from structured contexts, data screening, and RL.

  • Main Results: SAFARI improves task success and exploration score across all benchmarks and backbones, exceeding the best baselines by approximately 10%-15% and 8%-18%, respectively.The experiments use Meta-Llama-3.1-8B-Instruct and Mistral-7B-Instruct-v0.3 backbones.
  • Exploration Efficiency: SAFARI increases effective exploration while suppressing redundant wandering, with RL progressively widening the gap between effective and wasted exploration after SFT.SFT produces high effective and wasted exploration; RL1 sharply reduces wasted exploration, and RL2-RL3 further improve net efficiency.
  • Difficulty Scaling: As tasks become harder, SAFARI increases exploration extent from 0.16 to 0.20 to 0.35 and trajectory length from 4.95 to 5.41 to 6.20 across Easy, Medium, and Hard subsets.The baseline maintains trajectory lengths around 4.0 and exploration extent close to zero across difficulty levels.
  • Ablation Studies: Tree-structured contexts outperform direct prompting and list-structured contexts, improving TP by +16.63% and ES by +12.83%.Explicit exploration prompting yields only +3.14% in TP and +7.53% in ES, while list-structured contexts yield +12.24% in TP and +13.28% in ES.
  • Ablation Studies: Tree-structured prompts with data screening improve downstream SFT performance by +9.66% in TP and +5.61% in ES, while RL provides further gains only after suitable SFT initialization.Cognitive notes additionally improve performance by +5.03% in TP and +2.23% in ES.

6 Conclusion

The conclusion argues that intelligent agents must proactively acquire information beyond current observations, making proactive exploration foundational for robust decision-making in complex open-world environments.

  • 6 Conclusion: Proactive exploration lets agents acquire information despite short-term costs to improve future decision-making.It requires reasoning about whether the current knowledge state is sufficient for reliable planning.
  • 6 Conclusion: Proactive exploration is presented as a foundational capability for next-generation agents in complex open-world environments.It supports robust decisions when optimal actions depend on actively expanding and refining environmental understanding.

Limitations

The paper acknowledges that its proposed exploration-efficiency metric is only a heuristic proxy and is not strictly equivalent to effective exploration.

  • Heuristic Exploration Metrics: Eff(τ) measures exploration efficiency in the experimental setting but is explicitly anchored to terminal task reward, so it does not strictly equal actual effective exploration.The authors present Eff(τ) as an initial measurable proxy for exploration utility.

LLM Usage · A Details of the Interactive Tree-Structured History with Cognitive Notes · A.1 Formalization and Algorithmic Conversion

The paper uses LLMs as backbone and teacher models for trajectory construction, while introducing a tree-structured history that separates exploratory branches and records cognitive notes. This representation addresses the confusion caused by flat chronological histories in interactive environments.

  • LLM Usage: LLMs serve as both backbone models and teacher models for trajectory data construction, while language polishing is their only additional use.
  • A Details of the Interactive Tree-Structured History with Cognitive Notes: The section formalizes the proposed Tree-Structured History, its algorithmic conversion, operational mechanisms, and environment-specific implementations.
  • A.1 Formalization and Algorithmic Conversion: Interactive trajectories are conventionally represented as flat chronological sequences containing the task instruction, executed actions, and environmental observations.The sequence is denoted Ht = {u, (a1, o1), (a2, o2), . . . , (at, ot)}.
  • A.1 Formalization and Algorithmic Conversion: Flat histories conflate productive execution with exploratory detours and can mislead agents into treating abandoned backtracked states as active context.
  • A.1 Formalization and Algorithmic Conversion: The method maps each trajectory into a topological action tree whose nodes retain unique identifiers, executed actions, parent links, and child-branch tracking IDs.
  • A.1 Formalization and Algorithmic Conversion: Each node’s agent-managed note supports labels [SUCCESS], [FAILED], [DEAD END], and [SUB-OPTIMAL] for distinct exploration states.The labels mark completed milestones, execution errors, exhausted paths, and imperfect backup candidates, respectively.
  • A.1 Formalization and Algorithmic Conversion: A globally maintained active-position pointer tracks the agent’s current state, while Algorithm 1 formalizes conversion from sequences to trees.Exact structured output formats and prompt execution templates are provided in Appendix F.

A.2 Dual Relocation Mechanisms Across Different Target Domains · A.3 Operational Roles of Cognitive Notes with Concrete Case Study

The framework relocates its active tree pointer through action-driven synchronization when environments support explicit backtracking, and through direct pointer modification otherwise. Cognitive notes operationalize the resulting tree history by caching facts, marking branch status, encoding rules, revising hypotheses, and recovering checkpoints in a ScienceWorld case study.

  • A.2 Dual Relocation Mechanisms Across Different Target Domains: The framework uses two relocation paradigms: action-driven synchronization for environments with explicit backtracking and direct pointer modification for environments without it.WebShop uses environmental backward actions, whereas InterCode-SQL and ScienceWorld overwrite the global pointer outside the execution loop.
  • A.2 Dual Relocation Mechanisms Across Different Target Domains: In WebShop, executing a physical backtracking command synchronizes tree relocation with environmental state transitions and isolates unproductive paths into parallel side branches.The mechanism applies when the environment provides explicit actions such as clicking a <Back> button.
  • A.2 Dual Relocation Mechanisms Across Different Target Domains: Direct pointer modification supports two controls: target-node relocation resumes from an existing historical checkpoint, while next-parent assignment launches a new branch from a designated historical context.Target-node relocation does not spawn a node; next-parent assignment executes the subsequent action from the selected parent and creates a parallel branch.
  • A.3 Operational Roles of Cognitive Notes with Concrete Case Study: Cognitive notes convert passive tree topology into operational working memory for the long-horizon ScienceWorld task of freezing orange juice.The case study follows an unverified hypothesis that orange juice must be extracted from a raw orange.
  • A.3 Operational Roles of Cognitive Notes with Concrete Case Study: Notes cache verified environmental facts, such as kitchen-appliance information at node 2, preserving spatial knowledge without repeated look around actions.The cached snapshot covers unexamined appliances including the freezer and fridge.
  • A.3 Operational Roles of Cognitive Notes with Concrete Case Study: Explicit [DEAD END] tags mark failed branches and signal the policy to stop forward execution along unpromising paths.At node 10, the workshop branch receives this status after no juicing utilities are found.
  • A.3 Operational Roles of Cognitive Notes with Concrete Case Study: RULE LEARNED entries encode environmental constraints, preventing repeated syntactical or mechanical errors such as vague picking actions.At node 3, rejection of a vague picking action produces the rule “select index.”
  • A.3 Operational Roles of Cognitive Notes with Concrete Case Study: After the workshop hypothesis fails, notes preserve the failure rationale, revise the hypothesis toward pre-made juice, and relocate directly to the kitchen checkpoint to explore new sibling branches.From node 2, cached facts guide renewed exploration of the fridge or freezer, eliminating redundant wandering.

B Hyperparameters and Implementation Details

SAFARI’s experiments use a reproducible multi-phase pipeline implemented on 3 NVIDIA A100 (80GB) GPUs, with task-specific settings for trajectory synthesis, fine-tuning, exploration, contrastive optimization, and global iterations.

  • Implementation Setup: Experiments run on 3 NVIDIA A100 (80GB) GPUs, with core prompt templates provided in Appendix F.These configurations are reported to support full reproducibility.
  • Data Synthesis via Teacher Model: GPT-4o synthesizes 5 candidate trajectories per task using T = 1.0, top_p = 0.85, and task-specific step penalties.The step penalty γ is 0.1 for WebShop and InterCode-SQL, and 0.01 for ScienceWorld.
  • Supervised Fine-Tuning (SFT) Phase: The proactive agent receives 1 SFT epoch at 3 × 10−6, while the MC evaluator receives 3 epochs on Dscore at 2 × 10−5.The proactive-agent schedule establishes baseline capabilities while preventing premature overfitting.
  • Exploration Mechanics: Active exploration uses greedy decoding at T = 0, whereas MC reward estimation uses stochastic decoding at T = 1.0 with 5 rollouts per candidate action.The rollout process independently samples five trajectories for each candidate action.

C Information-Theoretic Exploration Metrics · D Case Study: Overcoming Hallucination via Proactive Exploration

The paper defines information-theoretic exploration metrics that distinguish breadth, depth, baseline-surplus gains, saturation, and reward-aligned utility. It then uses qualitative case studies to show how SAFARI audits candidates and gathers context to address decision hallucinations.

  • C Information-Theoretic Exploration Metrics: The metric jointly captures candidate-information breadth, explicit verification depth, and task reward to quantify exploration’s net utility.Breadth comes from exposed entities, while depth comes from focused entities obtained through direct interaction.
  • C Information-Theoretic Exploration Metrics: Exposed entities are revealed coarsely by observations, whereas focused entities are explicitly inspected or manipulated by the agent.The distinction includes actions such as entering links, selecting options, or clicking for details.
  • C Information-Theoretic Exploration Metrics: Trajectory accounting extracts, canonicalizes, filters, deduplicates, normalizes, and aggregates entities into global exploration scores.The implementation uses task-specific, manually customized rule-based extraction, filtering, and category mappings.
  • C Information-Theoretic Exploration Metrics: A fixed validation-trajectory baseline removes mandatory completion entities and measures surplus exploration beyond standard agent behavior.Non-positive baseline denominators are clipped to zero to avoid division-by-zero errors.
  • C Information-Theoretic Exploration Metrics: The metric excludes substandard wandering, averages category gains in primary analysis, and applies exponential saturation to limit brute-force trajectory inflation.Only exploration exceeding the baseline contributes, and α = 1 is fixed across reported experiments.
  • C Information-Theoretic Exploration Metrics: Reward coupling separates Effective Exploration from Wasted Exploration and subtracts redundant overhead to obtain Exploration Efficiency as net behavioral utility.Effective Exploration aligns proactive exploration with final task resolution, while Wasted Exploration penalizes aimless paths that fail to support terminal success.
  • D Case Study: Overcoming Hallucination via Proactive Exploration: Qualitative case studies show SAFARI using tree-structured memory and cognitive notes to audit candidates, gather missing context, and address fatal decision hallucinations.The studies span distinct domains and illustrate proactive exploration concretely.

D.1 Case 1: Webshop

In WebShop case 9021, SAFARI verifies multiple product candidates against the full request before purchasing, avoiding the premature purchases made by IPR/ETO and STeCa. This targeted candidate-auditing strategy achieves the correct chocolate option while reducing shopping errors.

  • Premature Purchase: IPR/ETO and STeCa click the first lexically plausible product and purchase without comparative verification.IPR/ETO buys B09RND5D4Y, while STeCa buys B002YM58UE; both exploit partial matches and terminate after only three steps.
  • Outcome: Reward = 1.0 for SAFARI, which correctly selects a chocolate option after checking multiple candidates.By contrast, Reward = 0.3333 / 0.0667 for purchases of a partial lexical match or wrong product type.
  • Proactive Candidate Verification: SAFARI searches with the full constraints and verifies product pages as candidates, returning to search results when a product is only a partial match.It inspects multiple products before selecting the required chocolate option.
  • Case Interpretation: The case shows that proactive exploration is targeted candidate auditing rather than random browsing, delaying purchase until key constraints are grounded in the environment.Comparing alternatives and recording product-level mismatches helps avoid premature exploitation and reduces environment-induced shopping errors.

D.2 Case 2: Intercode-Sql

In InterCode-SQL Task 119, rigid baselines hallucinate Afghanistan’s country code and fail, whereas SAFARI proactively inspects related schema information to avoid the assumption.

  • Proactive Context Gathering: SAFARI proactively inspects the country table schema to acquire the Name-to-Code mapping and avoid blind assumptions.The case study describes this exploration as preventing hallucination of the country code.
  • The Pitfall of Rigid Execution: In Task 119, IPR and STeCa inspect only the countrylanguage table before guessing Afghanistan’s unverified country code.They guess “AFG” or “AF,” bypassing semantic grounding.
  • The Pitfall of Rigid Execution: R = 0 results when premature exploitation of the guessed country code causes execution failure.The failure follows from hallucinating the country code without verifying the relevant schema mapping.
  • Proactive Context Gathering: The case illustrates proactive exploration as purposeful information gathering that aligns internal beliefs with external reality rather than random wandering.The authors characterize this strategy as completely eradicating environmental hallucinations.

E Implementation Details of Ablation Studies … G Prompt Templates for Baselines and Ablation Studies on WEBSHOP

The appendices specify SAFARI’s ablations, model configurations, trajectory-synthesis prompts, downstream policy variants, and runtime templates across WEBSHOP, INTERCODE-SQL, and SCIENCEWORLD. They also define baseline and structured prompt formats, including tree-based histories, exploration guidance, backtracking, memory updates, and environment-specific action constraints.

  • E Implementation Details of Ablation Studies; E.1 Environment and Model Configurations: The implementation appendix covers ablations, evaluation environments, backbone models, and task-specific WEBSHOP teacher prompts.Experiments use gpt-4o for trajectory synthesis and data distillation, and Meta-Llama-3.1-8B-Instruct for SFT and RL policy learning.
  • E.2 Teacher-Driven Trajectory Synthesis: Teacher trajectory variants compare direct, exploration-aware, list-structured, and tree-structured prompts while holding task-specific few-shot exemplars constant.Exploration-aware prompts add hypothesis testing, proactive backtracking, and search tolerance; list and tree variants optionally include notes.
  • E.3 Student Downstream Policy Learning: Student ablations remove exploration-rich SFT data, tree memory, data screening, or RL to isolate each component’s contribution.The variants are SAFARI w/ Original SFT, SAFARI w/o Tree-Structured, SAFARI w/o Data Screening, and SAFARI w/o RL.
  • F Prompts for SAFARI Across Benchmarks; F.1 Model Input Wrappers and Context Templates: SAFARI’s runtime prompts generalize tree-structured history and external note-taking across WEBSHOP, INTERCODE-SQL, and SCIENCEWORLD.At each turn, templates wrap instruction, observation, and action history, dynamically injecting serialized tree topology and memory metadata.
  • F.2 Full Prompt for the WEBSHOP Environment: The WEBSHOP prompt requires verifying hidden product attributes, configuring products before purchase, proactively backtracking, and accepting the best backup within 10 steps.It records behavior-tree nodes with status tags such as [FAILED], [DEAD END], [SUB-OPTIMAL], and [SUCCESS].
  • F.3 Full Prompt for the INTERCODE-SQL Environment: The INTERCODE-SQL prompt uses behavior-tree exploration, schema caching, branching after errors, simplified fallback queries, and strict output alignment.It forbids repeated failed queries and requires exact requested columns, original headers, and SELECT ordering.
  • F.4 Full Prompt for the SCIENCEWORLD Environment: The SCIENCEWORLD prompt frames actions as hypothesis-driven information gathering, requires evidence-based updates, and manages exploration timelines through branching behavior trees.Agents cache environmental facts in node notes, extract learned rules, and backtrack after failed or dead-end actions.
  • G Prompt Templates for Baselines and Ablation Studies on WEBSHOP; G.1 Model Input Wrappers and Context Templates; G.2 Standard Instruction Prompt.; G.3 Explore Instruction Prompt.: WEBSHOP baseline templates use chronological dialogue histories, whereas structured List and Tree variants inject serialized memory metadata into the action-history slot.The standard and exploration prompts preserve the search[keywords] and click[value] action format, with exploration instructions extending verification behavior.
Loading 2608.14339v1…