Title: REINFORCEMENT LEARNING ON WEB INTERFACES USING WORKFLOW-GUIDED EXPLORATION

Abstract: 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 "warmstart" 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:

We are interested in training reinforcement learning (RL) agents to use the Internet (e.g., to book flights or reply to emails) by directly controlling a web browser. Such systems could expand the capabilities of AI personal assistants (Stone & Soper, 2014) , which are currently limited to interacting with machine-readable APIs, rather than the much larger world of human-readable web interfaces.

Reinforcement learning agents could learn to accomplish tasks using these human-readable web interfaces through trial-and-error (Sutton & Barto, 1998) . But this learning process can be very slow in tasks with sparse reward, where the vast majority of naive action sequences lead to no reward signal (Vecerik et al., 2017; Nair et al., 2017) . This is the case for many web tasks, which involve a large action space (the agent can type or click anything) and require a well-coordinated sequence of actions to succeed.

A common countermeasure in RL is to pre-train the agent to mimic expert demonstrations via behavioral cloning (Pomerleau, 1991; Kim et al., 2013) , encouraging it to take similar actions in similar states. But in environments with diverse and complex states such as websites, demonstrations may cover only a small slice of the state space, and it is difficult to generalize beyond these states (overfitting). Indeed, previous work has found that warm-starting with behavioral cloning often fails to improve over pure RL (Shi et al., 2017) . At the same time, simple strategies to combat overfitting (e.g. using fewer parameters or regularization) cripple the policy's flexibility (Bitzer et al., 2010) , which is required for complex spatial and structural reasoning in user interfaces.

In this work, we propose a different method for leveraging demonstrations. Rather than training an agent to directly mimic them, we use demonstrations to constrain exploration. By pruning away bad exploration directions, we can accelerate the agent's ability to discover sparse rewards. Furthermore, Figure 1 : Workflow-guided exploration (WGE). After inducing workflow lattices from demonstrations, the workflow policy π w performs exploration by sampling episodes from sampled workflows. Successful episodes are saved to a replay buffer, which is used to train the neural policy π n .

because the agent is not directly exposed to demonstrations, we are free to use a sophisticated neural policy with a reduced risk of overfitting.

To constrain exploration, we employ the notion of a "workflow" (Deka et al., 2016) . For instance, given an expert demonstration of how to forward an email, we might infer the following workflow:

Click an email title → Click a "Forward" button → Type an email address into a textbox → Click a "Send" button This workflow is more high-level than an actual policy: it does not tell us exactly which email to click or which textbox to type into, but it helpfully constrains the set of actions at each time step. Furthermore, unlike a policy, it does not depend on the environment state: it is just a sequence of steps that can be followed blindly. In this sense, a workflow is environment-blind. The actual policy certainly should not be environment-blind, but for exploration, we found environment-blindness to be a good inductive bias.

To leverage workflows, we propose the workflow-guided exploration (WGE) framework as illustrated in Figure 1: 1. For each demonstration, we extract a lattice of workflows that are consistent with the actions observed in the demonstration (Section 3).

2. We then define a workflow exploration policy π w (Section 4), which explores by first selecting a workflow, and then sampling actions that fit the workflow. This policy gradually learns which workflow to select through reinforcement learning.

3. Reward-earning episodes discovered during exploration enter a replay buffer, which we use to train a more powerful and expressive neural network policy π n (Section 5).

A key difference between the web and traditional RL domains such as robotics (Atkeson & Schaal, 1997) or game-playing (Bellemare et al., 2013) is that the state space involves a mix of structured (e.g. HTML) and unstructured inputs (e.g. natural language and images). This motivates us to propose a novel neural network policy (DOMNET), specifically designed to perform flexible relational reasoning over the tree-structured HTML representation of websites.

We evaluate workflow-guided exploration and DOMNET on a suite of web interaction tasks, including the MiniWoB benchmark of (Shi et al., 2017) , the flight booking interface for Alaska Airlines, and a new collection of tasks that we constructed to study additional challenges such as noisy environments, variation in natural language, and longer time horizons. Compared to previous results on MiniWoB Shi et al. (2017) , which used 10 minutes of demonstrations per task (approximately 200 demonstrations on average), our system achieves much higher success rates and establishes new state-of-the-art results with only 3-10 demonstrations per task.

2. SETUP:

In the standard reinforcement learning setup, an agent learns a policy π(a|s) that maps a state s to a probability distribution over actions a. At each time step t, the agent observes an environment state s t and chooses an action a t , which leads to a new state s t+1 and a reward r t = r(s t , a t ). The goal is to maximize the expected return E[R], where R = t γ t r t+1 and γ is a discount factor. Typical reinforcement learning agents learn through trial-and-error: rolling out episodes (s 1 , a 1 , . . . , s T , a T ) and adjusting their policy based on the results of those episodes.

We focus on settings where the reward is delayed and sparse. Specifically, we assume that (1) the agent receives reward only at the end of the episode, and (2) the reward is high (e.g., +1) for only a small fraction of possible trajectories and is uniformly low (e.g., -1) otherwise. With large state and action spaces, it is difficult for the exploration policy to find episodes with positive rewards, which prevents the policy from learning effectively.

