PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration

Evan Zheran Liu, Kelvin Guu, Panupong Pasupat, Tianlin Shi, Percy Liang

arXiv:1802.08802v1cs.AI

TL;DR

Web-interface RL agents must discover long action sequences despite extremely sparse rewards, while existing assistant systems are limited to machine-readable APIs. The paper uses demonstrations to induce workflows that constrain exploration, and reports new state-of-the-art results with only 3–10 demonstrations per task.

  • Problem

    Web-interface RL aims to extend AI assistants beyond machine-readable APIs, but tasks can have extremely sparse rewards and many possible actions.

  • Method

    The method uses demonstrations to induce workflows that constrain exploration to action sequences analogous to expert actions, alongside a neural policy for web interfaces.

  • Results

    The system achieves new state-of-the-art results on web interaction tasks, with much higher MiniWoB success rates using only 3–10 demonstrations per task versus prior results using 10 minutes of demonstrations.

  • Takeaways & Limitations

    Workflow-guided exploration enables learning complex policies from sparse rewards and very few demonstrations while protecting the expressive neural policy from overfitting.

  • Takeaways & Limitations

    Workflows ignore environment-state differences, cannot express some actions, and may fail to select the correct workflow for a goal; structured inputs are also required for the current constraint language.

Abstract

from arXiv · show

Reinforcement learning (RL) agents improve through trial-and-error, but when reward is sparse and the agent cannot discover successful action sequences, learning stagnates. This has been a notable problem in training deep RL agents to perform web-based tasks, such as booking flights or replying to emails, where a single mistake can ruin the entire sequence of actions. A common remedy is to "warm-start" the agent by pre-training it to mimic expert demonstrations, but this is prone to overfitting. Instead, we propose to constrain exploration using demonstrations. From each demonstration, we induce high-level "workflows" which constrain the allowable actions at each time step to be similar to those in the demonstration (e.g., "Step 1: click on a textbox; Step 2: enter some text"). Our exploration policy then learns to identify successful workflows and samples actions that satisfy these workflows. Workflows prune out bad exploration directions and accelerate the agent's ability to discover rewards. We use our approach to train a novel neural policy designed to handle the semi-structured nature of websites, and evaluate on a suite of web tasks, including the recent World of Bits benchmark. We achieve new state-of-the-art results, and show that workflow-guided exploration improves sample efficiency over behavioral cloning by more than 100x.

1 INTRODUCTION

The paper addresses sparse-reward web RL by using demonstrations to constrain exploration rather than directly imitating them. It combines workflow-guided exploration with DOMNET and reports higher success on web tasks using few demonstrations.

  • Motivation: Web RL is difficult because large action spaces and coordinated action sequences make successful trajectories rare under sparse rewards.A single incorrect click or typed value can prevent reward discovery.
  • Motivation: Behavioral cloning can overfit because demonstrations cover only a small portion of websites’ diverse state spaces.Prior work found that behavioral-cloning warm starts often failed to improve over pure RL.
  • Workflow-guided exploration: WGE uses demonstrations to constrain exploration by pruning bad directions while avoiding direct exposure of the neural policy to demonstrations.This permits a more sophisticated neural policy with reduced overfitting risk.
  • Workflow-guided exploration: A workflow is a high-level, environment-blind sequence that constrains allowable actions without specifying the exact webpage element or text target.For example, it can require clicking an email title, forwarding, typing an address, and sending.
  • Framework: WGE induces workflow lattices, learns which workflows to select, stores successful episodes, and trains a neural policy from the resulting replay buffer.The framework’s workflow policy explores first, while the neural policy learns from reward-earning episodes.
  • Architecture and evaluation: DOMNET is designed for web states that combine structured HTML with unstructured language and images by reasoning relationally over tree-structured websites.The evaluation covers MiniWoB, an Alaska Airlines flight-booking interface, and additional tasks with noise, language variation, and longer horizons.
  • Architecture and evaluation: Using only 3–10 demonstrations per task, the system achieves much higher success rates and new state-of-the-art results compared with MiniWoB results using approximately 200 demonstrations on average.The comparison is against prior MiniWoB results that used 10 minutes of demonstrations per task.

2 SETUP

The setup considers web RL with delayed, sparse rewards and large state-action spaces. Goals and webpage states are represented explicitly, while actions are restricted to clicking DOM elements or typing goal-derived strings.

  • RL setting: The objective is to maximize expected discounted return from trial-and-error episodes.Episodes consist of observed states, selected actions, transitions, and rewards.
  • RL setting: The agent receives reward only at episode end, with high reward for few trajectories and uniformly low reward otherwise.This makes positive-reward episodes difficult to discover in large state and action spaces.
  • Web task representation: Each task supplies a structured or natural-language goal, and the state combines that goal with the webpage’s DOM tree.The DOM tree represents the current webpage state.
  • Web task representation: The action space contains Click(e) and Type(e,t), where e is a DOM leaf and t is a string derived from the goal.Typing may use a structured-goal value or consecutive natural-language tokens.

