PaperlayerView exact revision on arXiv

Source-linked AI summary

WebPilot: A Versatile and Autonomous Multi-Agent System for Web Task Execution with Strategic Exploration

Yao Zhang, Zijian Ma, Yunpu Ma, Zhen Han, Yu Wu, Volker Tresp

arXiv:2408.15978v1cs.AI

TL;DR

LLM web agents often struggle with complex, dynamic tasks, while classical MCTS faces large action spaces and incomplete information. WebPilot combines high-level planning and refinement with tailored local MCTS; on WebArena, it reports a 93% relative increase in success rate over concurrent tree-based methods.

  • Problem

    LLM-based web agents often rely on rigid state-action policies that lack flexibility for unseen tasks, while classical MCTS struggles with vast action spaces, unpredictable transitions, and incomplete information.

    Source: §1 · pp. 1–2

  • Method

    WebPilot decomposes tasks and refines high-level plans, then executes each subtask with tailored MCTS that refines decisions from new observations.

    Source: §1 · p. 2

  • Results

    93% relative increase in success rate over concurrent tree-based methods on WebArena; WebPilot achieves a 37.2% success rate there.

    Source: §1 · p. 2

  • Takeaways & Limitations

    WebPilot achieves SOTA results on WebArena, advancing general autonomous-agent capabilities for complex environments.

    Source: §5 · p. 9

    WebPilot's performance is limited by LLM capabilities in text-based interaction, and the absence of visual information places additional strain on performance.

    Source: §4.6 · p. 9

Abstract

from arXiv · show

LLM-based autonomous agents often fail to execute complex web tasks that require dynamic interaction due to the inherent uncertainty and complexity of these environments. Existing LLM-based web agents typically rely on rigid, expert-designed policies specific to certain states and actions, which lack the flexibility and generalizability needed to adapt to unseen tasks. In contrast, humans excel by exploring unknowns, continuously adapting strategies, and resolving ambiguities through exploration. To emulate human-like adaptability, web agents need strategic exploration and complex decision-making. Monte Carlo Tree Search (MCTS) is well-suited for this, but classical MCTS struggles with vast action spaces, unpredictable state transitions, and incomplete information in web tasks. In light of this, we develop WebPilot, a multi-agent system with a dual optimization strategy that improves MCTS to better handle complex web environments. Specifically, the Global Optimization phase involves generating a high-level plan by breaking down tasks into manageable subtasks and continuously refining this plan, thereby focusing the search process and mitigating the challenges posed by vast action spaces in classical MCTS. Subsequently, the Local Optimization phase executes each subtask using a tailored MCTS designed for complex environments, effectively addressing uncertainties and managing incomplete information. Experimental results on WebArena and MiniWoB++ demonstrate the effectiveness of WebPilot. Notably, on WebArena, WebPilot achieves SOTA performance with GPT-4, achieving a 93% relative increase in success rate over the concurrent tree search-based method. WebPilot marks a significant advancement in general autonomous agent capabilities, paving the way for more advanced and reliable decision-making in practical environments.

1 Introduction

WebPilot targets the inflexibility of state- and action-specific web-agent policies and the difficulties classical MCTS faces in complex web environments. It combines high-level plan refinement with tailored local MCTS, and reports strong WebArena performance.

1 Introduction

  • Existing web agents rely on rigid state-action policies, while classical MCTS faces vast action spaces, unpredictable transitions, and incomplete information.The cited alternatives also include methods limited to lower-complexity tasks and approaches with less flexibility for dynamic interaction.Source: §1 · pp. 1–2
  • WebPilot combines global planning and refinement with local, tailored MCTS to execute subtasks amid uncertainty and incomplete information.The global phase decomposes tasks and refines plans using observations; local decisions are iteratively refined from new observations.Source: §1 · p. 2
  • Global Optimization uses task decomposition, plan adjustment, progress monitoring, and information extraction to manage complex tasks.The Planner breaks tasks into subtasks; the Controller assesses completeness and can trigger re-execution, while the Extractor gathers supporting information.Source: §1 · p. 2
  • Local Optimization uses Goal-Oriented Selection and Reflection-Enhanced Node Expansion to steer and refine subtask execution.Dynamic Evaluation and Simulation incorporates real-time feedback and one-step forward simulations; Maximal Value Backpropagation prioritizes paths with the highest potential.Source: §1 · p. 2
  • On WebArena, WebPilot achieves a 37.2% success rate, surpassing SteP and a 93% relative increase over concurrent tree-based methods.The experiments also assess MiniWoB++; with GPT-3.5, WebPilot achieves a 29.1% success rate.Source: §1 · p. 2
  • The Hierarchical Reflection Mechanism pairs Strategic Reflection in Global Optimization with Tactical Reflection in Local Optimization.The paper reports that this mechanism enhances adaptive learning and decision-making in evolving environments.Source: §1 · p. 2
  • The Granular Bifaceted Self-Reward Mechanism guides MCTS by combining action effectiveness with goal-oriented potential.The paper presents this as a way to assess actions more precisely in dynamic and ambiguous environments.Source: §1 · p. 2

