Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This works introduces a lifelong RL problem in which new tasks can be possibly be expressed as a logical composition of previous ones.

Accordingly, they introduce algorithm (SOPGOL) that can autonomously determine whether a new task can be immediately solved using its existing abilities, or whether a task-specific skill should be learned.

The authors provide some theoretical guarantees on the performance of the algorithm, as well as empirical evidence that it can work in a toy setting.
main_review: This work is sound and can potentially shape future lifelong reinforcement learning (LRL) research.
I'm a bit skeptical however about its applicability in any use cases. 

**Strengths:**
- The introduced problem formulation is a good first step towards lifelong compositional RL agents.
- the theoretical guarantees for SOGPOL are satisfying
- the empirical study is well-aligned w/ the problem formulation and highlights the relevant regimes , i.e., 4.1 a)  vs 4.1 b) vs 4.2 

**Weaknesses:**
- The boolean task algebra is quite restrictive. I don't see many use cases for it. If the authors introduce a new problem setting, they should motivate it.
- assuming the agent can interact with the task as long as it needs is quite an unrealistic assumption in LRL.
- all experiments on toy tasks. I think a more realistic benchmark should be introduced. 
- there's no LRL baselines.
- in SOGPOL,
    - the new skill is initialize randomly. This will be pretty inefficient is more realistic settings.
    - IIUC, when learning, to enable transfer from previous tasks, goals need to be reached. But in realistic settings, goals will be hard to reach. So essentially lots time and compute will be wasted relearning over and over same things.

**Minor details:**
- def 3: $r_{MAX}$ is the same as $r_{MIN}$
- theorem 1: what is $\gamma$ ?
- what's the difference between prop. 1 and prop. 2 ?
- theorem 2: can you provide some intuition/explanation on those bounds?
summary_of_the_review: I think this work as merits.
I'm giving a weak reject because I would like to see more motivation for this work and how it could be adapted to use cases.
I'm currently keeping my confidence score somewhat low because the theoretical contribution could be significant enough to alleviate the need for thorough motivations/experiments.

======= POST REBUTTAL ==============

Thanks for all the explanations and clarification.
Some of my concerns have been resolved.
I'll increase my score to 6.
I will not go higher because I still think some experiments should be added in a realistic lifelong RL benchmark, i.e., where the tasks won't actually obey the theoretical task algebra. Upon acceptance, I still encourage the authors to add such an experiment.

Minor detail: please add the provided intuitions for Theorem 2 in the manuscript
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper builds upon previous work on the Boolean Task Algebra For Reinforcement Learning extending it to the discounted and stochastic tasks and to the lifelong RL setup. The authors show that techniques introduce in the previous work can perform close to optimal in a zero-shot transfer scenario. Next, they look into the number of skills needed in order to solve all the tasks and arrive at some lower bounds which are encouraging since they are close to log|G|, this is somewhat supported by empirical analysis later on.
The authors also introduce a method for using the known skills with SOP to solve new tasks and to bootstrapping the learning of new skills if needed. Overall, the method is very quick to learn when compared to a simple Q-learning baseline. This work is orthogonal to lots of related ones in the skill learning literature and would combine well with many of them.
main_review: Good work on this paper. I appreciate the background session as I had forgotten lots of details from the boolean task algebra, since I read it. The papar is very sound and the concern about the number of skills is reassuring. Using GPI on the extended Q_SOP and extended Q~ is a useful trick and yields good results. Within the problem formulation, the empirical method works well enough.

Some improvements can be made on the paper though:

1. The following claim right before theorem 2 seems incorrect: ".We now show ... generalises over any unknown non-stationary task distribution after learning only a number of tasks logarithmic in the size of the task space". My understanding is that theorem 2 is actually a lower bound on the number of goals needed to learn, and the upper bound is |G|, unless we make further assumptions, as you have shown already with D_worst in the experiments. The same applies to similar claims around the paper, for example, "which are
sub-logarithmic in the size of the task space" (abstract), 

2. The background session 2.1. is missing the Lemma 1 from previous work which is crucial to building its intuition and recover the non-extended reward and value (i.e. just maximize over G to recover the non-extended quantities). Without it, readers unfamiliar with previous work may struggle to understand definition 3 onwards.

3. I miss some discussion on the limitations of the method, specially in terms of using finite set of goals, which doesn't seem to be a strong requirement of the related work discussed. It's often not feasible to do that in some scenarios, so it can hinder the further applicability of this method, for example, some goals are defined as continuous regions of the state space.