3 INDUCING WORKFLOWS FROM DEMONSTRATIONS

The method induces workflow lattices from demonstrations by enumerating compatible action constraints at each time step. Shortcuts handle unnecessary or collapsible demonstration actions, while policy learning balances overly specific and overly general steps.

  • Workflow representation: A workflow step maps a state to a constrained set of actions similar to the demonstrated action.For example, Click(Tag("img")) permits clicking any DOM element with an img tag.
  • Lattice induction: For each demonstration step, the method enumerates compatible workflow steps and forms their cross product as paths in a workflow lattice.Each lattice path represents one induced workflow.
  • Lattice induction: Shortcut steps skip unnecessary actions or collapse consecutive actions into an equivalent single action.This allows induced workflow lengths to differ from demonstration lengths.
  • Constraint selection: Workflow steps vary in usefulness because highly specific constraints overfit demonstrations whereas highly general constraints admit irrelevant actions.The workflow policy learns which steps to use.

4 WORKFLOW EXPLORATION POLICY

The workflow exploration policy selects demonstrations and workflow steps, then samples compatible actions while remaining independent of environment state. Reinforcement learning trains this policy, and successful episodes support neural-policy training.

  • Episode generation: At episode start, the policy selects a demonstration associated with a similar goal.Demonstrations are sampled according to goal similarity.
  • Episode generation: At each time step, the workflow policy samples a workflow step from learned parameters and uniformly samples an action from that step’s allowed set.The policy’s workflow-step distribution is parameterized by ψz,t,d.
  • Episode generation: The workflow policy’s episode probability factors over demonstration selection, environment transitions, action compatibility, and workflow-step selection.This factorization describes the probability of an explored episode.
  • Policy properties: Because its decisions depend only on the demonstration and time step, the workflow policy uses fewer parameters and can learn quickly while reducing overfitting.Its environment-blindness prevents it from solving the task directly but helps identify useful behaviors.
  • Training: REINFORCE trains the workflow policy from episode returns using a baseline for variance reduction.The gradient estimate is unbiased, with Gt as the time-step return and vd,t as the baseline.
  • Training: Positive-reward episodes enter a replay buffer used to train the neural policy.Neural-policy updates combine on-policy and replay-buffer episodes using A2C.

5 NEURAL POLICY

The neural policy combines DOM-aware relational representations with on-policy and replay-based learning. DOMNET embeds goals and DOM elements, models spatial and hierarchical relationships, and outputs action and value predictions.

  • Training: Successful workflow-policy episodes enter a replay buffer for training the neural policy.On-policy and off-policy A2C updates both contribute to learning; replay contains only positively rewarded episodes.
  • Model architecture: DOMNET embeds DOM elements and the input goal, applies attention, and produces an action distribution and value function.The architecture is designed to represent websites’ tree-structured HTML while supporting policy and critic outputs.
  • DOM embedding: DOMNET captures interactions between related DOM elements so elements such as checkboxes and labels can exchange information.The embedder is motivated by relational and graph-embedding approaches.
  • DOM embedding: Spatial neighbors are DOM elements within 30 pixels, whose base embeddings are summed to form a spatial neighbor representation.Each element’s base embedding concatenates attributes such as tag, classes, and text.
  • DOM embedding: Depth-k tree neighbors are aggregated after a learnable affine transformation and max pooling, with higher-depth neighbors treated as more related.Tree-neighbor representations across depths are concatenated into the DOM embedding.

6 EXPERIMENTS

The evaluation covers three suites of interactive web tasks: MiniWoB, the newly constructed MiniWoB++ benchmark, and the Alaska Airlines flight-booking interface.

  • Evaluation suites: The experiments evaluate workflow-guided exploration and DOMNET across three suites of interactive web tasks.The suites are MiniWoB, MiniWoB++, and Alaska.

1. MiniWoB: the MiniWoB benchmark of Shi et al. (2017)

