Thank you for the time and effort put into your review.

Comparison to LTL2Action and GCRL-LTL.

We provided an in-depth empirical comparison along with a detailed discussion with LTL2Action in Appendix C.8. We plan to use the extra space afforded by a camera ready to move it into the final version of the paper.

Comparison to GCRL-LTL

In the related work section of the paper (lines 94-100), we provided a discussion of GCRL-LTL which justifies why we did not compare against that method. Please see the Baselines section in the meta-rebuttal for a more detailed discussion. We will clarify this in the final version of the paper.

Clarity, presentation, and notation

Thank you for the feedback. We will make the necessary fixes pointed out by the reviewer and further simplify the presentation in the final version.

DFAs represent all temporal tasks that become Markovian by augmenting the state-space with finite memory

Thank you for bringing this up. We will clarify what this means in the final version as it is indeed confusing / ill-posed. Here, a task is taken to be a Boolean property of an episode: you either perform it or you don't. By making a task Markovian we mean that the state of satisfaction can be determined by just looking at the current state, e.g., did you reach a goal state? Importantly, we are assuming that each state is labeled from a finite set. Mechanically, one can then identify the DFA task from the transitions of the finite states since the properties are only defined over the labels of the finite states.

Signal Temporal Logic (STL), finite memory, and DFAs

The short answer with STL is no. STL is not generally representable with finite memory. A longer answer with STL is that it depends on the specific STL formula and the semantics applied to (i) time, (ii) the signals, and (iii) how finite truncations of the signals are handled. But, per the earlier point, if the STL formula has a finite memory monitor, then yes it can be encoded as a DFA. In such cases, the DFA often corresponds to syntactic progression as seen in LTL2Action.

Is Reference [7] a concurrent submission or a typo?"

Reference [7] is neither a concurrent submission nor a typo. It is a non-archival workshop paper that we have written. It successfully solves the reward sparsity problem with DFA rewards in off-policy RL algorithms using hindsight experience replay.

In Figure 5, what are the black elements in the Legend? Why are they not present in the figures?

Zooming into that figure will reveal that each point has a distinct shape representing the kind of operation applied to the sampled cDFAs. These shapes correspond to the black elements in the legend. We will make this clearer in the final version.

What do the envelope colors in Figure 2 indicate?

Those colors are just there to help track where the messages came from. We will make this clearer in the final version.

Does the encoding generalize to conjunctions of the predicates on edges (e.g., Red & Green)? Are these considered during pretraining?"

Our work does not treat symbolic relations on the edges, however we think it is an interesting direction. Conjunctions may potentionally handled with a many hot encoding, but this is purely speculation.

Defn. 4.1. DFA Mutation

Consider the corresponding adjacency matrix of a DFA, which is a 0-1 matrix indicating the transitions between states. We randomly sample an entry in this matrix and toggle that entry (if the entry is 0, make it 1; and if the entry is 1, make it 0). This is precisely what a mutation is. We will update the definition in the final version and make it clear.

"What is being “minimized” here?"

The DFA is being minimized. Specifically, the number of states is being minimized. Conceptually, this corresponds to merging states that are interchangable (have equivilent residual languages). This results in a canonical representation that is irreducable. See https://en.wikipedia.org/wiki/DFA_minimization for details.

Should DFA and DFA(s) be used interchangeably?"

Thank you for pointing out this inconsistency. They are indeed not interchangable and we will correct these abbreviations in the final version.

Thank you for the time and effort put into your review.

Regarding the comment on the labeling function.

We agree with the potential usage of computer vision algorithms to segment and label states of the world from pixels. We think there is a lot of interesting and fruitful future work that could address this limitation. We will use the additional space to comment on this issue and hint at possible directions for future work in the final version of the paper.

Weaker performance in Zones.

The performance difference between the Letterworld and the Zones environments, as the reviewer pointed out, is due to the fundamental difficulty that comes with continuous control. That is, in continuous domains, it is harder to learn control from an uncountable domain of inputs, and it takes longer to reach a goal, resulting in lower discounted return. As suggested, we will include images from both environments to highlight these points and the fundamental difficulty of continuous domains along with a discussion on how to mitigate these difficulties.

Safety/correctness guarantees

Thank you for the question. At this point, without further research, we believe it is hard to say anything precise about the safety of the learned policies. To the best of our knowledge, there are still scalability issues with the state-of-the-art NN verification literature; however, the constrained planning methods direction pointed out by the reviewer is definitely interesting and is part of our broader research agenda. Another promising approach is also have the policy output a correct certificate, such as a reach-avoid martingale, to make the verification problem simpler.