We further assume that the agent is given a goal g, which can either be a structured key-value mapping (e.g., {task: forward, from: Bob, to: Alice}) or a natural language utterance (e.g., "Forward Bob's message to Alice"). The agent's state s consists of the goal g and the current state of the web page, represented as a tree of elements (henceforth DOM tree). We restrict the action space to click actions Click(e) and type actions Type(e,t), where e is a leaf element of the DOM tree, and t is a string from the goal g (a value from a structured goal, or consecutive tokens from a natural language goal). Figure 2 shows an example episode for an email processing task. The agent receives +1 reward if the task is completed correctly, and -1 reward otherwise.

3. INDUCING WORKFLOWS FROM DEMONSTRATIONS:

Given a collection of expert demonstrations d = (s 1 , ã1 , . . . , sT , ãT ), we would like explore actions a t that are "similar" to the demonstrated actions ãt . Workflows capture this notion of similarity by specifying a set of similar actions at each time step. Formally, a workflow z 1:T is a sequence of workflow steps, where each step z t is a function that takes a state s t and returns a constrained set z t (s t ) of similar actions. We use a simple compositional constraint language (Appendix A) to describe workflow steps. For example, with z t = Click(Tag("img")), the set z t (s t ) contains click actions on any DOM element in s t with tag img.

We induce a set of workflows from each demonstration d = (s 1 , ã1 , . . . , sT , ãT ) as follows. For each time step t, we enumerate a set Z t of all possible workflow steps z t such that ãt ∈ z t (s t ). The set of workflows is then the cross product Z 1 × • • • × Z T of the steps. We can represent the induced workflows as paths in a workflow lattice as illustrated in Figure 2 .

To handle noisy demonstrations where some actions are unnecessary (e.g., when the demonstrator accidentally clicks on the background), we add shortcut steps that skip certain time steps. We also add shortcut steps for any consecutive actions that can be collapsed into a single equivalent action (e.g., collapsing two type actions on the same DOM element into a single Type step). These shortcuts allow the lengths of the induced workflows to differ from the length of the demonstration. We henceforth ignore these shortcut steps to simplify the notation.

The induced workflow steps are not equally effective. For example in Figure 2 , the workflow step Click(Near(Text("Bob"))) (Click an element near text "Bob") is too specific to the demonstration scenario, while Click(Tag("div")) (Click on any <div> element) is too general and covers too many irrelevant actions. The next section describes how the workflow policy π w learns which workflow steps to use.

Click(Near( Text("Bob")))

Click(Near( Like(Field("from"))))

Click(Near( Text("Forward")))

Click(And(Tag("img"), Class("icon")))

Type(SameRow( Like("to")), Field("to"))

Type(Tag("input"), Field("to"))

Type(Tag("input"), Field(*)) Click(Tag("div"))

Click(Tag("span"))

Click(Near(Tag("div")))

Demonstration: goal = {task: forward, from: Bob, to: Alice} Workflow lattice:

s 1 s 2 s 3 s 4 a 1 a 2 a 3 a 4

Figure 2: From each demonstration, we induce a workflow lattice based on the actions in that demonstration. Given a new environment, the workflow policy samples a workflow (a path in the lattice, as shown in bold) and then samples actions that fit the steps of the workflow.

4. WORKFLOW EXPLORATION POLICY:

Our workflow policy interacts with the environment to generate an episode in the following manner. At the beginning of the episode, the policy conditions on the provided goal g, and selects a demonstration d that carried out a similar goal:

d ∼ p(d|g) ∝ exp[sim(g, g d )]

(1) where sim(g, g d ) measures the similarity between g and the goal g d of demonstration d. In our tasks, we simply let sim(g, g d ) be 1 if the structured goals share the same keys, and -∞ otherwise.

Then, at each time step t with environment state s t , we sample a workflow step z t according to the following distribution:

z t ∼ π w (z|d, t) ∝ exp(ψ z,t,d ),

(2) where each ψ z,t,d is a separate scalar parameter to be learned. Finally, we sample an action a t uniformly from the set z t (s t ).

EQUATION

The overall probability of exploring an episode e = (s 1 , a 1 , . . . , s T , a T ) is then:

EQUATION

where p(s t |s t-1 , a t-1 ) is the (unknown) state transition probability.

Note that π w (z|d, t) is not a function of the environment states s t at all. Its decisions only depend on the selected demonstration and the current time t. This environment-blindness means that the workflow policy uses far fewer parameters than a state-dependent policy, enabling it to learn more quickly and preventing overfitting. Due to environment-blindness, the workflow policy cannot solve the task, but it quickly learns to certain good behaviors, which can help the neural policy learn.

To train the workflow policy, we use a variant of the REINFORCE algorithm (Williams, 1992; Sutton & Barto, 1998) . In particular, after rolling out an episode e = (s 1 , a 1 , . . . , s T , a T ), we approximate the gradient using the unbiased estimate

EQUATION

where G t is the return at time step t and v d,t is a baseline term for variance reduction.

Sampled episodes from the workflow policy that receive a positive reward are stored in a replay buffer, which will be used for training the neural policy π n .

