Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning
Authors: Beyazit Yalcinkaya
Niklas Lauffer
Marcell Vazquez-Chanlatte
Sanjit A. Seshia
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
goal-conditioned reinforcement learning
formal methods
graph embeddings
representation learning
Primary area: reinforcement_learning
TL;DR: We show how to produce rich neural embeddings of temporal tasks for use in goal-conditioned RL.

Abstract: Goal-conditioned reinforcement learning is a powerful way to control an AI agent's behavior at runtime. That said, popular goal representations, e.g., target states or natural language, are either limited to Markovian tasks or rely on ambiguous task semantics. We propose representing temporal goals using compositions of deterministic finite automata (cDFAs) and use cDFAs to guide RL agents. cDFAs balance the need for formal temporal semantics with ease of interpretation: if one can understand a flow chart, one can understand a cDFA. On the other hand, cDFAs form a countably infinite concept class with Boolean semantics, and subtle changes to the automaton can result in very different tasks, making them difficult to condition agent behavior on. To address this, we observe that all paths through a DFA correspond to a series of reach-avoid tasks and propose pre-training graph neural network embeddings on "reach-avoid derived" DFAs. Through empirical evaluation, we demonstrate that the proposed pre-training method enables zero-shot generalization to various cDFA task classes and accelerated policy specialization without the myopic suboptimality of hierarchical methods.

Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning
Beyazit Yalcinkaya' University of California, Berkeley beyazit@berkeley. edu
Niklas Lauffer' University of California, Berkeley nlauffer@berkeley.co edu
Marcell Vazquez-Chanlatte Nissan Advanced Technology Center marcell. wwwnlatteeiinssaaalaaa com
Sanjit A. Seshia
University of California, Berkeley saeshia@berkeley, edu
Abstract
Goal-conditioned reinforcement learning is a powerful way to control an agent's behavior at runtime. That said, popular goal representations, e.g., target states or natural language, are either limited to Markovian tasks or rely on ambiguous task semantics. We propose representing temporal goals using compositions of deterministic finite automata (cDFAs) and use cDFAs to guide RL agents. cDFAs balance the need for formal temporal semantics with of interpretation: if one can understand a flow chart, one can understand a cDFA. On the other hand, cDFAs form countably infinite concept class with Boolean semantics, and subtle changes to the automaton can result in very different tasks, making them difficult condition agent behavior on. To address this, observe that all paths through a DFA correspond to a series of reach-avoid tasks and propose pre-training graph neural network embeddings on Treach-avoid derived" DFAs. Through empirical evaluation, we demonstrate that the proposed pre-training method enables shot generalization various cDFA task classes and accelerated policy specialization without the myopic suboptimality of hierarchical methods.
AND
GATv2
g Concatenate
S
Convolutional Noural Network
O
(sp
gi)
42
42
a
Palicy Network
Go to grean while awoiding red
Co to onange witl seiing wiin Tumbber timee
cDFA Embedding Space
Figure 1: Given a (conjunctive) composition of deterministic finite automata (shown on the left), we construct its embedding using graph neural network (GATv2) and use this embedding as goal to condition the reinforcement lcarning policy.
'Equal contribution
For more information about the project, visit: http:://radeemmbbdddiggggghbbbbb
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
Goal-conditioned reinforcement learning (RL) [3] has proven to be a powerful way to create AI agents whose task (or goal) can be specified (conditioned on) at runtime. In practice, this is done by learning goal encoder, i.e., a mapping to dense vectors, and passing the encoded goals as inputs to policy, e-g., feedforward neural network. This expressive framework enables the development of flexible agents that can be deployed in a priori unknown ways, e.g., visiting states never targeted during training. The rise of large language models has popularized leveraging natural language as an ergonomic means to specify a task, c.g., "pick up the onions, chop them, and take them to stove."
While incredibly powerful, tasks specified by target states or natural language have a number of shortcomings. First and foremost, target states are necessarily limited to non-temporal tasks. On the other hand, natural language is, by definition, ambiguous, providing little in the way of formal guarantees or analysis of what task is being asked of the Al agent.
To this end, we consider conditioning on tasks in the form of Boolean combinations of deterministic finite automata (DFAs). We refer to this concept class as compositional DFAs (cDFAs). The choice of cDFAs the concept class is motivated by three observations. First and foremost. DFAs offer simple and intuitive semantics that require only a cursory familiarity with formal languages-if one can understand flow chart, one can understand a DFA. Morcover, recent works have demonstrated that DFA and cDFA can be learned in a few shot manner from expert demonstrations and natural language descriptions [1] As such, DFAs offer balance between the accessibility of natural language and rigid formal semantics. The addition of Boolean combinations to cDFA, e.g., perform task AND task 2 AND task 3. provides simple mechanism to build complicated tasks from smaller ones.
Second, DFAS represent temporal tasks that become Markovian by augmenting the state-space with finite memory. Further, they are the "simplest" family to do so since their finite states are equivalent
to having& a finite number of sub-tasks, formally Nerode congruences [19]. This is particularly important for condicoond RL which necessarily treats temporal tasks differently than traditional RL. For traditional RL, because the task is fixed, one can simply augment the state space with the corresponding memory make the task Markovian. In goal-conditioned RL, this is not, in general, possible as it is unclear what history will be important until the task is provided. Instead, the encoded task must relay to the policy this temporal information. Third, existing formulations like temporal logics over finite traces and series of reach-avoid tasks are regular languages and thus are expressible as DFAs 11]. This makes DFAS a natural target for conditioning an RL policy on temporal tasks.
The expressivity of DFAs introduces a number of challenges for goal-conditioned RL. First, DFAS form countably infinite and exponentially growing concept class where subtle changes in the DFA can result in large changes in an agent's behavior. Notably, this means that any distribution over DFAs is necessarily biased with many "similar" DFAs having drastically different probability. Thus, to generally work with DFAs, one cannot simply match finite patterns, but need to learn to encode details necessary for planning. Second, very sparse binary reward signal- -did you reach the accepting state or not? Together with non-trivial dynamics, naive applications of RL become infeasible due to the lack of dense reward signal. Finally, the apponentially-expaddiin concept class presents computational limitations for encoding. For example, many interesting DFAs may be too large be feasibly processed by a graph neural network.
with traditional goal-based objectives, DFAs provide
To address these issues of reward sparsity and the need to encode planning, we introduce a distribution of DFAs, called reach-avoid derived (RAD). This concept class is inspired by the observation that all paths through a DFA correspond to a series of (local) reach-avoid problems. We argue in Section that RAD encourages learning to navigate a DFA's structure. Our first key result is that pre-training DFA encoders on RAD DFAS enables zero-shot generalization to other DFAS. Next, we treat the problem of DFA size. Many problems are naturally expressed compositionally. e.g., sequence of rules that must all hold or a set of tasks of which at least one must be accomplished. Due to their Boolean semantics, i.e., did you reach the accepting state or not, DFAs offer well-defined semantics under Boolean compositions. Our second key insight is to encode conjunction of DFAs (called cDFAs). This is done by using a graph attention network [9] (GATv2) to encode the individual DFA graph structure as well as the conjunction (AND) relationships between a collection of tasks. Recalling that the conjunction of any two DFAS grows (worst-case) quadratically, we observe that cDFAs offer an exponential reduction in the size of temporal tasks passed to GATv2.
With negations and disjunctions omitted as straightforward extensions.
2

---

