mlsanityData to 7 Oct 2026

Scalable methods for computing state similarity in deterministic Markov Decision Processes

arXiv 1911.09291 ↗First posted 21 Nov 2019cs.LG cs.AI stat.MLcited by 133

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 23; 2022: 23; 2023: 18; 2024: 17; 2025: 20; 2026: 31.

133 papers.

Sort:

By area:

  1. 2023Learning Interactive Real-World Simulatorscited by 440
  2. 2022Masked World Models for Visual Controlcited by 169
  3. 2021Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learningcited by 123
  4. 2020Primal Wasserstein Imitation Learningcited by 120
  5. 2023Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learningcited by 116
  6. 2022Reinforcement Learning with Action-Free Pre-Training from Videoscited by 107
  7. 2022Denoised MDPs: Learning World Models Better Than the World Itselfcited by 66
  8. 2021Towards Robust Bisimulation Metric Learningcited by 49
  9. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
  10. 2021MICo: Improved representations via sampling-based state similarity for Markov decision processescited by 43
  11. 2021Learning Markov State Abstractions for Deep Reinforcement Learningcited by 42
  12. 2023Proto-Value Networks: Scaling Representation Learning with Auxiliary Taskscited by 41
38 more
  1. 2025Towards General-Purpose Model-Free Reinforcement Learningcited by 40
  2. 2022Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learningcited by 38
  3. 2021Return-Based Contrastive Representation Learning for Reinforcement Learningcited by 36
  4. 2021Provable Representation Learning for Imitation with Contrastive Fourier Featurescited by 34
  5. 2021Proper Value Equivalencecited by 33
  6. 2021Action-Sufficient State Representation Learning for Control with Structural Constraintscited by 31
  7. 2021Offline Reinforcement Learning with Pseudometric Learningcited by 28
  8. 2022Curriculum Reinforcement Learning using Optimal Transport via Gradual Domain Adaptationcited by 28
  9. 2021Metrics and continuity in reinforcement learningcited by 26
  10. 2021Value Function Spaces: Skill-Centric State Abstractions for Long-Horizon Reasoningcited by 25
  11. 2026World-Gymnast: Training Robots with Reinforcement Learning in a World Modelcited by 25
  12. 2021Learning Representations for Pixel-based Control: What Matters and Why?cited by 24
  13. 2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
  14. 2022Continuous MDP Homomorphisms and Homomorphic Policy Gradientcited by 24
  15. 2023Learning World Models with Identifiable Factorizationcited by 23
  16. 2021Cross-Trajectory Representation Learning for Zero-Shot Generalization in RLcited by 20
  17. 2024Learning Latent Dynamic Robust Representations for World Modelscited by 20
  18. 2021When Is Generalizable Reinforcement Learning Tractable?cited by 19
  19. 2022Transfer RL across Observation Feature Spaces via Model-Based Regularizationcited by 18
  20. 2022Unsupervised Representation Learning in Deep Reinforcement Learning: A Reviewcited by 18
  21. 2021Improving Zero-shot Generalization in Offline Reinforcement Learning using Generalized Similarity Functionscited by 17
  22. 2025A Survey of State Representation Learning for Deep Reinforcement Learningcited by 17
  23. 2022Learning Task-relevant Representations for Generalization via Characteristic Functions of Reward Sequence Distributionscited by 15
  24. 2022Model-based Trajectory Stitching for Improved Offline Reinforcement Learningcited by 15
  25. 2021SimSR: Simple Distance-based State Representation for Deep Reinforcement Learningcited by 14
  26. 2026Sensorimotor World Models: Perception for Action via Inverse Dynamicscited by 14
  27. 2023Robust Representation Learning by Clustering with Bisimulation Metrics for Visual Reinforcement Learning with Distractionscited by 13
  28. 2025Dual Goal Representationscited by 13
  29. 2023Principal-Agent Reward Shaping in MDPscited by 12
  30. 2021MDPFuzz: Testing Models Solving Markov Decision Processescited by 11
  31. 2022Approximate Policy Iteration with Bisimulation Metricscited by 11
  32. 2022Learning on the Job: Self-Rewarding Offline-to-Online Finetuning for Industrial Insertion of Novel Connectors from Visioncited by 11
  33. 2026Learning Invariant Visual Representations for Planning with Joint-Embedding Predictive World Modelscited by 11
  34. 2021Adjacency constraint for efficient hierarchical reinforcement learningcited by 10
  35. 2023Bad Habits: Policy Confounding and Out-of-Trajectory Generalization in RLcited by 10
  36. 2023Understanding and Addressing the Pitfalls of Bisimulation-based Representations in Offline Reinforcement Learningcited by 10
  37. 2022BATS: Best Action Trajectory Stitchingcited by 9
  38. 2023Policy Gradient Methods in the Presence of Symmetries and State Abstractionscited by 8

50 most cited of 133 All 133 (JSON)