2 Related Work

The related-work section compares LLM-based web agents and MCTS-based agents. It describes limitations in adapting to complex, unseen tasks and motivates WebPilot's dual optimization approach.

2 Related Work

  • The section compares LLM-based web agents with MCTS-based agents, with a detailed comparison presented in Table 1.The cited text does not provide the table's cell values.Source: §2 · p. 3

2.1 LLM-Based Autonomous Web Agents

  • LLM-based web agents use either state-action demonstrations or exploration, but existing approaches still struggle with realistic, complex, or unseen tasks.SteP (Sodhi et al. 2024) uses expert-designed state-action policies; other approaches include Auto Eval & Refine (Pan et al. 2024) and LM-Tree Search (Koh et al. 2024).Source: §2.1 · p. 3

2.2 LLM-MCTS Applications

  • Traditional MCTS-based methods struggle with vast action spaces, unpredictable transitions, and incomplete information in web tasks.The passage contrasts these challenges with WebPilot's tailored MCTS for complex environments.Source: §2.2 · p. 3

3 Methodology

WebPilot models web task execution as uncertain, partially observed exploration, then combines global plan refinement with local MCTS to complete subtasks. Its method decomposes tasks, adapts plans from observations, and uses reflection and reward estimates to guide search.

3.1 Promblem Formulation

  • Web tasks are partially observable and dynamic, so agents must explore web elements and make decisions with incomplete information.Source: §3.1 · p. 3

Hierarchical Task Decomposition (HTD)

Reflective Task Adjustment (RTA)

3.3 Local Optimization: MCTS-Enhanced

  • Local Optimization assigns Explorer, Verifier, Appraiser, and Controller roles and proceeds through selection, expansion, evaluation, and backpropagation.Source: §3.3 · p. 5

Goal-Oriented Selection (GOS)

Reflection-Enhanced Node Expansion (RENE)

Dynamic Evaluation and Simulation (DES)

Maximal Value Backpropagation (MVB)

4 Experiment

Experiments evaluate WebPilot on WebArena and MiniWoB++, then examine its components, behavior, and limitations. WebPilot performs strongly on WebArena, while results on MiniWoB++ are competitive with the state of the art.

4.1 Experimental Setup

  • Evaluation uses WebArena’s 812 human-annotated tasks and 43 text-solvable MiniWoB++ tasks, with GPT-3.5 and GPT-4o; WebPilot’s per-subtask node limit is 10.The study compares against SteP and LM-Tree Search and uses a maximum token limit of 4096 and temperature 0.3 for the stated models.Source: Datasets and Metrics · p. 7, Baseline Models · p. 7

4.2 Results on WebArena

  • WebArena results include a 7.7% GitLab improvement over SteP; GPT-4o raises SR over GPT-3.5 by 11.8% in Shopping, 6.6% in Reddit, and 9.4% in GitLab.The paper attributes the GitLab advantage to high-level demonstrations and adaptability; it links model gains to improved reasoning and planning.Source: §4.2 · p. 8
  • LM-TS lacks task decomposition, making large state spaces harder to navigate; WebPilot’s hierarchical reflections support repeated strategy reassessment.The paper discusses both factors as explanations for WebPilot’s stronger performance, particularly in Reddit and GitLab.Source: §4.2 · p. 8

4.3 Results on MiniWoB++

  • MiniWoB++ results are competitive with SteP, whose slight edge is attributed to 10 action-level demonstrations versus WebPilot’s 4 high-level demonstrations and the tasks’ limited need for exploration.The evaluation focuses on 43 MiniWoB++ tasks solvable through text representation.Source: Datasets and Metrics · p. 7, §4.3 · p. 8

