# A Theoretical Analysis of State Similarity Between Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 43 references that are in the map.
- First posted on arXiv 19 Dec 2025.

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

- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2101.05265/) (2021)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [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)
- [Offline Reinforcement Learning with Pseudometric Learning](https://mlsanity.com/paper/2103.01948/) (2021)
- [Active Exploration in Markov Decision Processes](https://mlsanity.com/paper/1902.11199/) (2019)
- [Scalable First-Order Methods for Robust MDPs](https://mlsanity.com/paper/2005.05434/) (2020)
- [Robust Representation Learning by Clustering with Bisimulation Metrics for Visual Reinforcement Learning with Distractions](https://mlsanity.com/paper/2302.12003/) (2023)
- [Approximate Policy Iteration with Bisimulation Metrics](https://mlsanity.com/paper/2202.02881/) (2022)
- [Understanding and Addressing the Pitfalls of Bisimulation-based Representations in Offline Reinforcement Learning](https://mlsanity.com/paper/2310.17139/) (2023)
- [Bisimulation metric for Model Predictive Control](https://mlsanity.com/paper/2410.04553/) (2024)
- [True-data Testbed for 5G/B5G Intelligent Network](https://mlsanity.com/paper/2011.13152/) (2020)
- [Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observations](https://mlsanity.com/paper/2306.01243/) (2023)
- [A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications](https://mlsanity.com/paper/2509.18714/) (2025)

## Abstract (arXiv)

The bisimulation metric (BSM) is a powerful tool for analyzing 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 state similarity between multiple MDPs remains challenging. Prior work has attempted to extend BSM to pairs of MDPs, but a lack of well-established mathematical properties has limited further theoretical analysis between MDPs. In this work, we formally establish a generalized bisimulation metric (GBSM) for measuring state similarity between arbitrary pairs of MDPs, which is rigorously proven with three fundamental metric properties, i.e., GBSM symmetry, inter-MDP triangle inequality, and a distance bound on identical spaces. Leveraging these properties, we theoretically analyze policy transfer, state aggregation, and sampling-based estimation across MDPs, obtaining explicit bounds that are strictly tighter than existing ones 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.