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. 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 BID42 , 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 BID44 . 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 BID46 BID30 . 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 BID37 BID23 , 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 BID41 . At the same time, simple strategies to combat overfitting (e.g. using fewer parameters or regularization) cripple the policy's flexibility BID9 , 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, for all demonstrations d do Induce workflow lattice from d 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 BID50 or may be inferred from demonstrations BID1 . Second, soft policies may be learned from scratch or "warm-started" from demonstrations BID41 . Notably, sparse rewards prevented BID41 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 BID32 BID11 BID48 help the agent better explore the state space to encounter more reward; shaping rewards BID31 directly modify the reward function to encourage certain behaviors; and other works BID22 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 BID40 and AGGREVATE BID39 BID43 can query the expert policy to augment the dataset for training the agent. When only expert demonstrations are available, inverse reinforcement learning methods BID0 Ziebart et al., 2008; BID15 BID19 BID7 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 BID20 BID18 BID46 BID30 .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 BID10 BID21 or off-policy sampling BID26 . 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 BID45 BID25 BID17 , abstract partial policies BID33 , and abstract states BID38 BID14 BID27 . These frameworks require varying amounts of prior knowledge. The original formulations required programmers to manually specify the decomposition of the complex task, while BID3 only requires supervision to identify subtasks, and BID6 ; BID12 learn the decomposition fully automatically, at the cost of performance.Within the HRL methods, our work is closest to BID33 and the line of work on constraints in robotics BID36 BID34 . The work in BID33 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 BID2 BID28 , which require programmers to specify these constraints manually, our work automatically induces constraints from user demonstrations, which do not require special skills to provide. BID36 ; 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, BID36 only uses the constraints for planning and Perez-D'Arpino & Shah (2017) build a knowledge base of constraints to use at test time.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.Acknowledgments. This work was supported by NSF CAREER Award IIS-1552635.
We solve the sparse rewards problem on web UI tasks using exploration guided by demonstrations
{"src": "scitldr-AIC_train", "paper_id": "ryTp3f-0-"}