# Induction and Exploitation of Subgoal Automata for Reinforcement Learning

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2020.

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

- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [Decentralized Graph-Based Multi-Agent Reinforcement Learning Using Reward Machines](https://mlsanity.com/paper/2110.00096/) (2021)
- [Learning Task Automata for Reinforcement Learning using Hidden Markov Models](https://mlsanity.com/paper/2208.11838/) (2022)
- [Neural Reward Machines](https://mlsanity.com/paper/2408.08677/) (2024)
- [Learning Robust Reward Machines from Noisy Labels](https://mlsanity.com/paper/2408.14871/) (2024)
- [Detecting Hidden Triggers: Mapping Non-Markov Reward Functions to Markov](https://mlsanity.com/paper/2401.11325/) (2024)
- [Ground-Compose-Reinforce: Grounding Language in Agentic Behaviours using Limited Data](https://mlsanity.com/paper/2507.10741/) (2025)
- [Hierarchies of Reward Machines](https://mlsanity.com/paper/2205.15752/) (2022)
- [FORM: Learning Expressive and Transferable First-Order Logic Reward Machines](https://mlsanity.com/paper/2501.00364/) (2024)
- [Online inductive learning from answer sets for efficient reinforcement learning exploration](https://mlsanity.com/paper/2501.07445/) (2025)
- [Verifiable Reinforcement Learning Systems via Compositionality](https://mlsanity.com/paper/2309.06420/) (2023)
- [RewardFlow: Topology-Aware Reward Propagation on State Graphs for Agentic RL with Large Language Models](https://mlsanity.com/paper/2603.18859/) (2026)
- [Learning Reward Machines in Cooperative Multi-Agent Tasks](https://mlsanity.com/paper/2303.14061/) (2023)
- [Learning Symbolic Persistent Macro-Actions for POMDP Solving Over Time](https://mlsanity.com/paper/2505.03668/) (2025)
- [Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs](https://mlsanity.com/paper/2511.12706/) (2025)
- [Regular Decision Processes for Grid Worlds](https://mlsanity.com/paper/2111.03647/) (2021)
- [Learning Automata-Based Complex Event Patterns in Answer Set Programming](https://mlsanity.com/paper/2208.14820/) (2022)
- [Fully Learnable Neural Reward Machines](https://mlsanity.com/paper/2509.19017/) (2025)
- [Sample-Efficient Neurosymbolic Deep Reinforcement Learning](https://mlsanity.com/paper/2601.02850/) (2026)
- [Analyzing Robustness of Angluin's L* Algorithm in Presence of Noise](https://mlsanity.com/paper/2209.10315/) (2022)
- [SymDQN: Symbolic Knowledge and Reasoning in Neural Network-based Reinforcement Learning](https://mlsanity.com/paper/2504.02654/) (2025)
- [Physics-Informed Reward Machines](https://mlsanity.com/paper/2508.14093/) (2025)
- [Reinforcement Learning for Long-Horizon Unordered Tasks: From Boolean to Coupled Reward Machines](https://mlsanity.com/paper/2510.27329/) (2025)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)
- [Sample-efficient Neuro-symbolic Proximal Policy Optimization](https://mlsanity.com/paper/2604.25534/) (2026)
- [Explaining Reinforcement Learning Agents via Inductive Logic Programming](https://mlsanity.com/paper/2607.13655/) (2026)

## Abstract (arXiv)

In this paper we present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task's subgoals expressed as propositional logic formulas over a set of high-level events. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding. A state-of-the-art inductive logic programming system is used to learn a subgoal automaton that covers the traces of high-level events observed by the RL agent. When the currently exploited automaton does not correctly recognize a trace, the automaton learner induces a new automaton that covers that trace. The interleaving process guarantees the induction of automata with the minimum number of states, and applies a symmetry breaking mechanism to shrink the search space whilst remaining complete. We evaluate ISA in several gridworld and continuous state space problems using different RL algorithms that leverage the automaton structures. We provide an in-depth empirical analysis of the automaton learning performance in terms of the traces, the symmetry breaking and specific restrictions imposed on the final learnable automaton. For each class of RL problem, we show that the learned automata can be successfully exploited to learn policies that reach the goal, achieving an average reward comparable to the case where automata are not learned but handcrafted and given beforehand.