5. NEURAL POLICY:

As outlined in Figure 1 , the neural policy is learned using both on-policy and off-policy updates (where episodes are drawn from the replay buffer). Both updates use A2C, the synchronous version of the advantage actor-critic algorithm (Mnih et al., 2016) . Since only episodes with reward +1 enter the replay buffer, the off-policy updates behave similarly to supervised learning on optimal trajectories. Furthermore, successful episodes discovered during on-policy exploration are also added to the replay buffer.

Model architecture. We propose DOMNET, a neural architecture that captures the spatial and hierarchical structure of the DOM tree. As illustrated in Figure 5 , the model first embeds the DOM elements and the input goal, and then applies a series of attentions on the embeddings to finally produce a distribution over actions π n (a|s) and a value function V (s), the critic. We highlight our novel DOM embedder, and defer other details to Appendix C.

We design our DOM embedder to capture the various interactions between DOM elements, similar to recent work in graph embeddings (Kipf & Welling, 2017; Pham et al., 2017; Hamilton et al., 2017) . In particular, DOM elements that are "related" (e.g., a checkbox and its associated label) should pass their information to each other.

To embed a DOM element e, we first compute the base embedding v e base by embedding and concatenating its attributes (tag, classes, text, etc.). In order to capture the relationships between DOM elements, we next compute two types of neighbor embeddings:

1. We define spatial neighbors of e to be any element e within 30 pixels from e, and then sum up their base embeddings to get the spatial neighbor embedding v e spatial . 2. We define depth-k tree neighbors of e to be any element e such that the least common ancestor of e and e in the DOM tree has depth at most k. Intuitively, tree neighbors of a higher depth are more related. For each depth k, we apply a learnable affine transformation f on the base embedding of each depth-k tree neighbor e , and then apply max pooling to get v e tree[k] = max f (v e base ). We let the tree neighbor embedding v e tree be the concatenation of v e tree[k] for k = 3, 4, 5, 6.

Finally, we define the goal matching embedding v e match to be the sum of the embeddings of all words in e that also appear in the goal. The final embedding v e DOM of e is the concatenation of the four embeddings [v e base ; v e spatial ; v e tree ; v e match ].

6. EXPERIMENTS 6.1 TASK SETUPS:

We evaluate our approach on three suites of interactive web tasks:

1. MiniWoB: the MiniWoB benchmark of Shi et al. (2017) 2. MiniWoB++: a new set of tasks that we constructed to incorporate additional challenges not present in MiniWoB, such as stochastic environments and variation in natural language.

3. Alaska: the mobile flight booking interface for Alaska Airlines, inspired by the FormWoB benchmark of Shi et al. (2017) .

We describe the common task settings of the MiniWoB and MiniWoB++ benchmarks, and defer the description of the Alaska benchmark to Section 6.3.3. Environment. Each task contains a 160px × 210px environment and a goal specified in text. The majority of the tasks return a single sparse reward at the end of the episode; either +1 (success) or -1 (failure). For greater consistency among tasks, we disabled all partial rewards in our experiments.

The agent has access to the environment via a Selenium web driver interface.

The public MiniWoB benchmark1 contains 80 tasks. We filtered for the 40 tasks that only require actions in our action space, namely clicking on DOM elements and typing strings from the input goal. Many of the excluded tasks involve somewhat specialized reasoning, such as being able to compute the angle between two lines, or solve algebra problems. For each task, we used Amazon Mechanical Turk to collect 10 demonstrations, which record all mouse and keyboard events along with the state of the DOM when each event occurred.

Evaluation metric. We report success rate: the percentage of test episodes with reward +1. Since we have removed partial rewards, success rate is a linear scaling of the average reward, and is equivalent to the definition of success rate in Shi et al. (2017) .

6.2. MAIN RESULTS:

We compare the success rates across the MiniWoB tasks of the following approaches:

• SHI17: the system from Shi et al. (2017) , pre-trained with behavioral cloning on 10 minutes of demonstrations (approximately 200 demonstrations on average) and fine-tuned with RL. Unlike DOMNET, this system primarily uses a pixel-based representation of the state.2 

• DOMNET+BC+RL: our proposed neural policy, DOMNET, but pre-trained with behavioral cloning on 10 demonstrations and fine-tuned with RL, like SHI17. During behavioral cloning, we apply early stopping based on the reward on a validation set. • DOMNET+WGE: our proposed neural policy, DOMNET, trained with workflow-guided exploration on 10 demonstrations.

For DOMNET+BC+RL and DOMNET+WGE, we report the test success rate at the time step where the success rate on a validation set reaches its maximum.

The results are shown in Figure 3 . By comparing SHI17 with DOMNET+BC+RL, we can roughly evaluate the contribution of our new neural architecture DOMNET, since the two share the same training procedure (BC+RL). While SHI17 also uses the DOM tree to compute text alignment features in addition to the pixel-level input, our DOMNET uses the DOM structure more explicitly. We find DOMNET+BC+RL to empirically improve the success rate over SHI17 on most tasks.

By comparing DOMNET+BC+RL and DOMNET+WGE, we find that workflow-guided exploration enables DOMNET to perform even better on the more difficult tasks, which we analyze in the next section. Some of the workflows that the workflow policy π w learns are shown in Appendix B.

