Environment Generation for Zero-Shot Compositional Reinforcement Learning
Authors: Izzeddin Gur
Natasha Jaques
Yingjie Miao
Jongwook Choi
Manoj Tiwari
Honglak Lee
Aleksandra Faust
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adversarial Environment Generation
Compositional Reinforcement Learning
Minimax Regret Adversary
Auto Curriculum

Abstract: Many real-world problems are compositional – solving them requires completing interdependent sub-tasks, either in series or in parallel, that can be represented as a dependency graph. Deep reinforcement learning (RL) agents often struggle to learn such complex tasks due to the long time horizons and sparse rewards. To address this problem, we present Compositional Design of Environments (CoDE), which trains a Generator agent to automatically build a series of compositional tasks tailored to the RL agent’s current skill level. This automatic curriculum not only enables the agent to learn more complex tasks than it could have otherwise, but also selects tasks where the agent’s performance is weak, enhancing its robustness and ability to generalize zero-shot to unseen tasks at test-time. We analyze why current environment generation techniques are insufficient for the problem of generating compositional tasks, and propose a new algorithm that addresses these issues. Our results assess learning and generalization across multiple compositional tasks, including the real-world problem of learning to navigate and interact with web pages. We learn to generate environments composed of multiple pages or rooms, and train RL agents capable of completing wide-range of complex tasks in those environments. We contribute two new benchmark frameworks for generating compositional tasks, compositional MiniGrid and gMiniWoB for web navigation. CoDE yields 4x higher success rate than the strongest baseline, and demonstrates strong performance of real websites learned on 3500 primitive tasks.

