Abstract
In this paper, we present ISA (Induction of Subgoal Automata), an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves RL with the induction of a subgoal automaton—a structure whose edges are labeled by propositional logic formulas over high-level events. By utilizing state-of-the-art inductive logic programming (ILP), ISA learns minimal automata that cover observed traces of high-level events. We introduce a symmetry breaking mechanism to significantly reduce the search space. Our empirical evaluation across gridworld and continuous state space environments demonstrates that ISA achieves performance comparable to using handcrafted automata, effectively bridging the gap between high-level logical reasoning and low-level control.
Introduction
Reinforcement Learning (RL) has achieved remarkable success in mastering reactive behaviors. However, complex, multi-stage tasks with sparse rewards remain a significant challenge. To navigate these environments, agents require temporal abstractions—a "roadmap" of subgoals that decompose a long-horizon task into manageable segments.
While frameworks like Reward Machines (RMs) provide a robust way to represent these structures, they typically rely on human experts to define the automaton's topology and transitions. The goal of this research is to enable agents to discover these structures autonomously. The primary challenge in learning such automata is the computational complexity and the risk of overgeneralization. We propose the Induction of Subgoal Automata (ISA) framework to address these issues by interleaving task learning with logic-based induction.
The ISA Framework
ISA tightly couples Reinforcement Learning with Inductive Logic Programming (ILP) through a continuous feedback loop.
1. The Interleaving Loop
The agent begins with a trivial automaton. As it explores the environment, it generates "traces"—sequences of high-level events. When the agent encounters a trace that the current automaton cannot correctly recognize or explain (a counterexample), the induction process is triggered to update the agent's mental model.
2. Automaton Induction via ILASP
The system employs ILASP (Inductive Learning of Answer Set Programs) to find the minimal automaton that correctly recognizes all observed traces. By seeking the simplest possible model that fits the data, ISA adheres to the principle of Occam’s Razor, preventing the agent from over-complicating the task structure and promoting better generalization.
3. Symmetry Breaking
A core technical contribution of ISA is its symmetry-breaking mechanism. In logic programming, many functionally identical automata can be represented in different ways. ISA imposes a "canonical" structure during the search process, which drastically shrinks the search space. This optimization is crucial for making the induction phase practical for real-time interleaving.
4. Exploitation Strategies
Once an automaton is induced, the agent exploits its structure to learn an optimal policy. We evaluate two primary methods:
- Hierarchical RL (HRL): The agent learns specific "options" or sub-policies for each edge in the automaton.
- Q-learning for Reward Machines (QRM): This method allows the agent to share experience across different states of the automaton, significantly improving sample efficiency.
Experimental Evaluation
We evaluated ISA across three diverse environments to test its versatility:
- OfficeWorld: A grid-world benchmark where the agent must complete sequences (e.g., deliver coffee and mail to an office) while avoiding obstacles.
- CraftWorld: A Minecraft-inspired environment requiring resource gathering and tool crafting, testing the agent's ability to handle complex dependencies.
- WaterWorld: A continuous state-space environment where the agent interacts with moving colored balls. This environment tested ISA’s compatibility with Deep RL (specifically Double DQN) and its robustness to non-discrete event timings.
Key Results and Insights
The empirical analysis yielded several critical findings:
- Performance Parity: In nearly all test cases, policies learned using induced automata achieved average rewards equivalent to those using handcrafted, expert-provided automata.
- Computational Efficiency: The symmetry-breaking constraints were essential. They allowed the system to find minimal automata for complex tasks (such as the VisitABCD task) in seconds, whereas unconstrained induction often timed out.
- Robustness: ISA successfully handled the "noisy" traces inherent in continuous spaces like WaterWorld, proving that logic-based induction can effectively guide neural network controllers.
- Minimality as a Prior: Forcing the learner to find the smallest possible automaton prevents the agent from overfitting to specific exploration paths, leading to more reusable subgoals.
Conclusion and Future Work
ISA demonstrates that agents can autonomously discover the logical structure of complex tasks by interleaving RL with ILP. While the current framework requires predefined high-level observables (e.g., "at coffee machine"), it provides a powerful foundation for hierarchical reasoning.
Future research will focus on moving toward learning high-level events directly from raw sensory input (e.g., pixels) and further optimizing ILP to handle tasks with significantly larger state spaces. Additionally, incorporating failed attempts as negative examples could further refine the induced models and prevent overgeneralization.
Summary updated