6.3 ANALYSIS

6.3.1. MINIWOB++ BENCHMARK:

We constructed and released the MiniWoB++ benchmark of tasks to study additional challenges a web agent might encounter, including: longer time horizons (click-checkboxes-large), "soft" reasoning about natural language (click-checkboxes-soft), and stochastically varying layouts (multiorderings, multi-layouts). Table 1 lists the tasks and their time horizons (number of steps needed for a perfect policy to carry out the longest goal) as a crude measure of task complexity.

We first compare the performance of DOMNET trained with BC+RL (baseline) and DOMNET trained with WGE (our full approach). The proposed WGE model outperforms the BC+RL model by an average of 42% absolute success rate. We analyzed their behaviors and noticed two common failure modes of training with BC+RL that are mitigated by instead training with WGE:

1. The BC+RL model has a tendency to take actions that prematurely terminate the episode (e.g., hitting "Submit" in click-checkboxes-large before all required boxes are checked).

One likely cause is that these actions occur across all demonstrations, while other nonterminating actions (e.g., clicking different checkboxes) vary across demonstrations. 2. The BC+RL model occasionally gets stuck in cyclic behavior such as repeatedly checking and unchecking the same checkbox. These failure modes stem from overfitting to parts of the demonstrations, which WGE avoids.

Next, we analyze the workflow policy π w learned by WGE. The workflow policy π w by itself is too simplistic to work well at test time for several reasons:

1. Workflows ignore environment state and therefore cannot respond to the differences in the environment, such as the different layouts in multi-layouts. 2. The workflow constraint language lacks the expressivity to specify certain actions, such as clicking on synonyms of a particular word in click-checkboxes-soft. 3. The workflow policy lacks expressivity to select the correct workflow for a given goal.

Nonetheless the workflow policy π w is sufficiently constrained to discover reward some of the time, and the neural policy π n is able to learn the right behavior from such episodes. As such, the neural policy can achieve high success rates even when the workflow policy π w performs poorly.

6.3.2. NATURAL LANGUAGE INPUTS:

While MiniWoB tasks provide structured goals, we can also apply our approach to natural language goals. We collected a training dataset using the overnight data collection technique (Wang et al., 2015) . In the email-inbox-nl task, we collected natural language templates by asking annotators to paraphrase the task goals (e.g., "Forward Bob's message to Alice" → "Email Alice the email I got from Bob") and then abstracting out the fields ("Email <TO> the email I got from <FROM>").

During training, the workflow policy π w receives states with both the structured goal and the natural language utterance generated from a random template, while the neural policy π n receives only the utterance. At test time, the neural policy is evaluated on unseen utterances. The results in Table 1 show that the WGE model can learn to understand natural language goals (93% success rate).

Note that the workflow policy needs access to the structured inputs only because our constraint language for workflow steps operates on structured inputs. The constraint language could potentially be modified to work with utterances directly (e.g., After("to") extracts the utterance word after "to"), but we leave this for future work.

6.3.3. SCALING TO REAL WORLD TASKS:

We applied our approach on the Alaska benchmark, a more realistic flight search task on the Alaska Airlines mobile site inspired by the FormWoB task in Shi et al. (2017) . In this task, the agent must complete the flight search form with the provided information (6-7 fields). We ported the web page to the MiniWoB framework with a larger 375px × 667px screen, replaced the server backend with a surrogate JavaScript function, and clamped the environment date to March 1, 2017.

Following Shi et al. (2017) , we give partial reward based on the fraction of correct fields in the submitted form if all required fields are filled in. Despite this partial reward, the reward is still extremely sparse: there are over 200 DOM elements (compared to ≈ 10-50 in MiniWoB tasks), and a typical episode requires at least 11 actions involving various types of widgets such as autocompletes and date pickers. The probability that a random agent gets positive reward is less than 10 -20 .

We first performed experiments on Alaska-Shi17, a clone of the original Alaska Airlines task in Shi et al. (2017) , where the goal always specifies a roundtrip flight (two airports and two dates). On their dataset, our approach, using only 1 demonstration, achieves an average reward of 0.97, compared to their best result of 0.57, which uses around 80 demonstrations.

Our success motivated us to test on a more difficult version of the task which additionally requires selecting flight type (a checkbox for one-way flight), number of passengers (an increment-decrement counter), and seat type (hidden under an accordion). We achieve an average reward of 0.86 using 10 demonstrations. This demonstrates our method can handle long horizons on real-world websites.

6.3.4. SAMPLE EFFICIENCY:

To evaluate the demonstration efficiency of our approach, we compare DOMNET+WGE with DOMNET+BC+RL trained on increased numbers of demonstrations. We compare DOM-NET+WGE trained on 10 demonstrations with DOMNET+BC+RL on 10, 100, 300, and 1000 demonstrations. The test rewards3 on several of the hardest tasks are summarized in Figure 4 .

