Induction and Exploitation of Subgoal Automata for Reinforcement Learning

Daniel Furelos-Blanco, Mark Law, Anders Jonsson, Krysia Broda, Alessandra Russo

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

Abstract

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.
BibTeX
@article{furelosblanco2021induction,
  author = {Daniel Furelos-Blanco and Mark Law and Anders Jonsson and Krysia Broda and Alessandra Russo},
  title = {{Induction and Exploitation of Subgoal Automata for Reinforcement Learning}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  url = {https://openreview.net/forum?id=K4Tpc8TFVEI},
}
Figure