# Scalable methods for computing state similarity in deterministic Markov Decision Processes

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

## Key facts

- Cited by 133 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2019.

## Built on by (most cited first, 30 of 133)

- [Learning Interactive Real-World Simulators](https://mlsanity.com/paper/2310.06114/) (2023)
- [Masked World Models for Visual Control](https://mlsanity.com/paper/2206.14244/) (2022)
- [Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2101.05265/) (2021)
- [Primal Wasserstein Imitation Learning](https://mlsanity.com/paper/2006.04678/) (2020)
- [Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning](https://mlsanity.com/paper/2304.01203/) (2023)
- [Reinforcement Learning with Action-Free Pre-Training from Videos](https://mlsanity.com/paper/2203.13880/) (2022)
- [Denoised MDPs: Learning World Models Better Than the World Itself](https://mlsanity.com/paper/2206.15477/) (2022)
- [Making Linear MDPs Practical via Contrastive Representation Learning](https://mlsanity.com/paper/2207.07150/) (2022)
- [Towards Robust Bisimulation Metric Learning](https://mlsanity.com/paper/2110.14096/) (2021)
- [Learning Markov State Abstractions for Deep Reinforcement Learning](https://mlsanity.com/paper/2106.04379/) (2021)
- [MICo: Improved representations via sampling-based state similarity for Markov decision processes](https://mlsanity.com/paper/2106.08229/) (2021)
- [Proto-Value Networks: Scaling Representation Learning with Auxiliary Tasks](https://mlsanity.com/paper/2304.12567/) (2023)
- [Towards General-Purpose Model-Free Reinforcement Learning](https://mlsanity.com/paper/2501.16142/) (2025)
- [Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2204.13060/) (2022)
- [Return-Based Contrastive Representation Learning for Reinforcement Learning](https://mlsanity.com/paper/2102.10960/) (2021)
- [Provable Representation Learning for Imitation with Contrastive Fourier Features](https://mlsanity.com/paper/2105.12272/) (2021)
- [Proper Value Equivalence](https://mlsanity.com/paper/2106.10316/) (2021)
- [Action-Sufficient State Representation Learning for Control with Structural Constraints](https://mlsanity.com/paper/2110.05721/) (2021)
- [Offline Reinforcement Learning with Pseudometric Learning](https://mlsanity.com/paper/2103.01948/) (2021)
- [Curriculum Reinforcement Learning using Optimal Transport via Gradual Domain Adaptation](https://mlsanity.com/paper/2210.10195/) (2022)
- [Continuous MDP Homomorphisms and Homomorphic Policy Gradient](https://mlsanity.com/paper/2209.07364/) (2022)
- [World-Gymnast: Training Robots with Reinforcement Learning in a World Model](https://mlsanity.com/paper/2602.02454/) (2026)
- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [Value Function Spaces: Skill-Centric State Abstractions for Long-Horizon Reasoning](https://mlsanity.com/paper/2111.03189/) (2021)
- [Learning Representations for Pixel-based Control: What Matters and Why?](https://mlsanity.com/paper/2111.07775/) (2021)
- [A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning](https://mlsanity.com/paper/2111.11485/) (2021)
- [Learning World Models with Identifiable Factorization](https://mlsanity.com/paper/2306.06561/) (2023)
- [Learning Latent Dynamic Robust Representations for World Models](https://mlsanity.com/paper/2405.06263/) (2024)
- [When Is Generalizable Reinforcement Learning Tractable?](https://mlsanity.com/paper/2101.00300/) (2021)
- [Cross-Trajectory Representation Learning for Zero-Shot Generalization in RL](https://mlsanity.com/paper/2106.02193/) (2021)

## Abstract (arXiv)

We present new algorithms for computing and approximating bisimulation metrics in Markov Decision Processes (MDPs). Bisimulation metrics are an elegant formalism that capture behavioral equivalence between states and provide strong theoretical guarantees on differences in optimal behaviour. Unfortunately, their computation is expensive and requires a tabular representation of the states, which has thus far rendered them impractical for large problems. In this paper we present a new version of the metric that is tied to a behavior policy in an MDP, along with an analysis of its theoretical properties. We then present two new algorithms for approximating bisimulation metrics in large, deterministic MDPs. The first does so via sampling and is guaranteed to converge to the true metric. The second is a differentiable loss which allows us to learn an approximation even for continuous state MDPs, which prior to this work had not been possible.