How are reach or avoid transitions created

Conceptually, the reach/avoid transitions are indirectly constructed by first starting with a chain of N states and a failure state, FAIL:

$S_1 \rightarrow S_2 \rightarrow \cdots \rightarrow S_N$

For each state $1,\ldots,N$, the tokens are partitioned into reach/avoid/noop. The reach tokens advance that state ($S_i \rightarrow S_{i+1}$). The avoid tokens transition to FAIL. RAD is derived by mutating the transitions (toggling entries in the transition matrix) and minimizing. Conceptually, this acts to reintroduce features like cycles, skip connections that offer more than a single path, while avoiding fully connected ``random'' graphs.

Question about Fig. 4.

Due to time and compute. Running experiments in the Zones environment requires much more compute resources and time than Letterworld; therefore, we only run experiments for the best (frozen and pretrained GATv2) and baseline (GATv2 with no pretraining) configurations of the framework in the Zones environment. For the same resource reason, in Zones, we did not train the policies using embeddings produced by an RGCN model. We believe that the Letterworld experiments give enough evidence to conclude that embeddings of a pretrained and frozen GATv2 give the best performance in the continuous domain, but can include more experiments if it would be useful.

Question on training a general cDFA embedder

Thank you for the question. To answer this, first note that the pretraining is independent of the downstream application / MDP. Second, without environment semantics, the tokens are just labels that can be permuted, relabeled, etc. Thus, changing the labeling is as simple as deciding the index of each token. Therefore, one can pretrain a GATv2 model on RAD cDFAs with N symbols, and then use it in any environment and downstream application with up to N symbols.

Of course, in order to use the embedding of the environment, one must somehow ground/order the tokens. In our experiments, this is implicit through the evolution of the embeddings (as the DFA progresses, we provide the corresponding embedding). In the future, one could imagine sending as side information an embedding of each token, but this is purely speculative. We will make it clear in the final version.

Thank you for the time and effort put into your review.

Regarding Clarity of Sec. 3.1.

We appreciate this feedback on clarity so we will include an explanation for the specific graph encoding we use. Essentially, we apply four operations on a DFA to construct a graph encoding:

1. Add intermediate nodes between states to encode edge constraint information. Explanation: We want edge constraints to be used during message-passing. By introducing these intermediate nodes with edge constraint information, we make sure that each node receives messages including edge constraints needed to get to the next states.
2. Reverse all the edges. Explanation: We want each state to receive information from future states since the goal is to find an accepting path in the DFA.
3. Add self-loops. Explanation: We want each node to receive messages from itself to avoid forgetting the local node message. It is a common practice in the GNN literature.
4. Add edges from the nodes corresponding to the initial states of DFAs to the “AND” node. Explanation: The "AND" node can be understood as a conjunction operator aggregating messages from each DFA in the composition. It is connected to the initial states of each DFA because we want this operator to receive information from the current state of each DFA.

Curse of Dimensionality.

By the curse of dimensionality, if the reviewer means the exponential blow-up caused by taking the conjunctive composition of DFAs, please see the cDFA section of the meta rebuttal which clarifies how we avoid such a blow-up.

Comparison with other baselines

Please see the baselines section of the meta-rebuttal. To directly address your question, we will move the experiments comparing our work with LTL2Action (given in Appendix C.8) to the main body of the paper to help further contextualize the proposed method. The key result is that our approach does indeed generalize better given the RAD pretraining.

Insights into how the task embeddings support generalization.

We definitely believe that further research is crucial to understand why and how the task embeddings support generalization. However, we believe this is a research question on its own and should be investigated in future work. Please also note that our embedding space analysis given in Fig. 5 in the main body and Fig. 9 in the appendix provide an intuition for the generalization results we see in the paper by visualizing the structured nature of the learned embedding spaces.

How would the results of the generalized agents with task embeddings compare to specialized agents?

In our experiments, we did not see any significant difference between RAD pretrained agents versus agents trained for a single task class when evaluated on the same task class; therefore, we omitted these results. However, we can include such a comparison in the final version of the paper.

In Figure 4, why do the Zones results only have two models?

Due to time and compute. Running experiments in the Zones environment requires much more compute resources and time than Letterworld; therefore, we only run experiments for the best (frozen and pretrained GATv2) and baseline (GATv2 with no pretraining) configurations of the framework in the Zones environment. For the same resource reason, in Zones, we did not train the policies using embeddings produced by an RGCN model. We believe that the Letterworld experiments give enough evidence to conclude that embeddings of a pretrained and frozen GATv2 give the best performance in the continuous domain, but can include more experiments if it would be useful.