summary_of_the_review: This is a good paper with a sound method and good results. The author just need to work on a few points to award a clear acceptance.
Some claims about the efficiency of the algorithm with the number of goals need to be removed. A important step of the background is missing. Finally, some short discussion about limitations would be welcome.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides an interesting direction in the field of skill composition in reinforcement learning (RL). In particular, by extending Tasse et al. (2020)’s framework for Boolean task algebra, which allows for composing tasks and value functions using logical operators to yield optimal skills zero-shot, from deterministic shortest path tasks to discounted stochastic tasks, the paper proposes a new framework for lifelong RL that focuses not only on transfer between tasks for faster RL, but also gives guarantees on the performance of the agent over an unknown task distribution. Along with the framework, two main theoretical results are provided: (1) bounds on the performance of transferred policy on a new task, and (2) bounds on the necessary and sufficient number of tasks that need to be learned to guarantee performance over a distribution of tasks. Experiments are performed to verify the theoretical results in both transfer learning and lifelong RL settings in the PickUpObj and Fourrooms domains in the minigrid environment.
main_review: Positives:

- The idea of using logical composition to autonomously determine whether a given task can be immediately solved using existing policies or whether a new policy has to be learned and added to the policy library is interesting.

- Overall, the paper is well-written and it is easy to follow (if typos are not taken into account).

- It is nice to see that the paper contains theoretical results that provide bounds (i) on the performance of transferred policy on a new task and (ii) on the necessary and sufficient number of tasks that need to be learned by the agent so that it can generalize over a distribution. The proofs of the theorems also seem sound.

- The experiments section of the paper provides comprehensive results, including results on transfer after pretraining on a set of tasks (both base and arbitrary) and on lifelong transfer scenarios where the agent builds the skill set from scratch, verifying the theoretical results. Using three different task distributions in the lifelong RL setting is also a nice way to show how the algorithm would perform in best-case, worst-case and average-case scenarios.


Concerns:

1.  On the proposed framework:

	a.  One of my biggest concerns about this paper is the lack of explanation of where the extended reward (and value) functions come from in Defn. 6 (and Defn. 7). If it is going to be computed by the agent, then it requires the knowledge of the reward model ($r(s,a)$ and $r_{MIN}$) and goals $g\in\mathcal{G}$ which are supposed to not be known by the agent apriori (and may never be known if the environment is large). If it is assumed to be known in advance by the agent or if the considered environments are assumed to have an extended reward function themselves (as the experiments suggest), then I believe that it is an important assumption that should perhaps be made more clear. Afterall, regular environments are not likely to have this kind of a reward function. I am curious about a discussion on this.
    
	b.  It would also be nice if the paper can discuss any additional limitations of the proposed framework as there seems to be no discussion on this throughout the paper.
    
	c.  In Sec. 3.2, it is unclear how the negation operator for a task is defined? Could the authors clarify?
    
	d.  Also the motivation behind redefining the negation operator for the extended value function seems to be unclear. Is this just for obtaining better bounds as stated in the paper?
    

2.  Regarding the experiments:

	a.  Another big concern of mine is that although the experiments support the claims of the paper, I find them to be on very limited settings of the proposed domains. For instance, in the PickOpObj domain, the agent is always in a world with only 5 objects and after it picks one, the episode immediately terminates. What about cases where, for instance, the agent is surrounded by all of the 15 objects (in a larger environment) and it has to pick up all the objects associated with a 1 in the vector $T$? In this case, for the test task $T_2$, the agent would have to sequentially pick up all the 7 objects (as there are 7 1’s in $T_2$) and then terminate the episode. The same argument can be made for the Fourrooms domain as well, where the agent would be required to pass through the locations that have 1’s in the corresponding $T$ vector. Thus, I suggest for performing the same experiments in the paper in settings where the tasks don’t terminate after just picking/reaching an object/location, but continues until all the objects/locations are picked/reached (see e.g. the tasks in [1]). I think that these additional experiments would strengthen the results by showing that the proposed framework applies to a broad range of settings.
    
	b.  On the same note, in my understanding, it looks as if the definition of goal-based tasks is too restrictive. For example, if there are only two yellow keys in the environment and the task is to obtain yellow keys, is the goal defined as obtaining both of the keys and then terminating or obtaining the closest one and then terminating? The experiments seem to indicate that the latter is meant by goal-based tasks. Could the authors clarify on this point and give examples.
    
	c.  Also, although the paper states that there have been earlier work (Saxe et al., 2017; Haarnoja et al., 2018; Van Niekerk et al., 2019; Hunt et al., 2019; Peng et al., 2019) on skill composition, there seems to be no discussion on why there is no comparison with them. If these methods are not applicable in the settings considered, or if comparison with them does not make sense, then I believe that this should explicitly be mentioned (together with the reasons) in the paper. A discussion on this would be great.
    

