Relational Abstractions for Generalized Reinforcement Learning on Symbolic Problems

Rushang Karia, Siddharth Srivastava

Abstract: Reinforcement learning in problems with symbolic state spaces is challenging due to the need for reasoning over long horizons. This paper presents a new approach that utilizes relational abstractions in conjunction with deep learning to learn a generalizable Q-function for such problems. The learned Q-function can be efficiently transferred to related problems that have different object names and object quantities, and thus, entirely different state spaces. We show that the learned, generalized Q-function can be utilized for zero-shot transfer to related problems without an explicit, hand-coded curriculum. Empirical evaluations on a range of problems show that our method facilitates efficient zero-shot transfer of learned knowledge to much larger problem instances containing many objects.

Introduction

Reinforcement learning (RL) typically struggles to scale when the number of objects in a symbolic environment increases, as the state space explodes exponentially. For instance, in a network management task like "SysAdmin," an agent trained on a 5-computer network often fails when faced with 50 computers because the state representation—including object names and connection topologies—changes entirely.

Traditional RL algorithms like Q-learning are often instance-specific, learning policies for fixed configurations. In contrast, humans can grasp general rules (e.g., "reboot any computer that isn't running") that apply regardless of the network size. This paper introduces Generalized Reinforcement Learning (GRL), a method that uses logic-based relational abstractions to learn a Q-function independent of specific object counts or names, enabling zero-shot transfer from small training examples to massive problem instances.

Methodology

The GRL framework combines relational logic with deep learning through three core components:

  1. Relational Abstraction: Instead of raw state variables, the system uses Description Logics (DL) to generate abstract, "lifted" features. For example, a feature might represent "the number of computers currently running" rather than the status of a specific computer. These features are invariant to object names.
  2. Generalized Q-function ($Q_{GRL}$): These abstract features form a fixed-size input vector for a Deep Neural Network. Because the input size remains constant regardless of the number of objects in the environment, the same network can estimate Q-values for any instance size.
  3. Leapfrogging: To eliminate the need for manual curricula, the authors employ an iterative self-training technique. The agent begins by solving a minimal problem instance using standard RL and then uses that knowledge to bootstrap learning on progressively larger problems, building a robust generalized policy.
The GRL architecture: concrete states and actions are converted into abstract vectors using relational features, which are then processed by a deep neural network to estimate generalized Q-values.

Experimental Evaluation

The method was evaluated on four benchmark domains from the International Probabilistic Planning Competition (IPPC):

  • SysAdmin: Maintaining a computer network.
  • Academic Advising: Course scheduling with complex prerequisites.
  • Game of Life: Maximizing live cells in a cellular automata grid.
  • Wildfire: Managing fire suppression on a grid.

Training was conducted on very small instances (state spaces of $2^3$ to $2^8$), while testing involved massive instances with state spaces up to $2^{72}$.

Results and Discussion

GRL was compared against MBRRL (a state-of-the-art relational RL baseline) and SymNet (a model-based approach with access to action models).

Zero-shot transfer performance across four domains. GRL (green) consistently outperforms the MBRRL baseline (orange) and remains competitive with the model-heavy SymNet (gray).

Key findings include:

  • Superior Scaling: GRL significantly outperformed MBRRL in most domains. In SysAdmin, it successfully transferred knowledge from a 6-computer training set to a 50-computer test set.
  • Competitive Performance: GRL performed competitively with SymNet, despite SymNet having access to underlying transition equations that GRL had to learn from scratch. This highlights GRL's ability to handle "black-box" simulators without hand-coded action models.
  • Effective Abstraction: Mapping variable-sized concrete states to a fixed-size abstract feature space is the critical enabler for applying deep learning to generalized symbolic planning.

Conclusion

GRL demonstrates that agents trained on "toy" versions of symbolic problems can perform effectively on real-world scales without additional training. While the current logic-based features are powerful, future work will explore automatic feature discovery to capture even more complex relational properties. Additionally, the reliance on a problem generator for the "leapfrogging" curriculum remains a requirement for scaling to increasingly complex tasks.

Summary updated

Abstract

Reinforcement learning in problems with symbolic state spaces is challenging due to the need for reasoning over long horizons. This paper presents a new approach that utilizes relational abstractions in conjunction with deep learning to learn a generalizable Q-function for such problems. The learned Q-function can be efficiently transferred to related problems that have different object names and object quantities, and thus, entirely different state spaces. We show that the learned, generalized Q-function can be utilized for zero-shot transfer to related problems without an explicit, hand-coded curriculum. Empirical evaluations on a range of problems show that our method facilitates efficient zero-shot transfer of learned knowledge to much larger problem instances containing many objects.
BibTeX
@inproceedings{karia2022relational,
  author = {Rushang Karia and Siddharth Srivastava},
  title = {{Relational Abstractions for Generalized Reinforcement Learning on Symbolic Problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=fRoOh-8xdTi},
}
Figure