At a high level, how would you extend the approach to incorporate general boolean combinations?

Please see the meta-rebuttal section on cDFA.

Thank you for the time and effort put into your review.

Regarding LTL2Action not being finite

The reviewer is right in the sense that in the LTL2Action paper, the encoder could mechanically be applied to standard LTL, but there is no indication that this will work. The reality is that the training code and experiments only consider finite LTL. For example the corresponding line in the LTL2Action repo shows that an LTL task is declared done'' when the underlying LTL formula cannot be progressed'' anymore. The LTL2Action paper leaves room for the idea of using rewards to encode infinite horizon tasks, but we note that this is an active research topic with some of the more theortically sound and practical works on the subject post-dating LTL2Action. As such, we stand by our initial assement that LTL2Action should be compared against techniques for finite trace properties.

DFAs vs cDFAs

Please see the global rebuttal for an explanation of extension to negations and disjunctions.

Comparison with GCRL-LTL

Although the solved problems are similar, comparison with GCRL-LTL is an ``apples to oranges'' comparison as it is a hierarchical planning-based method that does not generate embeddings. These are fundamentally different approaches and the work on GCRL-LTL already provides a comparison. Such approaches will, of course, learn faster than an embedding space-based approach since they only learn the goals in the environment, and the temporal planning is done algorithmically. However, as pointed out by Reviewer bN73, we believe there are many interesting future works that could follow from our approach. Please see section Baselines in the global rebuttal for more details.

Having Boolean expressions on edges

Standard DFAs cannot have Boolean expressions on edges. Automata with Boolean expressions on edges are variants of symbolic automata, which is an extension that we leave for future work.

Regarding self transitions

As written on line 137 of the submission, for ease of notation, we assume stuttering semantics: "Omitted transitions are assumed to stutter, that is transition back to the same state".

Why is freezing better?

This is a good question. Our current hypothesis is that the RAD pre-training learns a sufficently good representation that introducing changes to it and/or computing the corresponding gradients ultimately makes performance worse. In particular, less of the gradient updates are directed at learning dynamics and instead try to overfit to the specific concept class.

However, as this is pure speculation, we have left such discussion out of the paper and think its an interesting avenue for future research.

Stress testing

The issue with the proposed conjunction stress test is that the more DFA you have in a conjunction, the less likely that the sampled task is satisfiable since each DFA is essentially a constraint over the set of accepted behaviors, and as the number of constraints increases, it is more likely to end up with an empty set. So it is hard to say if the framework would break because of a limitation of the approach or because the sampled tasks are not satisfiable. Nevertheless, its an interesting question to design a stress test that approriately seperates the the failure causes.

Comments on end-to-end function approximation

We respectfully disagree that the community is moving away from end-to-end function approximation, particularly for reward specification. If anything, the introduction of strong multi-modal image/language embeddings such as CLIP have resulted in an explosion of work focused on end-to-end learning from embeddings of a task. They include using sketches, language corrections, and of course language instruction.

Finally, while hierarchical planning is a powerful approach, as previously discussed, it is not a complete replacement for end-to-end function approximation. We believe that a focus on function approximation and embeddings for logical specifications not only aids generalization but also provides a path forward to integrate multiple modes (DFA embeddings, natural language embeddings, image embeddings) in machine learning models.

On exposition and definitions

Thank you for your feedback. As reviewer WW4E noted, combining formal objects like DFAs and MDPs can result in notation-heavy and unapproachable work. One technique we employed in the definitions of MDPs and goal-conditioned RL was a simplification of the essential components necessary to understand the material at hand. We will use the additional space afforded by the camera ready to remark that these are simplifications of the more general definitions as you note.

For example, we indeed omitted the reward (as is sometimes done in inverse learning works) to emphasize that we are in the binary sparse reward setting. Similarly, because goal-conditioned RL reduces to maximizing reach probability, this is the definition we employ. Again, we will make this clear in future versions.

Finally, we chose to omit definitions such as message passing NN and employ short hands such as "e.g.", "i.e." as they are standard within the NeurIPs community.

• Regarding Defn 3.1. DFA-condition policies use both the environment state and the DFA embeddings. This pair corresponds to the augmented state space. We showed this by abusing the notation and writing $\pi : S \times DFA$. We will make it clear in the final version.
• Minor questions. We use "concept class" and "task class" as well as "goal" and "task" interchangeably. We will clarify this and your other comments in the final version.