3.  Regarding related work:

	a.  Although the paper briefly talks about the GPE & GPI framework [1] in the related work section, I think there should be an extended discussion on the difference/similarities between this framework and the Boolean algebra framework developed in the paper as the two seem to be very related. For instance, by selecting the appropriate task vectors $\mathbf{w}$, one can also build a skill set that enables generalization across a distribution of tasks. In fact, this seems to have been demonstrated by a concurrent study [2].
    
	b.  Another closely related study on skill composition is the Option Keyboard framework [3]. It would also be nice to see a discussion on the differences/similarities of this framework and the proposed one.
    
	c.  I believe that providing a detailed discussion on the difference between the prior studies in 2c and the proposed method in the related work section can further clarify how the proposed method fits in the literature.


Minor comments (that have no effect on the final decision):

- Adding a newline (`\\`) to the title can make the spacing look better.
    
- There is a typo in the first paragraph of page 3 where “&” is used right after $\bar{r}_{MIN}$.
    
- In Defn. 3, I think there should be a $\min$ in the definition of $r_{M_{MIN}}$.
    
- In the first paragraph of Sec. 3.1, it should be “learned” instead of “said”. Also, in Defn. 5, does the agent sample a task or is a task provided by the environment? According to the experiments, the tasks seem to be coming from the environment.
    
- In the second paragraph of Sec. 4.1, it should be “RL method” instead of “RL learning method”.
    
- In Sec. 4.2, what is the value for the slip probability ($sp$)? It is not provided in any part of the paper.
    
- Maybe a really minor detail, but the fonts of the plots in Figure 2, 3 and 4 do not seem to match.
    
- In the last paragraph of Sec. 4.2, it should be $\mathcal{D}_{best}$  instead of  $\mathcal{D}_{sampled}$.

- What is EVF in Prop. 1 and Prop. 2? It should be written explicitly in its non-abbreviated form.
    
- In Sec. 2, is the virtual state a terminal state? If it is, I believe that naming it as so can avoid any possible confusion.
    
- In the second paragraph of Sec. 3.4, what does “... goal buffer according to $\mathcal{A}$.” mean? I think this should be clarified.
    
- Are policies assumed to be deterministic throughout the paper? If so, this should be stated explicitly.
    
- In Defn. 5, what does it mean to be “$\epsilon$-optimal” in task M? This should be defined explicitly.
    
- It seems like the $\mathcal{M}$’s in Sec. 2.1 do not correspond to the $\mathcal{M}$ in Eq. (1), as Sec. 2.1 assumes the undiscounted setting? If this is the case, I believe that the set of tasks in Sec. 2.1 should be named differently.
    
- In Defn. 5, does it matter whether $\mathcal{D}$ is a stationary or non-stationary distribution? (This is also assumed in Theorem 2 in Sec. 3.4) It does not seem to make any difference from the point of view of the proposed method. I believe that starting Defn. 5 as “Let D be an unknown distribution, possibly non-stationary, over a set of tasks …” would be more appropriate here.
    
- I believe that Eq. (1) is too general and it should be expressed more clearly. For instance, when $r_{MIN}$ and $r_{MAX}$ are both positive, all the states in $\mathcal{S}$ become desirable states and there will be no undesirable ones. When $r_{MIN} < 0$ and $r_{MAX} > 0$, some states in $\mathcal{S} \setminus \mathcal{G}$ may become desirable or undesirable states depending on $r_0(s,a)$. Having some restrictions on the possible values of $r_{MIN}$, $r_{MAX}$ and $r_0(s,a)$ can be helpful.


References:

[1] André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 117 (48):30079–30087, 2020.

