Decision Tree Methods for Finding Reusable MDP Homomorphisms

Alicia P. Wolfe, Andrew G. BartoAAAI 2006

Decision Tree Methods for Finding Reusable MDP Homomorphisms

Abstract

Reinforcement learning agents in complex environments often face the "curse of dimensionality," where the state space is too large for efficient exploration. This paper presents a novel algorithm that learns compact, reusable state abstractions by integrating the data efficiency of the UTree algorithm with the formal framework of Markov Decision Process (MDP) homomorphisms. By focusing on environmental dynamics rather than task-specific rewards, the method discovers symmetries that allow agents to transfer knowledge across multiple related tasks.

Bridging the Gap in State Abstraction

In Reinforcement Learning (RL), state abstraction is a critical technique for grouping similar states to simplify the learning problem. However, existing approaches often face a trade-off between formal rigor and practical flexibility. MDP homomorphisms provide a robust framework for finding environment symmetries but typically require prior knowledge of the full transition and reward models. Conversely, value-based methods like UTree learn abstractions directly from experience but produce "brittle" models that must be relearned if the agent's goal changes.

The authors propose a middle ground: an algorithm that learns compact abstractions from sample data while ensuring they are based on the underlying dynamics of the environment. This makes the resulting models reusable across different reward functions.

Learning CMP Homomorphisms

The core of the approach is the discovery of Controlled Markov Process (CMP) homomorphisms. A CMP is an MDP without a fixed reward function, characterized instead by an "output function" (e.g., sensor data or coordinates).

Figure 1: (a) Mapping a base CMP to an abstract CMP based on output functions (Y). (b) A partitioned state space for an integer counter (mod 8) demonstrating action recoding (g).

The algorithm introduces several key innovations:

  1. The Splitting Criterion: Unlike standard UTree, which splits nodes to predict $Q$-values, this algorithm splits nodes to better predict the current output function and the label of the next abstract state.
  2. Iterative Refinement: The process involves two loops. An inner loop builds the decision tree based on current state labels, while an outer loop updates these labels based on the new tree structure. This continues until state transitions become consistent and Markovian.
  3. Action Recoding: The method identifies "action symmetries," where different actions in different states are functionally identical. As shown in Figure 1(b), the algorithm learns to map these actions to a unified set of abstract actions ($a_1, a_2$).

Experimental Evaluation

The researchers tested the algorithm on two simulated environments:

  • Integer Counter: A 10-bit binary counter (1024 states) where the agent predicts specific bits. This tested the ability to ignore irrelevant high-order bits and find symmetries.
  • Blocks World: A classic benchmark where the agent moves colored blocks. This tested the handling of relational features and the ability to ignore "noise," such as the colors of blocks irrelevant to the current goal.

Key Results and Insights

The CMP algorithm demonstrated significant advantages in transfer learning. In the Counter experiment, the abstraction was successfully reused across 10 different tasks. While traditional methods like UTree had to relearn from scratch for every new goal, the CMP approach maintained high performance with minimal refinement dips.

Furthermore, the algorithm achieved remarkable model compactness. In the Blocks World, it reduced a massive state space to approximately 60 abstract states by correctly ignoring non-essential block colors and pile indices. By focusing on dynamics over rewards, the agent builds a map of "how the world works," which is inherently more robust to sparse rewards and environmental noise than value-based abstractions.

Future Directions

While promising, the authors note that the algorithm's performance depends on the initial set of features provided and the significance thresholds used for splitting. Future work will explore autonomous feature discovery and optimal sampling policies to further enhance the speed and quality of abstraction learning in real-world scenarios.

Summary updated

BibTeX
@inproceedings{wolfe2006decision,
  author = {Alicia P. Wolfe and Andrew G. Barto},
  title = {{Decision Tree Methods for Finding Reusable MDP Homomorphisms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure