Induction and Exploitation of Subgoal Automata for Reinforcement Learning

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

Introduction

Reinforcement Learning (RL) has demonstrated remarkable success in mastering low-level control tasks. However, high-level reasoning in environments with sparse rewards remains a significant hurdle. When a task requires a specific sequence of events—such as "collect wood, then iron, then craft a tool"—an agent receiving a reward only upon completion struggles to identify which intermediate actions were productive. While "Reward Machines" or automata can provide this necessary structure, they are typically handcrafted by experts, limiting the agent's autonomy.

This paper introduces ISA (Induction of Subgoal Automata), a framework designed to autonomously discover the hidden temporal structure of complex tasks. By interleaving RL with Inductive Logic Programming (ILP), ISA builds minimal finite-state machines where transitions represent logical subgoals, enabling agents to solve multi-stage problems as effectively as if they were provided with a human-engineered roadmap.

The ISA Framework

The ISA approach operates through two main interacting components: the RL Agent and the Automaton Learner.

  1. The RL Agent: The agent interacts with the environment, collecting "traces" of high-level events (e.g., "at coffee machine," "at office"). These traces serve as the data for the learning process.
  2. The Automaton Learner: Utilizing ILASP (Inductive Learning of Answer Set Programs), the learner induces a subgoal automaton that explains the observed traces. If the agent encounters a sequence of events that contradicts the current automaton, the learner generates a new, minimal automaton that accounts for all known data.

This interleaving process ensures that the agent's "map" of the task is constantly refined based on new experiences. The subgoals are expressed as propositional logic formulas (e.g., coffee AND NOT office), allowing the agent to handle complex conditions and generalize across different state combinations.

Efficiency and Minimality

A core innovation of ISA is its focus on minimality. By forcing the ILASP solver to find the smallest possible automaton that fits the traces, the system favors general solutions over those that simply memorize specific paths. This inductive bias allows the agent to generalize the task structure across different randomly generated environments.

To make this process computationally feasible, the authors introduced a symmetry breaking mechanism. In logic programming, the search space can be bloated by many equivalent automata that differ only in state labels. Symmetry breaking prunes these redundant structures, significantly accelerating the induction process. For instance, in the "CoffeeMail" task, this mechanism reduced induction time from hundreds of seconds to under twenty.

Exploitation of Learned Automata

Once an automaton is induced, the agent must exploit its structure to improve its policy. The paper evaluates two primary methods:

  • Hierarchical RL (HRL): The agent learns "options" or sub-policies to satisfy specific edges in the automaton. HRL is particularly robust because sub-policies for specific subgoals can often be reused even if the overall automaton structure is updated.
  • Q-learning for Reward Machines (QRM): This method treats the automaton as an external memory state, allowing the agent to track its progress through the task stages and adjust its behavior accordingly.

Experimental Evaluation

The ISA framework was tested across three diverse environments:

  • OfficeWorld: A grid-world navigation task involving delivery and obstacle avoidance.
  • CraftWorld: A Minecraft-inspired environment requiring resource collection and sequential crafting (e.g., "GetGem").
  • WaterWorld: A continuous state-space environment testing the system's compatibility with Deep RL and function approximation.

The results demonstrate that ISA-learned automata achieve average rewards comparable to those obtained using handcrafted, expert-designed automata. The system successfully scaled to tasks requiring up to 8 states, such as the "GetGem" task in CraftWorld, representing a high level of temporal complexity for an autonomous learner.

Limitations and Future Work

While ISA represents a significant step forward, several challenges remain. The system currently assumes that high-level events are pre-detected by an external system ("Observable Assumption"). Future research aims to integrate "Observable Discovery" to identify these key events directly from raw sensory input. Additionally, because the underlying ILP problem is NP-hard, scaling to even more complex tasks may require hierarchical automata structures. Finally, the system's reliance on positive examples can lead to overgeneralization, where the agent might fail to learn about negative constraints (like traps) if it never encounters them during successful runs.

Conclusion

ISA provides a robust framework for bridging the gap between low-level reinforcement learning and high-level symbolic reasoning. By automatically inducing the "rules of the game," ISA empowers agents to navigate complex, multi-stage environments with minimal human intervention, achieving performance parity with expert-guided systems.

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