[2] [https://openreview.net/forum?id=7IWGzQ6gZ1D](https://openreview.net/forum?id=7IWGzQ6gZ1D)

[3] Andre Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygun, Philippe Hamel, Daniel Toyama, Jonathan Hunt, Shibl Mourad, David Silver, et al. The option keyboard: combining skills in reinforcement learning. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 13052–13062, 2019.

summary_of_the_review: Overall, I think the paper can be a nice contribution to the field of lifelong RL, however, due to my concerns detailed above, I am currently voting for “marginally above the acceptance threshold”. Out of all my concerns 1a, 2a, 2b and 3a matters the most and I am willing to raise my score to accept if they are properly addressed. If, in addition, the authors can address the remaining points, this will increase the confidence in my voting to accept.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces an approach of logical decomposition of tasks as a particular set of MDPs. This logical decomposition allows to define a boolean logic over tasks and q-functions. Using this boolean logic, the paper continues in proving two boundaries for generalizing to new, unencountered tasks. The first states a boundary on performance on a new task when following a composition of previously learned policies. The second states that, to solve problems composed of k atomic tasks optimally, at most k skills will ever be required. The paper continues define a lifelong learning algorithm that relies on this logic to form a set of base skills. This algorithm is then evaluated on a multi-task and lifelong learning task, where it decidedly outperforms a standard deep q-learner.
main_review: ### Strengths
* The paper is generally well written and easy to follow, and explanations are intuitive.
* The chosen research problem, lifelong and multi-task RL, is both important and insufficiently studied.
* I really like the idea of having a task-composition logic. I think that this is an immensely interesting research direction.
* I like the theoretical results, even though they are a little unsurprising.

### Weaknesses
* Some important details are missing from the main paper: the exact algorithm proposed, and the exact setup of the experiments.
* The paper's experimental section is fairly weak in that all experiments are on the same, fairly simple task.
* It is not clear if the experiments are "fair", i.e., if the algorithms play on an equal playing field.

### Detailed questions/comments
* While the paper is properly anonymized in theory, I looked up "Nangue Tasse et al (2020)". The fact that they use near-duplicate language strongly suggests the same authors (or a violation of attribution). Please re-write to avoid this suspicion.
* Some notations are off or ambiguous (like in (2) - what does "s \neq s \in G" mean? Similarly in the theorems - why are there two inequalities combined with an equal sign?)
* It is completely unclear to me how the algorithm interacts with the chosen DQN model in detail. In particular, this sentence baffles me and I suspect that a lot is going on behind the scenes: "Having learned the optimal extended value functions for our base tasks, we can now leverage logical composition to do transfer learning on test tasks."
* Is the task composition provided to the learners in some way, or do they have to trial-and-error the task composition?
* From the look of the plots, a pure DQN may get competetive using sufficient samples? If so, please train with more data/longer. This would spin the paper more towards a data efficiency argument.
summary_of_the_review: The targeted problem - a lack of multi-task and lifelong learning capabilities of most RL algorithms - is an extremely important one, as it resembles real-life applications a lot more closely. Additionally, the idea of finding a decomposition of multiple tasks via boolean logic is highly appealing, as it allows structural abstraction in RL, another important but underexplored question. Unfortunately, the paper's contributions are a little underwhelming. The logical decomposition is nice but fairly straightforward. The theorems provide an interesting, but also not groundbreaking insight. And finally, the experiments are unclear in execution, only on one domain, and therefore unconvincing. Overall I really like the idea, but the paper needs substantial work to become a full contribution.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors study goal-based lifelong RL.  They leverage logical composition to create an algorithm for this setting, with the goal of better generalization.  They provide theoretical bounds for their approach, and provide empirical evidence that their approach generalizes and transfers well in practice.
main_review: Goal-based tasks: I think this is an interesting subset of RL problems, and that it is great to study this class of problems.  However, not mentioning this limitation in the abstract (and not even in intro) seems very odd; ideally “goal-based” would be not only in the abstract and intro, but also in the title, since there is such a fundamental difference between looking at RL in general and at this subset of RL.  It was odd to read the title, abstract, and intro, and then have my expectations of what the paper was about completely disrupted in the third sentence of Section 2.

Section 2 issues:

- r_0 is neither formally defined nor intuitively explained (ideally it should have both a definition and an explanation), so its significance and the difference between it and r is unclear.

- ”By penalising the agent for achieving…” are there typos in this sentence?  I cannot parse it.  Is \mathcal G— a new symbol (with the additional “—”)?  What does “r_min&” mean in this context?

- Definitions 1-2, extended reward function and extended Q-value function: I’m a little confused by what these are supposed to do.  Are we changing the problem/MDP, replacing the old reward function with the extended one?  Or are we changing the agent to utilize these concepts, while the problem remains the same?  Ideally, the text before/after these definitions would better explain the purpose of the definitions, avoiding this potential reader confusion.

- “the extended reward function has the effect of driving the agent to learn how to
separately achieve all desirable goals.” This is confusing to me; it seems like this may have the effect of driving the agent to learn how to achieve only some of the goals (perhaps only one), not all the goals.  (I suspect the confusion is due to one of the issues above, and will be cleared up by fixing and clarifying one of those issues.)

- Definition 3: since r_0 and r_[some task] have not been defined, I cannot parse definition 3.

- Because of the cumulative effect of the Section 2 issues above (particularly the notation issues), I am not able to give constructive feedback on the theoretical contributions of Section 3.  I found Section 3 difficult to follow, but could not determine if the problem was Section 3, or some of my confusions with Section 2.  While Section 2 is only the background section, it establishes some notation and concepts that likely are not standard for many readers with an RL background.  Since Section 3 proceeds to build upon Section 2, I think that the issues with Section 2 will significantly harm the readability of Section 3 for many readers.

[End Section 2 issues]

4.1 experiments: The experiments used only 4 runs, which is concerning for any experimental claims.  The claim is that SOPGOL is exhibiting transfer learning (4.1), and the evidence is that SOPGOL starts with much stronger performance than the baseline.  However, 4 runs is simply not a sufficient amount of data to make this claim.  I would encourage the authors to take the time to run 30+ runs in the future to make this claim more substantial.  Statistical significance testing would also be nice, but, if something like a t-test is used, much more data is needed anyway, since the t-test normality assumption is not reasonable with 4 runs (but might be reasonable with 30+, because of the CLT).

Minor Figure 4 formatting issue: I was thrown off by the lack of spacing between the two subfigures’ captions, and for a couple minutes was trying to understand it as a single paragraph starting as: “(a) Number of policies required to learn and store (b) Number of samples required…”.  The correct way of reading it, as two separate paragraphs side-by-side, is obvious once one sees it, but the way the paragraphs are set so close together makes me think that other readers may get confused as well.  (Also, the first lines of the two paragraphs are unfortunate in that they almost make sense when read in the wrong way; the wrong way of reading it only turns into obvious nonsense in the second or third lines.)  I suggest adding a bit of horizontal spacing between the sub-captions to help avoid this issue (if negative horizontal space was used here, please do not do that).

Minor notation edits:

- inconsistency in MDP tuple ordering (sometimes discount parameter is last, other times reward function is last).

- In theorem 1, T_SOP and \bar Q_SOP definitions use the equals symbol, should they use \coloneqq instead?

**Update after rebuttal:**

> We think of transfer along these lines of works [1,2,3]. For example, if an agent can learn to “pickup yellow objects”, then we would like it to transfer this knowledge to “pickup yellow keys” or even “pickup keys that are not yellow”. We are curious as to the kinds of tasks that you believe we should cover.

I’m not suggesting changing the tasks at all, but merely suggesting that the fact that the paper exclusively studies goal-based tasks be mentioned earlier (which you already said you would do, so no need to discuss this further).

Or am I misunderstanding?  Is the reasoning that most or all of transfer learning in RL can be framed as goal based tasks?  If so, it’s not so much a limitation that necessarily needs to be mentioned earlier; instead, in that case, I think the fix is to explain that most/all of transfer learning can be framed as goal-based tasks in the first paragraph of Section 2.

> Definitions 1-2...We will make that clearer in the paper

Great, thank you.

Point 3 of rebuttal: The revised version is much more clear, thank you.

More Definition 3 feedback: I still struggled with Definition 3 despite the clarifications above.  Was a “task” ever formally defined?  (See my clarity concerns below, the setting is still not clear to me.)  I was also confused about how a task could be “bounded”.

Two more points regarding lack of clarity in the setting:

1) > During each episode, the agent samples a goal to reach from its goal buffer. If it successfully reaches that goal, then the extended reward it receives is just the regular task reward from the environment. If it reaches a different terminal goal state, then the extended reward it receives is the large penalty. Hence the agent only gets the high task rewards when it reaches the goal it is trying to reach. This drives it to learn to achieve all the goals it encounters. Please see Fig 4 of Tasse et al. if that helps.

