CoChat
Sign Up
Cited by 3Reinforcement Learning in Roboticssemigroups and automata theoryAI-based Problem Solving and Planning

The DOI matches its Crossref record.

Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning

Open access
Yalcinkaya, Beyazit, Lauffer, Niklas, Vazquez-Chanlatte, Marcell, Seshia, Sanjit·2024·Advances in Neural Information Processing Systems 37
DOI 10.52202/079017-2322
Open this paper in CoChat — free accountOpen PDF

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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.52202/079017-2322

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • A filtering step rejects resulting trivial, uninteresting tasks; hence, the training distribution consists of non-trivial, solvable tasks.

    “A filtering step rejects resulting trivial, uninteresting tasks (e.g., singlestate DFAs); hence, the training distribution consists of non-trivial, solvable tasks.”

    From Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs (2025) · cites this paper as Yalcinkaya et al. 2024

    Section 4.2 (page unavailable) says the RAD sampler rejects mutations that produce trivial one-state DFAs, supporting the filtering claim. It does not say this check guarantees that every resulting compositional training task is solvable; the claimed guarantee goes beyond the stated filter. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • The suite's alphabet consists of 889 propositions.

    “The alphabet size consists of 889 propositions, which is almost two orders of magnitude larger than the alphabets considered in previous work (Kuo, Katz, and Barbu 2020; Vaezipoor et al. 2021; Yalcinkaya et al. 2024; Jackermeier and Abate 2025).”

    From Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs (2025) · cites this paper as Yalcinkaya et al. 2024

  • The suite's alphabet is almost two orders of magnitude larger than the alphabets considered in previous work.

    “The alphabet size consists of 889 propositions, which is almost two orders of magnitude larger than the alphabets considered in previous work (Kuo, Katz, and Barbu 2020; Vaezipoor et al. 2021; Yalcinkaya et al. 2024; Jackermeier and Abate 2025).”

    From Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs (2025) · cites this paper as Yalcinkaya et al. 2024

  • Vaezipoor et al. (2021) and Yalcinkaya et al. (2024) rely on environment-agnostic pretraining schemes to improve sample efficiency; they pretrain graph embeddings leveraging task structure only, without interacting with the actual environment.

    “Both Vaezipoor et al. (2021) and Yalcinkaya et al. (2024) rely on environment-agnostic pretraining schemes to improve sample efficiency; that is, they pretrain graph embeddings leveraging task structure only, without interacting with the actual environment.”

    From Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs (2025) · cites this paper as Yalcinkaya et al. (2024)

  • Each mutation involves randomly changing a transition, converting the accepting state into a sink, and minimizing the resulting DFA to ensure simplicity.

    “Each mutation involves randomly changing a transition, converting the accepting state into a sink, and minimizing the resulting DFA to ensure simplicity.”

    From Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs (2025) · cites this paper as Yalcinkaya et al. 2024

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 46

  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. IEEE, 2016.
  2. Rajeev Alur, Suguman Bansal, Osbert Bastani, and Kishor Jothimurugan. A framework for transforming specifications in reinforcement learning. In 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 ltl. In International Conference on Computer Aided Verification, pages 415-435. Springer, 2023.
  4. Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In International conference on machine learning, pages 166-175. PMLR, 2017.
  5. Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI 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, Jan Leike, Edward Hughes, Arian Hosseini, Pushmeet Kohli, and Edward Grefenstette. Learning to understand goal specifications by modelling reward. arXiv preprint arXiv:1806.01946, 2018. · arXiv
  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:2105.14491, 2021. · arXiv
  10. Mingyu Cai, Shaoping Xiao, Zhijun Li, and Zhen Kan. Optimal probabilistic motion planning with potential infeasible ltl constraints. IEEE transactions on automatic control, 68(1):301-316, 2021.
  11. Alberto Camacho, Meghyn Bienvenu, and Sheila A McIlraith. Finite ltl 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 McIlraith. Ltl and beyond: Formal languages for reward function specification in reinforcement learning. In IJCAI, volume 19, pages 6065-6073, 2019.
  13. Xuchu Ding, Stephen L Smith, Calin Belta, and Daniela Rus. Optimal control of markov decision processes with linear temporal logic constraints. IEEE Transactions on Automatic Control, 59(5):1244-1257, 2014.
  14. Jie Fu and Ufuk Topcu. Probably approximately correct mdp learning and control with temporal logic constraints. arXiv preprint arXiv:1404.7073, 2014. · arXiv
  15. E Mark Gold. Language identification in the limit. Information and control, 10(5):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. In 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. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
  20. Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A McIlraith. Reward machines: Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73: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, 34:10026-10039, 2021.
  24. Niklas Lauffer, Beyazit Yalcinkaya, Marcell Vazquez-Chanlatte, 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 IEEE/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:1906.03926, 2019. · arXiv
  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. Mateo Perez, Fabio Somenzi, and Ashutosh Trivedi. A pac learning algorithm for ltl and omega- regular objectives in mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 21510-21517, 2024.
  29. 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.
  30. Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep rein- forcement learning. arXiv preprint arXiv:1910.01708, 7(1):2, 2019. · arXiv
  31. 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 on Decision and Control, pages 1091-1096. IEEE, 2014.
  32. Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function ap- proximators. In International conference on machine learning, pages 1312-1320. PMLR, 2015.
  33. 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 593-607. Springer, 2018.
  34. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. · arXiv
  35. 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. · arXiv
  36. Sumedh Sontakke, Jesse Zhang, Séb Arnold, Karl Pertsch, Erdem Bıyık, Dorsa Sadigh, Chelsea Finn, and Laurent Itti. Roboclip: One demonstration is enough to learn robot policies. Advances in Neural Information Processing Systems, 36, 2024.
  37. Pashootan Vaezipoor, Andrew C Li, Rodrigo A Toro Icarte, and Sheila A Mcilraith. Ltl2action: Generalizing ltl instructions for multi-task rl. In International Conference on Machine Learning, pages 10497-10508. PMLR, 2021.
  38. Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
  39. Moshe Y Vardi. From church and prior to psl. In 25 Years of Model Checking: History, Achievements, Perspectives, pages 150-171. Springer, 2008.
  40. Marcell Vazquez-Chanlatte, Karim Elmaaroufi, Stefan J Witwicki, and Sanjit A Seshia. L * lm: Learning automata from examples using natural language oracles. arXiv preprint arXiv:2402.07051, 2024. · arXiv
  41. Marcell Vazquez-Chanlatte, Ameesh Shah, Gil Lederman, and Sanjit A Seshia. Demonstration informed specification search. CoRR, vol. abs/2112.10807, 2021. · arXiv
  42. Cameron Voloshin, Hoang Le, Swarat Chaudhuri, and Yisong Yue. Policy optimization with linear temporal logic constraints. Advances in Neural Information Processing Systems, 35:17690- 17702, 2022.
  43. Wojciech Wieczorek. Grammatical Inference. Springer, 2017.
  44. 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.
  45. Beyazit Yalcinkaya, Niklas Lauffer, Marcell Vazquez-Chanlatte, and Sanjit Seshia. Automata conditioned reinforcement learning with experience replay. In NeurIPS 2023 Workshop on Goal-Conditioned Reinforcement Learning, 2023.
  46. Cambridge Yang, Michael Littman, and Michael Carbin. On the (in) tractability of reinforcement learning for ltl objectives. arXiv preprint arXiv:2111.12679, 2021. · arXiv

Cited by

Sorted by citations

Metadata

Authors
Yalcinkaya, B., Lauffer, N., Vazquez-Chanlatte, M., & Seshia, S.
ORCID
Venue
Advances in Neural Information Processing Systems 37
Publisher
Neural Information Processing Systems Foundation, Inc. (NeurIPS)
Published
2024
Pages
72933-72963
ISSN
1049-5258 (ISSN-L)
DOI
10.52202/079017-2322
OpenAlex
W4415797027
Cited by
3
References
0
Citations by year
2026: 2 · 2025: 1
FWCI
0.87
Type
conference paper
Language
en
Open access
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation
  • Defense Advanced Research Projects Agency (FA8750-18-C-0101, FA8750)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
Keywords
goal-conditioned reinforcement learning, hierarchical reinforcement learning, compositional representations

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review