Research map / Reinforcement learning / Visual and representation RL
Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes conditioning goal-conditioned RL policies on compositions of DFAs (cDFAs) embedded by a GATv2 graph network, pre-trained on reach-avoid derived (RAD) DFAs for zero-shot generalization.
Problem
Goal-conditioned RL needs expressive, unambiguous representations of temporal (non-Markovian) tasks; target states and natural language are either limited to non-temporal tasks or ambiguous, and the space of DFAs is countably infinite with sparse binary rewards.
Approach
Represent temporal goals as conjunctions of DFAs embedded with a GATv2 encoder, pre-trained in a dummy MDP on RAD DFAs (mutations of sequential reach-avoid DFAs) so the frozen embedding generalizes zero-shot to other task classes and avoids the myopia of hierarchical planners.
Key results
- Frozen GATv2 pre-trained on RAD policies satisfy sampled RAD tasks over 95% of the time within 5 timesteps in Letterworld.
- Pre-trained GATv2 embeddings achieve roughly 90% to near 100% satisfaction across new cDFA task classes, generalizing to 10 DFAs in composition despite training max of 5.
- Policy trained on cRA.1.1.1.5 satisfies full RAD tasks about 90% of the time; without pre-training policies barely learn the tasks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Pre-train and freeze the cDFA encoder on RAD cDFAs | cDFA-conditioned policies · RAD cDFAs, Letterworld | task satisfaction rate | Helped |
| Pre-train the cDFA encoder on RAD cDFAs (ablation) | cDFA-conditioned policies · RAD cDFAs, Letterworld | task learning | Helped |
| Freeze the RAD-pretrained encoder rather than continue updating it (ablation) | RGCN cDFA-conditioned policy · RAD cDFAs, Letterworld | task performance | Helped |
| Use GATv2 rather than RGCN as the cDFA encoder | RAD-pretrained cDFA encoder · Unseen cDFA task classes, dummy DFA environment | accuracy | Helped |
| Use GATv2 rather than RGCN as the policy encoder | RAD-trained policies · Letterworld task generalization | task satisfaction | Helped |
| Use frozen rather than trainable RAD-pretrained GATv2 (ablation) | cDFA-conditioned policies · Letterworld task generalization | task satisfaction | Helped |
| Use RAD pretraining rather than no pretraining (ablation) | cDFA-conditioned policies · Unseen task classes, Letterworld | task satisfaction | Helped |
| Train on RAD cDFAs rather than a specialized subclass | cDFA-conditioned policy · Letterworld task generalization | episode length | Helped |
| Use GATv2 rather than RGCN | RAD-pretrained cDFA encoder · RAD cDFA pretraining | convergence speed | Helped |
| Train on longer cRA tasks | RAD-pretrained cDFA-conditioned policy · Letterworld | task satisfaction | Hurt |
| Use longer task lengths in Zones | RAD-trained cDFA-conditioned policy · Zones | task satisfaction | Hurt |
| Continue updating the pretrained RGCN during policy training rather than freeze it (ablation) | LTL2Action policy · Partially ordered and avoidance LTL tasks | task learning | Hurt |
Surprising findings
- Non-frozen pre-training performs significantly worse for RGCN than frozen, while freezing the GNN also trains about 20% faster.
- Policies trained on small cDFA subclasses zero-shot generalize to much longer tasks beyond the training class, despite the depth exceeding MPNN message passing range.
Limitations
- Assumes a labeling function mapping MDP states to the task alphabet.
- Unclear how cDFA encoders learn to represent tasks and how far generalization extends.
- Performance in continuous Zones domain drops for tasks of length 5 and more, likely due to timeouts.
Experimental setup
Datasets: RAD cDFA samples RA RAR reach parity PO and AV LTL tasks
Benchmarks: Letterworld Zones dummy MDP generalization
Metrics: satisfaction likelihood steps to completion t-SNE visualization cosine similarity Euclidean distance
Baselines: LTL2Action RGCN encoder no pretraining hierarchical approaches
Builds on: GATv2 LTL2Action proximal policy optimization relational graph convolutional network hindsight experience replay
Closest papers by meaning
- Zero-Shot Instruction Following in RL via Structured LTL Representations (NeurIPS 2026 · similarity 0.86)
- The Synergy of LLMs & RL Unlocks Offline Learning of Generalizable Language-Conditioned Policies with Low-fidelity Data (ICML 2025 · similarity 0.86)
- PcLast: Discovering Plannable Continuous Latent States (ICML 2024 · similarity 0.85)
- Reconciling Spatial and Temporal Abstractions for Goal Representation (ICLR 2024 · similarity 0.85)
- One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learning (NeurIPS 2025 · similarity 0.85)
- Skill Machines: Temporal Logic Skill Composition in Reinforcement Learning (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.