Adversarial Environment Generation for Learning  to Navigate the Web
Authors: Izzeddin Gur
Natasha Jaques
Kevin Malta
Manoj Tiwari
Honglak Lee
Aleksandra Faust
Venue:  (2021)
Keywords: Web Navigation
Adversarial Environment Generation
Web Environment Design
Minimax Regret Adversary
Auto Curriculum

Abstract: Learning to autonomously navigate the web is a difficult sequential decision making task. The state and action spaces are large and combinatorial in nature, and successful navigation may require traversing several partially-observed pages. One of the bottlenecks of training web navigation agents is providing a learnable curriculum of training environments that can cover the large variety of real-world websites. Therefore, we propose using Adversarial Environment Generation (AEG) to generate challenging web environments in which to train reinforcement learning (RL) agents. We introduce a new benchmarking environment, gMiniWoB, which enables an RL adversary to use compositional primitives to learn to generate complex websites. To train the adversary, we present a new decoder-like architecture that can directly control the difficulty of the environment, and a new training technique Flexible b-PAIRED. Flexible b-PAIRED jointly trains the adversary and a population of navigator agents and incentivizes the adversary to generate ”just-the-right-challenge” environments by simultaneously learning two policies encoded in the adversary’s architecture. First, for its environment complexity choice (difficulty budget), the adversary is rewarded with the performance of the best-performing agent in the population. Second, for selecting the design elements the adversary learns to maximize the regret using the difference in capabilities of navigator agents in population (flexible regret). The results show that the navigator agent trained with Flexible b-PAIRED generalizes to new environments, significantly outperforms competitive automatic curriculum generation baselines—including a state-of-the-art RL web navigation approach and prior methods for minimax regret AEG—on a set of challenging unseen test environments that are order of magnitude more complex than the previous benchmarks. The navigator agent achieves more than 75% success rate on all tasks, yielding 4x higher success rate that the strongest baseline.

Under review as a conference paper at ICLR 2021
ADVERSARIAL ENVIRONMENT GENERATION FOR LEARNING TO NAVIGATE THE WEB
Anonymous authors Paper under double-blind review
ABSTRACT
Learning to autonomously navigate the web is a difficult sequential decision- making task. The state and action spaces are large and combinatorial in na- ture. and successful navigation may require traversing several partially-observed pages. One of the bottlenecks of training web navigation agents is providing a learnable curriculum of training environments that can cover the large variety of real-world websites. Therefore, we propose using Adversarial Environment Generation (AEG) to generate challenging web environments in which train reinforcement learning (RI.) agents. We introduce a new benchmarking environ- ment, gMiniWoB, which enables an RL adversary to use compositional primi- tives to learn to generate complex websites. To train the adversary, present a new decoder-like architecture that can directly control the difficulty of the envi- ronment, and new training technique Flexible b-PAIRED. Flexible b- b-PAIRED jointly trains the adversary and a population of navigator agents and incentivizes the adversary to generate jjust-the-right-hhallleggg ously learning two policies encoded in the adversary's architecture. First, for its environment complexity choice (difficulty budget), the adversary is rewarded with the performance of the best-performing agent in the population. Second, for se- lecting the design elements the adversary learns to maximize the regret using the difference in capabilities of navigator agents in population (flexible regret). The results show that the navigator agent trained with Flexible b-PAIRED generalizes to new environments, significantly outperforms competitive automatic curriculum generation baselines-includingg a state-of-the-art RL web navigation approach and prior methods for minimax regret AEG on set of challenging unseen test environments that are order of magnitude more complex than the previous bench- marks. The navigator agent achieves more than 75% success rate all tasks, yielding 4x higher success rate that the strongest baseline.
environments by simultane-
INTRODUCTION
Autonomous web navigation agents that complete tedious, digital tasks, such booking flight or filling out forms, have a potential to significantly improve user experience and systems' accessibility. plane ticket Los Angeles leaving on Friday", and have the agent automatically handle the details of completing these tasks. However, the complexity and diversity of real-world websites make this formidable challenge.
The agents could enable user to issue requests such as, "Buy
General web navigation form-filling tasks such as these require an agent to navigate through a set of web pages, matching user's information to the appropriate elements on a web page. This is highly challenging decision-making problem for several reasons. First, the observation space is large, and obbsevable.be consisting of a single web page in the flow of several web pages (c.g. the payment information page is only one part of a shopping task). Web pages are represented using the Document Object Model (DOM), tree of web elements with hundreds of nodes. Second, actions are all possible combination of the web elements (fill-in boxes, drop-downs, click on the buttons) and their possible values. For example, the drop-down selection actions are only appropriate if there there is a drop-down menu present. Even if the agent is able to navigate the site to arrive at the correct page, and eventually select the correct element (e.g. the 'departure' field for booking a flight), there many possible values it can insert (e.g. all user input). Therefore, the action space is discrete and prohibitively large, with only a valid set of actions changing with the context. Finally, the same task, such booking flight, results in a very different experience and workflow depending on the

---