4.2 Results on WebArena

  • 37.2% SR with GPT-4o and a 93% relative increase over LM-TS establish WebPilot’s WebArena result, surpassing SteP.Table 2 reports WebArena success rates as percentages and identifies WebPilot as state of the art.Source: §4.2 · p. 7, Table 2 · p. 8

4.4 Ablation Studies

  • Ablations on 50 successful information-seeking and 50 website-interaction tasks identify child and sibling reflection, Controller, and Planner as important, with website-interaction tasks more affected.Removing Child Reflection corresponds to a 30% performance decline, particularly in website-interaction tasks; Planner removal also degrades complex-task performance.Source: §4.4 · pp. 8–9

4.5 Agent Behavioral Analysis

  • In GitLab examples, WebPilot learns unfamiliar functionality through exploration, adapts after ineffective actions, and revises subtasks when observations reveal a more direct route.Examples include finding a branch option, switching from static text to a link, and recognizing that completing one subtask satisfies remaining goals.Source: §4.5 · p. 9

4.6 Limitation

  • WebPilot’s performance is limited by LLM capabilities and text-only interaction, which requires inferring context that visual cues could provide.The paper gives the number of stars associated with an item as an example of a visual cue.Source: §4.6 · p. 9

5 Conclusion

The conclusion presents WebPilot as a multi-agent system combining global optimization with tailored local MCTS, reporting state-of-the-art results on WebArena. The related-work discussion contrasts its dynamic exploration with methods relying on static contexts, direct outcome rewards, or predefined policies.

5 Conclusion

  • WebPilot combines global optimization with tailored local MCTS and achieves state-of-the-art results on WebArena.The conclusion frames the system as a step forward for autonomous decision-making in complex environments.Source: §5 · p. 9

A Extended Related Works

  • Unlike RAP (Hao et al. 2023a), WebPilot targets dynamic web interaction; unlike LATS (Zhou et al. 2023a), it avoids reliance on direct outcome rewards.The paper says such rewards can be unavailable or impractical in real-world web tasks.Source: A Extended Related Works · p. 13
  • WebPilot’s real-time exploration contrasts with LLM-MCTS (Zhao, Lee, and Hsu 2024) and SteP (Sodhi et al. 2024), which rely on prior examples or predefined state-specific policies.The paper argues these forms of guidance can constrain adaptation to unforeseen scenarios.Source: A Extended Related Works · p. 13
  • LM-Tree Search (Koh et al. 2024) lacks task decomposition and uses sparse rewards, whereas WebPilot evaluates actions using real-time feedback.The paper connects LM-Tree Search’s design to scalability challenges on complex tasks.Source: A Extended Related Works · p. 13

B Experimental Setup

WebArena is partially observable and dynamically changing, making decisions difficult when relevant content is not visible or predictable. Its realistic pages also contain semantically similar or duplicate elements, so WebPilot uses exploration and reflections to resolve uncertainty about their functions.

B Experimental Setup

  • Web task environments are partially observable: content can change, and relevant elements may disappear from the current view after scrolling.The example describes a branch no longer visible while reviewing commit records.Source: B Experimental Setup · p. 13

B.1 Challenges in WebArena

  • WebArena’s realism and complexity expose agents to similar elements and unfamiliar website functionality.The paper presents WebArena as a primary benchmark derived from real-world websites.Source: §B.1 · p. 13

Similarity of Elements and Unknown Web Functionality

  • Semantically related sidebar labels can mislead navigation; WebPilot tests candidate links and reflects when one fails to reveal the target page.In the example, it tries “Repository” before “Project Information” leads to the Members page.Source: Similarity of Elements and Unknown Web… · p. 14

Complexity of Web Elements in Accessibility Tree, i.e., actree

  • The actree can represent one page as duplicate elements, including non-interactive static text beside a functional link; WebPilot adjusts after observing the difference.The paper notes that visual cues may not clearly distinguish such elements either.Source: Complexity of Web Elements in… · p. 14, Figure 4 · p. 14

Long-Horizon Task Complexity

WebPilot handles long-horizon tasks by decomposing them into subtasks and using checkpoints to recover from execution errors. The appendix also describes how task simplicity and MCTS design choices affect exploration and search.

Long-Horizon Task Complexity

  • For long-horizon WebArena tasks, Planner divides work into simpler subtasks and Controller checks completion, enabling recovery without redoing lengthy sequences.Subtasks serve as checkpoints, allowing WebPilot to revert when execution deviates from the optimal path.Source: Long-Horizon Task Complexity · p. 14

