LASER: LLM Agent with State-Space Exploration for Web Navigation

1 Introduction

• Prior methods use oracle trajectories as in-context examples and assume the correct action is chosen at every step, limiting recovery from test-time mistakes.Covering every possible scenario with many examples is described as costly or unrealistic.Source: §1 · p. 1
• LASER represents interaction as transitions among predefined states, allowing the agent to backtrack after a wrong action and choose actions associated with its current state.The state-transition diagram illustrates the formulation on WebShop.Source: §1 · pp. 1–2, Figure 1 · p. 1
• LASER significantly outperforms previous baselines and closes the gap with human performance on web navigation.The paper evaluates the approach on WebShop and transfers it to amazon.com.Source: §1 · p. 2

2.1 Problem Formulation

• The task begins with an environment, user instruction, and initial observation; actions produce new observations until the agent reaches a stopping state or completes the task.The agent's output is compared with the target to compute metrics.Source: §2.1 · p. 2

2.2 LLM Agent

• At each step, the agent receives the goal, state-specific instructions, the current observation, permissible actions, and prior thoughts and actions, then selects an action that changes or retains its state.It repeats this process until the stopping state or maximum step is reached.Source: §2.2 · p. 2

2.3 State Description

• LASER distinguishes states only when the structure of the current environment observation differs, allowing a handful of states to support exploration.For WebShop, the authors manually categorize possible states and write generic instructions with placeholder-based observation layouts, a high-level goal, and action guidance; they define four states.Source: §2.3 · p. 2

2.4 Action Space

• State-specific permissible actions rule out invalid choices; when the maximum steps force a stop, LASER can select an examined intermediate item as its final output.The authors also use a thought-and-action loop and a memory buffer for examined items considered non-matching.Source: §2.4 · pp. 2–3

3 Experiments

• On the WebShop task, LASER was powered by GPT-4-0613 and evaluated on 500 test set instructions using reward and success rate, with comparisons to ReAct, ASH, and WebGUM.Source: §3 · p. 3
• Table 3 is labeled as WebShop ablation results with zero-shot GPT-4 LASER as the standard configuration.The supplied passages do not state the ablation table's outcome values.Source: Table 3 · p. 3
• Amazon.com transfer evaluation applies LASER without modification to 100 WebShop test instructions and manually evaluates the results.Table 2 is labeled as Amazon.com results.Source: §3 · p. 3, Table 2 · p. 3

4 Results

• LASER outperforms baselines by large margins on both WebShop metrics and achieves results very close to human performance on amazon.com.The authors suggest amazon.com’s stronger search engine may explain why performance there exceeded WebShop.Source: §4 · p. 3

4.1 Analysis

• Adding one in-context example worsened performance, while removing function calling led to slightly worse results in the 200-instruction ablations.The authors hypothesize that examples can distract an agent that already performs valid actions 100% of the time.Source: §4.1 · p. 4
• Most tasks took three state transitions, while performance generally declined with longer trajectories and was much lower for length-15 episodes.Length-15 episodes required selecting from browsing history; the group still had a nonzero success rate.Source: §4.1 · p. 4, Figure 2 · p. 4
• With text-davinci-003, performance dropped substantially but remained above the baselines, showing transfer across LLMs with different capabilities.Source: §4.1 · p. 4

• LASER models interactive web navigation as state-space exploration, with state tracking that supports handling novel situations and backtracking from mistakes.Source: §5 · p. 4
• Using state-specific instructions without in-context examples, LASER outperforms all WebShop baselines by large margins and closes the gap with human performance on a real-world shopping website.Source: §5 · p. 4
• The analysis reports greater robustness to longer trajectories and generalization to other LLMs.Source: §5 · p. 4

• Experiments cover finding target items only, leaving tasks such as order tracking and checking order history untested.Source: Limitations · p. 5
• LASER requires manual annotation of possible states and descriptions, which may make it suitable mainly for specific domains with only a handful of states.The authors name e-commerce and travel booking as examples.Source: Limitations · p. 5
• Real-world deployment calls for extra testing; the authors stopped LASER before purchases on amazon.com and say high-stakes actions may need human verification.They cite LASER’s still-imperfect success rate and the potentially hard-to-recover consequences of actions such as buying an item.Source: Limitations · p. 5

• ReAct (Yao et al., 2023) and InnerMonologue (Huang et al., 2023) add a thought process before actions, while ASH and WebAgent (Gur et al., 2024) decompose decisions into simpler steps.Source: A Related Works · p. 7
• Synapse (Zheng et al., 2024b) also uses state-conditional prompts, but decomposes few-shot examples whereas LASER relies on state-specific instructions without in-context examples.Source: A Related Works · p. 7
• Planning approaches RCI (Kim et al., 2023), Adaplanner (Sun et al., 2023), and Reflexion (Shinn et al., 2023) address planning or refinement; the authors describe them as orthogonal and potentially combinable with LASER.Source: A Related Works · p. 7
• Multimodal agents use screenshots alone or combine screenshots with textual website elements, and the authors suggest incorporating state transitions into these agents.Source: A Related Works · p. 7

B Experimental Details

• WebShop evaluation used 500 test instructions and reward plus success rate, with success requiring an exact target-item match and partial reward for partial matches.Partial reward reflects price, category, hidden attributes, and customization options.Source: B Experimental Details · p. 7
• LASER used GPT-4-0613 for action selection through function calling and allowed at most 15 state transitions, enforcing the budget after 13 if needed.Source: B Experimental Details · p. 7
• Amazon.com transfer applied LASER to the first 100 WebShop test instructions after converting pages to WebShop format, then used human annotations to score item matches.Price-match results were omitted because both human and LASER achieved 100% on that dimension.Source: B Experimental Details · pp. 7–8
• ReAct and ASH used manually written instructions and annotated trajectories, while WebGUM used 1k gold trajectories; LASER relied solely on manual instructions.The paper frames these as low-level task-specific knowledge versus LASER’s high-level generalizable instructions, which the authors consider more efficient when human effort is similar or lower.Source: B Experimental Details · p. 8

C Case Studies

• Retrieval failure was the largest category, with 12 of 30 cases in which no returned item met the requirement despite a suitable query.The authors hypothesize that a more effective retriever or search engine could address these cases.Source: C Case Studies · p. 8
• Nine of 30 cases were “Item good enough”: the selected item met the instruction from the authors’ perspective but did not receive full score.The example was a green living-room table lamp within budget that was nevertheless considered incorrect.Source: C Case Studies · p. 8
• Nine of 30 cases involved missing details, where the selected item mismatched a specific instruction despite matching other attributes.In the example, the shoes matched the requested color and size but were not high heels; the authors suggest self-feedback or verification as a possible avenue.Source: C Case Studies · p. 8

E Licenses

• WebShop and ReAct are released under the MIT License for research purposes, and the experiments are described as consistent with that intended use.Source: E Licenses · p. 9
• The accompanying materials identify system instructions for search, result, and item states, plus instructions for generating actions and a state-specific action space.Source: Table 4 · p. 10, Table 5 · p. 10, Table 6 · p. 12
• The shopping-agent prompt presents the current observation, item information, target keywords, and maximum price, then instructs the agent to assess customization and inspect available details.The prompt directs the agent to buy a match, inspect more details, or return to earlier results when needed.Source: E Licenses · p. 11