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) has seen significant success in various domains, yet it continues to struggle with "symbolic" problems—tasks defined by logic and discrete objects, such as logistics, network management, or automated planning. The primary obstacle is the curse of dimensionality: as the number of objects in a system increases (e.g., more packages to deliver or more nodes in a network), the state space grows exponentially.

Standard RL algorithms, such as Q-learning, are typically "instance-specific." An agent trained to manage a network of five computers lacks the framework to interpret a network of fifty; it perceives the new environment as an entirely different state space because it lacks an understanding of the underlying logic governing the task. To address this, we propose a framework for Generalized Reinforcement Learning (GRL). This method enables an agent to learn a policy on small, manageable versions of a problem and transfer that knowledge to much larger, more complex instances without additional training.

Relational Abstractions via Description Logic

The core innovation of GRL is the use of Description Logic (DL) to create relational abstractions. Instead of feeding raw state variables (e.g., "Computer #3 is down") into a neural network, GRL uses DL to automatically generate features that describe relationships and concepts. For instance, a DL feature might represent "the set of all computers currently in a failed state."

This approach "lifts" the problem from specific object identities to general concepts. By focusing on the properties and relationships of objects rather than their names or specific counts, the state representation becomes object-invariant. This allows a Deep Neural Network (specifically a Multi-Layer Perceptron) to estimate Q-values based on a fixed-size input of abstract features, regardless of whether the actual problem instance contains 5 or 500 objects.

The GRL Framework

The GRL framework integrates relational logic with deep learning through several key mechanisms:

  1. Abstract Q-Function: The agent learns to map abstract relational features to Q-values. Because the feature vector size is determined by the complexity of the logic rather than the number of objects, the same network architecture is applicable across all problem sizes within a domain.
  2. Leapfrogging (Curriculum Learning): To ensure training efficiency, the authors employ a "learning-from-small-examples" strategy. The agent begins on a trivial version of the problem, masters it, and then uses that knowledge to "leapfrog" into progressively larger versions. This iterative process refines the generalized policy without requiring a manually authored curriculum.
  3. Model-Free Integration: Unlike many previous attempts at generalized planning, GRL does not require "action models" or pre-defined rules of environmental dynamics. It learns purely from interaction trajectories, making it applicable to realistic RL settings where the underlying physics or logic of the world is unknown.

Experimental Evaluation

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

  • Sysadmin: Managing a network of computers where failures propagate through connections.
  • Academic Advising: Planning course schedules with complex prerequisite structures.
  • Game of Life: A grid-based environment based on cellular automata.
  • Wildfire: Managing the spread of fire across a grid.

In these experiments, the agent was trained on small instances (e.g., Sysadmin with 3-6 computers) and tested on significantly larger instances (e.g., 50 computers) to measure zero-shot transfer performance.

Key Results and Insights

The empirical results demonstrate that GRL provides a robust bridge between symbolic reasoning and deep learning:

  • Superior Zero-Shot Transfer: GRL significantly outperformed MBRRL (a linear baseline) across all tested domains. In many scenarios, GRL achieved near-optimal rewards on large test instances immediately upon transfer, whereas the baseline struggled to generalize.
  • Competitive Performance: When compared to SymNet—a state-of-the-art method that utilizes closed-form action models (essentially the environment's source code)—GRL remained highly competitive. Despite having to learn dynamics from scratch, GRL occasionally outperformed SymNet, highlighting the power of its relational abstractions.
  • Sample Efficiency: By leveraging knowledge from small instances, GRL reduced the sample complexity on large problems by several orders of magnitude compared to training an agent from scratch on those same large instances.

Limitations and Future Work

While GRL represents a significant step forward, some limitations remain. The current action representation does not fully capture complex dependencies, such as specific relational properties of action parameters (e.g., "how many neighbors does this specific computer have?"). Future work will explore adding "counting" features to address this. Additionally, while "leapfrogging" is more automated than manual curricula, it still requires a problem generator capable of producing instances of varying sizes. Finally, as the complexity of the logic increases, the number of generated features could grow significantly, necessitating more advanced feature selection techniques in future iterations.

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