B.2 Characteristics of MiniWoB++

  • MiniWoB++ tasks are often instruction-driven, require only one or two actions, and use few elements, so WebPilot’s strategic capabilities yield less pronounced gains.The section presents MiniWoB++ as a simpler, diverse test environment, unlike more complex settings such as WebArena.Source: §B.2 · p. 15, Figure 6 · p. 15, Figure 7 · p. 15

B.3 Implementation Details

  • WebArena and MiniWoB++ use 10 maximum nodes, exploration bias 5, search depth 5, and 3 branches.The settings are described as balancing exploration and efficiency.Source: §B.3 · p. 15

Max Node Count nmax

  • Too many MCTS nodes can waste resources, while too few can terminate search before it reaches a target requiring multiple actions.The authors report that promising paths not found within the first two layers often indicate flawed initial paths, when Controller can assess completion and trigger re-execution.Source: Max Node Count nmax · p. 16

Num of Branches

  • WebPilot limits branches because LLM intuition often prioritizes useful choices, but too few branches can miss the correct path; the implementation uses 3.Initial explorations help DES lower scores for unpromising nodes and sibling reflections refine later actions.Source: Num of Branches · p. 16

Exploration Bias wpuct

  • Exploration bias shifts MCTS between depth-first and breadth-first search, and an excessively high setting may deter exploration of a promising node.The example describes a target link hidden in a dropdown; an appropriate bias helps Explorer pursue the optimal path.Source: Exploration Bias wpuct · p. 16

C.2 Illustrative Example: Impact of Reward Function

  • WebPilot’s reward function combines action effectiveness with the future promise of the resulting observation to favor useful actions and states that may lead to the target.Action effectiveness scores whether an action advances the subtask, while future promise evaluates whether the page can lead to the target page.Source: §C.2 · p. 16, Figure 8 · p. 16

C.3 Illustrative Example: Impact of MVB

  • Without Maximal Value Backpropagation, averaging can dilute a high-value path’s score, slowing search or causing failure under a limited node count.This is especially relevant when target states are concealed and must be uncovered through exploration.Source: §C.3 · p. 17

C.4 Illustrative Examples of Ablation Study Findings

The examples illustrate how WebPilot’s reflections and Controller support coherent, adaptive exploration and subtask-level decision-making. They show how feedback from failures, completion checks, and plan updates guide subsequent actions.

C.4 Illustrative Examples of Ablation Study Findings

  • The ablation examples illustrate component effects, including how child reflection preserves a coherent sequence of actions during multi-step tasks.For inviting a user, the sequence includes opening the dialog, entering the name, selecting the user, and completing the invitation.Source: §C.4 · p. 17, Illustrative Example: Importance of… · p. 17

Illustrative Example: Importance of Child Reflection Rct for Maintaining Coherent Thought Processes

  • Child reflection directs the next action toward selecting the matching dropdown item after a username is entered, avoiding interactions that could disrupt the invitation flow.The WebArena accessibility tree can leave elements outside the dialog visible, and interacting with them closes the dialog.Source: Illustrative Example: Importance of… · p. 17

Illustrative Example: Critical Role of Sibling Reflection Rst in Effective and Diverse Exploration

  • Sibling reflection shares failed-path experience with sibling nodes, helping WebPilot avoid redundant actions and redirect toward more promising alternatives.After clicking Repository leads to Files rather than Members, the reflection points to the Members link in the sidebar.Source: Illustrative Example: Critical Role of… · pp. 17, 19

Illustrative Example: Significance of Controller in Ensuring Subtask Accuracy and High-Level Decision-Making

D Illustrative Examples of Agent Behavioral Analysis

The behavioral examples show WebPilot exploring unfamiliar interfaces, adjusting actions to new observations, and resolving ambiguity through iterative refinement. The examples span website navigation, search interpretation, and task planning.

D Illustrative Examples of Agent Behavioral Analysis

D.1 Illustrative Example: WebPilot Learning Website Functionality by Exploring Unknowns

  • When a CMS Pages link is not initially visible, WebPilot explores the sidebar to locate it, illustrating navigation through unfamiliar interfaces.Source: §D.1 · p. 20

D.2 Illustrative Example: WebPilot Adapting Strategies Based on New Observations

  • When GitLab search results default to Projects and hide the Users tab, WebPilot revises its next action to select Users rather than assuming user results are unavailable.Source: §D.2 · p. 20

