Answer-Set-Programming-based Abstractions for Reinforcement Learning

Problem Statement
Reinforcement Learning (RL) enables agents to learn policies through interaction, but realistic applications often suffer from enormous state and action spaces, rendering naive learning approaches intractable. While approximation methods like Deep Q-Learning offer generalization, they frequently require vast amounts of training data and can exhibit instability. Relational Reinforcement Learning (RRL) addresses these limitations by utilizing first-order logic to reason about objects and their relations, facilitating generalization across similar states. Specifically, the CARCASS framework (Compact Abstraction using Relational Conjunctions for Aggregation of State-action Spaces) by van Otterlo (2004) models Markov Decision Processes (MDPs) using logical abstractions. However, the original CARCASS implementation relies on Prolog and SLDNF-resolution, which, while declarative in principle, often necessitates procedural features (such as rule ordering or cuts) for efficiency and lacks native support for nonmonotonic inference, optimization, and preference handling.

Methodology
The authors propose a general method for re-implementing the CARCASS framework using Answer-Set Programming (ASP). ASP is a fully declarative logic-based knowledge representation language that supports nonmonotonic reasoning, optimization, and constraints.

1. ASP Encoding of CARCASS: The authors define a labelling function to map abstract states and state-action pairs to ground terms. They construct a modular encoding comprising:

   • Programs ($P_{\hat{s}_i}$) that encode individual abstract states as rules where the body consists of the literals defining the abstract state.
   • Programs ($P_{\hat{s}_i, \hat{a}_{i,j}}$) that encode the covering relation for abstract state-action pairs, linking concrete actions to abstract ones via aCov atoms.
   • A decision-list mechanism ($P_{\hat{C}}$) using a choice rule to select exactly one covering abstract state per concrete state and a constraint to ensure the selection follows the ordered list (prioritizing the lowest index).
   • An "empty" abstract state ($\hat{s}_\infty$) with the highest index that covers all states not covered by specific rules, ensuring a default fallback.

2. Online Learning Integration: The authors integrate this encoding into an online Q-learning loop (Algorithm 2). For a given concrete state, the ASP solver computes an optimal answer set to determine the covering abstract state and the set of admissible abstract actions. The agent then selects a concrete action from the set covered by the chosen abstract action and updates the Q-value of the abstract state-action pair.

3. Background Knowledge: The framework allows for the inclusion of background knowledge ($P_B$) to infer complex properties (e.g., pathfinding, tower completeness) directly within the abstraction process, rather than requiring them to be pre-computed or procedurally implemented.

Key Contributions

1. General Encoding Method: The paper introduces a systematic method for encoding CARCASS abstractions in ASP, demonstrating how a fully declarative language can realize relational state-action abstractions.
2. Online Learning Adaptation: The authors show how to utilize ASP-based CARCASS abstractions within an online Q-learning setting, handling the dynamic selection of abstract states and actions.
3. Empirical Evaluation: The implementation is evaluated in two distinct domains:
   • Blocks World: An $n$-block stacking task where the abstraction reduces the state-action space to a constant size regardless of $n$.
   • MiniGrid: A suite of grid-world navigation tasks (e.g., Door Key, Multi Room) where background knowledge is used to infer room layouts and shortest paths, constructing abstract states based on the next node in the path.

Results
The empirical evaluation compares abstract Q-learning against concrete Q-learning across a 20-blocks world and three MiniGrid environments.

• Stability: Abstract Q-learning demonstrated consistent stability, with median returns and interquartile ranges remaining high after initial learning, whereas concrete Q-learning showed significant fluctuations or failure to converge in complex environments.
• Quality: Abstract Q-learning achieved high success rates (e.g., near 100% in the last 500 episodes for MiniGrid tasks), significantly outperforming concrete Q-learning, which often failed to achieve positive returns in the same timeframe.
• Sample Efficiency: The abstract approach required significantly fewer episodes to learn high-quality policies compared to the concrete approach. For instance, in the 20-blocks world, abstract learning achieved positive median returns by episode 376, while concrete learning remained at the baseline negative return.
• Modelling Differences: In the MiniGrid case study, the ASP encoding allowed for a compact, declarative specification of pathfinding and constraints, whereas the equivalent Prolog implementation required explicit algorithmic search (breadth-first search), highlighting ASP's advantage in separating problem specification from control logic.

Significance and Claims
The paper concludes that CARCASS implemented with ASP provides a promising approach for constructing abstractions in RL, particularly when domain knowledge is available. The authors claim that ASP-based abstractions offer a flexible alternative to Prolog-based CARCASS by supporting:

• Generalization: Through relational representations.
• Action Restrictions: Via declarative constraints.
• Problem Decomposition: By encoding complex reasoning patterns (like pathfinding or tower analysis) directly in the rules.
• Advanced Reasoning: Including nonmonotonic inference, optimization, and reasoning under incomplete knowledge.

The authors modestly note that while the learned policies are of acceptable quality and learned with fewer samples, there is no guarantee of convergence to an optimal policy in general, and the abstraction itself may not preserve the optimal policy for NP-hard planning problems (as seen in the Blocks World case where the abstraction trades optimality for tractability). The work positions itself as a step toward knowledge-driven frameworks for relational RL that support elaboration-tolerant policy learning.