Environment Generation for Zero-Shot Compositional Reinforcement Learning
Izzeddin Gur, Natasha Jaques, Yingjie Miao, Jongwook Choi,
Manoj Tiwari, Honglak Lee, Aleksandra Faust
Google Research, Brain Team
Mountain View, California, 94043
lizzeddinn natasha aques, yingjiemiao, mjtiwari, sandraf Sandrafaustt@googlee.om com [jwook, honglak)@umich edu
Abstract
Many real-world problems are compositional - solving them requires completing interdependent sub-tasks, either in series or in parallel, that can be represented as a dependency graph. Deep reinforcement learning (RL) agents often struggle learn such complex tasks due to the long time horizons and sparse rewards. To address this problem, we present Compositional Design of Environments (CoDE), which trains a Generator agent to automatically build a series of compositional tasks tailored to the RL agent's current skill level. This automatic curriculum not only enables the agent to learn more complex tasks than it could have otherwise, but also selects tasks where the agent's performance weak, enhancing its robustness and ability to generalize zero-shot to unseen tasks at test-time. We analyze why current environment generation techniques insufficient for the problem of generating compositional tasks, and propose new algorithm that addresses these issues. Our results assess learning and generalization across multiple compositional tasks, including the real-world problem of learning to navigate and interact with web pages. We learn to generate environments composed of multiple pages or rooms, and train RL agents capable of completing wide-range of complex tasks in those environments. We contribute two new benchmark frameworks for generating compositional tasks, compositional MiniGrid and gMiniWoB for web navigation. CoDE yields 4x higher success rate than the strongest baseline, and demonstrates strong performance of real websites learned on 3500 primitive tasks.
1 Introduction
Consider purchasing an airline ticket, logging in to a website, or buying movie tickets. These tasks can be completed by mastering small set of basic manipulation skills (primitives), such entering an appropriate text in a fill-in field, or selecting a date, and combining them in different ways to form easily generalize between compositional tasks
complex, compositional tasks [2). Humans purchase a ticket on an airline or fill out a form that they have not seen before, even when the task carries over several pages but training autonomous agents to do this is far from straightforward. Yet, unlocking generalization across related tasks would pave the way towards autonomous agents that can automatically handle the details of completing wide variety of real-world user requests such as, "Buy me a plane ticket to Los Angeles leaving on Friday". The complexity and diversity of real environments make this formidable challenge, especially due the exponentially exploding action space and sparse rewards.
Generalizing across compositional tasks is challenging for several reasons, including the tractability of training [4]] Many compositional tasks require planning over an excessively long horizon while providing only sparse rewards, making it difficult for RL agents learn. Presenting easy tasks
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(a) Iter=100
(b) Iter=12000
(c) Iter=24000
(d) Web Nav. Test
(e) cMiniGrid Test
Figure 1: Enviromments examples. Generated Web pages become more complicated over the course of training
(a-c), unseen test "Login" website (d) and "Task List" minigrid (e) environments. More Appendix |A.13
until the agent learns can be solution, but it is not clear how to construct such curriculum for complex compositional tasks [20 Manually designing a pre-defined curriculum is tedious, and intractable. Domain randomization (DR) [1 does not tailor the difficulty of the task to the ability of the agent. Automatically generating tasks tailored to the agent's learning progress is a promising approach, but as we will show, current approaches (e.g. ( suffer from fundamental limitations in the context of generating compositional tasks.
We present a new automatic curriculum generation algorithm. Compositional Design of Environments (CoDE), which jointly trains a Generator and a population of Learner agents. The generator is trained with a novel multi-objective reward function. Its first objective is to maximize the regret between the agents in the population and the perf-rerrorming agent, stabilizing regret estimation and making it less vulnerable to becoming stuck in local minima. Second, the generator is trained to adjust the task difficulty to match the learners' proficiency using an explicit difficulty incentive designed for use with compositional tasks. In this way, the generator builds more challenging environments when the learners are performing well, and reduces the difficulty when the learners are struggling. We demonstrate that this difficulty incentive addresses degenerative edge cases present in prior work.
By automatically searching for tasks on which the learners are performing poorly, the generator makes the learners more robust, enabling them to generalize to unseen tasks at test time. This ability necessary for many real-world tasks, such as web navigation. Prior work on web navigation relied on collecting demonstration data from a series of training websites [3 21], or training a separate policy for every single website [17 These techniques cannot scale because they would require re- ce-training the agents every time an airline company updated its site. In contrast, we show that CoDE produces robust agents with general form-filling and navigation skills that can be applied zero-shot to novel tasks at test time.
production-qualin system,
Another challenge in learning compositional tasks that the existing benchmarks do not match real-life complexities. For example, real websites are orders of magnitude more complex than existing benchmarks [36. 21). To address this problem, we introduce two new benchmark tasks for compositional task generation, which we are releasing in open-source. The first provides a way to automatically generate Minigrid
O navigation tasks which include subtasks such as locating a key to open a door. The second, generative MiniWoB (g.MiniWob), focuses on web navigation and manipulation (form-filling) tasks and enables generator construct increasingly complex form- filling websites, spanning multiple pages, out of common design primitives such as navigation bars, product carousels, item decks, and item carts (Figure D.. The evaluation environments in MiniWoBB are orders of magnitude more complex than Mini WoB, the prior web navigation benchmark (36
This paper makes the following contributions. First, we formally introduce compositional tasks by drawing a connection to the Petri Nets graph formalism, and showing its relationship to POMDPs. We then analyze why prior techniques for automatically generating curriculum of tasks are insufficient for compositional tasks, and propose new algorithm, CoDE that addresses these weaknesses. We build two new automatic task generation environments spanning simple navigation tasks and web navigation, and release both in open-source. We demonstrate strong empirical results across both domains. In the context of web navigation, we show that CoDE generates a curriculum of increasingly challenging websites. Resulting agents successfully generalize to complex, unseen sites at test time, and without additional training solve wide range of form-filling tasks from flight purchases to login in. CoDE agents solve the most difficult tasks with x 90% success rate, 4x improvement

---

(a) Primitives
(b) Example
(c) Example 2
Figure 2: Examples of compositional task primitives (a) and two different compositional tasks composed using the same primitives (b-c). Note, passive primitives (in grey) that do not lead to the task progression and serve as distraction for the agent. Difficulty budget for the generator is based the number of primitives used.
over the strongest baseline. Lastly, we demonstrate that the method scales up to real websites. The implementation of CoDE and gMiniWoB framework are available in open source at https //github. ctweuuubooom/egee wwwpoooeeeeeerrcceeeeeeeeeeeeeee htt.ar/wwtteageeeeeeeccerrrreaar
Related work
Compositional task representation: Compositional tasks G have been represented vector sum of primitive skills [9], or sequence of subtasks [30]. The dependency graph representation (2) 38]
considers a task the definition of the compositional tasks to represent real-work challenges. First, we allow primitives that do not lead to task completion. Second, we allow for partially observed environments. Third, formalize the task distribution with a family of Petri Nets (34.. which have also been used to describe robot tasks (TO), planning tasks (77), and workflows [1. We PNs with color and hierarchy, structured similarly to the workflows, but allow dangling nodes. Beccuti et al. 4 map PNs to MDPs, while we propose mapping between a of PNs to a set of POMDPs.
graph of subtasks equipped with dependencies as logical expressions. We relax
Curriculum Generation: A variety of curriculum learning methods exist which do not generate
whole enviromments. For example, Florensa et al. [ train Generative Adversarial Network (GAN) to generate a curriculum of goal images for a goal-conditioned policy to reach. Other methods focus on choosing which task out of set of pre-defined tasks present next 22
45
[2]. Another line of
research studies creating curricula where a target task is already given 40
31 Multi-agent training
also be effective for automatically generating curriculum 19 16
39
28). Czarnecki
et al. ? takes an alternative approach and generates a curriculum over agents instead of tasks. Finally, Active Domain Randomization 25 3i learns to set the parameters of an environment simulator in order to provide a curriculum of increasingly difficult environments. In contrast, we focus on sequentially constructing an entire environment or task, composed of multiple subtasks, without target task is explicitly given.
generates terrains for 2D walker with population of environment-genernee -eeneeringggnnniiigggggn adversaries. Campero et al. [5]] train a teacher to propose navigation tasks based on length threshold. Most closely related our work is PAIRED R. which gener- ates environments that induce maximal regret between pair of agents. However, PAIRED only demonstrates results simple gridworlds, and does not expand to complex, compositional tasks. We analyze several deficiencies in PAIRED that inhibit its use for the compositional setting, including a degenerate case where fails work at all. Our proposed algorithm addresses these deficiencies. To the best of our knowledge, we are the first work to attempt to automatically generate compositional tasks, and the first to apply environment generation to the problem of web navigation.
Environment Generation: POET
Web navigation benchmarks and tasks: MiniWoB [36] and MiniWoB++ 21 environments con- tribute fixed set of manually curated toy websites, and train agents using expert demonstrations for each website. This cannot scale effectively to cover the large variety of real-world websites, and cannot adapt changing websites. Further, these methods failed to solve complex tasks such as flight booking or social media interaction. Using a manually scheduled curriculum [77] improves upon these results, but does not adapt to the agent's progress or generalize unseen sites. This work differs in several ways. First, we introduce a new framework, gMiniWoB, that allows generating complex websites on-the-fly with tunable difficulty levels. Additionally, we do not rely on any expert demonstrations to augment sparse rewards. Most importantly, our web navigation agents generalize to unseen environments, an important requirement for wellwworld web navigation agents.
3 Compositional tasks problem definition
Compositional tasks are composed of subtasks, which in turn are composed of primitive skills. This type of problem can be formalized using task dependency graph, in which dependencies between the
3

---

subtasks are represented as edges (see Figure 2 We model tasks in which the agent must complete several subtasks in order to trigger phase transition in the environment, such as locating a key and unlocking a door in order to enter a new room, or completely navigating and correctly manipulating one web page in order to transition to the next one.
We assume that the navigation agent uses standard POMDP setup tuple (S, rr,,) where (s)) are partial observations, a E A are actions, and 7 [0, 1) is a discount
E S are states, factor. At each timestep i, the agent selects action ar according to its policy л, receives reward r(a, St), and the environment transitions according to ((s 1st, at). Agents seek maximize their return, the discounted sum of rewards: R(*) = Σi= ?
We use Petri Nets (PNs) 14 framework to formally define learnable compositional tasks. PNs are directional graphs consisting place and transition nodes, and easily model different dependencies such as sequential, concurrent, choice, etc. Places are system states; transitions are points in the process that takes the system to the next state. Edges determine the dependencies between nodes. At execution time, PNs have tokens that propagate through the net between places and determine the system state. In PNs with colors (CPN) [4] tokens are assigned a value, and Hierarchical PNs [T] replace subnets with transitions.
We define a primitive as a workflow (a special type of PN) with multiple places/transitions where there is no parallelism (see Figure 2a). They can be combined in parallel or serial using another transition (ex: Figure 26). The set colors, C, represents data semantics that agent needs to place in the environment to complete the task (i.e. flight departure or return dates). In the form filling task, agent needs to complete all the relevant fields before proceeding to the submit button that presents the next page. To that end, we introduce gate, a special transition state that completes a phase and moves the system to the next (e.g. move between the pages web navigation, or move between rooms in navigation tasks). Learnable compositional tasks, is a family of directed acyelic PNs with colors induced with a set of primitives Pc.
Learnable tasks described above map compositional tasks to POMDP (S, 0) that define RL navigation agents, and generator architecture which allows the generator to generate tasks only with the structure defined by PN. See Appendix A.1 I.II for more details on PetriNets and their connection to POMDPs.
4 Environment generation with minimax regret analysis
To train robust agents able to learn complex tasks, it would be helpful to generate a curriculum of tasks that are designed to be just outside of their current skill level. This requires training Generator policy ~ to construct an environment & that will challenge a learner policy π² (e.g.
[K] To find tasks that are solvable, but where the learner is weak, we can train the generator to maximize the regret. Regret is the difference between the return obtained by policy π² and the return that would have been obtained with the optimal policy x² in the same environment E: REGRET = R (T*) - R (T² Because the optimal policy is not known priori, PAIRED [ approximates the regret by introducing a third antagonist agent, with policy Λ², and computing the regret with respect to it: J JAIRED = Rº (T²)- Rº (T In order to generate a viable curriculum, regret minimization relies on the assumption that the reward function includes an incentive to complete the task more efficiently. In this case, the regret will be highest for easy tasks which could be completed in few steps by the optimal policy, but which the learner policy l fails to complete. Thus, regret is useful objective for inducing curriculum when it is possible for the generator to build impossible environments, and the reward includes incentives to complete the task in fewer timesteps.
Degenerate case. What happens if the assumptions listed above are violated? For example. consider the case where there is only binary reward E {+1,- -1} depending on whether the agent correctly performs subtask or not, and the generator constrained such that it cannot construct impossible environments. These assumptions are both true in the case of the compositional task graphs we study in this paper. Consider the simplest possible task graph, the Chain MDP pictured in Figure g The agent only receives positive reward if it reaches state sx, and from state st
Start Here
Goal
Figure In chain environments, it becomes exponentially more difficult to reach the goal via random exploration as N increases.

---

it can only reach state s;-1 or 8,41. The probability of reaching ey through random exploration is Prench (N) = O(p*) (see Appendix Section A.2 for the proof), which decreases exponentially as more states are added. By our assumption, we know it is possible to reach & and so the reward for the optimal policy is R(x*) = Then, maximizing REGRET 1 R (m²) reduces to minimizing the probability that the learner obtains reward, i.e. Preach (N). This can be accomplished by continuing to increase N. For compositional tasks, this means the generator will add as many elements to the environment as possible. In this case, maximizing regret will not lead to curriculum, and could actually slow learning more than randomly generating environments with Domain Randomization.
Sparse rewards. Even if the assumption that R (x*) is higher for easier environments is met, the regret signal used to train the generator can still be extremely sparse. Consider the case where both the learner and antagonist agent cannot solve the task. In this case, they never receive positive reward, their rewards are equal, and the regret is zero. This gives the generator no signal with which to learn to decrease the difficulty of the environment to enable them to start learning. Once again, the generator no better at generating a curriculum than randomly sampling environments.
Lack of convergence and stalled training. The proof that the PAIRED algorithm will produce a learner agent with minimal regret relies on the assumption that the game will reach a Nash equilibrium [. However, in practice gradient-based multi-agent RL has no convergence guarantees, is highly non-stationary, and will often fail to converge
If the game does not converge, then PAIRED minimizes regret with respect to the antagonist's 's policy, which only forces the learner to be as good as the antagonist. If the antagonist fails to improve, or reaches a local optimum, then the curriculum will stall and the learner cannot continue to improve.
23 24
5
Compositional Design of Environments (CoDE)
We present a new algorithm, Compositional Design of Environments (CoDE), for automatically generating a curriculum of compositional tasks, CoDE trains a generator to construct compositional environments out of primitives, and then uses those environments to train population P of learner agents. The rewards obtained by the learners across environments are used to compute a multi- objective reward function to train the generator to produce an effective curriculum.
Population-basee regret estimation: Despite issues with its estimation in prior work, regret is a useful incentive for environment generation because it encourages the generator to explore towards environments that promote variation in performance, indicating they have learning potential. Thus, the first component of our algorithm is new, more flexible population-basee estimate of regret (PopRegret) that is not subject to the problem of stalled training if the game converges to local optima. For each environment& constructed by the generator, each agent p E P collects M episodes in the environment. The regret is the difference between the average score of the population, and the score of the policy that achieved the highest average return over the M episodes. Let Re, (T²) be the return obtained by policy p in episode m. Then:
IP| Σ
J PoPREGuET_ = max Em [ (T")]
Em [ (T*))
(1)
P
K
As long as any agent has higher performance than any other agent, the objective will continue to identify environments in which there is learning potential, preventing training from stalling. As the agents continue learning, the best-performing agent in the population more closely approximates the optimal policy, providing a stronger estimate of the regret. Further, the regret estimate is smoother and more consistently positive than the regret obtained via the maximum of a pre-selected agent, providing more stable signal for the generator to learn to optimize.
Difficulty budget: Even with more stable estimate of the regret, training can still be slow and unstable if the rewards are sparse, and potentially subject to the degenerate case identified in Section q To address these issues, we add an incentive for the generator to tune the difficulty of the environment to the current skill level of the agents. Let N be the number of primitives added to the task graph, and p = arg max pEP R (TT) be the agent with the highest score in environment E. Then:
J DIFFICLLTY (E) = (1 (T*)= > 3] - -I[R (T²) < 8)) MANN/maa.
(2)
where 1 the indicator function and 8 < 3 are reward thresholds for failure and success, respectively. Thus, if the best perfformrr agent gets high score the task, the generator gets reward based on
5

---

Page 1
Page
Website
Usemane
Rendering
USERNAME
LOGIN
FIRSTNAME
Adversary
LSTM
LSTM
Obs
Figure 4: A sample rollout of the generator for compositional web navigation task. An initial observation (Obs) is given the beginning of the rollout. fo. fk. fr. and fi networks encode initial observation, creating subtasks, primitives, and encoding LSTM inputs. In practice, we also an additional independent network fr to create page indices where each primitive assigned.
the number of primitives it added to the environment, Nmass However, if all the agents are performing poorly, the generator is penalized according to the number of primitives it added and receives N 'naas" This makes adding more primitives risky, unless the generator can be sure that at least one agent in the population can solve the environment. It thus incentivized to create tasks that challenge all but the best- pest-performing agents in the population, while still decreasing the difficulty when the agents are not learning.
N
The generator is a decoder designed to construct an environment & by placing We assume fixed maximum number of subtasks K, and allow for up to N primitives to be added to the environment. To control for complexity, empty subtasks with no primitives are allowed. The generator's policy (E(o)) is conditioned on an initial observation oc ~ N (0, 1) sampled from the standard normal distribution, which allows to diversify its design distribution (similar a GAN generator [55). the environment according to:
Generator model:
set of primitives A within set of subtasks ..,,... Wk].
It then constructs
(E10 = TE. (k II IT (a:1aon-1:)))
where a, corresponds to a primitive. The generator first encodes oc with a feed forward network ho = (o(o)). The encoding An is passed to another network fx that outputs Categorical distribution CO, K), from which the number of subtasks is sampled k ~ Cat (0, K). Given & and initial state ho. the generator executes autoregressive LSTM policy to sample primitives a,, through network fP (see Appendix A. 14 for more details). Thus, the generator is a stochastic, open-loop policy. Note that there is SKIP action that does not add new primitive, enabling the generator to reduce complexity. The finished design E is sent to renderer module to generate the environment. Figure shows example of how the generator constructs environment which the renderer converts to website. Note that the generator is domain independent, and creates a generic compositional task or PN; indeed, use the same model for both experiment domains.
Difficulty budget implementation: Rather than directly counting the number of primitives for the difficulty, we replace N in Eq. n with the amount of probability the generator places on the This
SKIP action throughout generating the environment: Ñ := Σi= log Te (a, SKIP allows for a more direct control over generator policy to optimize difficulty. We also scale Eq. 2 by the reward received by the best berf-performing agent to provide further signal to the generator.
Algorithm D shows the CoDE training procedure. Both the generator and learner agents are trained using RI,, specifically A2C (26 with entropy regularization. For every training step, the generator constructs an environment ε, and the agents p E P collect M trajectories within E. Ehehe learner agents are trained using the standard task related reward. To train the generator, use the following multi-objective loss function that encourages the adversary to control the complexity of the environment by presenting tjust-the-right challenge" for the agents in P, where is hyperparameter:
Algorithm:
JEE = (1 a) POPREGRET (E,P) +
J DIFFICLLYY (E,
(4)

---

Algorithm 1: CoDE: Joint training of the generator and learner agents.
Initialize policies for generator δ. and agents TP, Vp E P for all training iterations do E *T(EEl0)), o ~ NN(, ;);
> Generator constructs environment
for p =0=,, -.... [P] do
for 1, M do (TP)
Collect rewards for agent p in environment Egg RL update for agent p using collected experience;
R (T(P))
Train learner
Compute JREGRET using Eq.
Compute J DDIFIIULIYY using Eq.
RL update for generator using Eq 4 as the reward
Train generator
Benchmark environments
We contribute two open-source frameworks for compositional tasks construction out of a set of primitives: Compositional MiniGrid (cMiniGrid) and Generative MiniWoB (gMiniWob).
cMiniGrid is compositional extension of MiniGrid navigation environments [6]. in which agents interact with various objects. eMiniGrid contains the following subtasks: pick up the key, unlock the door, pick up the ball, open the box, drop the ball in the box, reach the goal. The generator chooses subtasks add, and the renderer places objects. The problems have sparse rewards which are only given for completing a subtask, which each require many steps.
MMiniWob is generative extension of miniWob and miniWob++ web navigation benchmarks, extending them to multi-page navigation and richer websites. gMiniWob enables generation of web navigation tasks consisting of multiple web pages (subtasks), each composed of primitives (see Figure 2). The renderer handles linking the pages via output primitives (c.g. by adding a submit button). Each primitive is represented using Document Object Model (DOM) tree, and rendered using HTML. gMiniWoB implements 40 common web primitives, such as navigation bars, carousels, item decks, web forms, item carts, dropdowns, etc. The order in which primitives are added defines how a webpage will be rendered for the agent, facilitating controllable generation with rich design set. Every primitive changes the DOM structure when the agent interacts with it. 26 of the 40 primitives are active, while the rest are passive (i.e. they do not relate to the task, like an ad banner). When the generator adds an active primitive, the renderer adds the corresponding piece of data to the agent's instruction set, increasing the complexity of the task. For example, adding a 'First Name' text box also adds a new "firstname" " field into the instruction. See Appendix [T. for all the primitives, and Appendix for for the test set. Note that with 40 possible primitives across 10 web pages, gMiniWob provides the ability to generate se 10-4 distinct web navigation tasks.
As in 17. the web-navigating RL agent receives a text instruction containing various fields of information, and must interact with DOM elements, fill in the necessary information, and navigate through the pages to complete the task. The agent observes the DOM tree of the current page. Its actions are tuple (element, field) that denotes inputting the field into the element. For example, in flight booking task, given the instruction ("Departure Date": "Friday", Destination Airport: "Los Angeles (LAX)", "Address": ...), ), the agent must first pick the textbox labeled "dest", find the corresponding field in the instruction (Destination Airport) and type the value ("Los Angeles (LAX)"). The agent receives a small penalty each timestep to encourage efficient navigation. Correctly filling out information within the page results in positive reward, normalized over the total number of fields in the instruction (e.g. if there are F fields, the agent receives reward of 1/F). Agents receive reward of 1.0 for completing the task, and -1.0 otherwise.
7 Evaluations
Implementation: Following Gur et 17 the learner policy is an L.STM based DOM tree encoder and feed forward network to encode instruction fields. The policy outputs a joint distribution over
7

---

Env.
Task
DOM
Instr. Size
LfD
CL
ALP
PAIRED
CoDE
Size
DOM 21
Vis.
password
11
0%
100%
100%
100%
MiniWoB
enter-text
6
0%
100%
N/A
N/A
N/A
100%
36
dynamic
6
0%
100%
100%
100%
login
35
3%
23%
20%
92%
address
38
7
0%
15%
8%
98 %
gMiniWoB
payment
49
N/A
N/A
0%
7%
16%
93%
flight
60
0%
2%
20%
95%
shopping
183
12
0%
6%
Table 1: CoDE performance on MiniWoB form-filling and gMiniWob test environments compared several baselines. DOM Size and Instruction Size illustrate the complexity of the environment. Learning from Demonstration (LfD) and Curriculum Learning (CL) methods train separate model for each test environments, and the results are reported from the previous publications. PAIRED, ALP and CoDE train a single model that is evaluated across all benchmark tasks. CoDE generalizes all tasks, and outperforms all baselines.
elements and fields by measuring pairwise similarities between element encodings and instruction fields. We compute the value by using the marginal distribution of elements as attention weights element encodings and passing the context vector through feed-forward network. CoDE is implemented using ACME [18] with T'esorFlow [2] open-source libraries. The training is done on a single CPU, requiring about week of training. The results reported are averaged over 5 seeds.
Baselines: We compare to: a) PAIRED [ for fair comparison, we limit the size of the CoDE
population [P] 2, since PAIRED uses two agents estimate regret; b) ALP 32]; we use absolute
difference between rewards of a single navigator at timestep and ( as the reward for the adversary without any difficulty bugdet: Domain Randomization (DR): B5
sample the number of subtasks and the primitives from uniform distributions. d) Curriculum Learning (CL): based on the state-of-the-e oftt-h-rttht-tttt- web navigation RL agent Gur et al. [T.. We adapt this method to zero-shot environment generation where we are not given a specific website but a set of design primitives. We randomly sample each primitive w.r.t. probability p where p is initialized with small number and scheduled to reach 1.0 during training; d) Learning from Demonstrations for web navigation from and image (LID Visual) [1
DOM inputs (LID DOM) 36
Web navigation evaluation:
We evaluate our models on MiniWoB 36 and a suite of test environ- ments implemented in gMiniWoB ('Login', 'Enter Address', 'Flight Booking'. 'Enter Payment', and 'Shopping' websites). Each environment comes with 4 different difficulty levels by gradually adding more primitives. These environments performance measures how well agents can generalize to unseen websites at test time. To train CoDE use 40 hand-engineered primitives, included with gMiniWob which blocks for the test environments. Finally, we conduct an experiment based on real websites, where the extracted
explicitly presented to agents during training, so
also used building
generator chooses from among 3500 primitives scraped from the web. The primitives from 200 different websites the password change, food ordering, and shopping domains. We evaluate agents' performance held of real websites, never presented during training.
7.1 Results
Overall performance: CoDE outperforms the baselines across the benchmarks, both in web naviga- tion and cMiniGrid. CoDE at least 4x more successful at completing web navigation tasks than the strongest bascline (see Table Db. and reaches more than 90% task success across all difficulty levels (Figure 7. On cMiniGrid environments, CoDE has nearly 3x the success rate PAIRED, solving 45% 16% of tasks (Figure 5). demonstrating CoDE's versatility across very different domains. We present additional results and ablation study in Appendix A.3
Regret minimization with sparse reward: In eMiniGrid rewards are sparse, and frequently no agents in the population receive reward, resulting in zero regret and absence of training signal. As predicted, under these conditions maximizing the regret leads to poor performance (Figure 5). Training stalls, and the agents do not achieve high reward. contrast, adding the difficulty objective significantly improves results.

---

MIRED
CrDE
4.
6.0E-0.6
(a) Legend
(b) Complexity
(c) Regret
(d) Reward
Figure 5: eMiniGrid experiments. Due to sparse rewards, the PAIRED algorithm fails generate complex
environments or train agents with high reward. Adding difficulty incentive (with increasing a) enables both.
Distrinution active primit
1.0
PAIRE
1.0
1.0
0.8
Poptawcret
0.5
Rate
c..
3.9
CoDE
CoDE bwt popregreti
0.5
0.0
0.4
0.4
SopRegret
30.
0.2
0.2
CoBE
DRCCL
0.0
0.0
0.0
250
50n
250
1000
250
1000
250
1030
20000 43000 60000
80000
Evalu
(a) Payment
(b) Shopping
(c) Flight booking
(d) Primitives
Figure 6: Comparison of PAIRED
8 and CoDE averaged over 4 difficulty levels. (0): Percentage of active
primitives over training steps (see Appendix A.6 for details).
Importance of difficulty budget: Difficulty incentive leads large improvement in performance of CoDE over the baselines on the web navigation tasks (Figures O and 7 When agents are struggling learn and have very similar rewards, the regret becomes very small. This uninformative signal makes it difficult for the regret-based methods (PAIRED and PopRegret) to learn. On the other hand, CoDE provides clear signal to the generator that improves performance significantly under consideration. Detailed results are in Appendix A.8] and further ablation studies in Appendix A.10 investigate the effect of the budget weight a.
all tasks
Importance of better regret estimation: While the difficulty incentive provides a large boost to performance, it has limitation in that it may not always be straightforward to calculate the difficulty of a generated task (for example, if the number of primitives added does not correspond directly to difficulty). In this case, it is necessary to rely the regret objective becomes important. We demonstrate, two ways, that the proposed population- based regret estimate in Eq M (Figure 66. First, while PATRED training stalls, especially for difficult tasks such as shopping and flight booking, PopRegret agents learn more effectively. Second,
general objectives such as regret, and stablizing
(PopRegret) provides an advantage the regret estimation in PAIRED
assess the contribution of PopRegret to the CoDE algorithm by comparing CoDE with no PopRegret (i.e. using only the difficulty incentive) the full algorithm. While relying solely on the difficulty incentive is sufficient for easier tasks like payment, it does not perform as well as CoDE in more complicated tasks.
CoDE produces currieulum of emerging complexity, estimated by the number of active and passive primitives. CoDE starts around 60% random selection of primitives, and gradually generates more primitives while improving agent's performance (Figure bd Even as the complexity of the environments continues to increase, CoDE agents still perform consistently well without degrading performance (Figure 7 CL's performance drops significantly due ignoring agents' skill level and making environments that are too challenging for agents to complete, therefore ignoring their ability learn. DR performs poorly because the randomly generated environments are so complex that the agents never even begin learning.
Curriculum generation:
Next, both number of active and passive primitives increases (Appendix A.6 and the distribution of the primitives shifts to more complex and relevant primitives later on (Appendix A.5). Learning web page with more passive primitives is relatively easier task than page with more active primitives, because passive primitives either add noise and should be ignored by the agents, or are used by agents only to navigate to another page.
Active primitives not only increase DOM tree size, but the number of instruction fields as well, making the matching between elements and instruction more challenging.

---

Aogrgaced compertiinn un
jaficuuty lasss Apgrogztied 2ompii on Loficutty locks
Acortpatedd Scmppatison or 2dffouuyy tasks Agupoaated compar sen on officcity tocks
294
307
140
1993
74 121
2X1
940
240
1000
21 331 1903
(a) Difficulty level
(b) Difficulty level 2
(c) Difficulty level 3
(d) Difficulty level 4
Figure 7: Aggregated task success rate comparison of CoDE and haseline models on test environments with increasing difficulty levels. See Appendix A.8for for detailed results.
CoDE agents continue to improve performance thanks to the ability to tune the difficulty of the environments to agents' proficiency.
CoDE successfully scales to real-world web navigation with generator choosing from almost 100 times larger set of primitives, yielding = 10 possible environments. The trained agents generalize to unseen environments (Table 2 constructed out of real web data. As the distribution of real primitives mainly focus on username, password, and address fields, we observe a high evaluation success the Login and Address tasks. Even though we used the same primitives for the Flight as above results, we observe significant drop in perfor- mance which can be attributed to skewness of the primitive distribution.
Real website evaluation:
1
2
4
Login
62%
63%
55%
44%
Address
36%
25%
29%
38%
Payment
23%
18%
12%
9%
Shopping Flight
44%
36%
34%
31%
29%
25%
31%
23%
Table 2: CoDE performance real web- sites across tasks and difficulty levels.
8 Broader impact, limitations, and future work
PN formalism (Appendix A is useful beyond this work, as it exposes compositional task topology. We expanded workflow model, which although expressive for a rich set of tasks seeded with only a handful of primitives, is still only one topological class of tasks. Further investigation is needed into the correlation between compositional task toplogies and methods. Do these methods work for tasks with alternate routes? Our preliminary investigation shows that the difficulty budget is not appropriate for tasks without a goal state (terminal state in PNs), regardless if the goal is not-reachable, or the task is open-ended. What methods can enable learning compositional tasks with difficult topologies?
Next, we evaluated the model trained with real website primitives on test set with hand-engineered primitives, with surprising results: success rate ranging from 90% on address tasks to 0% in simple MiniWob enter-text. While expecting generalization across primitives is tall ask, the results show that in some cases is attainable. What are the circumstances when the primitives generalization is possible, and how develop models that expand the repertoire of primitives?
Conclusion
We present, Compositional Design of Environments (CoDE), a novel algorithm for zero-shot gen- cralization compositional task learning. First. the Petri Nets formalism enables definition of the learnable task built from the few selected primitives, algorithmic creation of RL agents and genera- tor and provides tools for toplogocial analysis of the learnable tasks. Second, we introduced two new objectives for curriculum generation: an improved, population-based estimate of regret, and a difficulty objective tailored the problem of generating compositional tasks. Next, a proposed domain- agnostic generator architecture builds new hierarchical tasks out of primitives. To facili- tate research on compositional tasks and environment generation, we controbuted two open-source benchmarks. Finally, we demonstrated that CoDE generates curriculum of emerging complexity, successfully trains agents outperforming baselines 4x, and results single RL agent capable of filling out generic forms and completing variety of tasks on real websites.
10

---

References
[1] Wil Aalst. The application petri nets to workflow management. Journal of Circuits, Systems, and Computers, 8:21-66, 02 1998. doi: 01142//0021826698000000
[2] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp. Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large- scale machine learning on heterogeneous systems, 2015. URL https: //ww://wwwwwwwww. tensorflos org/ Software available from tensorflow.org.
Kaiser,
[3] Philip E Agre and David Chapman. What are plans for? Robotics and autonomous systems, (1-2):17-34,, 1990.
[4] M. Beccuti, G. Franceschinis, and Haddad. Markov decision petri net and markov decision well-formed net formalisms. In Jetty Kleijn and Alex Yakovlev, editors, Petri Nets and Other Models of Concurrency ICATPN 2007, pages 43-62, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. ISBN 978-3-540-7309441
[5] 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. 12.00006.2222 12122, 2020.
[6] Maxime thevalier-Boisverr, Lucas Willems, and Suman Pal. Minimalistic gridworld environ- ment for openai gym. https:// wwwp///wiiim.aai/o///..o/.maa http://www.iinaaaaggammmmiiigiie gym-minigrid 2018.
[7] Wojciech Czarnecki, Siddhant Jayakumar, Max Jaderberg, Leonard Hasenclever, Yee Whye Teh, Nicolas Heess, Simon Osindero, and Razvan Pascanu. Mix amp; match agent curricula for reinforcement learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine URL WtRLhttps::/ppet https://pproceedingg
Learning Research, pages 1087-1095, PMLR, 10-15 Jul 2018.
mlr. wwwppprssvv000 wtw.prss/80/zzzrrccccrrk czarnecki 188.htmll
[8] 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.
[9] Coline Devin, Daniel Geng, Pieter Abbeel, Trevor Darrell, and Sergey Levine. Plan arithmetic: Compositional plan vectors for multi-task control. NeurIPS, 2020.
[10] Christian Dondrup, Ioannis Papaioannou, and Oliver Lemon. Petri net machines for human- agent interaction, 2019.
[11] Rainer Fehling. A concept of hierarchical petri nets with building blocks. In Grzegorz Rozenberg. editor, Advances in Petri Nets 1993, pages 148-168, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg. ISBN 978-3-540-47631-3,
[12] Dieqiao Feng. Carla P Gomes, and Bart Selman. A novel automated curriculum strategy to solve hard sokoban planning instances. Advances in Neural Information Processing Systems, 33, 2020.
[13] Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. Proceedings of Machine Learning Research, 2018. URL http:://proceedings. mlr. wwwppppessseepeppp /ttp://poeeeaaaaaaaarrprrrrrre// haae0//ffooenssa18 /
html
[14] Vijay Gehlot and Carmen Nigro. An introduction to systems modeling and simulation with colored petri nets. In Proceedings of the Winter Simulation Conference, WSC '10, page 104-118. Winter Simulation Conference, 2010. ISBN 978 424498642.
11

---

[15] Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint arXiv 2014.
[16] Alex Graves, Mare G Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Auto- mated curriculum learning for neural networks. arXiv preprint 1eXiv:1704.0000 03003, 2017.
[17] Izzeddin Gur, Uli Rueckert, Aleksandra Faust, and Dilek Hakkani-Tuu Learning to navigate the web. In ICLR, 2019.
[18) Matt Hoffman, Bobak Shahriari, John Aslanides, Gabriel Barth-Maron, Feryal Behbahani, Tamara Norman, Abbas Abdolmaleki, Albin Cassirer, Fan Yang. Kate Baumli, Sarah Henderson, Alex Novikov, Sergio Gómez Colmenarejo, Serkan Cabi, Caglar Gulcehre, Tom Le Paine, Andrew Cowie, Ziyu Wang, Bilal Piot, and Nando de Freitas. Acme: A research framework for distributed reinforcement learning. arXiv preprint arXiv:2006.00979, 2020.
URL https
wwwpxii.orrg/bbb//00/a 00979
[19] Joel Z Leibo, Edward Hughes, Mare Lanctot, and Thore Graepel. Autocurricula and the emergence of innovation from social interaction: manifesto for multi-agent intelligence research. arXiv preprint arXiv:
2019.
[20] Yunfei Li, Huazhe Xu, Yilin Wu, Xiaolong Wang, and Yi Wu. Solving compositional reinforce- ment learning problems via task reduction. In ICIR, 2021.
[21] Evan Zheran Liu, Kelvin Guu, Panupong Pasupat, Tianlin Shi, and Percy Liang. Reinforcement learning on web interfaces using workflow-guided exploration. arXiv preprint arXiv: 1xXxv:/802.08822 2018.
[22] Tambet Matüisnn, Avital Oliver, Taco Cohen, and John Schulman. Teacher- student curriculum learning. IEEE transactions on neural networks and learning systems, 2019.
[23] Eric Mazumdar, Lillian J Ratliff, Michael I Jordan, and S Shankar Sastry. Policy-gradicn algorithms have no guarantees of convergence in continuous action and state multi-agen settings. arXiv preprint arXiv: 07772. 2019.
[24] Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint 0rXiv:190.000830 2019.
[25] Bhairav Mehta, Manfred Diaz. Florian Golemo, Christopher J Pal, and Liam Paull. Active domain randomization. In Conference on Robot Learning, pages 1162-1176. PMIR, 2020.
[26] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. Proceedings of Machine Learning Research. PMLR, 2016. URL
http://proceeddings mlr. press/ pwwps///s/.../ v48/ h4t////////mmmm//mmm htt./mnnha.....mmmm html
[27] Sanjeev Naguleswaran and Langford B. White. Planning without state space explosion: Petri net to markov decision process. International Transactions in Operational Research, 16 (2):243-255) 2009. doi: https://doi.org// 10. 111.1.1........1111.1..11111.1 3995-5995..009990 .00674.x. 2009..0...... URL https
/ //onlinelibrary htw.uinelibbary..ieeey.l wwloo//ooiaaaee 10. 1t..////........................ .11.1/...145..... 1475- 3995. 20090006220
[28] Sanmit Narvekar and Peter Stone. Learning curriculum policies for reinforcement learning.
arXiv preprint arXiv: 001..1.......... 2018
[29] Sanmit Narvekar, Jivko Sinapov, and Peter Stone. Autonomous task sequencing for customized curriculum design in reinforcement learning. In IJCAI, pages 2536-2542, 2017.
[30] Junhyuk Oh, Satinder Singh. Honglak Lee, and Pushmeet Kohli. Zero-shot task generalization with multi-task deep reinforcement learning. In ICMI., 2017.
[31] Bei Peng, James MacGlashan, Robert Loftin, Michael L. Littman, David L. Roberts, and Matthew F. Taylor. Curriculum design for machine learners in sequential decision tasks. IEEE Transactions on Emerging Topics in Computational Intelligence, 2(4):268-27) 227-2 2018. doi:
10.1109/TETCL2016 2018 28299880
12

---

[32] Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre- Yves Oudeyer. Teacher algorithms for curriculum learning of deep in continuously parameterized environments. Conference on Robot Learning, pages 835-853. PMLR, 2020.
[33] Sharath Chandra Raparthy, Bhairav Mehta, Florian Golemo, and Liam Paull. Generat- ing automatic curricula via self-supervised active domain randomization. arXiv preprint a0Xiv:2002.07911, 2020.
[34] Wolfgang Reisig. Petri Nets: An Introduction. Springer- 0387137238.
Opringer-Verlag, Verlag, Berlin, Heidelberg, 1985. ISBN
[35] Fereshteh Sadeghi and Sergey Levine. Cad2rl: Real singlc-image flight without a single real image. arXiv preprint 1rXiv:1611.0423 1.0201, 2016.
[36] 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, pages 3135-3144, 2017.
[37] Sungryull Sohn, Junhyuk Oh, and Honglak Lee. Hicrarchical reinforcement learning for zero-shot generalization with subtask dependencies. In NeurlPS, pages 7156-7166, 2018.
[38] Sungryull Sohn, Hyunjae Woo, Jongwook Choi, and Honglak Lee. Meta reinforcement learning with autonomous inference of subtask dependencies. In International Conference on Learning Representations, 2019.
[39] Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play arXiv preprint 17X1v:1703.05407, 2017.
[40] Maxwell Svetlik, Matteo Leonetti, Jivko Sinapov, Rishi Shah, Nick Walker, and Peter Stone. Automatic curriculum graph generation for reinforcement learning agents. Proceedings of the AAAI Conference on Artificial Intelligence, 31, Feb. 2017. URL https://oja aaai org/
index. hndex.php/AAA//// phtp//AAl/arrtccc///er//////3
[41] Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pages 23-30. IEEE, 2017.
[42] Nelson Vithayathil Varghese and Qusay H. Mahmoud. A survey of multi-task deep reinforce- ment learning. Electronics, 9(),, 2020. ISSN 2079-9292, doi: 10.3390lelectronnics999111 URL httphttpp//// //wp::://www... mdpi
[43] 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: 001755,, 2019.
[44] 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.085.. 08536 2020.
[45] Yunzhi Zhang, Pieter Abbeel, and Lerrel Pinto. Automatic curriculum learning through value disagreement. Advances in Neural Information Processing Systems, 33, 2020.
13


Reviews:
[{"review_id": "vgoEQcFcDOh", "reviewer": "Reviewer_dK3z", "summary": "This paper proposes a framework to generate compositional tasks as automated curricula using a graph representation. The proposed method jointly trains a task generator and the RL agent by maximizing the regret between the trained agents and the best-performing agent and the difficulty of the environment. Experiments are conducted in two domains: MiniGrid and MiniWob.", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n\n- Compared to prior work, the use of Petri Net graph formalism and the formulation of regret and difficulty are original in this paper. The proposed CoDE algorithm has enough novelty. \n\n- The proposed graph formalism and the CoDE algorithm seem to be reasonable. Detailed ablation studies are provided to analyze the performance of the proposed algorithm. However, a few important baselines are missing in the experiments and there is no ablation study to analyze the design choices in the CoDE algorithm. \n\n- The paper is mostly well written and easy to follow. \n\n- This paper address an important problem of generating tasks as curricula and proposes an interesting solution. However, the significance of the proposed method was not fully justified due to missing comparisons with several state-of-the-art methods. \n\nWeaknesses:\n\n- One of my major concerns is that many state-of-the-art curriculum learning methods are not compared in the experiments, including ALP-GMM (Portelas et al. CoRL 2019), GoalGAN (Florensa et al. ICML 2018), and VDS (Zhang et al. NeurIPS 2020). Without comparisons with these recent works, it would be hard to justify the effectiveness of the proposed method. \n\n- The state/action spaces and the parameterization of the environments are not clearly explained in Sec. 6. Such information is important for understanding the complexity of the problems and should be mentioned in the paper. \n\n- The analysis in Sec. 4 is really helpful for the readers to better understand the problem. However, it would be better if more experimental results are provided to prove the hypothesis.\n\n- (Minor) The pargraph of the generator model in Sec. 5 is a bit confusing since some of the descriptions are specific to gMiniWob domain (e.g. \"page index\" in line 231). It would be better to describe the model design in a domain-agnostic manner. \n\n- Some of the citations on curriculum learning and task generation are missing: \n\n    -- M. Svetlik, Matteo Leonetti, J. Sinapov, Rishi Shah, Nick Walker, and P. Stone. Automatic curriculum graph generation for reinforcement learning agents. In AAAI Conference on Artificial Intelligence, 2017.\n\n    -- B. Peng, J. MacGlashan, R. Loftin, M. Littman, D. Roberts, and Matthew E. Taylor. Curriculum design for machine learners in sequential decision tasks. IEEE Transactions on Emerging Topics in Computational Intelligence, 2:268–277, 2018.\n\n    -- K. Fang, Y. Zhu, A. Garg, A. Kuryenkov, V. Mehta, L. Fei-Fei, and S. Savarese. Learning task-oriented grasping for tool manipulation from simulated self-supervision. Robotics: Science and Systems, 2018.\n\n    -- Wojciech Czarnecki, Siddhant M. Jayakumar, Max Jaderberg, Leonard Hasenclever, Yee Whye Teh, Nicolas Manfred Otto Heess, Simon Osindero, and Razvan Pascanu. Mix&match - agent curricula for reinforcement learning. In International Conference on Machine Learning, 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors provide discussions on the limitation of applying the difficulty budget to tasks without a goal state. It would be even better if the authors could suggest alternative solutions for such scenarios. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "S8prBssoBVl", "reviewer": "Reviewer_w21P", "summary": "The paper presents a method, Compositional Design of Environments (CoDE), for automatically constructing a curriculum over a complex domain of environments. The algorithm is framed as a multi-agent game: a generator constructs an environment using a sequence of actions, and afterwards a population of agents attempts to solve the constructed environment. Agents are trained to maximize the extrinsic reward they receive when attempting to solve the constructed environments. The generator reward, the main contribution of this paper, has two components: the first is a population-based regret computed as the difference between the average reward of the best performing agent in the population and the average reward across all agents in the population. The second component is a \"difficulty\" reward that encourages the generator agent to only complexify its constructed environments so long as one agent in the population remains capable of solving the task to a sufficient degree (given by a success threshold). If all agents fail the environment by another degree (the failure threshold), then the generator receives a negative reward, encouraging it to simplify its environment distribution when necessary.", "questions": "", "limitations": "", "rating": 6, "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": "The paper presents an interesting solution to automated curriculum design where the environments are themselves constructed by a reinforcement learning agent. The paper is most similar to previous work PAIRED, which also used regret as a learning signal for an environment generator agent. However, the main novelty presented in the paper is (1) a better regret estimate that uses a population of agents rather than only 2 (protagonist / antagonist) and (2) a difficulty reward signal that provides denser learning signal then regret only. Both improvements make sense intuitively and are clearly motivated in the main text.\n\nThe results and ablations seem to support that both of these modifications provide significant improvements over the PAIRED baseline. The results on gMiniWoB and the real website evaluation seem especially significant, and the real website dataset could be an interesting benchmark by itself for future research.\n\nHowever, there are some confusing aspects in the experiment section:\n1) On L295-296, it claims that CoDE only uses a population size of 2 for fair comparison to PAIRED. Can this then be understood that the CoDE results in the experiments section are PAIRED but with the added difficulty reward?\n2) Given that information, what is the difference between PopRegret and CoDE in e.g. Figure 6?\n3) How does population size affect final performance? This ablation seems important to motivating using |P| > 2.\n4) There is a mention of \"Flexible PAIRED\" and \"budget enforcement\" in Figure 6, but no additional information. Can you explain what is meant here?\n5) The success/failure thresholds of the difficulty reward seem like potentially important hyperparameters that can largely affect the final results of CoDE. I can't easily find what values these were set to in the text, can you describe this in more detail in the experiments section, including how you ended up at the values you chose?\n6) It would be interesting to see an ablation of these thresholds, and the performance of CoDE for various values. This would determine how critical these thresholds are to performance, and how easy they are to tune for agent designers.\n7) If the reward of an agent is unbounded, would using static thresholds still make sense? Or would you also need to increase the threshold with increasing/decreasing agent returns?\n8) It's mentioned that agents are optimized using a policy gradient method. Given the highly non-stationary environment that the population is trained under, was there any observation that agent optimization is affected by the shifts in environment distributions over training (e.g. catastrophic forgetting or learning speed reductions due to activations saturating during training)?\n9) In Figure 11, is there any intuition on why the CL baseline increases rapidly in performance but eventually collapses?\n\nAdditionally, can the authors comment on whether it is possible the generator and agent population fall into some unwanted local minima and how these solutions can be avoided? I think there is the possibility on very complex domains that the learning process gets stuck in a part of the game which might not overlap with the test distribution, e.g. in the space of creating any website, the generator can start designing extremely complex websites where even humans can not easily solve them.\n\nIn conclusion, I believe that the method is well-motivated and sufficiently empirically validated, and remains a useful contribution to the field of automated environment generation despite there being some limitations.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed in section 8 in the main text and in the appendix. \n\nA potentially major limitation of this work is that it requires both a way to represent tasks efficiently so that a generator can produce a valid task description in a small number of actions, as well as a way to transform simple task descriptions into environments that can be executed by reinforcement learning agents. Constructing these components could conceivably be more expensive in some domains than hand-designing a curriculum of training tasks.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "JtLdYhjFqQT", "reviewer": "Reviewer_uPhg", "summary": "The paper addresses the problem that RL is bad at learning the compositional rules guiding compositional problems. It proposes a two pronged approach: first, it proposes a task (de)composition strategy that allows building up tasks (or POMDPs) compositionally. Second, it proposes a regret-driven curriculum strategy that is able to construct compositional tasks of increasing complexity without supervision, which, in turn, can be used to train a learner that is then able to pick up on the rules of compositionality guiding the domain.", "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": "Pros:\n- The paper is very well written and easy to follow.\n- The goal of the paper is extremely important: very many real-world scenarios are compositional, and RL is severely lacking in this regard.\n- The individual design choices are well motivated.\n- The core idea, guiding the complexity of the domains given to the learning agent by a measure of regret, is intuitively plausible.\n- The authors test on existing domains (which appear to be solved) and design new harder domains that they release as open source.\n\nCons:\n- The first contribution of the paper, the hierarchical and compositional decomposition of tasks using petrinets, is only explained in the appendix. Given the relevance to the overall goals of the paper, I think that at least a paragraph or two should be spend on that in the main paper.\n- There is a discrepancy in the complexity of the two tasks: it looks as if the website domain is vastly more complex than the gridworld domain. Given that the gridworld domain would be more general and thus more relevant to the research community, it would have been nice to have this also scale to high complexity.\n- I find myself doubting the value of the new domains the authors are releasing along with the paper. Not because I am not convinced of their relevance (in fact, I do believe that the domains could be highly relevant), but because the suggested approach in the paper solves these domains (success > 95%), effectively making them redundant before they were even released to the public.\n\nOriginality:\nTo my knowledge, the proposed regret-based curriculum training strategy is novel and a creative solution to a fundamental problem.\n\nQuality:\nThe quality of the submission is very high. The language is clear, the paper is well structured, and the illustrations are good (though the text on the illustrations could be larger and sharper).\n\nClarity:\nThe clarity of the submission is high. Each argument made is easy to follow, and the overall structure makes it easy to understand each point in context.\n\nSignificance:\nThe core problem of the paper - RL's difficulties in generalizing over compositional domains - is highly significant. The significance of the entire paper is somewhat reduced by their choice of narrow domain.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not applicable", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes several solid contributions — 1) a method to decompose tasks in a compositional manner, so as to enable RL agents to generalize to unseen, complex test scenarios, and 2) new open-source benchmarks for testing compositional generalization in RL agents, on gridworld and web-based domains. The reviewers appreciated the novelty of ideas presented and agree that the paper is solving an important problem. The authors in their responses promise to add in ablation studies and additional clarifications on the framework (state space, actions, etc.), better comparison to related work on curriculum/self-supervised learning, and adding more complex environments to the open source benchmarks. With these changes, I think this paper will be quite valuable to the community and enable future research on compositional generalization in RL. 
Decision: Accept (Poster)