It’s not clear from the paper that each episode has the agent sampling a new goal for the task.  It becomes slightly more clear in Section 3 (but still isn’t completely clear then), but I think a big source of ambiguity and confusion in Section 2 is that this is not explained well.  More generally, the explanation of the relationships between goals, tasks, episodes, and the distribution of tasks needs work to improve clarity.

2)  3.1, task space size being 2^|G|: it’s not clear to me exactly where this is coming from.  Is it because each goal can be either r_min or r_max for a given task?  More clarity in section 2 would probably help avoid this confusion.

Summary of update:  Some concerns have been addressed (particularly the promised change in phrasing weakening the claims regarding the empirical results in 4.1), and I am increasing my score slightly, but clarity is still a major concern for me.  Because I am not understanding the setting and theory well, my confidence in my assessment is low, and I recommend disregarding my assessment if the other reviewers' clarity concerns are addressed.

summary_of_the_review: This paper is fascinating and well-motivated.  However, a few notation and clarity issues made it difficult to follow Sections 2-3, and I am also concerned about the statistical significance of the authors’ claims in 4.1.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers lifelong reinforcement learning. It extends a line of recent work in which logical composition is combined with goal-based reinforcement learning to achieve generalization to new tasks. The main contribution is theoretical, extending prior work to handle stochastic transitions and establishing asymptotic results for the lifelong learning setting. Experiments in grid-based domains illustrate SOPGOL, the main proposed algorithm, and show that it is possible to immediately generalize to new tasks in the lifelong setting.
main_review: ## Strengths

