Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is a combination of two previous works. One is about logical (boolean) compositional mechanisms for multitask learning, and the other is about logical formalisms for temporal skills, both in the context of typical reinforcement learning problems. The idea is to lift the first (composing behaviors in a structured way from individual Q-functions basically) to the case of of temporally extended behaviors, in this case modeled as reward machines. The overall idea is to come up with so-called skill machines, which can represent both types of structure. The idea is evaluated on a couple of domains, where the goal is to show that many different (composed) skills can be learned (or zero-shot, computed/assembled) from a couple of basic (temporal) skills.
strength_and_weaknesses: The main strength of the paper is the proposed combination of methods. I think it makes a lot of sense, it is based on very recent work, and I see the potential. The paper appears polished, sketches related work, and the experiments show progress.

A main weakness is the description of the method, the buildup of the story and the motivations/examples. This paper is in my top-k papers ever that are hard to review, hence any remark I make here could be the result of a misunderstanding on my side (disclaimer) but I do think it is mainly due to a poor description. I'm very knowledgeable of all the related work, and in particular the temporal/logical side of the matters, but I have a hard time understanding the method from its particular description in the text (and the appendices do not help much, since not much additional information is included).

The introduction section and Section 2 up to 2.2. are very clear in terms of setup, contributions and approach. Section 2.1. just gives the flavor of multi-task learning, compositions of Q-functions and so on, that are necessary for the rest of the paper. However, Section 2.2. is (in my opinion, and I re-checked the original papers on this topic) not understandable for the general (RL) reader, since it involves many things in only three small paragraphs, even though it implicitly assumes knowledge of how such machines work. For example, the "joint MDP" is used, but this relies on knowing more about temporal logic, the ability to compile into automata and the cross-product of machines with the MDP to create such a joint MDP. Later on in the paper, additional mentionings are made of for example "product" (page 4) and "cross product" (page 5) but never really explained. At this stage it would or could be an obvious thing to say that if we can see the problem as a joint MDP, and I mean the full product model, it again is a Markovian problem (which is the trick in many other papers in this area), hence the approach in Section 2.1. would already apply immediately (since the temporal dimension is compiled out essentially), and the combination will work. Ofcourse... you want to keep as much of the method on an abstract level (hence the reward machine) and you need more. In Section 3.1. the task space is first again formalized as a full product model and the compositional mechanism of Section 2.1. generalized to linear preferences over task primitives. I think this all makes sense, and is clear. The only thing that is not helping, is all the subtle differences of tasks, primitives, skills, goals, skill primitives and many other terms; in my opinion this could be made more clear throughout the paper too.

Section 3.3 is where I think most of the confusion comes from. I think that the motivation and definition of skill machines needs much more explanation and formalization. I you look at the Figures 1 and 2, we see that they are essentially reward machines (in structure) but the difference lies in the "preferences" on the lower parts of the nodes, which give preferences over action choices (in the reward machines, thus not actually action choices, but the condition of going from one high-level node to another). But, even though I have some general understanding of how this would be done (based on earlier definitions in the paper) the text and formalization as given here, are incomplete to me. The motivations for the preferences (state transitions and goals) and how they can be found, and what they mean, does not become clear enough (also not from the proofs of the definitions). Also the additional description of additional learning steps (on page 6) to finetune approximate SMs, is not clear enough for me. 

Section 4 on the experiments has mixed quality, in my opinion. I think the experimental setup and selection of experiments is fine, and clearly is targeted at showing the composition of temporal skills and the reuse or zero-shot computation of new skills is clear. The last experiment with the moving domain, and the exact (motivation for) the particular setup in learning needs more description. But overall, the texts in this section are somehow describing a lot, yet at the same time not very clear and structured. When only looking at the graphs, I see the main message, but the texts do not help much. Overall, I see that what the authors want to show is in the results: for example, the composition of "pick up blue objects or squares, but never blue squares" and then repeating it, is a clear example of the composition of temporal skills, and it works.

Additional aspects:
- Just before Section 2: "high-dimensional video game". This does seem relevant for the experiments at all, right? Same for the remarks about it in Section 4.3. itself.
- Even though I think Section 2.1. contains enough information, I do wish more information would be given about the limitations, and also on the exact motivation for the third rule on negation (generally it looks like Fuzzy operaters by the way, but that is not relevant here).
- Section 2.2. talks about general and simple RMs but it is sometimes unclear which one is the main one to go later on. Maybe be more clear about it here. This section could also use a big illustration of things. Also not clear whether the "function" or "scalar" difference is intuitive without illustrations.
- It is not explained how to move through a (*) location without "breaking any decoration" (see Fig 1 left vs caption).
- The formalization in Def 2. uses subscript 0 essentially for the background MPD even though in this context (with automata) it can be confused with the starting state.
- The discussion of multi-task setups, CRM, HRM and the use of experience for multiple skills is something that is known in hierarchical RL as well, and options. This aspect could be discussed more in detail here, combined with the last part of Section 3 on additional learning phases in the SMs.
- I think the first line of the conclusion is confusing (in the light of the remarks above too) in the sense that skills machines are "finite state machines that can be learned...". It is factually not true, since the automata themselves are not learned (but some parameters are computed or finetuned) and maybe this illustrates some of the confusion I have with parts of the paper still. 