Increasing the number of demonstrations improves the performance of BC+RL, as it helps prevent overfitting. However, on every evaluated task, WGE trained with only 10 demonstrations still achieves much higher test reward than BC+RL with 1000 demonstrations. This corresponds to an over 100x sample efficiency improvement of our method over behavioral cloning in terms of the number of demonstrations.

7. DISCUSSION:

Learning agents for the web. Previous work on learning agents for web interactions falls into two main categories. First, simple programs may be specified by the user (Yeh et al., 2009) or may be inferred from demonstrations (Allen et al., 2007) . Second, soft policies may be learned from scratch or "warm-started" from demonstrations (Shi et al., 2017) . Notably, sparse rewards prevented Shi et al. (2017) from successfully learning, even when using a moderate number of demonstrations.

While policies have proven to be more difficult to learn, they have the potential to be expressive and flexible. Our work takes a step in this direction.

Sparse rewards without prior knowledge. Numerous works attempt to address sparse rewards without incorporating any additional prior knowledge. Exploration methods (Osband et al., 2016; Chentanez et al., 2005; Weber et al., 2017) help the agent better explore the state space to encounter more reward; shaping rewards (Ng et al., 1999) directly modify the reward function to encourage certain behaviors; and other works (Jaderberg et al., 2016; Andrychowicz et al., 2017) augment the reward signal with additional unsupervised reward. However, without prior knowledge, helping the agent receive additional reward is difficult in general.

Imitation learning. Various methods have been proposed to leverage additional signals from experts. For instance, when an expert policy is available, methods such as DAGGER (Ross et al., 2011) and AGGREVATE (Ross & Bagnell, 2014; Sun et al., 2017) can query the expert policy to augment the dataset for training the agent. When only expert demonstrations are available, inverse reinforcement learning methods (Abbeel & Ng, 2004; Ziebart et al., 2008; Finn et al., 2016; Ho & Ermon, 2016; Baram et al., 2017) infer a reward function from the demonstrations without using reinforcement signals from the environment.

The usual method for incorporating both demonstrations and reinforcement signals is to pre-train the agent with demonstrations before applying RL. Recent work extends this technique by (1) introducing different objective functions and regularization during pre-training, and (2) mixing demonstrations and rolled-out episodes during RL updates (Hosu & Rebedea, 2016; Hester et al., 2018; Vecerik et al., 2017; Nair et al., 2017) .

Instead of training the agent on demonstrations directly, our work uses demonstrations to guide exploration. The core idea is to explore trajectories that lie in a "neighborhood" surrounding an expert demonstration. In our case, the neighborhood is defined by a workflow, which only permits action sequences analogous to the demonstrated actions. Several previous works also explore neighborhoods of demonstrations via reward shaping (Brys et al., 2015; Hussein et al., 2017) or off-policy sampling (Levine & Koltun, 2013) . One key distinction of our work is that we define neighborhoods in terms of action similarity rather than state similarity. This distinction is particularly important for the web tasks: we can easily and intuitively describe how two actions are analogous (e.g., "they both type a username into a textbox"), while it is harder to decide if two web page states are analogous (e.g., the email inboxes of two different users will have completely different emails, but they could still be analogous, depending on the task.)

Hierarchical reinforcement learning. Hierarchical reinforcement learning (HRL) methods decompose complex tasks into simpler subtasks that are easier to learn. Main HRL frameworks include abstract actions (Sutton et al., 1999; Konidaris & Barto, 2007; Hauser et al., 2008) , abstract partial policies (Parr & Russell, 1998) , and abstract states (Roderick et al., 2017; Dietterich, 1998; Li et al., 2006) . These frameworks require varying amounts of prior knowledge. The original formulations required programmers to manually specify the decomposition of the complex task, while Andreas et al. (2016) only requires supervision to identify subtasks, and Bacon et al. (2017) ; Daniel et al. (2016) learn the decomposition fully automatically, at the cost of performance.