* This work extends the previous results of (Nangue Tasse et al. 2020) to handle stochastic transitions.
* The topic area is relevant for ICLR.
* Lifelong learning is an important and challenging topic and this work proposes a compelling path toward addressing that challenge through a combination of reinforcement learning and logical composition.
* Overall the paper is well-organized and does not have too many typos, although see my notes below.
* The theoretical results may be of interest, although I had difficulty understanding some of the main statements, which hopefully I can clear up during the rebuttal period.

## Weaknesses

* The paper is overall difficult to follow and the notation is not always clear.
* I had a lot of trouble parsing the statement of Theorem 1. 
   * SOP(., .) is not defined, where the first argument is a set of binary vectors and the second argument is a single binary vector. The result of SOP is B_exp, which is then applied to \tilde{T}_n as if B_exp were a function (and similarly for Q)? I think I ultimately understand this part, but the notation seems abused to the point where it’s difficult to follow.
   * \tilde{T} (the approximation of T, presumably) is not defined within the scope of this theorem -- is it meant to appear in that line or not? I suspect that it was meant to be T, because the theorem does not have any assumptions about the accuracy of \tilde{T} as an approximation of T, and I’m sure that some assumptions would be required to draw any conclusions.
   * In (i), what is the meaning of $1_{T \not\in \tilde{T}_n}$? $T$ is a specification and $\tilde{T}_n$ is a set of specifications, so that subscript would either be true or false. But from context, this object must be a binary vector. What is it exactly?
   * Since I remain confused about the Theorem 1 formal statement, for now, I am trusting the written descriptions surrounding it.
* I also have some confusions surrounding Theorem 2:
   * Why are the cardinalities all that we care about? Is there an implication that a task and Q function are only included in those sets if they have been “mastered” with a certain level of accuracy?
   * How can we draw any conclusions when we have an arbitrary nonstationary distribution of tasks? What prevents a pathological example where we see the same task for the first T steps and then a different one on step T+1, for any T?
