Published as a conference paper at ICLR 2018 REINFORCEMENT LEARNING ON WEB INTERFACES USING WORKFLOW-GUIDED EXPLORATION
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.
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.