Experiments evaluate DOMNET and workflow-guided exploration on MiniWoB, MiniWoB++, and Alaska tasks under sparse-reward web interaction settings. The approach improves benchmark performance, handles difficult task variations, and uses far fewer demonstrations than behavioral cloning.

  • Benchmarks: MiniWoB++ adds stochastic environments and natural-language variation to the evaluation suite.The benchmark was constructed to study challenges absent from the original MiniWoB tasks.
  • Experimental setting: The experiments use a 160px × 210px web environment with text goals and mostly terminal rewards of +1 for success or −1 for failure.Agents interact through Selenium, and partial rewards are disabled for consistency.
  • Experimental setting: The study filters MiniWoB to 40 tasks requiring DOM clicks and typing strings from the goal, using 10 demonstrations per task.The original benchmark contains 80 tasks; demonstrations record mouse and keyboard events alongside DOM state.
  • Main results: DOMNET+BC+RL empirically improves success rates over SHI17 on most MiniWoB tasks, while DOMNET+WGE performs better on difficult tasks.SHI17 uses behavioral cloning and RL with substantially more demonstrations, whereas DOMNET+WGE uses 10 demonstrations.
  • MiniWoB++ results: 42% absolute success rate is the average improvement of DOMNET+WGE over DOMNET+BC+RL.The comparison identifies premature termination and cyclic behavior as common BC+RL failure modes mitigated by WGE.
  • Natural-language inputs: 93% success rate is achieved by WGE on unseen natural-language utterances in the email-inbox-nl task.Training gives the workflow policy structured goals and utterances, while the neural policy receives only utterances.
  • Alaska results: 0.97 average reward is achieved on Alaska-Shi17 with 1 demonstration, compared with 0.57 from the prior best result using around 80 demonstrations.On a harder Alaska version, the method achieves 0.86 average reward with 10 demonstrations.
  • Sample efficiency: Over 100x sample efficiency improvement is obtained over behavioral cloning in demonstrations: WGE with 10 demonstrations exceeds BC+RL with 1000 on every evaluated task.The comparison uses test reward on several of the hardest tasks.

7 DISCUSSION

The discussion contrasts workflow-guided exploration with prior approaches to sparse-reward web RL and frames workflows as demonstration-derived action constraints. The framework combines targeted demonstrations, abstraction, and expressive policies while limiting demonstrations’ exposure to exploration.

  • Prior web-agent work includes user-specified or demonstration-inferred programs and policies learned from scratch or warm-started from demonstrations.
  • Behavioral cloning and related demonstration-training methods can overfit complex website states, while sparse rewards have prevented successful learning in prior work.
  • Workflow-guided exploration defines demonstration neighborhoods by action similarity rather than state similarity, which is easier to specify for web interactions.
  • Unlike manually programmed constraints or constraints used only for planning or test-time knowledge, this work automatically induces constraints from demonstrations and uses them for exploration.
  • The framework uses demonstrations only for exploration, protecting an expressive neural policy from overfitting while enabling complex policies from sparse rewards and few demonstrations.

A CONSTRAINT LANGUAGE FOR WORKFLOW STEPS

The workflow constraint language is intentionally minimal and general, using compositional element selectors to specify permissible clicks and typing actions. It limits nesting to control combinatorial growth and derives literal selector values from demonstration states.

  • The language supports Click and two Type forms, including typing literals or goal-field values into elements selected by elementSet.
  • elementSet selects HTML elements by tag, text, substring, proximity, horizontal or vertical alignment, and optional class filtering.
  • The language limits nested elementSet applications to three, requiring the third application to be a Class filter.
  • When workflow steps are induced, valid tag, string, and class values are extracted from the corresponding demonstration state.

B EXAMPLES OF LEARNED WORKFLOWS

The learned workflows translate web tasks into sequences of abstract click and type constraints over page elements. Examples cover login, email forwarding, search, and flight booking, with selectors tied to goals and spatial or textual relationships.

  • Login: The login workflow types goal fields for username and password into input elements.
  • Email forwarding: The email-forwarding workflow locates the sender’s message, selects Forward, and types the recipient into a nearby subject-related field.
  • Search: The search workflow types the target into a button-near element, then clicks navigation and the target text to reach the requested result.
  • Flight booking: The flight-booking workflow fills departure and destination cities, selects dates and seat type, and submits through text, proximity, row, column, and class selectors.
  • Flight booking: Additional flight steps select the returning day, adjust passenger count, choose first class, and activate the final button.

C DETAILS OF THE NEURAL MODEL ARCHITECTURE

DOMNET embeds webpage structure and goals, then applies attentions that connect page elements with goal units. It produces target-element, typed-string, action-type, and value-function outputs for the neural policy.

  • Embeddings: The model embeds DOM elements and goal units, representing structured goals as key-value pairs and natural-language goals with an LSTM.
  • Attentions: A DOM context is formed by max-pooling and attention over DOM embeddings, producing a weighted representation of the page.
  • Attentions: Goal contexts use DOM context as a query over goal embeddings, with sentinel attention allowing the model to ignore the goal when appropriate.
  • Attentions: DOM element selection attends over element embeddings using a query formed from DOM and goal contexts, yielding a distribution over target elements.
  • Action selection: For a selected element, the model attends over goal embeddings to predict fields or token spans and uses the same query to classify click versus type.
  • Model architecture: The architecture ultimately produces an action distribution πn(a|s) and a value function V(s), the critic.
Loading 1802.08802v1…