Within the HRL methods, our work is closest to Parr & Russell (1998) and the line of work on constraints in robotics (Phillips et al., 2016; Perez-D'Arpino & Shah, 2017) . The work in Parr & Russell (1998) specifies partial policies, which constrain the set of possible actions at each state, similar to our workflow items. In contrast to previous instantiations of the HAM framework (Andre, 2003; Marthi & Guestrin, 2005) , which require programmers to specify these constraints manually, our work automatically induces constraints from user demonstrations, which do not require special skills to provide. Summary. Our workflow-guided framework represents a judicious combination of demonstrations, abstractions, and expressive neural policies. We leverage the targeted information of demonstrations and the inductive bias of workflows. But this is only used for exploration, protecting the expressive neural policy from overfitting. As a result, we are able to learn rather complex policies from a very sparse reward signal and very few demonstrations.

search-engine Enter "Cheree" and press "Search", then find and click the 5th search result.

{target: Cheree, rank: 5} Type(Near(Tag("button")),Field( * ))

Click(Text("Search")) Click(Like(">")) Click(Text(Field("target"))) Alaska {departure city: Tampa, destination city: Seattle, ticket type: return flight, departure day: 6, returning Day: 16, passengers: 3, seat type: first } Type(And(Near(Like("From")),Class("text-input-pad")),Field("departure city")) Click(And(SameRow(Tag("label")),Class(["input-selection","last"]))) Type(And(Near(Like("To")),Class("text-input-pad")),Field("destination city"))

Click(Like(Field("destination city"))) Click(And(SameCol(Tag("a")),Class(["calbg","text-input"])))

Click(Text(Field("departure day"))) Click(Like("Done")) Click(Near(Like("Return")),Class(["calbg","text-input"]))

Click(Text(Field("returning day"))) Click(Like("Done")) Click(Like("+")) Click(Like("+")) Click(Tag("h2")) Click(Text("First")) Click(And(Near(Tag("body")),Class("button")))

C DETAILS OF THE NEURAL MODEL ARCHITECTURE:

Embeddings. From the input state, we first embed the DOM elements e and the goal units u, where u is a key-value pair for structured goals and a token for natural language goals. The process for computing the embedding v e DOM of DOM elements is already described in Section 5. For the goal unit embedding v u goal , we embed each key-value pair as the sum of word embeddings, and embed natural language goals with an LSTM.

Attentions. After obtaining the embedding v e DOM of each DOM element e and v u goal of each goal unit u, we apply a series of attentions to relate the DOM elements with the goal:

1. DOM context: we applied max-pooling on v e DOM to get a query vector, and then attend over the DOM embeddings v e DOM . The DOM context is the weighted average of the attended DOM embeddings.

2. Goal contexts: we use the DOM context as the query vector to attend over the goal embeddings v u goal . We compute two goal contexts from two different attention heads. Each head uses sentinel attention, where part of the attention can be put on a learned NULL vector, which is useful for ignoring the goal when the next action should not depend on the goal.

3.. DOM element selection::

We concatenate the DOM context and goal contexts into a query vector to attend over on the DOM embeddings v e DOM . We use two attention heads, and combine the attention weights from the two heads based on ratio computed from the goal contexts. The result is a distribution over the target DOM elements e.

4. Typed string and action selection: For a given target DOM element e, we combine the goal context and the embedding v e DOM of e to get a query vector to attend over the goal embeddings v u goal . For structured queries, we get a distribution over the goal fields, while for natural language queries, we get distributions of the start and end tokens. The same query vector is also used to compute the distribution over the action types (click or type). 

:

http://alpha.openai.com/miniwob/

It is augmented with filters that activate on textual elements which overlap with goal text.

We report test reward since success rate is artificially high in the Alaska task due to partial rewards.

Figures and Tables:

Figure 4: Comparison between DOMNET+BC+RL and DOMNET+WGE on several of the most difficult tasks, evaluated on test reward. DOMNET+WGE trained on 10 demonstrations outperforms DOMNET+BC+RL even with 1000 demonstrations.

Figure 5: The architecture of the neural policy π n . The inputs from the state are denoted in blue, while the outputs are denoted in red. Q = query vector; M = memory matrix.

Update πn and critic V with e if e gets reward +1 then Add e to replay buffer

Table content: <table><tr><td/><td/><td/><td/><td/><td>Preprocessing:</td></tr><tr><td colspan="2">demonstrations</td><td>action</td><td/><td/><td>for all demonstrations d do</td></tr><tr><td/><td/><td/><td/><td/><td>Induce workflow lattice from d</td></tr><tr><td/><td colspan="2">state</td><td/><td/><td>Every iteration:</td></tr><tr><td/><td/><td>workflow policy π w</td><td/><td/><td>Observe an initial environment state</td></tr><tr><td/><td/><td>workflow lattices</td><td>explore</td><td>episodes</td><td>πw samples a workflow from a lattice Roll out an episode e from the workflow Use e to update πw</td></tr><tr><td/><td/><td/><td>train</td><td>store</td><td>if e gets reward +1 then Add e to replay buffer</td></tr><tr><td/><td/><td/><td/><td>replay buffer</td><td>Periodically:</td></tr><tr><td/><td/><td>train</td><td/><td/><td>if replay buffer size &gt; threshold then Sample episodes from replay buffer</td></tr><tr><td/><td/><td/><td/><td/><td>Update πn with sampled episodes</td></tr><tr><td>s</td><td colspan="2">neural policy π V ( s ) DOMNET p ( a | s) n</td><td>train explore</td><td>episodes store</td><td>Observe an initial environment state πn rolls out episode e</td></tr></table>

Success rates of different approaches on the MiniWoB tasks. DOMNET+WGE outperforms SHI17 on all but two tasks and effectively solves a vast majority. Results on additional tasks. (+ = MiniWoB++, Steps = task length as the maximum number of steps needed for a perfect policy to complete the task)

Table content: <table><tr><td/><td>100</td><td colspan="2">100</td><td colspan="2">100</td><td>100</td><td colspan="2">100</td><td colspan="2">100</td><td>100</td><td/><td>98</td><td>100</td><td>100</td><td colspan="2">95</td><td>100</td><td>100</td><td/><td>100</td><td>100</td><td/><td colspan="2">100</td><td>100</td><td/><td/><td>100</td><td colspan="2">100</td><td/><td>100</td><td>100</td><td/><td colspan="2">98</td><td colspan="2">100</td><td/><td>100</td><td>100</td><td/><td colspan="2">100</td><td>100</td><td/><td/><td>100</td><td>100</td><td/><td/><td>99</td><td>100</td><td/><td>99</td><td>99</td><td/><td>100</td><td>100</td><td/><td/><td>100</td><td colspan="2">100</td><td>100</td><td>100</td><td>99</td><td>100</td><td>99</td><td>100</td></tr><tr><td>Success Rate</td><td>0 25 50 75</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>83</td><td/><td/><td>83</td><td/><td/><td/><td>62</td><td/><td/><td/><td>53</td><td/><td/><td/><td>48</td><td/><td/><td/><td>31</td><td/><td/><td colspan="2">26</td><td/><td/><td colspan="2">23</td><td/><td/><td/><td>22</td><td/><td/><td colspan="2">20</td><td/><td/><td>18</td><td/><td/><td>0</td><td/><td/><td>0</td><td>0</td><td>0</td></tr><tr><td/><td/><td colspan="5">click</td><td/><td colspan="4">click</td><td/><td colspan="3">click</td><td/><td colspan="3">focus</td><td/><td colspan="2">focus</td><td/><td colspan="3">click</td><td/><td colspan="4">click</td><td colspan="3">click</td><td/><td colspan="3">click</td><td/><td colspan="3">click</td><td/><td colspan="3">grid</td><td/><td colspan="3">click</td><td/><td colspan="3">click</td><td colspan="3">navigate</td><td/><td colspan="2">click</td><td/><td colspan="3">enter</td><td>enter</td><td>login</td><td>enter</td></tr><tr><td/><td/><td colspan="5">dialog</td><td/><td colspan="4">test</td><td colspan="4">collapsible</td><td/><td colspan="3">text</td><td/><td colspan="2">text</td><td/><td colspan="3">test</td><td/><td colspan="4">button</td><td colspan="3">dialog</td><td colspan="5">checkboxes</td><td colspan="3">link</td><td colspan="4">coordinate</td><td/><td colspan="3">color</td><td/><td colspan="3">button</td><td/><td colspan="2">tree</td><td/><td colspan="2">option</td><td/><td/><td colspan="2">text</td><td>text</td><td>user</td><td>password</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>2</td><td/><td/><td>2</td><td/><td/><td/><td/><td/><td/><td/><td/><td>2</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="3">sequence</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>dynamic</td></tr><tr><td>Success Rate</td><td>0 25 50 75 100</td><td>97</td><td colspan="2">55</td><td colspan="2">100</td><td>36</td><td colspan="2">90</td><td colspan="2">100</td><td>34</td><td>93</td><td>92</td><td>0</td><td>78</td><td colspan="2">98</td><td>11</td><td>65</td><td>99</td><td>8</td><td>64</td><td>98</td><td colspan="2">61</td><td>0</td><td>96</td><td colspan="2">18</td><td>59</td><td>76</td><td>8</td><td>52</td><td>90</td><td>27</td><td colspan="2">22</td><td>99</td><td>3</td><td>42</td><td>99</td><td>11</td><td>64</td><td colspan="2">63</td><td>23</td><td>15</td><td colspan="2">100</td><td>0</td><td>26</td><td>99</td><td>34</td><td>37</td><td>47</td><td>15</td><td>32</td><td>52</td><td>25</td><td>16</td><td>16</td><td colspan="2">0</td><td>0</td><td>52</td><td>17</td><td>4</td><td>4</td><td>0</td><td>0</td><td>0</td><td>20</td><td>0</td><td>0</td></tr><tr><td/><td/><td colspan="5">click</td><td colspan="5">identify</td><td colspan="3">click</td><td/><td colspan="2">use</td><td/><td colspan="3">click</td><td colspan="3">click</td><td/><td colspan="3">enter</td><td colspan="4">count</td><td colspan="3">enter</td><td colspan="4">click</td><td colspan="3">email</td><td colspan="3">click</td><td/><td colspan="3">social</td><td/><td colspan="3">search</td><td/><td>tic</td><td/><td colspan="3">click</td><td colspan="3">choose</td><td colspan="3">choose</td><td>use</td><td>book</td><td>guess</td></tr><tr><td/><td/><td/><td colspan="3">tab</td><td/><td colspan="4">shape</td><td/><td colspan="3">widget</td><td colspan="3">auto-</td><td colspan="4">collapsible</td><td/><td>tab</td><td/><td/><td colspan="3">date</td><td colspan="4">shape</td><td colspan="3">time</td><td colspan="4">shades</td><td colspan="3">inbox</td><td colspan="4">shape</td><td colspan="3">media</td><td/><td colspan="3">engine</td><td/><td>tac</td><td/><td/><td>pie</td><td/><td colspan="2">list</td><td/><td/><td colspan="2">date</td><td>spinner</td><td>flight</td><td>number</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="4">complete</td><td/><td>2</td><td/><td/><td>2</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>toe</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="4">SHI17</td><td/><td colspan="10">DOMNET+BC+RL</td><td/><td/><td colspan="9">DOMNET+WGE</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="7">Figure 3: Task</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="11">Description</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="16">Steps BC+RL πw only WGE</td></tr><tr><td colspan="14">click-checkboxes</td><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="23">Click 0-6 specified checkboxes</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>7</td><td/><td/><td/><td/><td colspan="3">98</td><td/><td/><td/><td>81</td><td>100</td></tr><tr><td colspan="19">click-checkboxes-large +</td><td/><td/><td/><td colspan="12">. . . 5-12 targets</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">13</td><td/><td/><td/><td/><td/><td colspan="2">0</td><td/><td/><td/><td>43</td><td>84</td></tr><tr><td colspan="19">click-checkboxes-soft +</td><td/><td/><td/><td colspan="27">. . . specifies synonyms of the targets</td><td/><td/><td/><td/><td/><td>7</td><td/><td/><td/><td/><td colspan="3">51</td><td/><td/><td/><td>34</td><td>94</td></tr><tr><td colspan="44">click-checkboxes-transfer + . . . training data has 0-3 targets</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>7</td><td/><td/><td/><td/><td colspan="3">64</td><td/><td/><td/><td>17</td><td>64</td></tr><tr><td colspan="13">multi-ordering +</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="29">Fill a form with varying field orderings</td><td/><td/><td/><td>4</td><td/><td/><td/><td/><td/><td colspan="2">5</td><td/><td/><td/><td>78</td><td>100</td></tr><tr><td colspan="12">multi-layout +</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="27">Fill a form with varying UIs layouts</td><td/><td/><td/><td/><td/><td>4</td><td/><td/><td/><td/><td colspan="3">99</td><td/><td/><td/><td>9</td><td>100</td></tr><tr><td colspan="10">social-media</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="26">Do an action on the specified Tweet</td><td/><td/><td/><td/><td/><td/><td>2</td><td/><td/><td/><td/><td colspan="3">15</td><td/><td/><td/><td>2</td><td>100</td></tr><tr><td colspan="14">social-media-all +</td><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="20">. . . on all matching Tweets</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">12</td><td/><td/><td/><td/><td/><td colspan="2">1</td><td/><td/><td/><td>0</td><td>0</td></tr><tr><td colspan="16">social-media-some +</td><td/><td/><td/><td/><td/><td/><td colspan="33">. . . on specified no. of matching Tweets 12</td><td/><td/><td/><td/><td/><td colspan="2">2</td><td/><td/><td/><td>3</td><td>42</td></tr><tr><td colspan="9">email-inbox</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="24">Perform tasks on an email inbox</td><td/><td/><td/><td/><td/><td/><td/><td/><td>4</td><td/><td/><td/><td/><td colspan="3">43</td><td/><td/><td/><td>3</td><td>99</td></tr><tr><td colspan="13">email-inbox-nl +</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="18">. . . natural language goal</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>4</td><td/><td/><td/><td/><td colspan="3">28</td><td/><td/><td/><td>0</td><td>93</td></tr></table>

Phillips et al. (2016); Perez-D'Arpino & Shah (2017) also resemble our work, in learning constraints from demonstrations, but differ in the way they use the demonstrations. Whereas our work uses the learned constraints for exploration,Phillips et al. (2016) only uses the constraints for planning and Perez-D'Arpino & Shah (2017) build a knowledge base of constraints to use at test time.

Table content: <table/>

Peer review (iclr2018):
 Summary: The authors propose a method to make exploration in really sparse reward tasks more efficient. They propose a method called Workflow Guided Exploration (WGE) which is learnt from demonstrations but is environment agnostic. Episodes are generated by first turning demonstrations to a workflow lattice. This lattice encodes actions which are in some sense similar to those in the demonstration. By rolling out episodes which are randomly sampled from this set of similar actions for each encountered state, it is claimed that other methods like Behavor Cloning + RL (BC-then-RL) can be outperformed in terms of number of sample complexity since high reward episodes can be sampled with much higher probability. A novel NN architecture (DOMNet) is also presented which can embed structured documents like HTML webpages. Comments: - The paper is well-written and relevant literature is cited and discussed. - My main concern is that while imitation learning and inverse reinforcement learning are mentioned and discussed in related work section as classes of algorithms for incorporating prior information there is no baseline experiment using either of these methods. Note that the work of Ross and Bagnell, 2010, 2011 (cited in the paper) establish theoretically that Behavior Cloning does not work in such situations due to the non-iid data generation process in such sequential decision-making settings (the mistakes grow quadratically in the length of the horizon). Their proposed algorithm DAgger fixes this (the mistakes by the policy are linear in the horizon length) by using an iterative procedure where the learnt policy from the previous iteration is executed and expert demonstrations on the visited states are recorded, the new data thus generated is added to the previous data and a new policy retrained. Dagger and related methods like Aggrevate provide sample-efficient ways of exploring the environment near where the initial demonstrations were given. WGE is aiming to do the same: explore near demonstration states. - The problem with putting in the replay buffer only episodes which yield high reward is that extrapolation will inevitably lead the learnt policy towards parts of the state space where there is actually low reward but since no support is present the policy makes such mistakes. - Therefore would be good to have Dagger or a similar imitation learning algorithm be used as a baseline in the experiments. - Similar concerns with IRL methods not being used as baselines. Update: Review score updated after discussion with authors below.