Under review as a conference paper at ICLR 2021
Lue Nane
Nome
Partoona
Deal of the Day
Nare
HOME
Ceniig nerostion
Addres
wan
Lan Hare
Hame
Deet Card
Dea Car
Onter Capthr
Des
Post Here
Pagel ste
Facthone
(a) Iteration=100
(b) Iteration=1
(c) Iteration=24000
(d) Test
Figure Samples of generated web pages from selected websites taken from different snapshots the training (a-c) and unseen lest "Login" website (d). Over time, the number of pages in a website decreases but
the density of elements in page increases with more task-oriented elements. See Appendix A.II for more samples.
website. The agent must be able adapt and operate in the new environment to complete the task. Therefore, the reinforcement learning (RL) agents should be capable of zero-shot generalization to new environments.
Prior work made significant strides toward learning web navigation on a single website, yet the existing methods do not scale. Behavior cloning from expert demonstrations (Shi et al. 2017 Liu (et al. 2018) shows promising results, however, it requires a number of demonstrations for every single website. RL agent trained using synthetic demonstrations created with generative model Gur et al. (2019) improves the performance. Yet, the method still requires training separate policy for every single website requiring tens of thousands of interactions with every website. Lastly, the existing benchmarks (Shi et al. 2017: Liu et al. (0088) have limited complexity. Their DOM trees are fixed and considerably smaller than real websites.
We aim to train RL agents to solve web navigation form-filling tasks; by correctly entering relevant information into unknown websites. Successful generalization to new websites requires training an agent on large distribution of possible tasks and environments. The question is how to create distribution that will not only cover most realistic tasks, but can be presented in a curriculum that is learnable by the agent. Manually designing pre-defined curriculum of hand-built websites is tedious, and intractable. Another option would be to apply domain randomization (DR) (as e.g. Jakobi (1997;; Sadeghi & Levine (2016); Tobin et al. (2017) randomize parameters of websites, or automatically increase some parameter controlling the difficulty over time (as Gur et al. (2019)) However, all these approaches likely to fail to cover important test cases, and cannot tailor the difficulty of the parameter configuration to the current ability of the agent.
Adversarial Environment Generation (AEG) trains learning adversary automatically generate curriculum of training environments, enabling both increased complexity of training environments, and generalization new, unforescen test environments. However, if naively train minimax adversary-i.c. an adversary that seeks to minimize the performance of the learning agent-the adversary is motivated create the hardest possible website, preventing learning. Instead, PAIRED (Protagonist Antagonist Induced Regret Environment Design) (Dennis et al.) (020),, trains the adver- sary to maximize the regret, estimated as a difference between two navigation agents (protagonist and antagonist). While PAIRED shows exciting results, without an explicit feedback on how skillful antagonist and mechanism to control the difficulty of the environment, the method is susceptible to local minima, and has hard time learning the complex environments when the regret is zero.
We present Flexible D-PAIRED, which builds on PAIRED framework, and jointly trains the adversar- ial RL agent (adversary) and population of navigator agents. Flexible b-PAIRED adversary learns to present "just-the-righe wwwrrri-hhcllleggeee to the navigation agents. We enable Flexible b-PAIRED adver- sary to tailor the environment difficulty to the ability of the best performing agent by introducing an explicit difficulty budgeting mechanism, and a novel multi-of oojecti-beeetiveee loss function. The budgeting mechanism gives the adversary the direct control of the difficulty of the generated environment. The
2

---

Under review as a conference paper at ICLR 2021
adversary training simultaneously optimizes for objective that ties in adversary difficulty budget with the navigator agent's 's performance (observed expected return), and the population- based regret similar to PAIRED. Lastly, to enable AEG web-design, we present a new benchmarking environ- ment, g.MiniWoB, and a web-design adversary architecture. gMini enables an adversary to construct websites of increasing complexity out of common design primitives such as navigation bars, product carousels, item decks, web forms, and item carts. The evaluation environments in gMiniWob are order of magnitude more complex than miniWob (Shi et al. 2017). The adversary architecture is S'TM-bbased decoder, seeded with random seed. It first selects number of web pages. Then, at each step of an open loop, the adversary either emits a design element and its place- ment, or opts to skip an element and save design budget. The adversary's 's used difficulty budget is log-likelihood of joint probability of not adding design elements.
This paper makes the following contributions: i) A new benchmarking environment, gMiniWoB, which empowers the use of AEG for web navigation, by enabling the construction of websites out of compositional design primitives; ii) The Flexible b- b-PAIRED algorithm, which computes a more stable estimate of regret and directly incentivizes the adversary to tailor the complexity of the gen- erated environment the performance of the best-performing agent; iii) web navigation adversary decoder architecture, and iv) empirical results demonstrating that Flexible b-PAIRED generates a curriculum of increasingly challenging websites, and produces agents that can successfully gener- alize to navigating complex, unseen sites at test time. Flexible b-PAIRED approach significantly outperforms prior work on minimax regret AEG (Dennis et al.) 2020 as well a state-of-the of-the-art approach for using RL to train web navigation agents (Gur et al. 2019), resulting in agents that com- plete the most difficult tasks with more than 75% success rate, 4x improvement over the strongest baseline. We are releasing @MiniWoB in open-source in the hopes of enabling further progress on this problem. We hope that this work will provide a meaningful way to make progress on the excep- tionally challenging problem of learning to navigate the web, and will be of interest to the wider RL research community for auto-curricllum design in complex and compositional environments.
RELATED WORK
Web navigation benchmarks and tasks: Prior work training agents to navigate the web intro- duced the MiniWoB (Shi et al. (017)) and MiniWoB++ (Liu et al. 2018) enviromments, a fixed set of manually curated toy websites, but relied on obtaining expert demonstrations for each website, which cannot scale effectively to cover the large variety of real-world websites, and cannot adapt to changing websites. Further. these methods failed solve complex web navigation tasks such as flight booking or social media interaction (Gur et al., 2019). Gur et al. (2019) take a step farther by training an RI. agent to solve complex web navigation tasks using a scheduled currieulum. The curriculum linearly increases a parameter p. in which 1 - p controls the number of web elements that are solved by querying an oracle policy, which is obtained via expert data. This work differs in several ways. First, we introduce new framework, gMiniWoB, that allows generating complex websites on-the-fly with tunable difficulty levels. Additionally, we do not rely on any expert demon- strations augment sparse rewards. We use AEG to automatically learn to generate curriculum of web navigation tasks that are tailored to the current skill level of the agent. Next, we make no assumption the availability of any website while they assume websites given a priori. Lastly, our web navigation agents generalize to unseen environments.
Goal Generation: Florensa et al. (2018) trains Generative Adversarial Network (GAN) for gen- crating a curriculum of goals with fixed environment dynamics. A generator is trained to output new goals and the discriminator is trained to predict if the goal is achievable. The generator is boot- strapped from sample goals that the initial agent is able to reach in the environment. It is tested on simple navigation tasks with the same environments. In contrast, we train an adversary that gen- erates curriculum of environments, including goals, starting with an empty environment in which bootstrapping generator network from sample episodes is not possible. We test on unseen environ- ments with more complicated and high dimensional state and action spaces.
Adversarial Environment Generation: Multi-agent training can be an effective method for au-
tomatically generating curriculum of RL tasks (e.g. Leibo et al. (2019); Matüienn et al. (2019); Graves et al. (2017); Portelas et al. 20200). For example, Asymmetric Self Play (ASP) (Sukhbaatar et al.) 2017) trains agents, in which the second agent must learn to repeat the actions taken by
the first, demonstrator agent. Both agents play in the same, fixed environment. In contrast, we use a
third agent learn generate challenging new environments. POET (Wang al. 2019 2020) is
3

---