1.1 Contributions. Our main contributions are: (1) we propose compositional DFAs (cDFAs), which balance formal semantics, accessibilityy, and expressivity. as a goal representation for temporal tasks in goal-conditioned RI; (2) we propose encoding cDFAs using graph attention networks (GATv2); (3) we propose pre-training the cDFA encoder on reach-avoid derived (RAD) DFAs, and (4) we perform experiments demonstrating strong zero-shot generalization of pre-training on RAD DFAs.
Our work explores a temporal variant of goal-conditioned RI. 33 where goals are represented as automata. While traditionally focused on goals as future target states, this has since been extended to tasks such natural language 77 21 26 37 and temporal logic [38]. While not as expressive as natural language, we believe cDFAs offer a balance between the ergonomics of language while maintaining unambiguous semantics-smmething of increasing importance due to the seemingly inevitable proliferation of Al agents to safety-critical systems. Moreover, DFA inference has rich literature 66, 15
1.2 Related Work.
28 451 with recent works have even shown the ability to learn DFA and cDFA from natural language and expert demonstrations eennonttraionn-bbidiinng the gap even more between natural language and automata specified goals [4] 42 43).
17
24
27
Operating in a similar space, previous work, L.TL.Acctin 33, has shown success with using (finite) linear temporal logic (LTT.), modal extension of propositional logic, to condition RI. policies on. In fact, the pre-training and test domains used in this paper are directly derived from that work.
Our choice to focus on DFA rather than LTL is two-fold. First and foremost, over finite traces, LTL is strictly less expressive than DFA, For example, LTL cannot express tasks such as "the number of times the light switch is toggled should be even." Second, like DFA, LTL tasks constitute countably infinite set of tasks. This again means that any distribution over LTL is necessarily biased certain subclasses. On the one hand, the syntactic structure makes separation of subclasses very easy. On the other, it remains unelear how to generalize to "common" L.T. formula. By contrast, we argue that the local reach-avoid structure of DFAs offers direct mechanism for generalization. Finally, we note that while L.TL exponentially more succinet than DFA, this largely mitigated by supporting boolean combinations of DFAs (cDFAs).
Moving away from goal-conditioned RL, recent works have proposed performing symbolic planning on the DFA and cleverly stringing logether policies to realize proposed paths 16 22 23 30).
However, their method can still suffer from sub-optimality due to their coal-conditioned value functions being myopic. Specifically, if there are multiple ways to reach the next sub-goal of a temporal task, the optimality of the next action depends on the entire plan, not just the next sub- sub-goal- destroying the compositional structure used for planning. For example, Figure 4 shows a simple example which hierarchical approaches will find a suboptimal solution due to their myopia. In contrast, conditioning on cDFA embeddings allows our policies to account for the entire task.
On the single-task LTL-constrained policy optimization side, several works have tackled the problem in varying settings [10
13 36 44). Adjacent to these efforts, various approaches have explored LTL specifications and automaton-like models objectives in RL K
32] 46 48)
A different line of work considers leveraging quantitative semantics of specifications to shape the
reward I 22 25 36.. However, all of these lines of work are limited to learning a single, fixed goal.
Finally, in a previous work 47, we used hindsight experience replay [ to solve the reward sparsity problem for DFA-conditioned off-policy learning of DFA task classes. We observe that our RAD pre-training pipeline has similar sample efficiency while generalizing to larger classes of DFAs.
2
Preliminaries
In the next sections, we will develop a formalism for conditioning agent behavior on temporal tasks represented DFAs. To facilitate this exposition, we quickly review goal-conditioned RL and DFA.
2.1 Goal-Conditioned RL. We start with technical machinery for goal-conditioned RL.
Definition 2.1. A Markov Decision Process 3 (MDP) is a tuple M = (S. A, T),, where is a set of states, A is set of actions, and T is map determining the conditional transition probabilities, ie. Pr(s// s, a)
def T(s', a, 8) for 8, E S and a E A. We assume that M contains a sink
We omit reward function since in a gonl-conditioned setting with varying objectives/rwaard.
3

---

state, S, denoting the end of an episode. Any MDP, M,, can be given 7-temporal discounting semantics by asserting that each transition can end the episode with probability 1 1-y. y. Formally, ("(s',a,)) = (1 7) T(s', 0, (), for 8, of 8.
Definition 2.2. Let & be a set of states called goals. A goal-conditioned policy π : S + AA, a map from state- -oaalegggaaaa pairs to distributions over actions. Together, an MDP .M and goal-conditioned policy, n,, define a distribution of sequences of states, called paths.
A goal-conditioned reinforcement learning problem is a tuple consisting of a (possibly unknown) MDP and a distribution over goals, Pr(g) for g 9. The objective of goal-conditioned RL is to maximize the probability of generating a path containing g.
2.2 Deterministic Finite Automata. Next, we provide a brief refresher on automata.
Definition 2.3. A Deterministic Finite Automaton (DFA) is tuple AA = (Q, Σ, 6, a finite set of states. > is finite alphabet, 8 : Q x Σ + Q is the transition function, go E Q is the initial state, and F' _ Q are the accepting states. The transition f'unction can be lifted to strings via repeated application, 8* Q x E- - Q. One says A accepts x if 8 (40. X) E F. Finally for simplicity, we abuse notation and denote by DFA the set of all DFA.
Fo. F). where Q
Visually, we represent DFAs as multi-graphs whose nodes represent states and whose edges are annotated with a symbol that triggers the corresponding transition. Omitted transitions are assumed to stutter, i.e., transition back to the same state. DFAs have a number of interesting properties.
Up state isomorphism, all DFAs can be minimized to canonical form, e-g., using Hopcroft's algorithm [8.. denoted by minimize(AA) Further, DFAs are closed under Boolean combinations. For example, the conjunction of two DFAs, Ai and A2, denoted Ai A A,2 is constructed by taking sementt-wss, 6((q1, 92). r) = (41, σ), (2(2 r)). Also, (41, 92) E F if q1 E F1 and q2 E F2. While DFAs are closed under conjunction, each pair-wise operation results in a O(n)) increase in the number of states. Definition 2.4. A compositional DFA (cDFA) is a finite set of DFA, C (A,,...,AA}} The monolithic DFA associated to cDFA, C, is given by monolithic(C) del cDFA are inherited from its monolithic DFA, i.e., a string x is accepted by cDFA C if and only if is accepted by monolithic(C). Graphically, cDFA are represented as trees of depth 1 where the root corresponds to conjunction and each leaf is itself a DFA.
the product of the states, Q Q x Q2. and evaluating the transition functions
M A. The semantics of
2.3 Augmenting MDPs with cDFAs. Observe that DFAS can be viewed as deterministic MDPs leading to a natural cascading composition we refer to as DFA-augmention of MDP. Informally, one imagines that the MDP and DFA transitions are interleaved. First, the MDP transitions given an action. The new state is then mapped to the DFA's alphabet. This symbol then transitions the DFA. The goal is to reach an accepting state the DFA before the MDP reaches its end-of-episode state.
Formally, let A and M be a DFA and MDP, respectively and let I. S - Σ denote a labelling function mapping states to symbols in the DFAs alphabet. The new MDP is constructed as quotient of the cascading composition of A and M. First, take the product of the state spaces, S' x Q. The action space is M's action set. The transition of the MDPs state is as before and the DFA transitions are given by: 8(q, L(s)). In order for there to be unique goal and end-of-episode state, we quotient S Q as follows: (i) (8, q) are treated as a single end of episode state and (ii) for all accepting states, q E F. the product states (s, q) are treated as a single accepting (goal) state.
3 Compositional Automata-Conditionet Reinforcement Learning
We are now ready to formally define (compositional) automata-coonditioned RL as a variant of goal-conditioned RL where goals are defined in the augmented MDPs
Definition 3.1. A DFA-conditioned policy, π S x DFA + AA is a mapping from state-DFA pairs to action distributions. A and P is a distribution over DFAs. The objective is to maximize the probability of generating a path containing the accepting state. ODFA-conditioned RL is defined via the underlying monolithic DFA.
RL problem is a tuple (M, P), where M is an MDP
'Note that in practice, RL (and by extension conditiidi RL) policies often consume a state observation rather than the state itself. This is simple extension to the above which is left out for simplicity of exposition.

---

AND
40
42
42
41
41
gt
Figure 2: Message passing illustration on the featurization of the cDFA given in Figure
The proposed architecture for conditioning RL policies temporal tasks encoded as cDFA is given in Figure At step t, given an observation and a cDFA Ct, we compute an embedding 8; of the observation or using convolutional neural network and embedding 9: of C2 (constituting goal) using a meessgg-ppssiing policy network to get action aę. After taking dt, initial state of each A E C. based on the transition taken. We then minimize each updated DEA to form the next cDFA C++1, which is used to get the next action a++1-
neural network (MPNN). We then concatenate 8; and gr and feed it to a
the next observation o++1 update the
3.1 cDFA Featurization. In order to pass cDFA C. to MPNN, we construct featurization Gc, = -Vyc, &c., ). Details of this process are given in Appendix Essentially, we apply four sequential modifications to the graph structure trivially induced by C:: (i) add new nodes for every transition in each DFA in the composition, remove these transitions to connect the new nodes to the source and target nodes of the removed transitions, and in the feature vectors of the new nodes, encode all symbols triggering that transition using positional one-hot encodings, (ii) reverse all the edges, (iii) add self-loops to all nodes, and (iv) add edges from the nodes corresponding to the initial states of DFAS to the "AND" node. Figure shows the featurization of the cDFA given Figure
3.2 cDFA Embedding. Given cDFA featurization Sc, = (Vc,, Ec,, lc,), we construct an embedding the cDFA using a graph attention network (GATv2) (9] performing a sequence of message passing steps map each node vector. For ease of notation, refer to the features of node v E Ve. as fop hc, (v). At each message passing step, node features are updated as:
h4
Σ Ovvu BruWigthus
(E)(v)
where ((v) denotes neighbors of v, Wege is a linear map, and ava is the attention score between and u computed as:
Chu softmax;(ew/)
Eva = LeakyReLU (Warehy + Wegthw),
where is vector and Were is a linear map. After message passing steps the feature vector of the cDFA's "AND" node (which has received messages from all A, E C.) represents the latent space encoding ge of the temporal task given by C.
4 Pre-training on Reach-Avoid Derived (RAD) Compositional Automata
In this section, we introduce pre-training on reach-avoid derived (RAD) cDFAs. This pre-training is designed to solve three important problems. First, we wish to avoid simultaneously learning a control policy and embeddings for the cDFAs. Second, we wish to learn that performs well across cDFA distributions. Third, we wish to have either a domain- -specffc or a general cDFA-conditioned policy that performs well across different cDFA distributions.
cDFA encoder
To alleviate the first problem, i.c., decoupling of learning control and cDFA embeddings, we follow (38) and pre-train our cDFA encoding GNN on "dummy" MDP containing single non- end-of-episode state. To solve this dummy MDP, we connect single linear layer the output the GNN which maps cDFA embeddings to the symbols in its alphabet. We then take these symbols and
Note that the same weights, W and Wess used in each message- message-passing step.
5

---

Mutate and minimize
40
41
94
43
40
41
42
42
q
SRA DFA
RAD DFA
Figure 3: An example sequence of local reach-avoid problems and RAD DFA obtained from it.
take transition (either stuttering one one that changes the state of the DFA) in each DFA of the composition. The episode ends either when all DFAs end up in their corresponding accepting states (reward 1) or when one of the DFAs in the composition ends up in non-accepting sink state (reward -1). The cDFA-augmentation then only models the dynamics the cDFA being conditioned on. The resulting cDFA-conditioned RL problem can thus focus on only learning to encode the cDFAs.
4.1 Sequential reach-avoid as the basis for planning, What remains then is to support gener- alization to other cDFA distributions. particular, recall that cDFAs (and DFAs) lack canonical "unbiased" distribution making it priori difficult to pre-select a cDFA distribution. To begin, observe that realizing any individual state transition q - q' through DFA corresponds to a reach-avoid task: (i) eventually transition to state o' and (ii) avoid symbols that transition to a state different than q and q' Further, a path through a DFA, (1.-.-- : In corresponds a sequence of reach-avoid (SRA) tasks. Notably, illustrated in Figure 3 SRA tasks can be represented as DFA. Thus, in order to generally reason about satisfying DFA, our neural encoding must be able to solve SRA tasks.
4.2 Reach-avoid derived DFAs. For general DFAs, there can be arbitrarily many (often infinitely many) paths leading to an accepting state, resulting in multiple SRA tasks interacting and interleaving. Thus, the overall structure of a DFA might be much richer than an SRA task even though consists of local reach-avoid problems. Building the observation that paths of a DFA correspond to SRA tasks, we define reach-avoid derived DFAs as a generalization of SRA.
Definition 4.1. We define mutation of a DFA
be the process of randomly changing a transition of A, removing the outgoing edges of the accepting state, and then minimizing. To change a transition, uniformly sample state-symbol-stan triplet (,,,,')) and define 5(g, σr) def q'. A DFA A is said to be m m-recch- derived (m-RAD) if it can be constructed by mutating an SRA DFA m-times.
We define the (m. p) RAD distribution over DFAs follows: (i) sample a SRA DFA, A, with k + states where k ~ Geometric(p): each transition stutters with probability 0.9 and is otherwise made a reach avoid transition with equal probability; (ii) sequentially apply m mutations where mutations leading to trivial one-state DFAs are rejected. To avoid notational clutter, we shall often suppress m. p and say RAD DFAs. Finally, we define the RAD cDFA distribution by sampling n RAD DFAs. where n is also drawn from geometric distribution. See Appendix B for the pseudocode, Figure demonstrates how mutations and minimization can turn an SRA DFA into RAD DFA. To get the RAD DFA, we apply two mutations to the SRA DFA, adding two new transitions: (i) from go gs on green and (ii) from qa to qi on blue, and then the minimization collapses go and q4 to single state.
Experiments
We explore the following 6 questions on several task classes in discrete and continuous environments:
RQ1 Do our policies overcome the limitations of hierarchical approaches?
RQ2 Does pre-training of the cDFA encoder RAD cDFAs accelerate cDFA-conditioned RL?
RQ3 Does freezing the cDFA encoder negatively impact cDFA-conditioned RL performance?
RQ4 Do the cDFA-embeddings pre-trained on RAD generalize other task classes?
RQS How does the RAD pre-trained cDFA encoder represent the corresponding cDFA?
RQ6 Do RAD pre- trained cond-conditioned policies generalize across task classes?

---

0.8
90
Discounted return
0.6
91
Hierarchical limit
Optimal
0.2
4
10
20
Frames (thousands)
Figure 4: An example in which the myopia of hierarchical approaches causes them to find a suboptimal solution. the task is to first go to orange and then green, the hierarchical approaches will choose the closest orange which takes them further from green whereas our approach finds the optimal solution.
Letterworld Environment. Introduced in 4 [38. Letterworld is 7x7 grid where the agent occupies one square a time. Some squares have randomly assigned letters which cDFA tasks are defined over. The agent can move in the four cardinal directions to adjacent squares. Moving into square with letter satisfies the corresponding symbol. The agent observes position and the letters in each grid. Each layout has 12 unique letters (each appearing twice) and horizon of 75.
Zones environment. Introduced in (38] (building on Safety Gym (31). Zones is as an extension to Letterworld with continuous state and action spaces. There are 8 colored of each color) circles randomly positioned in the environment. cDFA tasks are defined over colors. The agent's action space allows it to steer left and right and accelerate forward and backward while observing lidar, accelerometer, and velocimeter data. The environment has a horizon of 1000.
Task classes. In addition to RAD, we consider the following task classes in our experiments.
Reach (R): Defines total order over & Uniform( (1, K) symbols. c.g., 9o and q1 in Figure Reach-Avoid (RA): Defines an SRA task of length k ~ Uniform( (1, K), e.g., first DFA in Figure Reach-Avoid with Redemption (RAR): Similar RA, but they have transitions from their avoid state to the previous state, e.g., the sub-DFA with states qu- Q1, 93 in Figure
Parity: A sub-class of RAR where the symbol that leads the avoid state also triggers a transition back to the previous state, e.g., the DFA on the right in Figure [ These tasks are not expressible in LTL due to their languages not being star-free regular
Given bound N, using these task classes, generate their compositional counterparts by sampling n ~ Uniform( 11 .) many DEAS to form a cDFA. As a short-hand notation, for example, we refer to RAR cDFAs with maximum number of conjunctions where each DFA has task length of also as cRAR. 1.3. and refer to its associated monolithic (see Definition 2.4 class as 1.R.1.22.133 i.e., without the "c" prefix. We use the same abbreviation convention for other task classes well. We use cRAD for RAD cDFAs with truncated distributions and NT-cRAD for the not-truncated version.
Finally, for comparisons with 38 we include the task classes defined in that work, i.e., partially ordered (PO) and avoidance (AV) finite LTL tasks, represented as cDFAs.
Pre-training procedure. We pre-train GATv2 RAD eDFAs in the dummy MDP as described in Section 4 We set both geometric distribution parameters of the RAD cDFA sampler to 0.5 and that n < and
truncate these distributions number of DFAs in a composition is 5, and the maximum number of states of each DFA is 10. As baseline for GATv2, we also pre-train relational graph convolutional network (RGCN) 34
< 10, i.e., we make sure that the maximum
Training procedure. We experiment with training policies three ways: Training without pre- training (no pretraining), with frozen MPNNs pre-trained on RAD as described in Section (pretrain ing (frozen)), and allowing the pre-trained MPNN continue receiving gradient updates (pretraining).
We use proximal policy optimization (PPO) 351 for all reinforcement learning setups, giving reward of +1 when rollout reaches the accepting state of the cDFA task. -1 when rollout reaches

---

Discounted return
Letterworld
Zones
0.8
0.8
GATV2 no pretraining
0.6
0.6
GATv2 pretraining
0.4
0.4
GATv2 pretraining (frozen)
RGCN no pretraining
0.2
0.2
RGCN pretraining
0.0
0.0 RGCN pretraining (frozen)
10
15
20
5
15
Frames (millions)
Frames (millions)
Figure 5: Training curves (error bars show a 90% confidence interval over 10 seeds) in Letterworld (discrete) and Zones (continuous) for policies trained on RAD cDFAs, showing that frozen pre-trained cDFA encoders perform better than non-frozen ones while no pre-training barely learns the tasks.
a rejecting sink state of the cDFA task, and 0 the environment reaches the timeout horizon without achieving the cDFA task. See Appendix D for the hyperparameters and compute used.
RQ1 eeFe-eDDddditttee conditioned policies do not suffer from myopia. First, we present the experiment results highlighting the myopia of hierarchical approaches. To this end, we construct simplified variation of the Letterworld environment, given in Figure 4 where the task is to visit the orange square before the green one. Observe that any hierarchical approach, like [23 30), based high-level planning over some automaton-lin structure suffers from myopia. Specifically, such approaches do account for the overall task while planning for the intermediate goals. In this example, hierarchical approaches fail to differentiate between the two orange squares in the context of the given task. On the other hand, our approach quickly converges the optimal policy as given in Figure
RQ3 Pretraining helps policies perform better faster. Figure 5 shows training curves for learning on RAD tasks using RGCN (dashed curves) and GATv2 (solid curves) as the MPNN module in Letterworld. Without pre-training in the dummy environment (blue curves), the policies barely learn how to accomplish the tasks, likely because of the difficulty in trying to simultaneously learn an embedding of the cDFA task and learn the dynamics of the environment required to reach certain symbols. Frozen pre- pre-training (green curve) helps tremendously in learning the RAD task class the Letterworld regardless of the MPNN module architecture. The policies learned are able to satisfy sampled RAD tasks on average over 95% of the time and within 5 timesteps. Non-frozen pre-training (red curve) also helps the policies learn more quickly, but with significant difference between GATv2 and RGCN. Notably, non-frozee pre-training performs significantly worse for RGCN than its frozen counterpart, showing that freezing the MPNN module after pre-training actually helps performance. We further note that the wall clock training time was significantly faster due to not propagating gradients through the MPNN (about 20% faster).
Pretrained cDFA embeddings generalize well. We tested pre-trained GATv2 and RGCN models on various new cDFAs and their associated monolithic task distributions in the dummy DFA environment. Figure 10 in Appendix C.2 presents experiment results averaged over 10 seeds and 50 episodes per seed. The left y-axis illustrates the satisfaction likelihood while the right y-axis presents the number of steps needed to complete the task. The figure shows that GATv2 achieves approximately 90% accuracy across all tasks, with nearly 100% accuracy in most cases. Although RGCN generalizes comparably to GATv2 in most instances, it achieves around 80% accuracy for both cRA.1.5.1.5 and cRA.1.1.1.10 whereas GATv2 performs at nearly 90% and 100%, respectively.
RQ4:
Considering that the maximum number of DFAs in a composition seen during training is 5 (sampled with low probability) and the DFA with the maximum task length is (with maximum of 10 states, sampled with even lower probability), these generalization results are quite remarkable. GATv2 can generalize to 10 DFAS in composition as well as DFAs with a task length of 10 with nearly 100% accuracy. Furthermore, Figure 10 shows that the embeddings produced by GATv2 lead to shorter episodes compared RGCN, indicating that GATv2 learns better representations for cDFAs. Overall, regardless of the MPNN model used, pre-training the RAD cDFAs provides generalization.

---

Reach-Avoid Derived
Reach-Avoid with Redemption
2-Conjunction Collapse
Reach-Avoid
Parity
1-Step Advance
Reach
No Op
1-5tep Advance Leading Accept
0.8
0.0
0.5
1.0
1.5
2.0
2.5
3.0
(o) GATv2 2-D 4-SNE
(b) GATv2 Cosine similarity heat map
(c) GATv2
Euolidean distaance heat
Figure 6: Visualizations of the embeddings generated by GATv2 pre-trained RAD cDFAs,
illustrating that the learned embedding space reflects the similarities between different task classes.
RQ5: cDFA embedding space is well-clustered. Our GATv2 cDFA encoders learn 32-dimensional embeddings, and, as shown in the previous answer, generalize well to other cDFA classes. To study the cDFA embeddings, we sample cDFAs from RAD, RA, RAR, reach, and parity task classes. For each class, we also introduce two variants: 2 2-conjunction collapse and 1-step advance. The former randomly selects two DFAs of cDFA and collapses them down to a single DFA, and the latter takes random stutterriing transition the cDFA. We study the embedding space in two different ways. One projects the embeddings down to 2D using t-SNE 33). The other computes pairwise cosine similarities and Fuclidean distances of the embeddings. See Appendix C.3 for the RGCN results.
The results are given in 6 first observe that modifications like 2-conjunction collapse and 1- step advance result in similar embeddings, showcasing the robustness provided by pre-training GATv2 on RAD. Moreover, due to the I-step advance operation, some cDFAs end up in their accepting states, and we see that accepting cDFAs are well-isolated inside the green region in Figure 6a. Similarly, we observe that parity samples are mapped very close to RAR samples (its parent class).
The same figure also demonstrates that GATv2 successfully separates different cDFA classes into distinct clusters. This separation is further confirmed by the cosine similarity (c.f. Figure (6)) and Fuclidean distance heat maps (c.f. Figure (b). On the other hand, both heat maps also show that the RAD cDFA class very rich in terms various DFAs contains since has both similar and different samples compared to other task classes. Notably, we see that the vast majority of RAD cDFA we sample are -odd----iittibttion for the other classes implying robust generalization.
Policies Trained RAD generalize well. Figure (blue) shows how well the policies trained on RAD generalize to other task distributions. Both frozen and non-frozen (see Appendix CC.) pre- pre-trained policies generalize well across the board with slight edge to frozen pre- pre-training. Notably, the policies suffers almost no performance loss on non-truncated RAD tasks even though was only trained on the truncated distribution. The policy sees the largest dip in satisfaction likelihood on
RQ6;
Satisfaction
1.0
0.5
RAD
1.1.1.
CRAR 1212
0.0
RA.
RA.1.2.11
RA.
1.2
1.1.3
RAR.1.2.1
RAR.1
1.
RAR.1
1.1.1.1...
1.2
P1.2
1.3
P1.
1.2
1.
1.1.2.1.
1.1.3.1.
GRAD
NTTCRAD
RALL
2.2
131.
GRA.
PRA.1.
PAA.1.0.11.
5.1.5
GRA.1.111.
CRAR.1.2.
1.10
1.AR133.11
1.2
GRAR.1
1.111
CRAR.1
CRAR.1.10.11
1.0.1.100.111
GRAR.I
1.1.1.11.111
121.2.1.2
CR.13
1.2
1.1.1.1
c..1
1P.1
cP.1111
1.100
c.1.2.112
113.13
RR.
1.1.55
1.1.1011111
cR.1
1.111110
Figure Pre-training the cDFA encoder lets policies trained Letterworld subclasses generalize
OOD, All policies were trained using frozen GATv2. See Appendix C,5 for training curves.

---

1.0
Satisfaction
0.5
RAD Pretraining
LTL Partially Ordered
LTL Avoidance
0.0
cP0.1.5.1.4
cPO.1.6.1.5
cPO.1.8.1.7
@PO.1.10.111
GPO.1.1.1.10
cAV.1.3.1.2
CAV.1.2.1.3
Figure 8: Satisfaction generalization capabilities on LTL tasks (from (88 of LTL2Action (38
policies vs policies trained on RAD cDFAs. See Appendix C.8 for training curves of policies.
longer compositional reach avoid (cRA) tasks. Interestingly, even very long cRA tasks of up to 10 symbols can be satisfied above 90% of the time, even though such long tasks put the satisfying state in cDFA past the depth that the message passing in our MPNNs reach. Overall, the performance of the non-pun pre--re--rre traitrained models (see Appendix [C4) follows similar (albeit dramatically worse) non-pre-trainee trend as the pre-trained models. They do see some success in the easier task classes such as reach and parity but perform poorly in more difficult task classes that contain rejecting sink states. Our generalization experiments comparing GATv2 to RGCN show that even though RGCN performs comparably, GATv2 outperforms in all cases (see Appendix 6..6.
Figure 7 shows that RAD pre-trainn gre-tranning allows policies trained in Letterworld to zero-shot generalize far out of distribution. If you take RAD pre-trained cDFA encoder and train policy on some small subclass 1cRA.1.1.1.5 and CRAR.1.2.1222 their class and
the policies can still handle much longer tasks within tasks outside of their class. In the case of cRA.1.1.115. the training of the policy module never gets to see a multistage task, only multiple conjunctions, yet it's able to satisfy tasks from the full RAD distribution 90% of the time.
We also compare against policies trained using I.TL syntax embeddings pendix C.8 shows training curves for these policies where pre-training was performed similar to RAD pre-training except only on the specialized class that randomly samples between 10.1.5.1.4 and AV.1.3.1.2 (task classes from (38). Figure 8 shows how well these policies and our RAD pre-trained policy generalize in the Letterworld to harder version of PO and AV. The results show that our method generalizes well across all tasks. Furthermore, in some cases, it outperforms the LTL policy the task is specifically trained on, e.g., even though the LTL policy shown by the green bar is trained on 1.,.1.3.1.2, our method outperforms it. Similarly, observe that although specifically trained on cPO. 1.5.1.4 tasks, it achieves 100% accuracy just like the LTL policy that is specifically trained this task class. In addition to all of the earlier generalization results, this figure shows that RAD pre-training generalizes to these out of distribution tasks just as well as the policies from 38 though it is not specifically trained these tasks.
38
Figure 21 Ap-
method was not
6 Conclusion
We introduced compositional deterministic finite automata (cDFA) expressive and robust goal representation for temporal tasks in goal-conditioned reinforcement learning Addressing the limitations of hierarchical approaches and the challenge of extending goal-conditioned RL to non-Markovian tasks, we proposed using cDFAs to leverage formal semantics, accessibility, and expressivity. By employing graph attention networks v2) construct embeddings for cDFA tasks and conditioning the RL policy on these representations, our method encourages the policy take the entire temporal task into account during deciision-mkinge Additionally, we introduced reach-avoid derived (RAD) cDFAs to enable the learning of rich task embeddings and policies that generalize unseen task classes. Our experiments show that pre-training strong zero-shot generalization and robustness. Using cDFAs to encode temporal tasks enhances explainability and enables automated reasoning for interpretable and safe Al systems.
RAD cDFAs provides
6.1 Limitations. A limitation of this work is the assumption of labeling function mapping MDP states to the task alphabet. Also, further research is needed to understand how cDFA-encoders learn to represent tasks and how much further their generalization capabilities can be pushed.
10

---

Acknowledgments and Disclosure of Funding
This work is partially supported by DARPA contracts FA8750-18-C-0101 (AA) and FA8750-23-C. 0080 (ANSR), by Nissan and Toyota under the iCyPhy Center, and by C3DTI Niklas Lauffer is supported by an NSF graduate research fellowship.
References
[1] Derya Aksaray, Austin Jones, Zhaodan Kong, Mac Schwager, and Calin Belta. Q-learning for robust satisfaction of signal temporal logic specifications. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 6565-6570. IEFF, 2016.
[2] Rajeey Alur, Suguman Bansal, Osbert Bastani, and Kishor Jothimurugan. A framework for transforming specifications in reinforcement learning. Principles of Systems Design: Essays Dedicated to Thomas A. Henzinger on the Occasion of His 60th Birthday, pages 604-624. Springer, 2022.
[3] Rajeev Alur, Osbert Bastani, Kishor Jothimurugan, Mateo Perez, Fabio Somenzi, and Ashutosh Trivedi. Policy synthesis and reinforcement learning for discounted Itl. In International Conference on Computer Aided Verificution, pages 415-435, Springer, 2023.
[4] Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In International conference machine learning, pages 166-175. PMLR, 2017.
[5] Marcin Andrychowicz. Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
[6] Dana Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87-
106, 1987.
[7] Dzmitry Bahdanau, Felix Hill, Leike, Edward Hughes, Arian Hosseini, Pushmeet Kohli, and Edward Grefenstette. Learning to understand goal specifications by modelling reward. arXiv preprint 1806.0006 2018
[8] Alper Kamil Bozkurt, Yu Wang. Michael M Zavlanos, and Miroslav Pajic. Control synthesis from linear temporal logic specifications using model-free reinforcement learning. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 10349-10355.. IEEE, 2020.
[9] Shaked Brody, Uri Alon, and Eran Yahav, How attentive are graph attention networks? arXiv preprint arXiv: 2021.
[10] Mingyu Cai, Shaoping Xiao, Zhijun Li, and Zhen Kan. Optimal probabilistic motion planning with potential infeasible Itl constraints. IEEE transactions on automatic control, 68(1):00--316,
2021.
[11] Alberto Camacho, Meghyn Bienvenu, and Sheila A Mcllraith. Finite Itl synthesis with environ- ment assumptions and quality measures. In Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, 2018.
[12] Alberto Camacho, Rodrigo Toro Icarte, Toryn Q Klassen, Richard Anthony Valenzano, and Sheila A Mcllraith. Ltl and beyond: Formal languages for reward function specification in reinforcement learning. In IJCAI, volume 19, pages 6065-6073, 2019.
[13] Xuchu Ding, Stephen Smith, Calin Belta, and Daniela Rus. Optimal control of markov decision processes with linear temporal logic constraints. IEEE Transactions on Automatic Control, 59)5: 1257, 2014.
[14] Jie and Ufuk Topcu. Probably approximately correct mdp learning and control with temporal logic constraints. arXiv preprint 1:Xx:11444.777.. 2014.

---

[15] E Mark Gold. Language identification in the limit. Information and control, 1065):447-474, 1967.
[16] Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate. Deep reinforcement learning with temporal logics. In Formal Modeling and Analysis of Timed Systems: 18th International Conference, FORMATS 2020, Vienna, Austria, September 1-3, 2020, Proceedings 18, pages 1-22. Springer, 2020.
[17] Marijn Heule and Sicco Verwer. Exact DFA identification using SAT solvers. ICGI, volume 6339 of Lecture Notes in Computer Science, pages 66-79. Springer, 2010.
[18] John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Theory of machines and computations, pages 189-196. Elsevier, 1971.
[19] John E. Hoperoft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison- Addison-Wesley. 1979.
[20] Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A Mcllraith. Reward machines:
Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73: 13:173-208 2022.
[21] Yiding Jiang, Shixiang Shane Gu, Kevin P Murphy, and Chelsea Finn. Language as an abstraction for hierarchical deep reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
[22] Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. Advances in Neural Information Processing Systems, 32, 2019.
[23] Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur. Compositional reinforcement learning from logical specifications. Advances in Neural Information Processing Systems,
2021.
[24] Niklas Lauffer, Beyazit Yalcinkaya, Marcell Vazquez-Chanlatee Ameesh Shah, and Sanjit A Se- shia. Learning deterministic finite automata decompositions from examples and demonstrations. In Conference on Formal MEthods in Computer-Aided Design-FMCAD 2022, page 325, 2022.
[25] Xiao Li, Cristian-Ioan Vasile, and Calin Belta. Reinforcement learning with temporal logic rewards. In 2017 IEEF/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3834-3839. IEEE, 2017.
[26] Jelena Luketina, Nantas Nardelli, Gregory Farquhar, Jakob Foerster, Jacob Andreas, Edward Grefenstette, Shimon Whiteson, and Tim Rocktäschel. A survey of reinforcement learning informed by natural language. arXiv preprint arXiv: /906.03926. 2019.
[27] José Oncina and Pedro Garcia. Inferring regular languages in polynomial updated time. In Pattern recognition and image analysis: selected papers from the IVth Spanish Symposium, pages 49-61. World Scientific, 1992.
[28] Rajesh Parekh and Vasant Honavar. Learning dfa from simple examples. Machine Learning. 44:9-35, 2001.
[29] Mateo Perez, Fabio Somenzi, and Ashutosh Trivedi. A pac learning algorithm for Itl and omega- regular objectives mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 21510-21517, 2024.
[30] Wenjie Qiu, Wensen Mao, and He Zhu. Instructing goal-conditioned reinforcement learning agents with temporal logic objectives. Advances in Neural Information Processing Systems, 36, 2024.
[31] Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration deep rein- forcement learning, arXiv preprint arXiv: 7(1:2, 2019.
12

---

[32] Dorsa Sadigh, Eric S Kim, Samuel Coogan, S Shankar Sastry, and Sanjit A Seshia. A learning based approach to control synthesis of markov decision processes for linear temporal logic specifications. In 53rd IEEE Conference Decision and Control, pages 1091-1096. IEFE, 2014.
[33] Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function ap- proximators. In International conference machine learning, pages 1312-1320. PMLR, 2015.
[34] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The semantic web: 15th international conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, proceedings 15, pages 193-607. Springer, 2018.
[35] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:170700344/ 2017.
[36] Ameesh Shah, Cameron Voloshin, Chenxi Yang, Abhinav Verma, Swarat Chaudhuri, and Sanjit A Seshia Deep policy optimization with temporal logic constraints. arXiv preprint arXiv:2404.11578, 2024.
[37] Sumedh Sontakke, Jesse Zhang, Séb Amoll, Karl Pertsch, Erdem BIyIk, Dorsa Sadigh, Chelsea Finn, and Laurent Itti. Roboclip: One demonstration is enough to learn robot policies. Advances in Neural Information Processing Systems, 36, 2024.
[38] Pashootan Vaezipoor, Andrew C Li, Rodrigo Toro Iearte, and Sheila A Mcilraith. Ld2action: Generalizing Itl instructions for multi-task rl. In International Conference on Machine Learning, pages 10497-10508. PMLR, 2021.
[39] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, (11)), 2008.
[40] Moshe Y Vardi. From church and prior to psl. In 25 Years of Model Checking: History, Achievements, Perspectives, pages 150-171. Springer, 2008.
[41] Marcell Vazquez-Chanlatte Karim Elmaaroufi, Stefan Witwicki, and Sanjit A Seshia. L'Im: Learning automata from examples using natural language oracles. arXiv preprint arXiv:2402.07051, 2024.
[42] Marcell Vazquez-Chanlatte, Ameesh Shah, Gil Lederman, and Sanjit A Seshia. Demonstration informed specification search. CORR, vol. 1as/2112.10800) 2021.
[43] Marcell Jose Vazquez-Chankee Chanlatte. Specifications from Demonstrations: Learning, Teaching, and Control. University of California, Berkeley, 2022.
[44] Cameron Voloshin, Hoang Le, Swarat Chaudhuri, and Yisong Yue. Policy optimization with linear temporal logic constraints. Advances in Neural Information Processing Systems, 17690 17702, 2022.
[45] Wojeiech Wieczorek. Grammatical Inference. Springer, 2017.
[46] Eric M Wolff, Ufuk Topcu, and Richard M Murray. Robust control of uncertain markov decision processes with temporal logic specifications. In 2012 IEEE 51st IEEE Conference on decision and control (CDC), pages 3372-3379. IEEE, 2012.
[47] Beyazit Yalcinkaya, Niklas Lauffer, Marcell Vazquez-Chanlatte, and Sanjit Seshia. Automata conditioned reinforcement learning with experience replay. In NeurIPS 2023 Workshop Conditoond Reinforcement Learning, 2023.
[48] Cambridge Yang, Michael Littman, and Michael Carbin. On the (in) tractability of reinforcement learning for Itl objectives. arXiv preprint arXiv:2 a1X1v:2111.12679 2021.
13

---

A Details of cDFA Featurization
To construct the featurization of a cDFA C, we first build individual graph featurizations for each DFA in the composition and then combine them single featurization for C, For each Ar Ct. we construct a directed graph G.A, = (VA,, E PAA)). where es E VA. re the states of Ar. Cvn (v, u) EA, represents the transitions of At. and PA. EA, + 2 maps each edge enw to set of symbols in A, 's alphabet, denoting different symbols triggering a transition from v to u. Using the graph representation GA., we construct the DFA featurization 9A. = (V EA hA.).
The sketch of the iterative construction of GA, is given in the following paragraph.
Initially, GA, has all the nodes of GA.. and it does not have any edges. For each Evu (r,u) u) E EAc. add new node eu to V.A. and two new edges to A.-- one from to the new node C.u and another one from evu u. Then, add self-loop edges for each node. Once G constructed this way, we reverse its edges to ensure that message passing transmits information to the initial state of the DFA. To include the details of individual nodes, each E VA, is associated with an input node feature A, (v). For VA A, (v) indicates whether v is the initial, an accepting, or a rejecting state. For each Gvu E V.. \. VA. A. (Reu) has one-hot positional encodings of each symbol in PA, (Rew).
Once all featurizations are constructed for each A, E C₁, we construct the composition' 's featurization Gc, = (Vc,, Ee, he, It is constructed by taking the union of all G., for each A, E C. adding an "AND" node VAND to the graph, and including new edges from the nodes corresponding to the initial states of all A, C. to VAND- Notice that taking this union is trivial since all nodes and edges of a DFA in the composition are unique. Through one-hot encoding
unique index in the feature vector be, (UAnd) of VAND, the "AND" node is encoded different kind of node that does not share any features with other nodes in the graph, making distinguished compared to nodes representing DFA states and transitions. Figure 2 shows the featurization of the cDFA in Figure] 1
14

---

B RAD cDFA Sampler Algorithm
Algorithm|
T shows the pseudocode for RAD cDFA sampling.
Algorithm RAD cDFA Sampler
Require: Geometric distribution parameters Pn. and pk and maximum number of mutations m
1: n (eometric(p.)
2: C = 0
3: for + to do
4:
Geometric(pps)
5: A 4 +Sample reach-avoid DFA with k 2 states by sampling a reach and an avoid symbol
uniformly from the alphabet for each state and adding these random transitions; for other symbols, add a stuttering transition with probability 0.9, or, make it reach or avoid with equal probability
6: for < vn do
7:
A' A
8:
Mutate A' by sampling a state pair s') and a symbol a and adding s S Make A''s accepting state sink by removing its out transitions and minimize A' A' is not trivially accepting then A + AA'
9:
10:
11:
C CU {A}
12:
Return C
In the experiments, we bounded the size of sampled cDFAs using truncated geometric distributions for n and k with upper bounds and 10, respectively, and l was fixed per rollout enviromment. Using multiple environments with different sampler instantiations, combined with mutations applied to the sampled DFAs, allowed policies to encounter a diverse range of DFAs of varying sizes during training.
15

---

C
Results
C.1 Pretraining learning curves: GATv2 vs RGCN. Figure 9 presents the learning curves for pre-training of GATv2 and RGCN on RAD cDFAs in dummy MDP. The figure illustrates that GATv2 converges faster than RGCN, potentially highlighting the benefits of the attention mechanism.
GAT
RGCN
1.0
1.0
Discounted return
Discounted return
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
-0.2
00.2
2
6
10
2
8
10
Frames (millions)
Frames (millions)
Pretraining
Figure 9: Learning curves for pre-training RAD cDFAs in the dummy MDP.
16

---

C.2 Generalization of pre-trained cDFA embeddings: GATv2 vs RGCN. Figure 10 presents the generalization experiment results in the dummy MDP. It shows that pre-trained GATVZ consistently outperforms RGCN with almost 100% accuracy in most cases. It also learns to solve the dummy MDP with less steps compared to RGCN. Overall, we observe that pre-training on RAD cDFAs provides good generalization to other cDFA task classes for both GATv2 and RGCN.
Satisfaction
1.0
Steps
0.5
GATV2
RGCN
0.0
RA.1.3.1.3
RAR.1.3.2
1.R.1.3.1..3
P.1.311.3
R11.3.1.3
CRAD
NT-CRAD
GRA.13.1.
GRA.1.....
P.A.11.
G.A.I.1...
GRAR.13.13
GRAR.15..1
P11111
GR..3.13.
GR.15.1..5
dR.1.0.111
cR.11.11110
CRAR.
Figure Generalization results GATv2 and RGCN pre-trained on RAD cDFAs, where satisfaction likelihood (left) and step count (right) shown by the solid lines and by cross-hatching, respectively.
17

---

C.3 Embedding space analysis: GATv2 vs RGCN. Figure 11 presents the embedding space analysis results for both GATv2 and RGCN. Results show that RGCN demonstrates competence in effectively separating different classes, albeit with certain limitations. While it succeeds in distinguishing reach from other classes, struggles to differentiate RA tasks from parity and RAR. Even though parity and RAR cDFAs share structural similarities with RA cDFAs. this lack of separation is concerning as there a semantic difference between these task classes-RA cDFAs have rejecting states but parity and RAR cDFAs do not. However, it still successfully clusters cDFAs that are 2-conjunction collapsed and 1-step advanced while also isolating accepting ones in the green region shown in Figure ITd. illustrating the robustness provided by pre-training RAD cDFAs.
Another point to note is the scales of the Euclidean distance heat maps given in Figure Ti- and Figure TTF The distance scale for RGCN is from 0 to 1.5 whereas the scale for GATv2 is from 0 to 3. Moreover, we see darker colors Figure 1. suggesting that GATv2 captures semantic nuances by effectively leveraging the embedding space for robust representations of cDFAs. The analysis results suggest that GATv2 learns a richer representation of the cDFA embedding space, likely due to its attention mechanism, which enables it to attend to relevant features and relationships within the data.
Reach-Avoid Derived
Reach-Avoid with Redemption
2- 2-Conjunction Collapse
Reach-Avoid Reach
Parity
1-Step Advance
No Op
1-Step Advance Leading Accept
0.0
0.5
1.5
1.5
2.5
2.5
3.0
[=] GATv2 2-D L-SNE
(b) GATv2 Cosine similarity heat map
(c) GATV2 Euclidean distance heat
0.6
0.7
0.3
0.9
1.0
2.0
ROCN 1-SNE
(6) RGCN
Cosine similarity map
(0 EEclidean heat map
Figure 11: Visualizations of the embeddings generated by GATv2 and RGCN pre-trained on RAD cD- FAs. showing that the learned embedding space reflects the similarities between different task classes.
18

---

C.4 Generalization of policies: pre-trained vs not pre-trained. Figure 12 compares the gener- alization strengths of policies with not-pre-trained, pre-trained srraineddann-frozzen and pre-trained GATv2 cDFA encoders. It shows similar pattern to the learning curves given in Figure 5 Specifically, we see that the frozen one outperforms others while the pre-trained one performs comparably. However, we see that not-pre-trained one does not come close to the others, indicating that learning embedding spaces through pre-training is essential for good performance and generalization to different task classes. Figure 13 presents the number of steps taken in Letterworld to solve the task for the same experiment. We see a similar trend where without pre-training model needs to take a lot steps to end the episode (either successfully unsuccessfully). Both pre- trained models take significantly fewer steps while the frozen one solves the task fastest. Combining both figures, we see that the frozen version generalizes well while also learning to solve tasks faster.
Satisfaction
frozen
pretrain
no pretrain
1.0
0.5
0.0
RA.1.2.1
1.2.1.2
RA.1.3.1.3
RAR.1.2.11
RAR.1.3.1
P1
P1.3.1.
R.1.1.12
R11.1.133
GRAD
NT-CRAO
WAL22
111111111
1.111
224R111111
5 R
EEST
1.10 8'
RAR.1
CRAL
80
Figure 12: Effect of pre-training on satisfaction generalization capabilities in Letterworld.
Number of Steps
60
frozen
pretrain
no pretrain
40
20
RA.1.2.1.2
RA.1.3.1.33
1.2.1.2.1.2
R.R.1.3.1.3
P12212
P1.3.1.3
R1.2.11
R.1.3.1.3
RRAD
NT-RAD
GR111.1
GRA.13.11.
GRA.1.5.1.
PA.11101111
GRA.1.1...0.
GRAR.122112
1...133.113
GRAR.155.1.5
11..1110.1111
1.R.11111111
@21.2.1.2
021.3.1.3
011.513
11111.11
11111
G.121112
c..1333..
c..15.1..5
GR.1.10.111
cR.1.111110
RA
RAR.
RAR.1
Figure 13: Effect of pre-training number of steps generalization capabilities in Letterworld.
19

---

C,5 Training curves and steps generalization for other task classes We first present the training curves for RA.1.1.1.5 and RAR.1.2.1. using RAD pre-trained cDFA encoders. Figure 14 shows that policies trained on RAD and RAR. 1.2.1.2.1 converge relatively faster than the one trained on R.A..1.1.5. Notice that R.A.II.1.55 samples cDFAs with more than DFAs with high probability (since the number of conjunctions sampled uniformly at random from the given interval) whereas the probability sampling such big compositions is lower in RAD (as it sampled from a geometric distribution). Thus, the figure indicates that it is relatively harder to learn big conjunctions.
In Figure 7 we shared the satisfaction generalization results for these policies, testing how well these policies trained on specialized task distributions generalize to other task distributions. Here, we provide the number of steps taken to finish the episode during the generalization experiments in Figure [5] Observe that training the policy on RAD cDFAs results in shorter episodes. However, is still worth noting that other policies perform comparably and provide good generalization on unseen tasks.
1.0
Discounted return
0.8
0.6
0.4
0.2
0.0
2
7
10
12
15
17
20
Frames (millions)
RAD
ReachAvoid 1
ReachavvoidRedempttonn_
1_2_1_2
Figure 14: Training curves for RA and RAR policies with RAD-pre-trained GATv2 in Letterworld.
Number of Steps
60
RAD
cRA.1.1.1.5
cRAR.1.2.1.2
40
0
RA.1. RA.1.2.11
RA 9A.1.3.1
RAR.1
1.
RAR 1.3.1.311
R1
.3
12
P.1 3.1.3.3
R1 2.1.2.2 2
3
R.1 1.3
RRAD
NT-CRAD
CRA.1 1.2.2.1 1.
R4A
1.3
GRA.1.10
CRA
1.5
GRA.111.1
1.5
10.1
GRAR.1
1.1.1.10
GRAR.1.3.
GRAR.1.5
1.AR.1.10
CRAR.1
5.1.5
GRAR.1
10.11.111
111.1111111
CP112211
1.11
PP.1.311
12
1.3
PP.
1.115
11.51.5
1.5
10.1
c.1.2211..
10
1.2
GR.
G.1.3311.
R.1.5
cR.1.10.1..
CR cR.1.1.1.110
Figure 15: Number of steps generalization comparison between policies trained on RAD, R.A11..1.5
and RAR. 1.2.1.2.1.
20

---

C.6 Generalization of pre-trained policies: GATv2 vs RGCN. Figure 16 present the results. compares policies with frozen and pre-trained GNNs (both GATv2 and RGCN). In line with the training curves, we can see that GATv2 outperforms RGCN across the board, with the most significant differences on harder task classes with many symbols or many conjunctions. Figure 17 shows the number of steps taken in the same experiments, indicating that GATv2 also learns to complete the tasks with fewer steps compared to RGCN. The results highlight the superior performance of GATv2.
Satisfaction
1.
0.5
GATV2
RGCN
0.0
1.3
P1.Z.122
R1.3.1.3
R.1.2.1.
R.1.1.13.
GRAD
NT-CRAD
0A1.221122
0A1.1.1113
GRA.1
GRA1110.111
GRA.1.111110
GRA
CRAR
CRAR
0PAR1110.11
GRAR1111.1.
0P11.21.22
dP.1.31..3
d21.5.1.5
021.10.111
0P11111110
dR.1.211.2
02.1.311.3
cR.15.1..5
CR.1.10.111
cR.11111100
R1.3
RA
RA
RAR
RAR
Figure 16: Satisfaction generalization capabilities of policies trained on RAD cDFAs with frozen and
pre-trained cDFA encoders in Letterworld, comparing GATv2 and RGCN.
Number of Steps
40
GATV2
RGCN
20
1.1
A.R.1.311.
1.1.1
R133.1
1.1.3
R12.1.
R13.333
RRAD
NF-CRD
GR1.12222..
CRA 1.1.131111
CRA GRA.1.5.1
0A1.1110.11.
0RA11.1.11
CRAR112122
1AAR13113
1RAR1155
11..11001111
1RAR
1111.00
cP.12.1.2
cP.13.1..
cP.15.1..5
@P1.10.111
cP111.110
cR.1.211.2
GR.1.311..
cR.15511.
08.1100.111
cR.1111111
RA.1.22.
R1
RA
RAR
RAR
GRA
CRAR
CRAR
Figure 17: Number of steps generalization capabilities of policies trained on RAD cDFAs with frozen
and pre-trained cDFA encoders in Letterworld, comparing GATv2 and RGCN.
21

---

C.7 Generalization of pre-trained policies in continuous domains. Figure 18 shows the general- ization results for a policy (with a frozen and pre-trained GATv2) trained on RAD DFAs in Zones. The results show that our method can generalize to cDFAs with up to 10 DFAs in the composition as long as each DFA's task length is relatively short. We see that it does not perform as well in tasks with length 5 and more. This is probably due to the fact that control and navigation are much harder in continuous domains compared to discrete ones. Therefore, the low accuracies we are seeing for tasks with more length might be due to timeouts. It is worth noting that the policies can generalize up to 10 conjunctions in a cDFA, which is completely out of distribution for the policy. Overall, the results show that training on RAD DFAs provide zero-shot generalization in continuous domains as well.
Satisfaction
10
0.5
0.0
RA.1.2.1.2
RA.
1A.1.3.112.
RAR.1.2.1
1.R.1.2.11..
RAR.1 1.R.1.3.11.
1.
P11221.2
P1 P1.3.1.
1.2
R.1.2.1.2
R.1.3.1
CRAD
NT-cRAD
RRA.2.
CRA.1. G.A.1.11..3
CRA
R.A.1..I...
CRA.1
GRA.1.10.1..
GRA.1.1.111
C.AR.1...12
1.10
CRAR.1.3..
CRAR.1
CRAR.1.10.1.
CRAR.1
1.111...1.
CRAR.
1.
1.1.1.
1.10
PP.122111
1.1.3.11.3
GP cR11551.5
1P1.00111
0.11.11111
CR.122.112
CR.
0R.13.11
CR.
0.115.1.5
CR.1 CR.1.10.1.
CR cR.1.1.1.11
Figure 18: Satisfaction generalization results of policies trained on RAD cDFAs with frozen and pre-trained GATv2 cDFA encoders in the Zones environment (continuous domain).
Figure shows the number of steps taken to complete the episodes in the same experiment. We see that when the policy satisfies task class with high probability, it can also complete it with fewer steps. On the other hand, in almost all cases where it could not satisfy the task with high probability, it also took more steps in those episodes, suggesting that the policy might have timed out.
Num. of Steps
1000
500
RA.1.2.1. 1.2
RA.1.3 1A.1.3.1..3
RAR.1.21 1.R.1.2.11.
RAR. 1.3.1.11
1.2
3.3
P1.2.1.2
R1.31 1.3.1.3
R1 R11.2.12 1.2
R.1.1.133
CRAD
NT-CRAD
-RA.1.2.1.3
CRA.1. GRA.1.311.
1.1.1.5.11.5
1.11
1.110
GRAR.1.3.113
CRAR.1.5.1
3.3
CRAR.1.10.1.
151.1.5
CRAR.1.1.1.1.
1...1.1.11.1
1.1..1.1.1100
1.1.00
cP.1.2.1.2
3......1.3
5..15.11.5
0P1.10.111
cP.1.111.11
cR.12211.2
cR.1.3.1.
cR.155.1.5
CR.1.10.1
12.1101..11
1.111111.110
1.11
GRA.1.
CRA.
CRA
CP.
CR.1
Figure 19: Number of steps generalization results of policies trained on RAD cDFAs with frozen and
pre-trained GATv2 cDFA encoders in the Zones environment (continuous domain).
22

---

C.8 Generalization of pre-trained policies: RAD cDFAs vs LTL2Action. To compare our approach to the closest work the literature, we design an experiment with LTL2Action [38] Recall that one of our main contributions is our RAD pre-training procedure that provides generalization across different tasks. Defining such a general L.TI task class not a trivial problem and contribution on this own. Moreover, the intuitions used to develop the RAD cDFA class are not applicable to LTL as it is not as easy to generate interesting and satisfiable LTL formulas. Therefore, for LTL2Action, we define a joint task distribution consisting of partially ordered and avoidance tasks, which are task classes defined in 338. To sample LTL tasks, we flip a coin and pick a samplers.
116
Disoouttdd
Prannes (millions)
Figure 20: Learning curve for pre-training LTL policies on the joint distribution of PO and AV.
Figure 20 present LTL2Action's learning curve for the pre-training of an RGCN in the joint LTL task distribution. As the figure shows, the model can easily learn to distinguish these LTL tasks.
Eventually. 1.5.1.4
Until. Until.1.3.1. 1.3.1.2
Discounted return
Discountod return
0.75
0.6
0.50
0.4
0.00
2
10
12
15
17
20
10
12
15
17
20
Frames (millions)
Frames (millions)
No pretraining
Protraining
Pretraining (frozen)
Figure 21: Learning curves for training LTL policies on PO and AV LTL tasks.
We then take the pre-trained RGCN and use it to train policy that is exclusively trained these task classes, i.c., partially ordered or avoidance LTL tasks. Figure 21 presents the learning curves for this training. The figure shows that if we let the RGCN get gradient updates during training, then pre-training does not help as much as freezing the network. We saw a similar behavior for RGCN in Figure 5] which further justifies choice of using network with attention mechanism. Furthermore, in (38. authors show that pre-training on specific task classes helps training even when
of
let the RGCN continue getting gradient updates. Combining these results from (38] with what we are seeing on Figure 21 suggests that when pre-trained on rich classes with multiple distinct task patterns, RGCN need forgel about the other task classes it learned during pre-training and has focus its capacity on the specific task class it is being trained on. We do not see such gap in the learning curves when we let GATv2 get gradient updates, see Figure 5 suggesting that GATv2 does not suffer from the same issue as RGCN, and it learns more robust cDFA embeddings.
Number of Steps
60
RAD Pretraining
LTL Partially Ordered
LTL Avoidance
20
.P0.1.5.144
(PO.1.6.1.5
dPO.1.8.777
60.11.0.111
dF0.1.1.1110
CAV.1.3.1.2
CAV.1.2.1.3
Figure 22: Number of steps generalization capabilities of LTL policies RAD-cDFAs policies.
Figure 22 presents the number of steps taken for the generalization experiments, showing that in all cases our policy trained on RAD cDFAs perform comparably to the specialized LTL policies.
23

---

D Hyperparameters and Compute Usage
Both for the RGCN and GATv2 cDFA encoders, we use hidden dimension size 32 and perform message passing steps. Also, for GATv2, we use heads for the multi-head attention.
For both Letterworld and Zones, we implemented same actor and critic architectures. The actor network comprises three fully connected layers, each with 64 units and ReLU activations, while the critic network has three fully connected layers with 64, 64, and units, using a Tanh activation. For pretraining, simplified the actor and critic to single-layer models without hidden units, allowing the cDFA encoder to learn rich embedding space. For environments with discrete actions, the actor's output passed through log softmax and logit layer. In continuous action settings, used a Gaussian distribution, parameterizing the mean and standard deviation with two separate linear layers from the actor's output. To construct observation embeddings, for Letterworld, we employed 3-layer convolutional network with 16, 32, and 64 channels, 2x2 kernels, and stride of In Zones, 2-layer fully connected network with 128 units per layer and ReLU activations used.
Table shows the hyperparameters used for every training run in the experiments section. Each seed in the experiments section was as an individual Slurm job with access to 4 cores of an AMD EPYC 7763 running at 2.45GHz and access to at most 20gb of memory. RAD pre-training experiments took approximately 14 hours each for 10 million timesteps, policy training in Letterworld took approximately 55 hours (50 hours for the frozen GNN version) for 20 million timesteps, and policy training in Zones took approximately 120 hours (70 hours for the frozen GNN version).
Hyperparameter
Pretraining Env.
Letterworld Env.
Zones Env.
Learning rate
0.001
0.0003
0.0003
Batch size Number of epochs
1024
32
2048
2
4
10
Discount
0.9
0.94
0.998
Entropy Coefficient
0.01
0.01
0,003
GAB(A)
0.5
0.95
0.95
Clipping
0.1
0.2
0.2
R.Sprrp a
0.99
0.99
0,99
Max. grad. norm.
0.5
0.5
0.5
Value loss coef.
0.5
0,5
0.5
Table I: PPO pre-training and policy training hyperparameters.
24

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the introduction, we clearly list our contributions, and the experiments section, we list the research questions explore. We then relate these research questions and their answers to the listed contributions while discussing the experiment results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Throughout the paper and explicitly in the conclusion, clearly state the limitations of the work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
25

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: The paper does not include any theorems or proofs. But, we still give rigorous formalism mapping cDFA-cconitioned RI to the well-known goal-conditioned RL problem.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data provided or not)?
Answer: [Yes]
Justification: We provide all the information needed to reproduce the main experimental results. In the corresponding section, we define all the RL environments, all the task classes, the pretraining procedure. the training procedure, and the algorithms used in the experiments. We also provide all the hyperparameter values in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
26

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: In footnote the first page, include link the webpage of the project. This page includes all data and code with instructions to reproduce the experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ wttppssccpppbllc////cccccccpttpe
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all the training and test details in the main body the paper as well in the supplementary material included in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All plots in the paper report error bars whenever applicable. We also provide other appropriate information (e.g., number of seeds, sample size, etc.) about the statistical significance of the reported experimental results.
27

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All the details regarding computer resources given in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: : http:::////eurrtee wwwpeepp...ppppppcpppeeepppppeee hccppullic/tthhccccddee......
Answer: [Yes]
Justification: We confirm that the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
28

---

Answer: [Yes]
Justification: We discuss the societal impacts of our work in the context of explainable and interpretable Al systems.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
We clearly credit and cite all the original papers that produced the assets we used as baseline, benchmark, etc.
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
29

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaeed, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The RAD DFAs can be considered new asset as it is sampling distribution
over DFAs. Its complete definition given both the main body and the appendix.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper involves neither crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper involves neither crowdsourcing research with human subjects.
30

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
31


Reviews:
[{"review_id": "niwEdIk4dZ", "reviewer": "Reviewer_A6oy", "summary": "This paper considers the multi-task setting where each task is a temporal logic task specified by a conjunction of deterministic finite automata (cDFA). To address the sample efficiency and generalisation problems present in this setting, they propose a method for generating good cDFA embeddings which can then be used by a universal value function approximator to learn general policies. Precisely, they propose converting a given cDFA into a graph which can then be passed to a graphical neural network (GNN) like GATv2 to create a vector embedding of the task. Similarly to prior work that demonstrated the benefit of pretraining GNN embeddings on LTL tasks (LTL2Action), this paper also proposes the *reach avoid derived* DFA (RAD-DFA) task distribution to pretrain the GNN embeddings. They then demonstrate that using frozen pretrained embeddings leads to better performance than finetuning, and no pretraining leads to abysmal performance. Finally, they also demonstrate that their pretraining procedure leads to reasonable cDFA embeddings and help with generalisation.", "questions": "Please refer to the weaknesses above.", "limitations": "The authors have discussed some of the limitations. However, there seems to be several other ones. For example,\n\n- Just like *some* prior works, the paper assumes that all tasks are defined over a fixed set of given atomic propositions. If the set increases, everything needs to be retrained.\n- The paper demonstrates their approach only on DFAs with one atomic proposition per edge. It is unclear how it will behave when the DFA transitions are more complex (i.e. arbitrary Boolean expressions over the atomic propositions)?\n- The paper relies on UVFAs to learn general policies. Hence, it is likely that it can only generalise to tasks *similar* to those it is trained on, and not to tasks that are *significantly* out of distribution. The paper does not investigate when the model fails to generalise and why. That would have helped the reader have some justified intuition of what types of tasks are *significantly* out of distribution for function approximation to fail for proposed approach.\n\n\nI recommend the authors carefully think of the various significant limitations of their approach, such as the one I mentioned above, and explicitly state and discuss them in the paper.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "## Originality\n- This work combines three established directions of research, namely: temporal logic task specifications (in the form of DFAs specifically), goal conditioned RL (using UVFAs specifically), and graph neural networks (GATv2 specifically).\n- The intersection of these three subfields is of more recent interest and only just emerging in the literature. Thus, there is an element of originality in the specific manner in which they are combined in this work with the aim of improving sample efficiency and generalisation in RL. \n- Also the specific manner in which a GNN is pretrained to generate good DFA embeddings (by introducing the RAD pretraining task set) appears to be fairly new.\n\n## Quality and Clarity\n- The work provides mathematical formulations for the main concepts needed to understand the approach, which aid the quality of the work. \n- Assumptions, while not formally stated are mentioned too. \n- The explanation of the framework is also detailed and coherent which makes the contributions of this work more apparent.\n- The paper includes a number of Figures which are helpful, clear and in the case of Figure 1, aids the message of the work quite a lot.\n- The paper includes a number of experiments that illustrate the goal embeddings learned by the proposed approach, and the resulting sample efficiency and generalisation over specific task distributions.\n\n## Significance\n- Temporal logic instruction following is an important direction of work and has wide applications---for example in multitask, lifelong learning and safe RL. \n- So leveraging GCRL (with UVFAs) and pretrained GNN embeddings to improve sample efficiency and optimality---important issues in general in RL---for DFA specified tasks can be particularly impactful and widely adopted. In this sense, this work could guide future work and ideas.", "weaknesses": "# Major\n\n## Originality\n- Overall, this work is very similar to LTL2Action (Vaezipoor et al. 2021) and does not deviate particularly far from the work presented there beyond considering DFA specified tasks instead of LTL ones, which is just a choice of task specification language (regular/DFA vs LTL/BuchiAutomata). Also the paper claims that LTL2Action is limited to \"finite\" LTL (line 82). It is not clear what is meant by \"finite\" here. If it means finite trace, then that is incorrect. LTL2Action is applicable to any LTL specification.\n- In addition, relying only on a UVFA for sample efficiency and generalisation is a widely known idea that has also been explored in prior works. While the exact implementation here may be new (such as the specific way the goal/task embedding is obtained), the ideas are familiar from a function approximation front. \n- The paper introduces the cDFAs, but this does not seem novel since they don't seem meaningfully different from DFAs and the distinction does not seem relevant for the proposed approach.  Hence this just adds more notations and terminologies. Also, the footnote on page 2 says \"With negations and disjunctions omitted as straightforward extensions\". It is not clear how they are straightforward, unless cDFAs are indeed just DFAs as I mentioned previously.\n\n## Quality and clarity\n### Mathematical formulations\n- I found it very hard to fully understand the proposed framework and judge the soundness because there are a number of incorrect statements and missing information.\n- The MDP definition (Def 2.1) is wrong. An MDP is a five tuple M = (S,A,T,R,$\\gamma$) where $R$ is the reward function and  $\\gamma$ is the discount factor (optional when $\\gamma=1$). It is not a triple M = (S,A,T). The objective of goal-conditioned RL is not to maximize the probability of generating a path containing g (lines 127-128), but instead to maximise the value function (the expected cumulative rewards). \n- It is fine if the authors want to focus on the maximisation of the success probability, but then the paper needs to describe how that will be achieved in the RL setting defined.\n- The reward function and discount factor for the problem formulation are never defined. The only reward function mentioned in the mathematical formulations is the one used for pretraining the GNN. Since the experiments uses the same reward scheme for learning policies, I suggest the authors formally state that in their problem formulation. Additionally, Table 1 shows that the experiments use a discounting, meaning that the learned policies *do not* correspond to the maximisation of success probability.\n- The paper says that goals are defined in the augmented MDPs (line 164), but the DFA-conditioned policy uses the environment states and not the augmented ones (Def 3.1).   \n - The paper uses message-passing neural network (MPNN) (line 173) as a core factor in their approach, but never define nor describe what these are.\n- The paper proposes cDFAs as a novel goal-representation for temporal tasks in goal-conditioned RL. Beyond the fact that I am not convinced that they are meaningfully different from DFAs, the paper gives no theory nor conducts any experiment to demonstrate that they \"balance formal semantics, accessibility, and expressivity\" as claimed in their first contribution. In general, since the authors claim it as a main contribution of this work, they should justify why it is better than other representations like RMs, LTL, GTL, TLTL, SPECTRL, etc. I think such rigorous justifications are not needed if they did not claim it as a contribution of this work.   \n\n### Experiments\n- It is not clear why the main paper contains no experiment comparing with prior works. The only such experiment is left to the appendix, and only uses LTL2Action as baseline which is not state-of-the-art (there is also no sample-efficiency comparison). Without state-of-the-art baselines like [1] or [2] in the main paper, it is hard to tell how good the proposed approach is. Given that [2] drastically outperforms LTL2Action in their experiments in the same domains, this work does not look promising as it only shows similar performance to LTL2Action. \n- The paper claims that the proposed approach is applicable to any DFA, but the DFAs used for pretraining the goal encoder (Algorithm 1) and the ones used for the experiments (page 7) only have one atomic proposition per edge (e.g. $red$, $square$, etc). These are the simplest DFA transitions possible. In general the edge of a DFA is a Boolean expression over the atomic propositions (e.g. $red \\wedge \\neg square$). It is unclear if the approach generalises to more complex DFAs (where the edges/transitions can be arbitrary Boolean expressions).  \n- All the example DFAs used are generally not satisfiable in the environments considered since their states lack self-transitions (e.g. in Fig 1). Since all the task distributions used for the experiments are defined similarly, it is unclear why the results show high success rates on them (they should be generally unsolvable). This suggests that important details of the implementation of the approach for the experiments may be different from what has been described in the paper.\n- It is also unclear what the tasks sampled from the defined distributions look like. It would have helped if the authors included examples of the simplest and most complex DFAs sampled during training and during testing. \n- It is unclear why freezing the pretrained weights performs better than finetuning. This is counter-intuitive but is never explained in the paper.\n- Given how the performance of the proposed approach is heavily reliant on the goal embeddings obtained from pretraining (the performance is abysmal without it), it is concerning that the paper did not stress test it to understand when it fails and why. For example, what if the number of conjunctions goes up to 100 where each DFA has a task length that also goes up to 100 (relates to the temporal curse of dimensionality)? What if the DFA transitions are more complex, that is when they are arbitrary Boolean expressions over the atomic propositions (relates to the spatial curse of dimensionality)?\n\n## Significance\n- This work does not make a very large step forward from prior work (the addition of state-aware planning), but it is one. So I do not want to be overly pessimistic on the front of significance, but it is necessary to note that the contributions of this work are relatively incremental. If I understood the paper correctly, the only main contribution is the approach for pretraining a *good* goal (DFA) embedding. Additionally Figures 20-21 also only shows similar performance to non-state-of-the-art prior work (LTL2Action). \n- The absence of theory does not help. Theory guaranteeing generalisation and convergence to optimal policies (as claimed) under some reasonable assumptions would have helped. The lack of experiments comparing with state-of-the-art baselines like [1,2] also does not help.\n- Relying only on a UVFA for generalisation has clear limitations (e.g. in terms of the spatial and temporal curses of dimensionality present in temporal logic tasks), since no optimality and generalisation guarantees can be given even in finite MDPs (like grid-worlds). This is why the field has largely moved away from such approaches. More recent works such as [1,2] (and the large majority of prior works like [3,4]) break down the problem into a set of reach-avoid sub-tasks (goals), then use planning (or HRL) to determine how to sequence those goals (addressing the temporal curse). These works use UVFA for the sub-goal policies only when the goal space is sufficiently large. When the goal space isn't too large, such as in the letter grid-world, these methods can still learn and generalise without relying on a UVFA (by learning the policies/options for each goal independently).\n- This reliance on end-to-end function approximation for generalisation hurts the significance of this work.\n\n\n[1] Tasse, Geraud Nangue, et al. \"Skill Machines: Temporal Logic Skill Composition in Reinforcement Learning.\" The Twelfth International Conference on Learning Representations. (2024)\n\n[2] Qiu, Wenjie, Wensen Mao, and He Zhu. \"Instructing goal-conditioned reinforcement learning agents with temporal logic objectives.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[3] Araki, Brandon, et al. \"The logical options framework.\" International Conference on Machine Learning. PMLR, 2021.\n\n[4] Jason Xinyu Liu, Ankit Shah, Eric Rosen, George Konidaris, and Stefanie Tellex. Skill transfer for temporally-extended task specifications. arXiv preprint arXiv:2206.05096, 2022.\n\n# Minor\n\n- It is not clear what \"concept class\" means or how it is different from a \"task class\". Are they the same?\n- It is not clear what GATv2 in the caption of Figure 1 means. Please add in the caption that it is a GNN.\n- It is seems like \"task\" and \"goal\" are mean the same thing in this work (line 16), i.e. they mean a DFA. Is that correct? That wasn't clear. \n- Adding the cDFA in Fig 1 to Fig 2 will\n- There are a couple minor typos or writing mistakes. For example:\n - There are numerous places where shorthands like \"i.e.\" and \"e.g.\" are used (e.g. first paragraph of the introduction). It is not recommended in a formal writing. Please spell them out.\n - The sentence on Line 184 doesn't end.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_Thank you for the time and effort put into your review._\n\n### Regarding LTL2Action not being finite\nThe 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.**\nFor example the [corresponding line in the LTL2Action repo](https://github.com/LTL2Action/LTL2Actionblob/485cbc1055dc9fbfbba50350c85de11fc1730540/src/ltl_wrappers.py#L98) 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\nof 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](https://proceedings.mlr.press/v202/voloshin23a.html) 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.\n\n### DFAs vs cDFAs\nPlease see the global rebuttal for an explanation of extension to negations and disjunctions.\n\n### Comparison with GCRL-LTL\nAlthough 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\nand 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.\n\n### Having Boolean expressions on edges\nStandard 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.\n\n### Regarding self transitions\nAs 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\".\n\n### Why is freezing better?\nThis 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.\n\nHowever, as this is pure speculation, we have left such discussion out of the paper and think its an interesting avenue for future research.\n\n### Stress testing\nThe 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.\n\n### Comments on end-to-end function approximation\nWe 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](https://rt-sketch.github.io/), [language corrections](https://yay-robot.github.io/), and of course [language instruction](https://llarva24.github.io/).\n\nFinally, 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.\n\n### On exposition and definitions\nThank 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.\n\nFor 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.\n\nFinally, 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.\n\n- **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.\n- **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.", "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": "", "extra_scores": {}}, {"review_id": "Emy1dU6c7Q", "reviewer": "Reviewer_Ww4e", "summary": "This work focuses on goal-conditioning policies using DFAs. This leverages the ability of DFAs to be composed - in this case the work focuses on conjunction. Two main pieces are introduced in leverging DFAs: 1) a GATv2 model which provides task embeddings from the DFA, 2) pre-training of the GATv2 on Reach Avoid Derived compositional automata which trains the embeddings with a basis representation in terms of the RAD embeddings which can then be used to represent other DFA embeddings. Once the  DFA embeddings is obtained it is appended to the environment state space and used to train a policy. Experiments demonstrate the benefit of GATv2 over an alternative RGCN (when pre-training and not freezing the embeddings) and also demonstrate the benefit of pre-training the task embeddings, particularly when freezing the embeddings after.", "questions": "1. How would the results of the generalized agents with task embeddings compare to specialized agents?\n2. In Figure 4, why do the Zones results only have two models?\n3. At a high level, how would you extend the approach to incorporate general boolean combinations\n\nIf the authors could address my concerns with regard to the curse of dimensionality, and answer these questions I would likely advocate for acceptance.", "limitations": "Limitations are mentioned and I do not see any omissions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "# Originality\nThe use of DFAs and similar representations of tasks is a popular idea in RL at the moment. However, this work focuses on the use of the DFA within a longer pipeline to obtain the embeddings. This use appears novel as most works I am aware of tend to use fairly literal and inflexible representations of the DFAs or state machines. This work then also puts some interesting pieces together - DFAs for task representations, GATv2 to represent a graph, RAD pretraining. Overall this all supports the novelty of this work and I do believe this is a strength.\n\n# Quality\nThe aim and hypothesis of this work is clear. Each step of obtaining the task embedding is justified and validated with experiments. The ablation study does demonstrate the utility of both GATv2 and the pretraining from RAD tasks. Moreover the additional experiments and visualisations support the fact that GATv2 is learning to produce reusable and semantically meaningful task embeddings.\n\n# Clarity\nOverall the paper is well written, notation is used sparingly and intuitive. This is particularly useful as the combination of DFAs and MDPs can often become very notation heavy. I appreciate the effort placed in making this work clear. Images and visualization are also neat and clear and support understanding.\n\n# Significance\nEnabling generalization in RL, and specifically task generalization is an important problem. It has particular utility for enabling safe and adaptable RL agents. This work provides a new perspective and step towards this goal. I do think that this work would lead to future work and new ideas.", "weaknesses": "# Clarity\nFigure captions could elaborate more. As it stands they are vague and do not add any explanation or support understanding of the figure. Secondly, Section 3.1 is unclear due to the omission of an explanation for the DFA modifications. As a result it is unclear why any of these steps are needed, but this seems to be an important and early part of the pipeline. Thus, it leaves the entire pipeline feeling unclear or at least on an uneasy grounding.\n\n# Significance\nUnfortunately, I think the significance of this work may be its biggest weakness. Firstly, it is not clear to me that it is trivial to extend the findings on conjunctions will generalize to general boolean combinations as is mentioned in lines 144 and 145. Secondly, the curse of dimensionality which results from conjunctions of DFAs is never addressed or touched on. Perhaps the vector representation of task embedding does support generalization - and the visualizations would even support this - but it is not discussed. This is even more worrying when considering that a fixed dimension for the task embeddings is used. Thirdly, the experiments do support the answering of the research questions posed. However, the experiments do not compare to any other baselines from the literature, which makes it difficult to contextualize and build from this work. Finally, and I acknowledge that the authors point this out in the limitations section and so I will take this point lightly, but there is no insight into how the task embeddings support generalization. This does unfortunately limit the significance of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_Thank you for the time and effort put into your review._\n\n### Regarding Clarity of Sec. 3.1.\n\nWe 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:\n\n1. 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.\n2. 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.\n3. 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.\n4. 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.\n    \n### Curse of Dimensionality.\nBy 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.\n\n### Comparison with other baselines\nPlease see the baselines section of the meta-rebuttal. \nTo 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.\nThe key result is that our approach does indeed generalize better given the RAD pretraining.\n\n### Insights into how the task embeddings support generalization.\nWe 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.\n\n### How would the results of the generalized agents with task embeddings compare to specialized agents?\nIn 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.\n\n### In Figure 4, why do the Zones results only have two models?\nDue to time and compute.\nRunning 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. \n\n### At a high level, how would you extend the approach to incorporate general boolean combinations?\nPlease see the meta-rebuttal section on cDFA.", "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": "", "extra_scores": {}}, {"review_id": "9ua4bhP4aj", "reviewer": "Reviewer_bN73", "summary": "This paper extends the framework of goal-conditioned reinforcement learning to support temporally-extended goals specified as (compositions of) deterministic finite automata (cDFA), avoiding the limitations of state-based goals and the ambiguities of natural language specifications. The authors introduce a graph neural network architecture for embedding cDFAs to vectors via message passing. They then develop a pretraining distribution for learning cDFA embeddings, which is constructed by leveraging the insight that paths in a DFA correspond to a series of reach-avoid tasks, motivating a distribution of cDFAs that are derived from sequential reach-avoid DFAs. In experiments, the authors show that pretraining on this distribution produces generalizable embeddings that capture the structure of DFA space, while also enabling the training of generalizable cDFA-conditioned policies. The authors run these experiments on two labeled MDPs, Letterworld and Zones, showing that embeddings or policies trained on only RAD DFAs or other DFA subsets often achieve high goal satisfaction rates even when presented with cDFAs with longer task lengths and higher composition numbers. cDFA conditioned policies using a frozen cDFA embedder trained on the RAD distribution also lead to high satisfaction rates across the board in Letterworld, with reasonable strong performance in Zones (a harder continuous MDP).", "questions": "There were a couple of minor things I didn't fully grasp, which it'd be great to clarify:\n\n- When constructing/sampling a SRA DFA (e.g. RHS of Figure 3) how are reach or avoid transitions created? Is the reach transition always a transition to the accepting state? Or is it to a a state that eventually leads to an accepting state? Is it the case that there is a single long path to the accepting state? And is the avoid transition always to a single sink state? I couldn't fully understand this from Appendix B.\n\n- In Figure 4, in the panel for Zones, where is the (non-frozen) GATv2 pretraining line baseline? And am I right to say that the RGCN baseline was not trained for Zones?\n\n- For each MDP with its own labeling function and alphabet, do you basically to do the RAD pretraining phase for specifically that alphabet of symbols? Or is there hope of training a cDFA embedder that generalizes across different MDPs with different labeling functions and alphabets?", "limitations": "The authors have adequately discussed a number of limitations of their work. It would be good to also discuss the fact that interpretable specifications (in the form of cDFAs) do not immediately lead to verifiably safe behavior.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a very well-written and thorough paper that made for a pleasant and insightful read. Despite not working much with DFAs or GNNs, I found both the overall idea and the low-level details very easy to understand, because all key concepts are carefully but concisely explained, with figures that clearly illustrate what a cDFA is, how it can fed into a GNN, and what the structure of SRAs and RADs look like. The design of the RAD pretraining distribution was also very insightful, demonstrating careful thinking about what motifs ought to be repeated across a large class of DFAs (namely, reach-avoid tasks), and how that could be exploited to enable generalization. Experiments were very clearly laid out and thoroughly executed, covering a wide range of DFA classes to test generalizability, and demonstrating that the proposed method actually does lead to cDFA-conditioned policies that generalize quite well across the board.\n\nIn terms of motivation and impact, I think it's great that people are exploring more expressive and well-defined notions of goals in the context of goal-conditioned RL. While working with formal specifications is not very popular in machine learning these days, I think a strong paper like this one helps to elevate the profile of using such specifications to enable more interpretable and generalizable RL systems. As such, I think this paper could have a decently large impact within the fields of both goal-conditioned RL and people working on formal methods in RL / ML.", "weaknesses": "As the authors themselves note, probably the main weakness / limitation of work that relies on symbolic specifications like cDFAs or LTL formulae is that it requires MDPs with a labeling function. This limitation isn't insurmountable --- for e.g., it should be possible to use computer vision algorithms to segment and label states of the world from pixels -- but in the final version of the paper, I think it'd be good to discuss this a bit more, since it might help readers appreciate how work like this could be applicable without a oracle labeling function.\n\nAnother slight weakness of the paper is that most of the experiments focus on Letterworld, with weaker average performance in the more realistic environment of  Zones. This raises questions about how applicable the method will be to more realistic tasks. With the extra page in the final version, I think it'd be good to show images of both environments, and examples of harder cDFAs in those environments, just to illustrate how difficult it might be to solve those tasks. Otherwise it might be easy to write-off e.g. Letterworld as a toy domain even though with cDFAs the tasks can be quite long-horizon. It might also be good to say a bit bout how performance could be improved for harder tasks like Zones.\n\nFinally, I think one thing that bears discussing in the final version is how this framework might enable safety/correctness of the policy, not just interpretability of the specification. While it's no doubt a safety benefit to have more interpretable specifications that say exactly what correct behavior is, this on its own doesn't guarantee the resulting learned policies are safe. I wonder if the authors could say a bit more on this point, perhaps by connecting to work on formal verification of NNs, or by combining cDFA-conditioned RL with constrained planning methods, using the learned policy to accelerate provably safe planning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_Thank you for the time and effort put into your review._\n\n### Regarding the comment on the labeling function.\nWe 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.\n\n### Weaker performance in Zones.\nThe 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.\n\n### Safety/correctness guarantees\nThank 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](https://ojs.aaai.org/index.php/AAAI/article/view/26407).\n\n### How are reach or avoid transitions created\nConceptually, the reach/avoid transitions are indirectly constructed by first starting with a chain of N states and a failure state, FAIL:\n\n> $S_1 \\rightarrow S_2 \\rightarrow \\cdots \\rightarrow S_N$\n\nFor 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.\n\n### Question about Fig. 4.\nDue to time and compute. \nRunning 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. \n\n### Question on training a general cDFA embedder\nThank 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.\n\nOf 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.", "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": "", "extra_scores": {}}, {"review_id": "TdCzZOXLtB", "reviewer": "Reviewer_7HER", "summary": "This paper tackles Goal-conditioned Reinforcement Learning (RL) when used with Temporal Logic Objectives. The benefits of directly considering Deterministic Finite Automatons (DFAs) as the task definition leads to a new class of Compositional DFAs introduced that cover a conjunction of several tasks. These cDFAs can be encoded using a Graphical Neural Network that is pretrained on a novel task distribution (RAD). Experimental results show the approach generalizes to several task classes.", "questions": "1. Should the statement in L35 be better quantified or validated with references? \"DFAs represent all temporal tasks that become Markovian by augmenting the state-space\nwith finite memory”. Does this hold when Signal Temporal Logic (STL) is considered a temporal task language as well? \n2. Is Reference [7] a concurrent submission or a typo?\n3. In Figure 5, what are the black elements in the Legend? Why are they not present in the figures?\n4. What do the envelope colors in Figure 2 indicate? Does the encoding generalize to conjunctions of the predicates on edges (e.g., Red & Green)? Are these considered during pretraining?\n5. Defn. 4.1. could use some clarity. How is a random transition defined in a mutation? Is this simply changing the target node of a given transition to a random state in the DFA? What is being “minimized\" here?\n6. Minor grammatical error - Should DFA and DFA(s) be used interchangeably? I would think the following references to DFA should be changed to DFAs (L31, L33, L80, L85-87, and more)", "limitations": "The limits of cDFA encoding are not fully explored (mentioned).", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Compositional DFAs are a more general form of multi-task descriptions. The proposed method is a straightforward way to encode these objectives and solve them.\n- The range of task classes considered is extensive and covers a variety of problem settings.", "weaknesses": "- The approach follows the similar structure as LTL2Action [41] but replaces the LTL Module with a different GNN (GATv2) and considers cDFAs or compositions/conjunctions of DFAs. The modifications w.r.t. LTL2Action apart from this and the pre-training step over a new randomly sampled (RAD) task distribution are novel yet arguably incremental.\n- Baselines appear lacking which bring into question the merits of the approach. A direct comparison to LTL2Action [41] and GCRL-LTL [32] using the monolithic DFA of the cDFA in the experiment could be possible and if not, the reason should be justified.\n- The paper is at times hard to follow and overloaded with notations and conventions. Some improvements could be made in the description of RAD pre-training (see questions) and the task nomenclature 1.X.1.X in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "_Thank you for the time and effort put into your review._\n\n### Comparison to LTL2Action and GCRL-LTL.\nWe 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.\n\n### Comparison to GCRL-LTL\nIn 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.\n\n### Clarity, presentation, and notation\nThank you for the feedback.\nWe will make the necessary fixes pointed out by the reviewer and further simplify the presentation in the final version.\n\n### DFAs represent all temporal tasks that become Markovian by augmenting the state-space with finite memory\nThank you for bringing this up. We will clarify what this means in the final version\nas it is indeed confusing / ill-posed.\nHere, a task is taken to be a Boolean property of an episode: you either perform it or you don't.\nBy making a task Markovian we mean that the state of satisfaction can be determined\nby just looking at the current state, e.g., did you reach a goal state?\nImportantly, we are assuming that each state is labeled from a finite set.\nMechanically, one can then identify the DFA task from the transitions of\nthe finite states since the properties are only defined over the labels of the finite states. \n\n### Signal Temporal Logic (STL), finite memory, and DFAs\nThe short answer with STL is no. STL is not generally representable with finite memory.\nA 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.\nBut, per the earlier point, if the STL formula has a finite memory monitor,\nthen yes it can be encoded as a DFA.\nIn such cases, the DFA often corresponds to syntactic progression as seen in LTL2Action.\n\n### Is Reference [7] a concurrent submission or a typo?\"\nReference [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.\n### In Figure 5, what are the black elements in the Legend? Why are they not present in the figures?\nZooming into that figure will reveal that each point has a distinct shape representing the kind of operation applied to the sampled cDFAs. \nThese shapes correspond to the black elements in the legend. We will make this clearer in the final version.\n\n### What do the envelope colors in Figure 2 indicate?\n\nThose colors are just there to help track where the messages came from. We will make this clearer in the final version.\n\n### Does the encoding generalize to conjunctions of the predicates on edges (e.g., Red & Green)? Are these considered during pretraining?\"\nOur work does not treat symbolic relations on the edges, however we think it is an interesting\ndirection. Conjunctions may potentionally handled with a many hot encoding, but this is\npurely speculation.\n\n### Defn. 4.1. DFA Mutation\nConsider 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.\n### \"What is being “minimized” here?\"\nThe DFA is being minimized. Specifically, the number of states is being minimized.\nConceptually, this corresponds to merging states that are interchangable (have equivilent residual languages).\nThis results in a canonical representation that is irreducable.\nSee https://en.wikipedia.org/wiki/DFA_minimization for details.\n\n### Should DFA and DFA(s) be used interchangeably?\"\nThank you for pointing out this inconsistency. They are indeed not interchangable\nand we will correct these abbreviations in the final version.", "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": "", "extra_scores": {}}]

Author rebuttal:
_We'd like to thank the reviewers for their time and efforts.
Below, are common points we'd like to emphasize across all reviews._

## RAD Pretraining + Frozen Embeddings
First, we wanted to highlight what we consider the most important contributions of our work:

1. The RAD pretraining.
1. The frozen encoder and RAD embeddings.

Notably, RAD is a carefuly crafted task distribution
that exploits DFA specific structure to encourage zero-shot generalization to downstream tasks.
Reviewer bN73 put it well when they wrote:

> [RAD is designed from] what motifs ought to be repeated across a large class of DFAs (namely, reach-avoid tasks), and how that could be exploited to enable generalization. 

We believe that our generalization results (Figure 6 and Appendix C.2-C.8), training with frozen embeddings (Figure 4), and embedding visualizations (Figure 5 and C.3) speak to the usefulness and generality of RAD pretraining. *We see RAD pretraining as a building block for other applications.*

- **Multi-modal task descriptions:** One might consider combining multiple embeddings for control problems. For example using our RAD embeddings to specify a mission level task, preferences using natural language CLIP embeddings, and a grounding of atomic propositions/labels using [hand drawn sketchs](https://rt-sketch.github.io).
- **Task retrevial:** In the future, one might train a natural language to RAD embeddings network to enable vector database retrieval of tasks that a robot is pre-authorized to perform.


## Baselines
A common question raised by reviews (A6oy, 7HER) is about baselines. The only existing approach directly comparable to ours is LTL2Action, which we compare against in Appendix C.8. With the additional space, we will move this comparison to the main body of the paper.

Several other works (e.g., [1,2,3,4] from reviewer A6oy and GCRL-LTL also mentioned by 7HER) pursue a totally different technique for goal-conditioning with logical specifications. These works use a hierarchical framework: classical planning techniques (e.g. Dijkstra’s algorithm) are used to plan over an automaton (or automaton-like structure) and trained neural policies accomplish the individual steps in the plan. While these works can also be used for satisfying logical specifications over MDPs, they differ in two critical ways: 

1. They don't produce task embeddings. Our work is explicitly focused on generating useful task embeddings (see above for why), which we accomplish largely through RAD pretraining. 
2. Hierarchical planning techniques (including all of the papers mentioned above) are generally sub-optimal. Figure 1 in the attached pdf shows a gridworld demonstrating the problem with hierarchy. The robot's task is to first go to orange and then green. A hierarchical plan would first attempt to reach orange in the quickest way, which would be going to square (a). However, because hierarchical plans are unable to account for the entire task and the dynamics of the MDP, they don't realize that this now takes them further away from the second part of the task, reaching green.The situation can be made substantially worse if (i) the non-Markovian reasoning requires reasoning even further into the future and (ii) the dynamics of the MDP were somehow irreversible so that choosing the wrong orange square makes it _impossible_ to then reach the green square. It is easy to construct such traps for current hierarchical approaches. By using task embeddings (our work and LTL2Action), policies reason about the _full_ task, and thus could avoid such traps.

We will make these differences clearer in the final draft.

## Differences from LTL2Action

As noted in the paper and by several other reviewers, the mechanics of our approach take inspiration from LTL2Action.
Superficially, the main changes are the encoder (now based on GATv2) and the target representation (automata rather than logical sentences).

A key argument of the paper is that by focusing on DFA, we can exploit the fact that (i) solving a DFA ``just'' corresponds to finding a satisfying path and (ii) that subproblem can itself be represented as a DFA. This is fundamentally not the case with **declarative semantics** such as temporal logic which are naturally represented as syntax trees and require non-local reasoning (does satisying one part of the subtree effect the satisfaction of the other?) As the next section emphasizes, cDFA offer a middle ground and support the non-temporal syntatic structure of the LTL while allowing DFAs to handle the temporal relations.


## cDFAs.
The conjunctive composition (cDFAs) investigated in the paper joins the graphs of several DFAs into a single graph. This is done by adding an "AND" node that is connected to each DFA in the composition and avoids explicitly computing the composition of the DFAs (an exponential blow-up of the number of states). For example, given N DFAs each with M states, their conjunctive composition is a DFA with $O(M^N)$ many states whereas their cDFA representation (which does not compute the composition explicitly) has $O(M\cdot N)$ many states. The cDFA representation avoids *the exponential blow-up in the number of states caused by the explicit evaluation of the composition*; therefore, addresses the curse of dimensionality.

**Arbitrary DFA compositions.** One can express arbitrary Boolean combinations of DFAs in a cDFA representation, using a CNF tree. Extending conjunctive composition to arbitrary Boolean combinations follows from three observations:

1. Any Boolean formula can be expressed in the CNF format.
2. We can combine DFAs in a CNF tree, where the "AND" node would again be the root node, i.e., level 0, the disjunction nodes would be in level 1, and DFAs would be in the leaves.
3. DFAs are closed under negation, and the number of states stays constant when a DFA is negated, so negations can be directly applied to individual DFAs.

Meta-review: The paper proposes a method for goal-conditioned reinforcement learning using a collection of deterministic finite automata (cDFAs) to define temporally-extended tasks. It introduces a graph neural network to embed cDFAs into vectors and a pretraining procedure using a Reach Avoid Derived (RAD) task distribution. This pretraining improves the generalization and performance of policies by leveraging these embeddings. Experiments demonstrate that freezing the pretrained embeddings results in better performance and showcases generalisation to several task classes.

There was much discussion on the paper, in particular with the positioning of the proposed approach in relation to existing work (most notably LTL2Action). This was addressed to the satisfaction of the reviewers during the rebuttal phase. There are still some outstanding issues with the paper: more empirical evaluations comparing against GCRL-LTL and understanding the tradeoffs between this style of approach and one involving UVFAs only, would strengthen the paper, and there are still concerns about how the RAD pretrained embeddings degrade depending on the task distribution.

Despite these shortcomings, the reviewers generally agree on acceptance, and authors are encourage to incorporate additional experiments and suggestions as provided by the reviewers.
Decision: Accept (poster)