Online Abstraction with MDP Homomorphisms for Deep Learning

Ondrej Biza, Robert Platt

TL;DR

This paper introduces Online Partition Iteration, a novel algorithm that learns abstract Markov Decision Processes (MDPs) directly from experience in continuous state spaces using MDP homomorphisms. By mapping complex environments into compact, simplified representations, the algorithm enables agents to successfully transfer structural knowledge to new tasks via the options framework, significantly outperforming standard deep reinforcement learning baselines.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents often struggle in environments with continuous state spaces and high-dimensional action spaces (such as robotics) because they are forced to learn policies at a low level of abstraction. State abstraction—grouping similar states and actions together—is a powerful way to simplify these problems.

A mathematically rigorous way to do this is through MDP homomorphisms, which map a complex original MDP to a compact "quotient" MDP while preserving transition and reward structures. However, prior methods for finding these homomorphisms required full knowledge of the environment's transition dynamics or were restricted to narrow, discrete domains. This paper tackles the challenge of learning general MDP homomorphisms online from model-free experience in continuous, high-dimensional environments.

Abstraction for the task of stacking two pucks. The top diagram shows a minimal three-state quotient MDP homomorphic to the complex underlying configurations at the bottom.

Methods

The authors propose Online Partition Iteration, adapting classic bisimulation-based partitioning algorithms to work with a continuous stream of experience. The core pipeline consists of:

  1. Initial Experience Collection: An agent interacts with the environment (using a random policy or a vanilla Deep Q-Network) to collect a diverse buffer of transitions.
  2. Online Partition Iteration: The algorithm starts by grouping transitions that receive identical rewards. It then iteratively refines this partition using a State Projection step.
  3. Neural Network Classification: To handle continuous spaces, a deep neural network classifier (specifically a Dilated Residual Network, DRN-C-26) is trained to classify state-action pairs into their corresponding abstract blocks.

To make this process robust against neural network classification errors, the authors introduce several critical augmentations:

  • Class Balancing: Oversampling minority classes (like rare reward-giving transitions).
  • Confidence Calibration: Using Platt scaling to calibrate the softmax probabilities of the classifier.
  • Size & Confidence Thresholds: Ignoring predicted abstract blocks that fall below a certain size or confidence threshold to prevent the algorithm from "hallucinating" non-existent states.

Finally, the learned abstract MDP is used for Transfer Learning. The agent creates a set of options (temporally-extended actions) based on the abstract states, allowing it to guide exploration efficiently when dropped into a new, related task.

The projection process where a single state $s$ is evaluated under multiple actions, and the classifier predicts state-action blocks to determine which abstract state block $s$ belongs to.

Datasets

The algorithm was evaluated on two primary environments:

  • Continuous Pucks World: A newly designed robotic manipulation proxy. The state is represented as a $112 \times 112$ depth image, and the action space consists of pixel coordinates ($12,544$ possible actions). Tasks include stacking pucks, arranging components, and building stairs.
  • Discrete Blocks World: A classic RL benchmark consisting of 3 blocks and 4 positions ($12$ tasks of varying difficulty), used primarily to compare performance against historical baselines.
The goal states of the four types of tasks in the continuous pucks world domain.

Key Insights and Ideas

  • The Error Cascade Dilemma: Learning abstractions online creates a feedback loop: the classifier at step $t$ defines the labels used to train the classifier at step $t+1$. Without confidence calibration and thresholding, classification errors compound exponentially, leading to catastrophic over-segmentation of the state space.
  • Options vs. Weight Sharing: When transferring knowledge to a new task, initializing an RL network with weights from a previous task can cause the agent to get stuck in local optima (e.g., repeatedly recreating the old task's goal). Transforming the abstraction into options provides structured exploration vectors that avoid this trap.
  • Action Aggregation: In pixel-action spaces (like Pucks World), the homomorphism naturally groups thousands of individual pixel coordinates into semantic macro-actions like "pick up puck" or "do nothing," drastically reducing the effective branching factor.

Key Results

  • Pucks World Transfer: In task transfer experiments (e.g., transferring knowledge from a 2-puck stack task to a 3-puck stack task), the options-based transfer method reached the goal significantly faster than the baselines. For instance, the proposed method required $2558 \pm 910$ steps to reach the target performance, compared to $5335 \pm 1540$ steps for a vanilla DQN baseline.
  • Blocks World Comparison: When evaluated against the prominent historical baseline (Wolfe et al., 2006), the proposed decision-tree variant achieved a higher average reward per time step significantly faster, demonstrating the efficiency of learning directly from the reward function without requiring an explicit output function.
Comparison of the proposed method against Wolfe et al. (2006) in the Blocks World environment, showing faster convergence to a higher average reward.

Limitations and Future Work

  • Deterministic Restriction: To remain sample-efficient and avoid explicitly estimating continuous probability distributions, the transition function is strictly limited to deterministic environments. Extending this to stochastic dynamics remains an open challenge.
  • Classifier Sensitivity: The algorithm's success is heavily bottlenecked by the classifier's accuracy. In more complex tasks like "building stairs," the individual state-action blocks are less distinct, leading to noisy, suboptimal partitions. Future work will focus on improving classification boundaries in highly complex visual scenes.

Summary updated

Abstract

Abstraction of Markov Decision Processes is a useful tool for solving complex problems, as it can ignore unimportant aspects of an environment, simplifying the process of learning an optimal policy. In this paper, we propose a new algorithm for finding abstract MDPs in environments with continuous state spaces. It is based on MDP homomorphisms, a structure-preserving mapping between MDPs. We demonstrate our algorithm's ability to learn abstractions from collected experience and show how to reuse the abstractions to guide exploration in new tasks the agent encounters. Our novel task transfer method outperforms baselines based on a deep Q-network in the majority of our experiments. The source code is at https://github.com/ondrejba/aamas_19.
BibTeX
@misc{biza2018online,
  author = {Ondrej Biza and Robert Platt},
  title = {{Online Abstraction with MDP Homomorphisms for Deep Learning}},
  year = {2018},
  eprint = {1811.12929},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.12929},
}
Figure