D.3 Illustrative Example: WebPilot Resolving Ambiguities Through Iterative Refinement

  • For an ambiguous Reddit recommendation task, Planner proposes a relevant-subreddit subtask, Explorer reviews the subreddit list, and Controller validates the destination.Source: §D.3 · p. 20

D.4 Illustrative Example: High-Level Demos Generalize Better to Unseen Tasks

WebPilot’s high-level demonstrations support plans for tasks not explicitly covered by those examples. The illustrated Shopping task was completed, as were three additional tasks from the same template.

D.4 Illustrative Example: High-Level Demos Generalize Better to Unseen Tasks

  • WebPilot generalizes high-level domain strategies to an unseen Shopping task, completing it and three additional tasks from the same template.The task was to find a customer’s name and email using a phone number; the plan navigated to Customers, searched the number, and extracted the information.Source: §D.4 · p. 20

D.5 Illustrative Example: Strategic Differences Between WebPilot and SteP

The examples contrast SteP’s repeated, policy-driven actions with WebPilot’s decomposition of tasks into focused subtasks and adaptive exploration. This lets WebPilot reach the intended target and verify task-specific details.

D.5 Illustrative Example: Strategic Differences Between WebPilot and SteP

  • WebPilot used Hierarchical Task Decomposition to isolate the Members-page goal and reach it, while SteP remained stuck repeating the Settings action.SteP repeatedly tried the Settings page; WebPilot focused on the Members page and adapted its strategy when challenged.Source: §D.5 · p. 21
  • For the upvote task, SteP repeatedly clicked “UPVOTE” without achieving the outcome, while WebPilot assessed the task’s aspects and prioritized the needed actions.SteP halted after repeating the same action; WebPilot flexibly assessed and executed the necessary actions.Source: §D.5 · p. 21
  • For contributor extraction, SteP answered without setting the requested branch and succeeded coincidentally, whereas WebPilot’s first subtask set the branch to “main.”The default “development” branch happened to have the same top contributor as “main”; WebPilot’s decomposition explicitly addressed the branch requirement.Source: §D.5 · p. 21

E.1 Comparative Analysis of Agent Behavior with GPT-3.5 and GPT-4

The examples compare GPT-3.5 and GPT-4 behavior and describe text-observation limitations and components of WebPilot’s workflow. GPT-4 performs better in the reported exploration and planning examples, while text-based observations can obscure relationships and visual information.

Case 2: Utilizing the ”Scroll” Action to Explore

  • GPT-4 was more effective than GPT-3.5 at scrolling to reveal a hidden profile-settings textbox and completing the homepage-modification task.GPT-3.5 struggled and failed at this operation, while GPT-4 handled it more effectively.Source: Case 2: Utilizing the ”Scroll” Action… · p. 25

Case 3: Plan Generation for Unseen Tasks

  • GPT-4 generally generated more successful plans than GPT-3.5 for unseen tasks, with especially improved results on some task templates.The passage notes that high-level demonstrations help generate plans for unseen tasks.Source: Case 3: Plan Generation for Unseen Tasks · p. 25

Case 4: Knowledge Precision

  • For a route-planning task, GPT-4 produced the correct plan for searching from New York to Portland, while GPT-3.5 struggled to output the correct city names.The task asks for the path and travel time from “the Big Apple” to the biggest city in Maine.Source: Case 4: Knowledge Precision · p. 25

E.2 Text-based Observation vs. Vision-based Observation

  • Text-based observations can mislead order identification through proximity, omit visual information such as repository stars, and fail to show state changes conveyed by page content.Examples include a nearby element leading to the wrong pending-order number, star information represented inadequately in an actree, and issue-filter tabs whose text remains unchanged after filtering.Source: §E.2 · p. 25, Element Not Directly Observable · p. 26

Invisible Dropdowns

F.2 Detailed Description of Action Effects Effect(at) in RENE

  • Action-effect assessment distinguishes page changes from within-page edits using base URLs, while the pseudocode places exploration, scoring, and controller checks in the subtask search.For unchanged URLs, Explorer describes page-element changes; for changed URLs, it describes the new page.Source: §F.2 · pp. 26–27, §F.4 · p. 29

F.3 High-level Demonstrations for the CMS Domain

  • A CMS tax-report example decomposes the task into navigating to Reports, opening Tax Report, then setting the date range and generating the report.Source: §F.3 · p. 27

Related papers

Loading 2408.15978v1…