clarity,_quality,_novelty_and_reproducibility: The clarity (and with that the reproducibility) is not adequate yet, I think. The novelty of the work is clear; I have not seen any combination of these two approaches yet, and it makes a lot of sense. The quality of the work (technically) is good enough, I think, but parts of it are not well described which make it not possible (for me) to fully evaluate it properly. The description and motivation of the technical parts needs work.
summary_of_the_review: A mixed evaluation, and one of these harder to review papers in my opinion. I clearly see the technical and conceptual positives in this paper, and I see the potential and the interesting outcomes of the paper. Yet, the description of some parts of the technical aspects is not yet clear enough for me to fully evaluate it. I do not want to kill a (potentially) good paper, hence I vote for a (weak) accept and await the discussion to see whether it can be improved still.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considered a multi-task reinforcement learning problem where all tasks share the same state space, action spaces, and the transition dynamics. A skill machine is proposed to solve complex task involving temporal and concurrent composition which can be learned from reward machine. The authors prove that an agent can solve it while adhering to any constraints. Through experiments, the authors demonstrate the efficiency of the proposed method in several environments. The result shows that the proposed method can provide a near-optimal behavior for a long horizon task without further learning. 
strength_and_weaknesses: Strength:
The proposed method takes use of the finite state machine to solve complex RL tasks. The proposed method guarantees that the resulting policy adheres to the logical task specification. The idea is promising given the fact that the algorithm can learn policies for multiple tasks at the same time. Sufficient experiments are presented to support the statement in this paper.


Weakness: 
Since the proposed method is a finite state machine based, I expect the algorithm suffers from the curse of the dimensionality. The example of office gridworld is simple and small in terms of the goal, state, and action spaces. I would like to read a bit more about how to generalize the proposed method in the case when the spaces are much larger which is more likely to be true in real applications.
The number of goals is very limited in the experiments presented here. It will be great if the authors can present some examples that has larger goal space. 
clarity,_quality,_novelty_and_reproducibility: The proposed method is novel. This paper is well written. 
summary_of_the_review: The multitask reinforcement learning problem is important. But I have concern about the scalability of the proposed method to a more complex real problems.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The submission introduces skill machines (SM), an approach to compositionally generalize over a space of tasks defined as reward machines (RM). In particular, this formulation enables compositional generalization both over concurrent goals (e.g., achieve a ^ b) and temporal goals (e.g., achieve a "then" b). The proposed approach uses planning over the RM leveraging the known RM transition function, and then chains pre-trained skills together to follow the plan. Theoretically, the authors show that SMs are sound, in that if a solution to the task exists in terms of the primitive skills, the SM will find it. Empirically, the method achieves zero-shot generalization, and improves with further training, on one set of grid world tasks and one set of image-based tasks.

strength_and_weaknesses: ########### Strengths ###########
- The motivation for the work is excellent: using RL to train primitive skills that can serve as a basis for solving a multitude of tasks via composition, both concurrently and temporally, as specified by RMs

########### Weaknesses ###########
- I had a difficult time following the details of the approach and the corresponding theory behind it. Perhaps the authors could add more technical details to their manuscript?
- I also had difficulty understanding the exact experimental setting used throughout Section 4
- If my understanding was correct, then I am uncertain about the novelty of the contributions in this work. I hope the authors can clarify this during the discussion period.

clarity,_quality,_novelty_and_reproducibility: I should start by saying that I completely agree with the authors' motivation in developing compositional RL methods, and I think that most in the community would agree with this motivation---whether the compositionality should be built in by design as in this setup or learned automatically from data leads to broader disagreement, but still developing explicitly compositional techniques has good merit.

