Relational State Abstractions for Generalizable Agent Policies

52 concepts50 papers1 proposal

Traditional deep reinforcement learning (RL) often treats the world as a flat grid of pixels or a fixed-length vector of features. While powerful, this approach is inherently brittle: an agent trained to navigate a room with three chairs may fail entirely when a fourth is added, simply because the input dimensions or global pixel patterns have changed.

To overcome this, a growing body of research focuses on relational state abstractions. Instead of processing raw sensory data as a monolithic block, these methods "lift" the environment into a structured representation of discrete objects and the relationships between them. By reasoning about classes of objects rather than specific pixel coordinates, agents can achieve human-like generalization and zero-shot transfer to complex, unseen environments.

From Pixels to Entities

The first step in relational abstraction is decomposing a scene into its constituent parts. Rather than viewing an image as a 2D array of intensities, researchers like Woof propose representing the state as a set of object embeddings. In this view, a game state is not a fixed matrix but a collection of entities—such as "player," "key," and "door"—each with its own learned attributes.

This shift allows agents to focus on task-relevant information while ignoring background noise. For instance, Chen et al. demonstrate that by using foundational segmentation models to identify objects, agents can maintain high performance even when the background is filled with dynamic, distracting visuals that would typically overwhelm a standard convolutional neural network. Similarly, Xu et al. show that representing scenes as entity-centric feature vectors enables models to reason about subgoals and preconditions independently of the global pixel configuration.

Lifting Logic for Infinite Scaling

The true power of relational representations lies in their ability to handle an arbitrary number of objects. This is achieved through First-Order Logic (FOL) and Relational Markov Decision Processes (RMDPs).

In a standard MDP, the state space grows exponentially with the number of objects. However, by using first-order predicates—logical statements like on(BlockA, BlockB)—the complexity of the problem becomes independent of the total number of objects. Driessens et al. pioneered the use of incremental first-order decision trees to learn policies that remain valid regardless of how many objects are in the environment.

This "lifted" reasoning allows for remarkable scaling. Guestrin demonstrated that an agent could learn a value function in a small, simple environment and immediately apply it to a much larger one by approximating the total reward as a sum of contributions from individual object classes. More recently, Karia et al. showed that using description logics to map symbolic environments into fixed-size relational features allows for zero-shot transfer from tiny training examples to massive problem instances.

Bridging the Gap with Neurosymbolic Frameworks

While symbolic logic provides structure, neural networks provide the flexibility to handle raw data. Modern "neurosymbolic" approaches attempt to combine these strengths. Frameworks like NUDGE, introduced by Delfosse et al., transform raw sensory input into object-centric representations that identify spatial and functional relationships. This allows the agent to learn differentiable logic policies that are both high-performing and human-readable.

These abstractions also facilitate better human-AI collaboration. By "lifting" pixels into a relational format, the RAEL framework developed by Darvishvand et al. allows agents to query human experts for advice using symbolic terms. Because the agent is reasoning about objects and relations rather than abstract pixel patterns, the human's advice can be easily integrated into the agent's logical framework.

Why It Works: Relational Invariance

The intuition behind the success of relational abstractions is invariance. In many tasks, the "rules of the game" do not change based on where an object is located or how many objects exist. A robot learning to pick up a cup should not need to relearn the concept of "grasping" just because the cup is moved to a different table or because there are now five cups instead of one.

By representing the state through relative predicates (Marom) or object-oriented hierarchies (da Silva and Costa), the agent learns a policy that is invariant to these permutations. As Sanner and Kersting argue, using logical formulas to define rewards and transitions allows the agent to reason about classes of objects, making the model's complexity dependent on the logic of the task rather than the scale of the environment.

Ultimately, relational state representation moves AI away from rote pattern matching and toward a structural understanding of the world, enabling agents to plan, explore, and generalize in ways that mirror human cognition.

Key Foundational Work

A message processing system with object-centered semantics (1990) — contributed 2 concept elements to this direction.
Meta-Evaluation as a Tool for Program Understanding (1977) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_relational_state_representation_11d705e4,
  title = {relational state representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-state-representation/rdr_11d705e49ddd4601bf28f81f2a59193d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_relational_state_representation_11d705e4_v1,
  title = {relational state representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-state-representation/rdr_11d705e49ddd4601bf28f81f2a59193d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake