# Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning

arXiv: https://arxiv.org/abs/2411.00205 · HTML: https://mlsanity.com/paper/2411.00205/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 31 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [Interpretable and logic-guided RL](https://mlsanity.com/deeprl/interpretable-and-logic-guided-rl/)

## Builds on (most cited first, 25 of 25)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [A Survey of Reinforcement Learning Informed by Natural Language](https://mlsanity.com/paper/1906.03926/) (2019)
- [Language as an Abstraction for Hierarchical Deep Reinforcement Learning](https://mlsanity.com/paper/1906.07343/) (2019)
- [RoboCLIP: One Demonstration is Enough to Learn Robot Policies](https://mlsanity.com/paper/2310.07899/) (2023)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Learning to Understand Goal Specifications by Modelling Reward](https://mlsanity.com/paper/1806.01946/) (2018)
- [Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning](https://mlsanity.com/paper/1909.07299/) (2019)
- [LTL2Action: Generalizing LTL Instructions for Multi-Task RL](https://mlsanity.com/paper/2102.06858/) (2021)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [On the (In)Tractability of Reinforcement Learning for LTL Objectives](https://mlsanity.com/paper/2111.12679/) (2021)
- [Optimal Probabilistic Motion Planning with Potential Infeasible LTL Constraints](https://mlsanity.com/paper/2007.14325/) (2020)
- [Policy Synthesis and Reinforcement Learning for Discounted LTL](https://mlsanity.com/paper/2305.17115/) (2023)
- [A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs](https://mlsanity.com/paper/2310.12248/) (2023)
- [Finite LTL Synthesis with Environment Assumptions and Quality Measures](https://mlsanity.com/paper/1808.10831/) (2018)
- [Demonstration Informed Specification Search](https://mlsanity.com/paper/2112.10807/) (2021)

## Built on by (most cited first, 19 of 19)

- [Spot the Fake: Large Multimodal Model-Based Synthetic Image Detection with Artifact Explanation](https://mlsanity.com/paper/2503.14905/) (2025)
- [One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2508.01561/) (2025)
- [Provably Correct Automata Embeddings for Optimal Automata-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2503.05042/) (2025)
- [Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Data](https://mlsanity.com/paper/2507.10741/) (2025)
- [ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning](https://mlsanity.com/paper/2510.14176/) (2025)
- [Automaton Constrained Q-Learning](https://mlsanity.com/paper/2510.05061/) (2025)
- [PlatoLTL: Scaling LTL-Guided Multi-Task RL](https://mlsanity.com/paper/2601.22891/) (2026)
- [Accelerated Learning with Linear Temporal Logic using Differentiable Simulation](https://mlsanity.com/paper/2506.01167/) (2025)
- [Automata-Conditioned Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2511.02304/) (2025)
- [Zero-Shot Instruction Following in RL via Structured LTL Representations](https://mlsanity.com/paper/2602.14344/) (2026)
- [SpecRLBench: A Benchmark for Generalization in Specification-Guided Reinforcement Learning](https://mlsanity.com/paper/2604.24729/) (2026)
- [Controllability in preference-conditioned multi-objective reinforcement learning](https://mlsanity.com/paper/2605.10585/) (2026)
- [RLAF: Reinforcement Learning from Automaton Feedback](https://mlsanity.com/paper/2510.15728/) (2025)
- [Zero-Shot Instruction Following in RL via Structured LTL Representations](https://mlsanity.com/paper/2512.02633/) (2025)
- [Learning Bilevel Policies over Symbolic World Models for Long-Horizon Planning](https://mlsanity.com/paper/2605.15975/) (2026)
- [Goal-Conditioned Agents that Learn Everything All at Once](https://mlsanity.com/paper/2605.23551/) (2026)
- [Direction-Conditioned Policies via Compositional Subgoal Scoring for Online Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2606.16515/) (2026)
- [Temporal Logic Guided Universal Task Representations for Reinforcement Learning](https://mlsanity.com/paper/2608.15509/) (2026)
- [Jaxolotl: A Unified High-Performance Benchmark Suite for LTL-Based Multi-Task RL](https://mlsanity.com/paper/2609.38065/) (2026)

## Abstract (arXiv)

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.