Perhaps my greatest concern with this paper is that I had a very difficult time finding details of the exact problem setting, approach, and experimental design. Here are some questions that may help clarify some things, which the authors hopefully can address and revise their manuscript to reflect the answers to these questions.
- The manuscript mentions multiple times that the proposed approach exhibits "concurrent compositionality". My understanding is that this stems directly from the use of Nange Tasse et al.'s (2020) [NT20 hereafter] method as the underlying mechanism for learning the primtive skills. Is this understanding correct? I believe this is correct based on this sentence form the beginning of Section 3.2: "We can leverage prior work to solve each individual task using a set of base primitive skills (NT20)." If this understanding is correct, I would encourage the authors to more explicltly state this (e.g., "We leverage NT20's method for learning the base primitive skills, which endows our method with the capability to achieve concurrent compositionality.") If not, what part of the proposed approach deals with the learning of the base skills in such a way?
	- As a side note, I would like to see a clearer discussion on the distinction between concurrent and temporal compositionality. If I understood correctly, the authors use concurrent compositionality to refer to goals specified as "achieve A and B", and temporal compositionality for goals such as "achieve A then B". If this is correct, in many cases the goals specified as concurrent might still be achieved sequentially (e.g., open door 1 and door 2---the agent presumably can't open both at the same time). Is the primary difference that the temporal compositionality explcitly encodes the temporal nature in the task specification?
- The manuscript also states that the primitive skills are learned in a reward-free setting. What exactly does this mean? I initially took it to mean that the task primitives were not manually specified, and the agent explored the environment in some exploratory way, say via curiosity-driven exploration. However, later parts of the manuscript seem to suggest that the task primitives are indeed manually specified. For example, in Section 4.3: "We first train the agent on three base task primitives: pick up blue objects, pick up purple objects, and pick up squares." Could the authors please clarify?
- I also have several questions about the experimental setting:
	- Sec. 4.1: What is the exact experimental setting? The primitive skills are trained on how many tasks and for how long? My interpretation of this sentence: "previous work (NT20) has shown that learning the WVFs takes longer than learning task-specific skills", is that these primitive skills are expensive to obtain. It would be useful to get a sense of how expensive it is for this domain.
	- Sec. 4.1: How is the agent achieving zero-shot performance on the single-task scenario (the rewards are high at the very beginning of the training curves) if, as the authors state, "In the single task domains, ... CRM, HRM and skill machines now cannot leverage prior knowledge"
	- Sec. 4.2: Could the authors for example compute the length of trajectories as a proxy for the qualitative results in Appendix 7? This way, we might get a quantitative comparison that better differentiates SM and QL-SM
	- Sec. 4.2: "skill machines with Q-learning always begin with a significantly higher reward" -- there is no discernible difference in reward w.r.t. SM in Fig 3. What do the authors mean with this claim?
	- Sec 4.3: "In such cases, learning new skills few-shot by leveraging the SM would guarantee convergence to optimal policies as demonstrated in Section 4.2" -- was this validated empirically for the image-based domain?

If my understanding is mostly correct, then the approach uses NT20 to learn primitive skills, and then uses value iteration over RMs to discover how to sequence the skills to achieve temporally specified goals (e.g., in LTL). If this is the case, the novel contribution of the paper in terms of an algorithm is described in these 2 sentences: "To achieve this, we first plan over the reward machine (using value iteration, for example) to obtain Q-values for each transition. We then select the skills for each SM state greedily." Hopefully a revised version of this manuscript can provide a lot more detail, to gauge more accurately the extent of the contributions. The theory in theorem 3 essentially says that there exists some SM that can solve any task in the given task space, but is this also the case for the SMs found via the approximate planning-based solution? 


############## Additional feedback ##############

The following points are provided as feedback to hopefully help better shape the submitted manuscript, but did not impact my recommendation in a major way.

Intro
- So far I'm pretty excited to see where this goes. The problem seems interesting and the promises of the results are high. 

Sec 3 
- It took 4 full pages to cover the background and definitions. While these are not super commonly known results, and so it might make sense to go over them in some detail, maybe it would be better to compress these sections a little to give more room for technical details about the proposed solutions.
- The running example domain is a nice way of guiding the reader

Sec 3.1
- Is the set of task-specific goal rewards for the task primitives manually specified? If so, how? And how does this relate to the notion of "reward-free" specified earlier in the paper for learning the base skills?
- I didn't follow how Lemma 2 in NT20 implies the proof in Theorem 1 here. Why can we assume that pi* is the same? For self-containedness, it might be worth to clarify that more explitly in the Appendix.
- Why do the skills for the task primitives enable solving logical composition? Are we assuming that we are directly following NT20 and so the problem of logical composition is solved via their method?

Sec 3.2
- It seems, up to this point, that these preference functions would be completely unlearnable
- It also seems that, for an exact solution, a different one would have to be learned for each new RM (= task)

Sec 3.3
- My understanding is that the approximate planning over RMs chooses one-hot preferences, as shown in the theorem

Sec 5
- Isn't the ability to handle negation (and all forms of concurrent composition) just a direct consequence of using NT20 under the hood?
- The comparison against options seems a bit unfair because SMs directly use planning to achieve long-term reasoning. Why not compare against similar planning-based approaches?

Typos/style/grammar/layout
- Multi-task or multitask? I saw both in different parts of the paper
- Sec 4.2: there are no orange curves in Fig 3

Supplement
- Source code is not included with the submission, which could have helped clarify some of the details of the proposed solution.
summary_of_the_review: Overall, I think the motivation for this work is strong, but had a hard time finding the technical details needed to precisely understand what the technical contributions of the submission are. I strongly encourage the authors to provide as much detail as possible about their approach in a revised manuscript and to engage in the discussion so I can better understand their contributions. In the meantime, with the manuscript in its current state, I cannot recommend it for acceptance. I will use a low confidence score for my rating to indicate that I have a number of questions that, if clarified, might significantly alter my assessment of the work.

############# Update after rebuttal ###############

I am increasing my score from 3 (reject) to 5 (marginally below threshold) per the discussion with the authors, and increasing my confidence accordingly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new RL framework wherein a set of base skills are learned in a reward-free setting followed by combination of these skills and learning skill machine to produce a complex behavior specified using languages such as linear temporal logic. This allows zero-shot mapping from high-level LTL specification to complex behavior. This is particularly helpful in solving long horizon task n the presence of a sparse learning signal. 
strength_and_weaknesses: Strengths:

- The idea of learning individual skills separately from the task-specific policy is very interesting.

- The combination of individual skills with reward machines can be very effective. 

Weaknesses: 

- There is a major assumption in the paper that needs to be more clearly stated. The considered multitask setting assumes that the underlying MDP can be designed such that the reward for any specific task is R0 + R_\tau where R0 is default reward and R_\tau is reward for a specific task tau. This is not necessarily true, and some work on IRL https://proceedings.neurips.cc/paper/2018/hash/74934548253bcab8490ebd74afed7031-Abstract.html have noticed this to recognize the value of learning temporal specifications as rewards (because this simple sum decomposition is not always feasible). This does not weaken the main contribution of the paper but it is important to recognize the significance of this assumption. 

- The tasks's state space is defined to be product of the environment state and the set of constraints incorporating the set of propositions that are currently true. The latter set can be exponential, and this seems to indicate an exponential blow-up in the state space with the growth in the size of the specifications.

- The experiments seem to use mostly planning tasks. Using examples from Safe AI Gym would be useful to evaluate the full potenital of this method since it is being represented as a general RL approach and not just something limited to discrete planning. 
clarity,_quality,_novelty_and_reproducibility: There are some technically inaccurate statements in the paper. Formally, "regular language" is a particular class of languages and saying that "any regular language, such as linear temporal logics" is inaccurate. LTL is not in RE.  Also, "video game environment" can be rewritten as "game environment". 

At some point in the paper, it states that "We therefore only need concern ourselves with how to solve any task expressed as a linear combination of the primitive tasks" . It is not clear why any task would correspond to such a linear combination. 




summary_of_the_review: Overall, the approach presented in the paper is interesting, but its explanation has some gaps, making the reviewer unable to appreciate it fully. Clarification to the doubts expressed in the review would be useful. 

The reviewer has requested some minor revisions for technical accuracy and would encourage a careful review of some statements. Overall, the paper has enough merit to deserve a positive score and the reviewer has raised the rating.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper addresses a very important problem, providing a way to learn a basis set of low-level skills and then combine them both in "series" (to satisfy temporal logic constraints) and "parallel" (to satisfy Boolean combinations of objectives).  To do so, it combines existing strategies for handing temporal-logic objectives via reward machines and for Boolean combination of goals.  These are new, interesting, complimentary mechanisms and it is not trivial to combine them, so this paper offers significant novelty.

All reviewers and the AC found the paper to be interesting and potentially important.  However, we all also found it very difficult to understand (and the reviewers were well qualified to be able to understand a paper in this area).   Even after significant improvements by the authors, the most critical (sections 3.2 and 3.3) remain elusive.  And, in the experiment descriptions, it was never clear exactly what was learned, when.  There is learning of primitives, analytic (zero-shot) composition of them given a goal spec, but then also something that happens "few-shot" and a mention of the possibility of fine-tuning in the conclusion.  

To really succeed in communicating, it might be helpful to have two things:
1.  A data-flow diagram that explains the computational stages of the overall approach:  what is the input to the entire system?  how are the primitives learned?  what happens when a new task specification arises?  etc.
2.  A more intuitive description of the construction in section 3, and then step-by-step explanation of the example in figure 2.   (Even at the level of detail of explaining the relationship between definition 5 and the skill-machine diagrams.)

We recognize that papers have finite space;  it might be that a somewhat more abstract, intuitive, and compressed description of the two pre-existing composition techniques would allow more room for motivation, intuition and examples of the new contributions.

We would strongly encourage the authors to revise the paper for future submission and look forward to reading it.
justification_for_why_not_higher_score: We all worked hard to understand the paper but were not satisfied with our understanding.  This means that other readers are likely to find it difficult to understand and to replicate.
Decision: Reject