Measuring Structural Similarities in Finite MDPs

Hao Wang, Shaokang Dong, Ling ShaoIJCAI 2019 · OpenReview

Abstract

In this paper, we investigate the structural similarities within a finite Markov decision process (MDP). We view a finite MDP as a heterogeneous directed bipartite graph and propose novel measures for state similarity and action similarity in a mutual reinforcement manner. We prove that the state similarity is a metric and the action similarity is a pseudometric. We also establish the connection between the proposed similarity measures and the optimal values of the MDP. Extensive experiments show that the proposed measures are effective.

Introduction

In Reinforcement Learning (RL), identifying structural similarities between states and actions is critical for tasks such as transfer learning and MDP abstraction. Transfer learning allows an agent to apply knowledge from one environment to another, while abstraction simplifies complex environments into more manageable representations.

Existing approaches, such as bisimulation metrics and MDP homomorphisms, face significant limitations. Bisimulation often fails to account for the specific roles of actions, potentially missing symmetries where different actions in different states lead to identical outcomes. Conversely, MDP homomorphisms are often too rigid for practical, noisy environments. This research addresses these gaps by proposing a similarity measure that is both flexible and mathematically rigorous.

Methodology

The proposed approach shifts from traditional algebraic views to a graph-theoretical framework. An MDP is modeled as a heterogeneous directed bipartite graph $G_M$, where nodes represent states and actions, and edges represent decisions or transitions.

Representation of an MDP as a heterogeneous directed bipartite graph $G_M$.

Recursive Similarity Measures

The core of the method is a mutually reinforcing recursive definition:

  1. State Similarity ($\sigma_S$): Two states are considered similar if the sets of actions available to them are similar. The Hausdorff distance is employed to compare these sets, ensuring the measure satisfies the properties of a mathematical metric.
  2. Action Similarity ($\sigma_A$): Two actions are similar if they yield similar immediate rewards and lead to similar future state distributions. The Earth Mover’s Distance (EMD) is used to compare these probability distributions.

This coupling ensures that the similarity of a state depends on its available actions, and the similarity of an action depends on the states it transitions into. An iterative algorithm is used to compute these values until convergence.

Theoretical Properties

The authors prove that $\sigma_S$ is a true metric (satisfying the triangle inequality), while $\sigma_A$ is a pseudometric. Crucially, they establish that the similarity distance between two states or actions provides an upper bound on the difference between their optimal values ($V^*$ and $Q^*$). This theoretical link guarantees that states identified as similar will have comparable utility for an agent.

Experimental Evaluation

The measures were evaluated using synthetic grid-world MDPs ranging from $3 \times 3$ to $33 \times 33$ grids. These environments allow for clear testing of structural symmetries, such as the equivalence of corner states.

The $3 \times 3$ grid-world state space and available actions used for symmetry testing.

Key Results

  • Symmetry Detection: In a $3 \times 3$ grid case study, the proposed measure successfully identified structural symmetries that standard bisimulation metrics failed to capture.
  • Distributional Nuance: On larger grids, the proposed measures provided a "flattened" distribution of distances. Unlike traditional metrics that often cluster distances near 1.0, this approach effectively distinguishes between varying degrees of similarity.
  • Robustness: The measures proved robust to variations in discount parameters ($C_S$ and $C_A$), which can be tuned to emphasize either reward or transition similarity.

Conclusion

This research introduces a robust, graph-based framework for measuring similarity in MDPs. By leveraging mutual reinforcement between state and action similarities, the method provides a more nuanced and theoretically grounded metric than existing alternatives. While the computational cost of EMD and Hausdorff distances presents a challenge for scaling to massive state spaces, future work involving parallelization and similarity search queries offers a path toward broader application in large-scale Reinforcement Learning.

Summary updated

Abstract

In this paper, we investigate the structural similarities within a finite Markov decision process (MDP). We view a finite MDP as a heterogeneous directed bipartite graph and propose novel measures for state similarity and action similarity in a mutual reinforcement manner. We prove that the state similarity is a metric and the action similarity is a pseudometric. We also establish the connection between the proposed similarity measures and the optimal values of the MDP. Extensive experiments show that the proposed measures are effective.
BibTeX
@inproceedings{wang2019measuring,
  author = {Hao Wang and Shaokang Dong and Ling Shao},
  title = {{Measuring Structural Similarities in Finite MDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=uwza5H32di},
}
Figure