* As a delta on the previous work of (Nangue Tasse et al. 2020), I am not sure if this work constitutes a substantial enough standalone contribution for an ICLR paper. There are advances to be sure, but they are relatively incremental. If I am able to get a better understanding of the theorems, that may change my perspective.
* The experiments are good to illustrate the main ideas, but they are not a substantial standalone contribution, since the domains are very simple and the baseline comparisons are very limited.
* I was surprised by the new definition of Q-function negation in section 3.2 because the value of the Q-function before negation is not used, except when determining whether the output should “toggle” between Qmax or Qmin. Can you explain this?
* I would like to see a discussion of the relationship between this line of work and propositional AI planning. The composition of goals is very related. It will be easy to find differences, and I think this line of work may offer a different and valuable perspective. I just think that the work would be strengthened by deeply exploring these connections.
* The premise of the transfer results in this work is that the task specification for a given task is not known, and so we have to compute and use an approximation of it. I am having trouble imagining a scenario where this structured space of possible task specifications is known, but the specification for a given task is not known. Is the idea that for a given task, there may actually be no “true” task specification, and so the approximation is just the “closest” specification that we can find? That would be more compelling, but I don’t think that we can use this interpretation because it would require leaving the class of MDPs defined in this work, and including MDPs that do not necessarily have the good-goal/bad-goal structure with the fixed r0 reward function.
* This comment is about boolean task algebra for RL in general, not just the present work. Though the theoretical contributions here may be interesting in their own right, I am struggling to imagine a practical scenario where it would be preferable to use this framework instead of one where we learn or compute a universal goal-conditioned value function instead. To elaborate, here is my attempt to describe this line of work through the lens of universal goal-conditioned value function learning:
   * Say that we compute/learn a universal goal-conditioned Q function $Q(s, g, a)$. Given any goal state $g$, we can do $argmax_{a} Q(s, g, a)$ to get optimal actions.
   * This line of work says: instead of learning a single goal-conditioned Q function, we could compute/learn multiple goal-conditioned Q functions, one per “task”, where a task is a set of goal states. Each of these Q functions is like an “expert” about some part of the goal space.
   * When given a new task $\mathcal{G}$, if we had a universal $Q$, then we could recover an optimal action via $argmax_{a} \max_{g \in \mathcal{G}} Q(s, g, a)$. This would be “zero-shot” transfer in the sense of this paper.
   * But instead, if we only have the goal-space expert Q functions, we will query the experts for whom $\mathcal{G}$ is within their expertise and combine their outputs according to the relationships between $\mathcal{G}$ and the expertises. This too will accomplish “zero-shot” transfer. But what is gained over the universal approach?
* Related to the previous point, the super-exponential zero-shot generalization advertised in this work and the previous work strikes me as a little bit disingenuous. If I am able to do X, and I’m also able to do Y, then I am automatically also able to do “X or Y”. Is that really generalization? Fundamentally, that is my reading on what’s happening in this work -- we’re learning how to accomplish each of the goals (indirectly, through the tasks, which are sets of goals), and then we’re recombining them in different ways, so that if we know how to achieve goal 1 and goal 2, we also know how to achieve “goal 1 or goal 2.”


## Minor Points

* In the first sentence of the paragraph before Definition 3, is that & meant to be there? I think there may be a formatting error.
* I know that the notation $g \neq s \in \mathcal{G}$ is not original to this work, but it is confusing and should be changed. For example, two different ways to parse this: $\forall s \in \mathcal{G}. g \neq s$; or $\exists s \in \mathcal{G}. g \neq s$. Furthermore, $\mathcal{G} \subseteq \mathcal{S}$, so can’t we just say $g \not\in \mathcal{G}$?
* It would be useful to define SOP explicitly even if it’s simple.
* When first defining the approximate task specification $\widetilde{T}$, it would be helpful to say whether that object is also a binary vector, like $T$, or if it instead could have non-binary values. Since it’s an approximation and there is some uncertainty about the true specification, the latter is plausible.
summary_of_the_review: For the reasons described above, especially concerning clarity and novelty, I am recommending a weak reject at this stage. However, after getting a better understanding of the theoretical contributions, I may be willing to raise my score.
review_title: null

Meta-review: I thank the authors for their submission and active participation in the discussions. This papers is borderline. On the positive side, reviewers emphasized this is a well written [ovqB,1zPe] and sound paper [BUDa] with good theoretical [td5N,ovqB,1zPe] and empirical [BUDa,td5N,ovqB] results. On the negative side, reviewers remarked clarity [KyZj,AVki], incremental with respect to Tasse et al (2020) [KyZj], relatively restricted Boolean task algebra [td5N], toyish nature of the environments considered [ovqB], and some missing details [1zPe]. During discussion, the sentiment seems to be somewhat lukewarm with none of the reviewers strongly favoring acceptance or rejection. It seems the main remaining concern is around the toyish nature of the environments used in this paper. I acknowledge that and I believe the authors could include experiments on more complex environments. However, I also give the authors credit for addressing most of the reviewer's concerns during rebuttal and for presenting a solid empirical and theoretical result that the research community can build upon in the future. I am therefore recommending acceptance of this paper and highly encourage the authors to further improve their paper based on the reviewer feedback.
Decision: Accept (Poster)