Under review as a conference paper at ICLR 2021
DIV
DIV
LABEL
LABEL
DIV
stext VAR*
#text "First Nove
INPUT text="UVerraxp""
INPUT text-VAR*
INPUT
(a) An underspecified DOM tree template. The text box is always included, its text and label element are variables.
(b) A fully specified DOM primitive where a label is created and its text is assigned.
(c) A fully specified DOM primitive where only the inner text within the text box assigned.
Figure 2: An example underspecified DOM tree template (a) and its instantiations (b,c) with different values. (*) indicates variable; either an element or one of its attributes. (c) is used in Page 1 and (b) is used in Page 2 in Figure
an AEG technique which uses a population of adversaries to generate the terrain a 2D walker agent must learn to navigate. To create curriculum, POET requires generating many new environments, testing all agents within each one, and discarding environments based on a manually chosen a reward threshold, which wastes significant amount of computation. Campero et al. (2020) use teacher to propose navigation tasks; the teacher's s reward is based on whether the agent takes more steps than threshold, a hyperparameter that is linearly increased over the course of training.
Most closely related to our work is PAIRED (Dennis et al. 2020), which is an AEG method for training agents with minimal regret that works by constraining the enviromment-genraatin adversary using the performance of a second agent. However, PAIRED only demonstrated results on simple gridworld environments, and did not expand to the type of complex, nigh-dimensional state-action space required for web navigation. We improve PAIRED using more flexible estimate of the regret, as well as a budget mechanism, and show that this significantly improves performance.
RL with Autoregressive Models: Keneshloo et al. 2020) outlines training sequence- seguence-o--equeene to-sequence (seq2seq) models with RL algorithms. Previous models first pretrained a seq2seq model with ground-truth inputs and outputs and then finetuned with RI using different reward functions such as BLEU score. In this work, we propose decoder-like autoregressive adversary model that is trained without any ground-truth data. The model is fed its own predictions from previous time steps and updated using a novel ad adversarial objective.
3 BACKGROUND ON WEB NAVIGATION PROBLEM
Following previous work (Shi et al., 2017 Gur et al., 2019 Liu et al. 2018), formulate web navigation as a sequential decision making problem where we train an agent, parameterized by network TTa, (s;; θ,), that maps an input state st output action distribution to maximize the cumulative discounted reward, iie., O Σr 7'r; where T₁ the reward time step t, 7 is discount factor, and 7 is the length of an episode. We use the web page and user instruction as the input state. The web page dynamically updated each time step, while the instruction is fixed at the beginning of an episode. We represent web pages using Document Object Model (DOM), a tree of elements in a page, where each element denoted by a set of (attribute, value) pairs and an array of features (such as spatial coordinates). Instructions given set of fields where each field is a (key, value) pair. Keys are fixed for each task and values dynamically change based on user input.
Each action is represented as an input; i.e. typing the value of the field into the element. Agents receive task success reward (1.0 or -1.0) at the end of each episode, a potential-based reward when the value of an element in the page is updated, and a small penalty each timestep to encourage efficient navigation. As an exam- ple, consider flight booking task where the agent is given an instruction { "'Departure Date": "Friday", Destinat in Airport: field (e.g. destination airport) and finds the corresponding text box in the page; then the corre- sponding value ("Los Angeles (LAX)") typed in to the text box. If this value is correct, the agent receives positive reward of 1/2 where 2 the number of fields the instruction.
tuple (clement, field) that denotes acting on the element using the field
"Los Angeles (LAX) "). The agent first picks
4 METHODS FOR LEARNING TO DESIGN WEB ENVIRONMENTS
This Section presents the generative MiniWob environment (Section 4.1. the adversary neural net- work architecture (Section 4.2p and the adversary training procedure Section 4.3
4

---

Under review as a conference paper at ICLR 2021
Page
Website
Rendering
USERNAME
LOGIN
FIRSTNAME
Adversary
0bc
A sample rollout the adversary for compositional environment generation for web navigation problem. An initial observation (Obs) is given at the beginning of the rollout. fo. fgx ft., fp, and fr denote networks for encoding initial observation, generating number of pages, page indices primitives, prdicivsp,miitives. and encoding LSTM inputs, respectively.
Figure 3:
4.1 GENERATIVE MINIWOB (GMINIWOB) ENVIRONMENT
Generative MiniWoB (gMiniWoB) creates website environments for form-filling tasks, which con- sist of linked-list of webpages, & = [W..... Wx]. Each webpage, W,, is DOM tree that contains number of elements, such fill-in boxes, drop downs, and buttons. To create new environment En, gMiniWoB starts with an empty website that is gradually populated by new pages, W. A subset of elements are also augmented with events that enable page transitions. For example, an "on-click" event on a Submit button on a page W., will link to a page W1+1-
We formulate the website design as combining a set of primitive DOM sub-trees that are general enough to create complex websites but also facilitate controllable generation. The order in which the primitives are combined also defines how the web page will be rendered well. Let's assume that we are given a list of DOM tree primitives T and an empty web page W = =(S, C.) where S is single root node of the DOM tree and is an ordered list of subtrees rooted S which is initially empty. By repetitively sampling new primitives from T and appending them to C, we create new page, W, which follows the order of primitives in C when rendered (see Figure 3
We first create set of underspecified DOM tree templates, a sub-tree with certain elements and attributes are replaced with variables. Assigning values variables in a template fully specifies a DOM tree primitive that is placed in subtree C to create a new web page, W (Algorithm 2) For example, an input template (Figure 2ab as variable label and text box with a common parent. There two ways to assign values, either by picking the label element and assigning a value to its text attribute (Figure 2b), assigning a value to the inner text of the text box and ignoring the label element (Figure
Website Design Primitives: gMiniWoB implements 40 different design primitives from 11 dif- ferent underspecified DOM templates. The primitives are widely used across the web and include 'navigation bars', 'product carousels', 'item decks', 'web forms', 'item carts', 'dropdowns', etc. Every primitive includes at least one actionable element that changes the DOM structure when the agent interacts with it. Each primitive belongs to of the two categories based on their use in the reward computation: (i) Active primitives (used), and (ii) Passive primitives (not used). 26 of the 40 primitives are active, while the rest are passive. When active primitive is added a web page, the instruction automatically grows as well. For example, adding 'First Name text box in Figure 2c also adds a new "firstmame" field into user instruction. Expanding the instruction set makes active primitives more complicated to learn, while the passive primitives mostly serve as noise. However, real websites contain many distracting elements (passive primitives), so is important for agents to learn to ignore them. Appendix details all the design primitives used, and Appendix A. shows the websites in the test set.
For simplicity of illustration, we show an example generation process where primitives are generated in an increasing order of the page indices; however, in our formulation (see Section 4.2 for details), the page indices corresponding to consecutive LST timesteps do necessarily inerease monotonically.
5

---

Under review as a conference paper at ICLR 2021
4.2 ADVERSERIAL ENVIRONMENT DECODER ARCHITECTURE
We present an adversary decoder policy for the compositional environment generation problem where the goal is place set of design primitives set of locations. Adversary generates (website) environment, & [W1.... Wk]. We assume fixed maximum number of pages K, although to control complexity, we allow pages and subtress to be empty.
We parametrize the adversary with policy क TE TE(a"l0*) such that
N
TE(A o² TE.. (k)KK II (a, by a0....... bo....... 2=
where N is upper limit the number of outputs (total number of primitives in the environment Ew), K is an upper limit on the number of web pages, a, is a design primitive. We augment the primitive design actions described in Section 4.1 with special SKIP action that does nothing when executed by the renderer. This allows the adversary to control the number of primitives added. b, is web page index of where the primitive a, should be placed in the page. Observation 0 is an initial observation. The adversary first samples the number of locations k from a parametrized Categorical distribution (O, K). Conditioned 04, it executes an autoregressive model to generate a set of primitives and their corresponding locations within environment totalling at most N primitives placed over k pages.
a is the resulting
The initial observation A is sampled from the standard normal distribution, to allow the adversary to diversify its design distribution. This observation is encoded with a feed forward network ho fo(o") and hg is passed to another network fK that outputs distribution over number of empty pages. The same hidden state hng is passed to an LSTM network as the initial input vector and output of the LSTM is used by two independent networks f' and Sr. to (i) learn distribution over design primitives and (ii) learn a distribution over locations, respectively. We sample an action (a joint primitive and location pair) from these distributions and they are encoded by another network fr into a hidden state which is used as the input to the LSTM at the next step. After N steps, sampled design actions sent renderer module which generates the environment (Figure B)
Note that the adversary is domain independent, and creates a generic compositional task environment each containing sub tasks sampled from the design primitives.
with K linked Since the renderer interprets the design decisions and builds the environments for the navigator agents use, the adversary architecture can be used in other domains without modification.
4.3 ADVERSARY TRAINING
We train both the adversary and navigation agents with reinforcement learning. At every step / of the training, the adversary generates an environment (t). The web navigation training initializes population of navigation agents A {A,,i 1,... ..a). The agents A, A collect M tra- jectorics T. with returns R.y. Rt,j is a discounted cumulative reward that agent A, observers by navigating the environment, Ew., and resulting in trajectory Ti.j TA The navigation agents use the standard task related reward described in Section for training and out-of-box A2C with entropy (Mnih al., 2016). To train the adversary, we present a new loss function which augments A2C with entropy with a custom loss function that encourages the adversary to control the complexity of the environment, by presenting "just-the-right" challenge for the agents in A (see Algorithm Tp.
4.3.1 LOSS FUNCTIONS
Let (c) be observed returns (cumulative discounted reward) of an agent A;(() A while sam- pling 7th trajectory during training iteration t. Let RA and R. be maximum and average expected returns at the iteration f,
Rd = max B(R.), R² = E[E[]]] B[R.]
1 M
Σ
Righ i i= 1,...,M M
(2)
Then, the adversary loss function consists of two terms,
Ew)) [0 (EGRET(AI&..) + a Truiget (0 A, Ew)
(3)

---

Under review as a conference paper at ICLR 2021
Algorithm b-Flexible PAIRED training. Joint training of the adversary and navigation agents.
Input:A: Initialize the agents independently
2: for all training iterations do
3: Ew Run the adversary ag generate a new website
4: for i = 1, ... na do
5:
R;
6:
for: j = 1, 1,... M do
7:
R - Run agent A, E A the environment & and collect rewards. Expected return for agent A,
8:
R; 4 R, +
R
M
9:
end for end for
10:
11:
RA max, RD R - E > Maximum and mean expected return from the agents. Compute regret as in Equation 4 Update adversary using Equation and REGRET(A) (w) as the reward. D Train adversary. Train navigation agents.
12:
(E - R RA-RRR
13:
14:
Update parameters of VA; A using R3 returns in A2C.
15:
end for
where is a balancing factor between the two losses. Ia is standard A2C loss with cross-entropy regularizer added to encourage adversary's s exploration. The reward function for the Jn is regret, estimated as the difference between expected performance of the best and average agents:
REGRET(A(E..) R RARR"
(4)
The second loss term is budget loss,
N Tuudget (0 (, RAA Σ log T SKIP a0....-1, b0,,,,,,...11))))
(5)
We an environment difficulty objective to bind the adversary's 's design budget the performance of the best agent. We approximate the effective budget of the adversary as the expected number of non-SKIP actions over N time steps and update this budget according to whether the agents are learning. This objective encourages the adversary to use less budget (more SKIP actions) when the agents are not yet learning (i.e., RA is negative low): it encourages the adversary to use more budget (less SKIP actions) when the navigator agents are performing well and collecting positive rewards in the environment. On the flip side, when the agents are collecting negative reward, the adversary is encouraged to decrease the budget and sample less design elements (and more SKIP actions).
4.3.2 LOSS FUNCTIONS DISCUSSION
Budget loss provides training signal for the adversary when the regret reward is sparse, which hap- pens when all agents performing very similarly, and it acts encourage the adversary decrease the difficulty of the environment. Consider the scenario where agents are placed on the home page of shopping website where there are many possible elements, but only single button that takes them to their account page. During exploration, agents mostly collect negative rewards for taking incorrect actions, bounded this case, the regret is very small and sparse, which hinders the adversary's 's ability to design environ- ments at an appropriate difficulty for agents to learn. We approximate the environment difficulty and the effective budget of the adversary the expected number of non-SKIP actions over N created elements, and update this budget according to whether the agents are learning.
very narrow interval (as there is only single optimal action). In
The regret presented in Equation 4 contributes two subtle, but important changes over the prior work. First, the presented regret does not make distinction between antagonist and protagonist agents, and instead annotates the best performing agent as the antagonist. As long any agent has a higher performance than the other agent, the objective will continue to improve the weakest agent. During that time, the other agents continue learning, and therefore provide stronger maximum performance against which we measure the regret. This is why we call flexible. Second, the estimates for the protagonist returns smoothed and computed best mean return, instead of

---

Under review as a conference paper at ICLR 2021
maximum of pre-selected agent. While this might be further underestimating the regret, it provides a more stable estimate.
Note that when the adversary creates non-trivial environments, REGRET is close to zero and the budget loss in Equation | dominates the RL loss. However, when the adversary creates trivial websites, the RL loss and regret encourage the adversary to explore towards environments that promote variation in performance. Those are less trivial, hence pushes the adversary towards increasing the difficulty.
EVALUATIONS
5.1
EVALUATION SETUP
We evaluate our models on a variety of web environments implemented in gMiniWoB as well as MiniWoB frameworks (Shi et al. 2017 Liu et al., 2018). We implemented several challenging websites with varying difficulty levels using the same set of design primitives in gMiniWoB. These environments include 'Loginn', 'Enter Address", 'Flight Booking', 'Enter Payment', and 'Shopping' websites, where the agents need enter text or select information in the website while navigating between pages. Each environment comes with 4 different difficulty levels by gradually adding more primitives to websites. These environments are never explicitly presented to agents during training, so performance in them measures how well agents can generalize to unseen websites test time.
Following Gur et al. (219), we utilize an LSTM based DOM tree encoder and a feed forward network to encode profile fields. The navigator agent policy outputs joint distribution over elements and fields by measuring pairwise similarities between element encodings and profile fields. We compute the state-value by using the marginal distribution of elements as attention weights over element encodings and passing the context vector through a FF network. Web navigation agents are trained with an actor-critic algorithm (Liu al., (2018). We train the LSTM- based adversary network using Flexible PAIRED and Flexible b-PAIRED with policy gradient (See Appendix 1. for more details on adversary policy network).
Agent architecture:
Baselines: We benchmark PAIRED, Flexible PAIRED, and Flexible b-PAIRED against two addi- tional baselines. First, a Domain Randomization (DR) agent, which we implement using a similar approach as Dennis et al. (2020). We first sample the number of empty pages k from a uniform dis- tribution U U1, K.. Next, we randomly sample primitive (including SKIP), and a page from (10, k] for N steps. Second, Curriculum Learning (CL. approach, which adapts the scheduled curriculum idea of Gur et al. (2019) to zero-shot environment generation where we are not given a specific web- site but set of design primitives. We randomly sample each primitive w.r.t. probability where p is initialized with a small number and scheduled to reach 1.0 during training.
5.2 RESULTS
We first compare the original PAIRED algorithm (which used separate antagonist and protagonist agents) to the proposed Flexible PAIRED algorithm that annotates the best performing agent as the antagonist. Flexible PAIRED considerably improves upon PAIRED, which fails to learn in this vironment (Figure 4. One reason is that when agents are separate and have very similar rewards, especially early during training, the regret becomes very small. This uninformative signal makes it difficult for the adversary to learn. On the other hand, Flexible PAIRED computes a consis- tently positive regret signal, which more clearly indicates to the adversary which environments are challenging. but still feasible. The further ablation studies show that adding budget improves per- formance for both flexible, and original PAIRED method (see Appendix A.7 for MiniWoB studies and Appendix A.8 for budget weight ablation).
Comparison on test environments: We evaluate the performance of the proposed models and base- lines on task success rate computed across test environments with different difficulty levels. Flexi- ble b-PAIRED outperforms Flexible PAIRED indicating the budget objective significantly improves performance (Figure 5). Further, both techniques significantly outperform the baseline models on all tasks, with Flexible b-PAIRED effectively reaching more than 75% task success across all difficulty levels. Even the complexity of the environments continues to increase (see Section 5.2 Flexible b-PAIRED agents still perform consistently well without degrading performance. While CL out- performs Flexible PAIRED early in the training, its performance drops significantly due ignoring
8

---

Under review as a conference paper at ICLR 2021
Login
Enter Address
Enter Payment
1.0
0.6
Taok Success Rate
b FAJRED
0.6
Fiexible D-PAIRED
0.4
0.4
0.2
0.22
0.0
3000
2000
3000
Pvbliuation
Evailstion
Evaluation
(a) Login
(b) Address
(c) Payment
Shopolng
Flight Booking
Distribution primitives
1.0
Succes Bane
0.8
0.5
0.8
0.6
0.6
0.6
0.4
0.4
0.4
Flexible FAIRED
0.2
Flexible biRAIRED
1000 Evaluation
2000
25600 75c001000075000
Evaluation
(d) Shopping
(c) Flight booking
(f) Primitives
Figure 4: Comparison of PAIRED (Dennis 2020 and Flexible PAIRED with and without budget en- forcing; averaged over 4 difficulty levels. (f): Percentage of active primitives over training steps (see Appendix
A.4 for more details).
Acupeeated
Acugggated compatisan
Augreqaried
1.7
Taxk Coseese
2302
Smataation Seeps
Strgs
Duskutton Stegs
(a) Difficulty level I
(b) Difficulty level 2
(c) Difficulty level
(d) Difficulty level 4
Figure 5: Aggregated task success rate comparison of Flexible b-PAIRED and baseline models on test envi- ronments with increasing difficulty levels. See Appendix f.6 detailed results.
agents' skill level, and making environments that are too challenging for agents complete. We also observe that Flexible b-PAIRED learns faster than Flexible PAIRED on all environments as Flexible b-PAIRED reacts to agents' performance faster than Flexible PAIRED (see Appendix[A.6)
Environments complexity: While agent performance improves over time, we would like to know if they presented with more challenging environments over training. We estimate the number of active and passive primitives generated as a measure of environment complexity. Learning a web page with more passive primitives is relatively easier task than a page with more active primitives, because passive primitives either add noise and should ignored by the agents, or are used by agents only navigate to another page. On the other hand, if there will the size of the DOM tree increase but the number of profile fields will increase, making the matching between elements and profile more challenging. Flexible b-PAIRED starts around 60% random selection of primitives, and gradually generates more active primitives early on (Figure 4f). Although presented with more active primitives by Flexible b-PAIRED, agents are still able to improve thanks to Flexible b-PAIRED's ability to accurately tune the difficulty of the environments according to agents' skill. During training, more and more passive primitives are also introduced where number of active primitives also keeps increasing (see Appendix A.4). We also observe that the distribution of the primitives shifts later the training to more complex and relevant primitives (see Appendix A.3).
more active primitives, not only
6 CONCLUSION
This work presents a novel technique for Adversarial Environment Generation (AEG), which we show improves significantly over prior work. In addition, we apply AEG to the problem of web navigation, and provide an open-source environment that enables learning to design complex web- sites out of set of compositional primitives. Our Flexible b- D-PAIRED method is able to generate curriculum of increasingly complicated websites, and successfully trains agents which can navigate challenging, high-dimensional websites.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Andres Campero, Roberta Raileanu, Heinrich Küttler, Joshua B Tenenbaum, Tim Rocktäschel, and Edward Grefenstette. Learning with amigo: Adversarially motivated intrinsic goals. arXiv preprint arXiv:2006. 2tti:2000.1112222 /2/22, 2020.
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. Neural Information Processing Systems, 2020.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. Proceedings Machine Learning Research, 2018. URL http:
//proceedings mw.. www.mpp...s....mmmmmmmmmm v80 frensssa 8a html
Alex Graves, Mare Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. arXiv preprint vrXiv:1704.03033 2017.
Izzeddin Gur, Uli Rueckert, Aleksandra Faust, and Dilek Hakkani-Tur. Learning to navigate the web. In ICLR, 2019.
Nick Jakobi. Evolutionary robotics and the radical envelope-of-noine hypothesis. Adaptive behavior, 6(2):325-368, 368, 1997.
Y. Keneshloo, T. Shi, N. Ramakrishnan, and C. K. Reddy, Deep reinforcement learning for sequence-to-sequencc models. IEEE Transactions on Neural Networks and Learning Systems, 31(7):2469-2455 2020. doi: 10. 10.1109/TN 20119.922141..
Joel Leibo, Edward Hughes, Mare Lanctot, and Thore Graepel. Autocurricula and the emergence of innovation from social interaction: A manifesto for multi-agent intelligence research. arXiv preprint arXiv:1903.0077 2019.
Evan Zheran Liu, Kelvin Guu, Panupong Pasupat, Tianlin Shi, and Percy Liang. Reinforcement learning web interfaces using workflow-guided exploration. arXiv preprint arXiv:/802.00S0 2018.
Tambet Matiisnn Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learn- ing. IEEE transactions on neural networks and learning systems, 2019.
Eric Mazumdar, Lillian Ratliff, Michael Jordan, and S Shankar Sastry. Policy-gradiens algorithms have guarantees of convergence in continuous action and state multi-agent settings. arXiv preprint arXiv:1907.03712, 2019a.
Eric V Mazumdar, Michael Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint arXiv:1901. 100.0008000888, 2019b.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep rein- forcement learning. Proceedings of Machine Learning Research. PMLR, 2016. URL http:
//proceedings.o mlr. press v48 mn hal6 hal..hmml
Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre- Yver Oudeyer. Teacher algorithms for curriculum learning of deep in continuously parameterized environments. In Conference on Robot Learning, pp.
PMLR, 2020.
Fereshtch Sadeghi and Sergey Levine Cad2rl: Real single-image flight without a single real image. arXiv preprint arXiv:1611.04200 2016.
Tianlin Shi, Andrej Karpathy, Linxi Fan, Jonathan Hernandez, and Percy Liang. World of bits: An open-domain platform for web-based agents. In International Conference on Machine Learning. pp. 3135-135,144, 2017.
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. arXiv preprint 1oXiv:1703.055 2017.
10

---

Under review as a conference paper at ICLR 2021
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Do- main randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp. 23-30. IEEE, 2017.
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O Stanley. Paired open-ended trailblazer (poet); Endlessly generating increasingly complex and diverse learning environments and their solutions. arXiv preprint arXiv:1901.0175,, 2019.
Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeff Clune, and Kenneth O Stanley. Enhanced poet: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. arXiv preprint arXiv:2003.088 085300000.8886.... 2020.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.I PROTAGONIST ANTAGONIST INDUCED REGRET ENVIRONMENT DESIGN (PAIRED)
Adversarial Environment Generation (AHG) trains an adversary policy TE to design environments to minimize the performance of an agent's ' policy, Tp. Let R -i=1"" ,"r,"" be the total reward received by the agent for trajectory i. In minimax AEG, the objective for the adversary simply: -Re. Thus, minimax adversaries are incentivized to create excessively difficult or impossible envi- ronments, which may not enable the agent learn. Instead, PAIRED (Dennis et al. (020) trains the adversary to maximize the agent's ' regret, which is defined as the difference between the agent's ' re- turn and the return of the optimal policy, R - R When the reward function includes an incentive to complete the task more efficiently (which is true in case), the regret will be highest for easy tasks which could be completed a few steps by the optimal policy, but which the current policy fails to complete. Therefore, adversary that maximizes the regret will continue to propose easier tasks until the agent begins to solve them, making regret desirable objective for AEG.
To estimate the regret, PAIRED introduces third agent, the anlagonist (with policy TA), and strains the adversary to only generate feasible environments which the antagonist can complete. When the adversary generates an environment E, both the protagonist and antagonist collect M trajectories with returns R2 .... Ry Rig Ri in E. The regret is then estimated as:
REGRET max R
1 M
Σ
R
(6)
As Dennis et al. (2200) show, if the adversary and antagonist coordinate and reach Nash equilib- rium with the protagomist, then the protagonist will have learned to minimize the regret. However, in practice gradient-baat baseed multi-agent RL has no convergence guarantees, is highly non-stationary, and will often fail to converge (Mazumdar et al., 2019a b). If the antagonist and adversary in PAIRED fail to coordinate, then PAIRED minimizes regret with respect the antagonist's 's policy. In that case, the objective in Equation forces the protagonist to learn to be as good the antagonist. the antagonist fails improve, or reaches a local optimum, then the adversary cannot continue to train the protagonist. In Section 4.3.1 problem.
we propose improved objective which addresses this
A.2 TRAINING FLOW
In Figure 6 illustrate the high level workflow of the AEG with budget mechanism.
A.3 DISTRIBUTION OF PRIMITIVES DURING TRAINING
During training, the distribution of primitives become more skewed towards active primitives early on shown Figure but as the environments get more challenging, more passive primitives are introduced as well (Figure (7]. What we observe from the histograms in Figure iis is that new primitives are slowly introduced while the ranking of the primitives is also slightly changed.
A.4 ACTIVE AND PASSIVE PRIMITIVE FREQUENCIES
In Figure 8 present frequencies of active and passive primitives during training. With Flexible- bPAIRED, number both active and passive primitives increase resulting in more complex web- sites.
A.5 CREATING FULLY-SPECIFEED PRIMITIVES FROM UNDERSPECIFIED TEMPLATES
In Algorithm 2 we outline the process for generating a new fully-specified primitive from a given underspecified DOM template.
12

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Generating new fully-specified primitive from an underspecified primitive.
1: Imput:!) (Dn; De): An underspecified DOM template, a sub-tree with elements D, and edges De
2: Input:V C CDn: A list of elements that correspond to variables in D,
3: Input:Ay,t A list of variable attributes Au,, for an element D,,
4: for E V do
> Iterate over variable elements. Add/remove variable element.
5: Flip coin. If it heads, D,, Dn \ {o).
6: end for
b Iterate over non-variable elements. Iterate over variable attributes for element v. 9: Flip coin. it is heads, sample and assign value for Add/remove an attribute.
7: for Dn do
8:
for E Av, do
10: end for
If there is at least one variable attribute remaining for element v, Dn - Dn \ fo}.
12: end for
A.6 DETAILED RESULTS ON TEST ENVIRONMENTS
We detail the aggregated results in Figure 5 and present performance of agents across tasks and difficulty levels (Figure TT On the easiest level of tasks, CL achieves slightly lower performance than Flexible b-PAIRED early in the training while as the task difficulty increases, the gap becomes more apparent. We observe that the primitive distribution in Figure 7c and task success rate results are consistent in which late the training, the adversary focuses more on the 'Flight Booking' related primitives and its performance still strongly increases.
A.7 RESULTS ON MINIWOB ENVIRONMENTS
In Table 2 we present results on MiniWoB form-filling tasks and compare them gMiniWoB test tasks. MiniWol tasks are independent of @MiniWoB and they have completely unobserved DOM structures and labels. We load only the trained embedding layers from the final checkpoint there no element dependency on these DOMs. We show that we navigation agents trained with Flexible b-PAIRED are able to solve all MiniWoB tasks.
Compared to gMiniWoo WoB tasks, they are much simpler where DOM and instruction sizes are up to 10 times smaller. They also have only few input elements that the agent interact with while in gMiniWoB there are 10s of input elements making the gMiniWob WoB a formidable benchmark. As an example, in the Shopping task, size of the state and action spaces reach 5550 (number of tokens for all attributes in all elements in DOM) and 240 (total number of element and instruction pairs), respectively.
A.8 COMPARISON OF a IN BUDGET WEIGHTING
In Figure plot results where Flexible b-PAIRED is trained with different weights. For a 0.25, the performance drops substantially as the model gives more weight to the RL loss overall. In this work, used 1.25 for main results.
13

---

Under review as a conference paper at ICLR 2021
difficulty level
difficulty level
difficulty level
difficulty level
Ree JARREO
Login
Fice DITAREED
0.0
0.0
0.0
Ehillaatoon Sieps
Ehllaatonn Siecs
Exilcatin Siece
Exillation Siere
Enter Address
0.00
0.0
1000
2000
2000
1000
2003
2000
1000
2003
3000
2000
2003
3200
Enter Payment
0.
0.0
30005
Evallationn 50005
Elellcationn 500155
Eliiliattion 500155
Shopping
1000
2000
2000
1000
2000
3000
1000
2003
3000
2000
2003
3500
Flight Booking
CHalLUttinn S:655
EXSrLIaon 5185s
Evilluation She5s
Evillatton S5e
Table 1: Task success rate comparison of PAIRED and baseline models on test environments with increasing difficulty levels. From left to right, columns correspond increasing difficulty. From top to bottom, rows correspond to different test environments.
Task Name
Task Success
DOM Size
DOM Size
DOM Depth
Instruction Size
(Inputs)
enter- pase-pp
1.0
3
11
5
enter-text
1.0
2
6
4
enter-iext-dynamic
1.0
2
6
4
login (gMiniWoB)
0.92
10
34
21
address sgMiniWoll
0.74
38
22
payment (gMiniWoBi
0.78
13
49
28
flight (gMiniWoB)
0.79
16
60
33
shopping (gMiniWoB)
0.77
20 (40)
111
(183)
(111)
12
Table 2: MiniWoB form-fillin filliniiig environment results compared to gMiniWoB test environments. In- puts correspond to elements that are interactable by agents. For shopping, we report maximum and total (in parentheses) across 3 pages for DOM related statistics.
14

---

Under review as a conference paper at ICLR 2021
A.9
WEB ENVIRONMENT DESIGN PRIMITIVES
Design Primitives and Their Descriptions
Design Primitive
Design Template
Active/Passive
Description
addressline
input
active
Main address information
addressline2
input
active
Secondary address information
cabin
multi-selection
active
Multiple cabin options
captcha
input
active
Captcha information
carousel
carousel
passive
Items with images in carousel
with previous and next buttons
cart
cart
passive
Items in a product cart with promo
code information
CC
multi-selection active
Multiple credit card type options
CCCVV input active
Credit card CVV information
ccexpdate input active
Credit card expiration date informa- tion
conumber
input
active
Credit card number information
city
input
active
City address information
dealmedia
media
passive
Product media with image, label, and link
deck
deck
passive
Multiple product decks with image, label, and link
departureairport
input
active
Departure airport information
departuredate
input
active
Departure date information
destinationairport
input
active
Destination airport information
destinationdate
input
active
Destination date information
firstname
input
active
First name information
flighttype
multi-selection
active
Multiple flight type options
footerl
footer
passive
Footer with links and information
forgotpassword
link
passive
Link with forgot password context
forgotusername
link
passive
Link with forgot username context
fullname
input
active
First and last name information
header
label
passive
Generic header
header-login
label
passive
Header for login form
header.select.items
label
passive
Header for item selection
inpgroupl
input
passive
Generic input with default search context
lastname
input
active
Last name information
navbar
navigation bar
passive
A navigation bar with menu
next_checkout
button
passive
Next button with checkout context
next login
button
passive
Next button with login context
next login page
button
passive
Next button with login context
numberofpeople
multi-selection
active
Multiple number of people options
password
input
active
Password information
rememberme
selection
active
Checkbox with remember me con-
text
state input
active
State information
stayloggedin
selection
active
Checkbox with stay logged in con-
text
submit
button
passive
Submit button
username
input
active
Username information
zipcode
input
active Zipcode information
In Table A.9
we present the list of design primitives, corresponding templates, types, and descrip-
tions.
15

---

Under review as a conference paper at ICLR 2021
A.10 LIST OF TEST ENVIRONMENTS
In Figure 11 we present screenshots of the testing environments with the hardest difficulty levels. While "Login", "Enter Address", "Enter Payment", and "Flight Booking" are single page environ- ments, "Shopping" is multi-page environment where an agent needs to first navigate the home page and then solve "Login" and "Enter Address" tasks.
A.1I EXAMPLE WEB PAGE DESIGNS
In Figure present more screenshots of generated pages by the adversary from including multi- page websites. They cover a very broad spectrum of complexities and DOM tree structures. As an example, two web pages on the top right both have "City", "CVV", and "Address" elements but with different orders. This allows the web navigation agents to observe website in multiple different ways for better generalization.
A.12 IMPLEMENTATION DETAILS ON WEB NAVIGATION AND ADVERSARY NETWORKS
Following Gur et al. 2019), we design web navigation agent networks as DOM and profile encoders with pairwise similarity scoring. Each web navigation agent policy network has 104501 parameters.
we detail the adversary network architecture for single design action with the param- eters used in this work. We use 100 dimensions for hidden vectors for all dense layers as well as LSTM network. Every dense layer is stacked twice and tanh activation function is applied on the output of non-final dense layers. Total number parameters for the adversary policy network 152461.
In Figure 13
16

---

Under review as a conference paper at ICLR 2021
Learn to Jointly Design and Navigate Environments
REGRET and Navigator
performance
Design Adversary
Train Navigator Agents
Evaluate Navigator Actors
Last
Environment
Dacoder
reperta
Creates "just-right"
population navigator agents navigate the environment collects episodes..
The best performing agent is tested on unseen evaluation environments.
challenge for the navigation agents, Stays within a soft difficulty budget.
Popnant
Card
Trained with the REGRET and the best performing agent's score.
Trained with task success rewards.
Mou Cille
Example training website
Example
Figure 6: Training workflow. The adversary unrolls an environment, adding one element at the time of each page. That environment is passed on population of navigation agents under training. The navigators collect several episodes in the environment, and collect their estimates returns. The weight of the navigator agents updated w.r.t. their scores. And the adversary weights updated w.r.t. regret estimate and performance score of the best performing agent.
17

---

Under review as a conference paper at ICLR 2021
net Dyp
Geter
conantiee
deserT mal por
500
(a) Early
nigltiys
numiendoooe
odd eetrame
Add INTEENO
haader saledt
desemt reaipoo
500
(b) Middle
del livel Shal cert
THodde offic Sent
Dealhed
Seserturnal
Aurlogaed
fistraree
100
300
500
(c) Late
Figure 7: Histograms of primitives from early, middle, and late snapshots of the training.
18

---

Under review as a conference paper at ICLR 2021
Frequency of active primitives
Frequency of passive primitives
25
Flexible PAIRED
Flexible PAIRED
Flexible b-PAIRED
15
Flexible b-PAIRED
Frequency
Frequency
15
10
10
0
25000 50000 7500010000012000
25000 50000 75000100000125000
Training Steps
Training Steps
(a) Active Primitives
(b) Passive Primitives
Figure 8: Frequencies of active and passive primitives during training.
Aggregated comparison difficulty tasks Aggregated comparison difficulty tasks
1.0
1.0
Task Success Rate
Task Success Rate
0.8
0.8
0.6
0.6
alpha=02
0.4
alpha-0.5
0.4
alpha-0.75
0.2
0.2
alpha-1.25
1000
2000
3000
1000
2000
3000
Evaluation Steps
Evaluation Steps
(a) Difficulty level 1
(b) Difficulty level 2
Aggregated comparison on difficulty tasks
Aggregated comparison on 4 difficulty tasks
Task Task Success Rate
Task Success Rate
0.6
0.4
0.2
1000 2000
3000
1000
2000
3000
Evaluation Steps
Evaluation Steps
(c) Difficulty level 3
(d) Difficulty level 4
Figure 9: Aggregated task success rate comparison Flexible b-PAIRED trained with different a weights.
19

---

Under review as a conference paper at ICLR 2021
HOME
HOME
HOME
Poyment
Depa
HOME
O
Nirara
Ap
Passwcrd
29 Dack
Dalratio drs
Cab
Cap
Zpoxde
Frll
Dawnyy
Ruadio
(a) Login
(b) Enter Address
(c) Enter Payment
(d) Flight Booking
Figure 10: Screenshots of single page environments.
20

---

Under review as a conference paper at ICLR 2021
Dawal of
inde!
Title $0.99 decorptinn
Title
$1.98
Titlc S0 10
HOME
Title
HOME
Addros
sohic drow plow
Revonterre Capth
V00 ERR the Cergary Cortect femm Rupprt Pub
Zocado
Page argeraeeeen
Search
(a) Home Page
(b) Login Page
(c) Address Page
multi-page page "Shopping" environment. The "Shopping" environment is composed of complex home page and additional "Login" and "Enter Address" pages.
Figure 11: Screenshots of multi
21

---

Under review as a conference paper at ICLR 2021
Payment
Crudit Card
Cit
Cele
City
Roundiip
DW
Exprate
A3074C
Addras
Ad0895
Dio Ceicha
Mrrene
Actress
loged
Ota keceot
Rememerre
Ciyy
City
Piit
Diel the Day
Oelitedd!
Login
Depert
DWV
Expratill
Abhees
ON
Dear
Domey
Roandip
Drpull
Antmes
DW
AM0
Diar Capcha
wm
Cbty
O Bonnery
O
Caann
scnnery
Usemarre
Dee Capthe
Pleswond
Soarch
Acdress
Skay lagis
bock
Piic
Calén
2peads
Connory
agadt
Remember
Figure 12: Screenshots of sample pages generated by the adversary.
22

---

Under review as a conference paper at ICLR 2021
Next state Input for LSTM
concat
Output encoder network
[100 50)
[100
[10 x 100)
[41 100j
p(number of pages)
p(page location)
p(primitive)
Number of pages prediction network
[100 x 10)
Page location
[100
[100 x 41)
Primitive prediction network
prediction network
[100 x 100)
[100 x 100]
[100 100]
LSTM [2 100 x 400]
Initial observation encoder
[100 100]
[100 100]
Observation 100]
Figure 13: Each box corresponds to dense layer with the shape the corresponding linear trans- formation matrix. Each dense layer also includes a bias vector with the same size as the columns of the corresponding matrices.
23


Reviews:
[{"review_id": "wzz8-AIR3MM", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper improves upon existing approaches for learning to fill forms on the web automatically. The main idea is to train an adversary to generate a curriculum of environments to train an agent to learn to fill forms on the web. Training such an adversary can be challenging since the adversary may prove to be too strong for the main agent to learn anything from. Thus, the paper proposes few techniques to control or shape this adversary such that the main agent is able to learn quickly as compared to similar existing approach. \n\nThe paper is well-written and clear for most parts. I feel the improvements the paper suggests are insightful and significant. The empirical analysis is also quite satisfactory and clearly shows the superiority of the proposed approach over existing baselines.\n\nI dont have any major criticism for the paper as I quite like it. Here are a few minor points that I think the paper can improve on:\n- The paper can benefit from a more general formulation of the task it solves. Currently, the paper is focused on web navigation tasks. This is not a weakness per se, but an abstract and general formulation of the task and solution can enhance the paper.\n- On similar lines, the paper should consider toning down the claims a litte. Web navigation is quite a complex task that may use more than one aspect (if I may say so) of human intelligence. The paper presents an approach for matching provided information to the correct box in a web-form. This is quite simple as compared to web navigation. \n- The paper can benefit from a few figures explaining the proposed system and experimental setup.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "SoEawEi2joh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main research contribution of this paper is the Flexible-PAIRED, and bPAIRED algorithms for generating Web Sites that can be then \"used\" by automatic agents. The modifications to the original PAIRED algorithm is quite simple but proven to be effective in the paper.\n\nHonestly, I believe the paper has some merit but in the current form is quite difficult to be understood.\n\nFirst and foremost, it is really not clear what are the motivations behind the research work. I understand that you want to learn a policy for filling in a web form but, honestly, I am not sure I got that. The examples you make are not super clear, you should give an idea, for instance, of what's the complexity of the tasks in the examples. For instance, booking a flight to LAX for Friday involves: i) inputting LAX in an entry box, clicking search button, select flights according to user preferences (how are these taken into account, BTW?) and then pay using a credit card. Now, all of these passages are quite difficult and complex and I am not sure the technique presented in the paper actually can do that. From the paper it is not clear what are the tasks considered and how they are generated.\n\nThe second question I have regards the relevance of the results. While the difference between PAIRED and Flexible-PAIRED and Flexible-bPAIRED are large, it is not clear that a success rate of 80% can be considered high enough for real systems.\n\nOne thing that should be improved is readability, in general. For instance, the description of the PAIRED algorithm is quite difficult to follow. I understand that this is not an algorithm that is developed by the authors but the description should be done in a correct way that will make the reader understand what are the shortcomings and why you had to propose Flexible-PAIRED and bPAIRED.\n\nA relatively minor point that needs explanation regards the impact of the simplification of the generation process described in Section 4. It is not clear if the limitations of the primitives used also limit greatly the diversity of the generated pages making the task simpler.\n\nIt is true, though, that results are much better than the baseline and for this reason I believe the paper has some merit.\n\nMinor issues:\n1. The first sentence in the Introduction is difficult to understand and does not set correctly the goals of the paper. What do you learn to generate? DOMs or Tasks + DOMs?\n2. The regret will be highest for easy --> the regret will be higher\n3. \"assume links between pages are implicitly defined by events attached to certain elements.\" --> This sentence is not clear", "extra_scores": {}, "extra_text": {}}, {"review_id": "OOk7hDt2pDy", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the problem of learning to autonomously navigate the web, such as filling out web forms. It proposes a curriculum learning method that uses Adversarial Environment Generation (AEG) to build a curriculum of challenging web navigation tasks. It is based on the idea of creating training environments for RL agents. The paper is well written and easily accessible. The problem in this work is an interesting application of RL. The idea is not very new and extends from previous works using AEG.\n\nIt is difficult to compare the difference between the paper and PAIRED (Dennis et al., 2020). Because PAIRED (Dennis et al., 2020) is not public yet. However, as described in the related work, it seems like that the paper just applies AEG methods on complex, high-dimensional environments with some extension. The novelty of the work is limited. \n\nIn addition, the GAN part is also similar to Goal GAN (Florensa et al., 2017). The difference is how to label an environment (or a goal in Goal GAN). It is better to have more details about the adversary architecture. For example, how to label environments and train the adversary architecture.\n\nIt is unclear why the Adversarial Environment Generation (AEG) can provide a curriculum of learning different tasks. It is worth providing more experimental results about the progress of curriculum learning. \n\nOverall, the main weaknesses are the novelty of the idea compared to previous works and how curriculum learning works for navigating the web tasks.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JsVoR1DlVCq", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a technique for adversarial generation of environments for the interesting problem of web navigation, and provides an environment that enables learning to design complex websites out of a set of compositional primitives. Then, it also proposes a method to adversarially generate a curriculum of increasingly complicated websites, and uses it to train agents which can navigate more challenging, high-dimensional websites.\n\nStrengths:\n1. An interesting novel problem domain; which is going to be very useful in a number of human computer interaction applications.\n2. The web navigation environment is interesting - it will hopefully spur more research for this problem\n3. The training of agents with an autoregressive adversary policy is interesting.\n\nWeaknesses:\n1. The discussion on related work on this application seems sparse; hence, for me, it was hard to judge the novelty of this work.\n2. More discussion of the environment - some examples, what makes it hard, or easy would help the reader understand the key challenges.\n3. More discussion on past work in interactive learning with autoregressive adversarial policies would be helpful. It will help the reader understand why this is a different interactive task and what makes it more interesting or challenging.\n4. The experimental section is too sparse. Some more ablation studies on different parts of the model - e.g. budget enforcing on the adversary would be helpful.\n5. The b-paired and flexible b-paired agents seem to be very similar to each other - especially for some problems. Some more analysis of this would be useful.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of agents learning to autonomously navigate the web, specifically by focusing on filling out forms. The focus is on using adversarial environment generation to form a curriculum of training tasks.
Thank you for the revisions to the manuscript, which have particularly improved readability.
The presented problem is really interesting and seems an important real-world problem for RL.
Despite this, as the paper stands the results are not completely convincing. It seems like there is also scope to rigourously analyse the proposed method on other, better known domains to better quantify its limitations.
Decision: Reject