# A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications

arXiv: https://arxiv.org/abs/2509.18714 · HTML: https://mlsanity.com/paper/2509.18714/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 23 Sep 2025.

## Builds on (most cited first, 6 of 6)

- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Towards Robust Bisimulation Metric Learning](https://mlsanity.com/paper/2110.14096/) (2021)
- [Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2204.13060/) (2022)
- [Understanding and Addressing the Pitfalls of Bisimulation-based Representations in Offline Reinforcement Learning](https://mlsanity.com/paper/2310.17139/) (2023)
- [ExTra: Transfer-guided Exploration](https://mlsanity.com/paper/1906.11785/) (2019)

## Built on by (most cited first, 4 of 4)

- [A Theoretical Analysis of State Similarity Between Markov Decision Processes](https://mlsanity.com/paper/2512.17265/) (2025)
- [TERRA: Task-Embedded Reasoning and Representation Architecture for Cross-Domain Applications](https://mlsanity.com/paper/2606.01520/) (2026)
- [Compositional Behavioral Semantics for State Abstraction in Reinforcement Learning](https://mlsanity.com/paper/2606.25357/) (2026)
- [BIFROST: Bridging Invariant Feature Representation for Observation-space Sim2Real Transfer](https://mlsanity.com/paper/2607.01410/) (2026)

## Abstract (arXiv)

The bisimulation metric (BSM) is a powerful tool for computing state similarities within a Markov decision process (MDP), revealing that states closer in BSM have more similar optimal value functions. While BSM has been successfully utilized in reinforcement learning (RL) for tasks like state representation learning and policy exploration, its application to multiple-MDP scenarios, such as policy transfer, remains challenging. Prior work has attempted to generalize BSM to pairs of MDPs, but a lack of rigorous analysis of its mathematical properties has limited further theoretical progress. In this work, we formally establish a generalized bisimulation metric (GBSM) between pairs of MDPs, which is rigorously proven with the three fundamental properties: GBSM symmetry, inter-MDP triangle inequality, and the distance bound on identical state spaces. Leveraging these properties, we theoretically analyse policy transfer, state aggregation, and sampling-based estimation in MDPs, obtaining explicit bounds that are strictly tighter than those derived from the standard BSM. Additionally, GBSM provides a closed-form sample complexity for estimation, improving upon existing asymptotic results based on BSM. Numerical results validate our theoretical findings and demonstrate the effectiveness of GBSM in multi-MDP scenarios.