# On the Learning and Learnability of Quasimetrics

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 66 references that are in the map.
- First posted on arXiv 30 Jun 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Deep metric learning using Triplet network](https://mlsanity.com/paper/1412.6622/) (2014)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [An efficient framework for learning sentence representations](https://mlsanity.com/paper/1803.02893/) (2018)
- [Learning Fine-grained Image Similarity with Deep Ranking](https://mlsanity.com/paper/1404.4661/) (2014)
- [Hyperbolic Entailment Cones for Learning Hierarchical Embeddings](https://mlsanity.com/paper/1804.01882/) (2018)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Order-Embeddings of Images and Language](https://mlsanity.com/paper/1511.06361/) (2015)
- [On the Similarity between the Laplace and Neural Tangent Kernels](https://mlsanity.com/paper/2007.01580/) (2020)
- [The Emergence of Spectral Universality in Deep Networks](https://mlsanity.com/paper/1802.09979/) (2018)
- [Model-Based Visual Planning with Self-Supervised Functional Distances](https://mlsanity.com/paper/2012.15373/) (2020)
- [An Inductive Bias for Distances: Neural Nets that Respect the Triangle Inequality](https://mlsanity.com/paper/2002.05825/) (2020)
- [Hyperbolic Disk Embeddings for Directed Acyclic Graphs](https://mlsanity.com/paper/1902.04335/) (2019)
- [The Stochastic Shortest Path Problem : A polyhedral combinatorics perspective](https://mlsanity.com/paper/1702.03186/) (2017)
- [Shortest path distance approximation using deep learning techniques](https://mlsanity.com/paper/2002.05257/) (2020)
- [Multidimensional Dominance Drawings](https://mlsanity.com/paper/1906.09224/) (2019)
- [Nested Subspace Arrangement for Representation of Relational Data](https://mlsanity.com/paper/2007.02007/) (2020)

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

- [Optimal Goal-Reaching Reinforcement Learning via Quasimetric Learning](https://mlsanity.com/paper/2304.01203/) (2023)
- [Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making](https://mlsanity.com/paper/2406.17098/) (2024)
- [Temporal Straightening for Latent Planning](https://mlsanity.com/paper/2603.12231/) (2026)
- [Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings](https://mlsanity.com/paper/2211.15120/) (2022)
- [Horizon Generalization in Reinforcement Learning](https://mlsanity.com/paper/2501.02709/) (2025)
- [Physics-informed Temporal Difference Metric Learning for Robot Motion Planning](https://mlsanity.com/paper/2505.05691/) (2025)
- [Temporal Distance-aware Transition Augmentation for Offline Model-based Reinforcement Learning](https://mlsanity.com/paper/2505.13144/) (2025)
- [State Chrono Representation for Enhancing Generalization in Reinforcement Learning](https://mlsanity.com/paper/2411.06174/) (2024)
- [Quasimetric Value Functions with Dense Rewards](https://mlsanity.com/paper/2409.08724/) (2024)
- [Compositional Transduction with Latent Analogies for Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2605.20609/) (2026)
- [QuasiNav: Asymmetric Cost-Aware Navigation Planning with Constrained Quasimetric Reinforcement Learning](https://mlsanity.com/paper/2410.16666/) (2024)
- [GOSPA and T-GOSPA quasi-metrics for evaluation of multi-object tracking algorithms](https://mlsanity.com/paper/2507.13706/) (2025)
- [From Connectivity to Rewards: Dense Reward Learning with Directed State Graphs](https://mlsanity.com/paper/2609.10781/) (2026)
- [ChronoSRL: Temporal Geometry for Self-Supervised Reinforcement Learning](https://mlsanity.com/paper/2609.36238/) (2026)
- [Do Better Goal Representations Improve Goal-Conditioned Reinforcement Learning?](https://mlsanity.com/paper/2609.39901/) (2026)

## Abstract (arXiv)

Our world is full of asymmetries. Gravity and wind can make reaching a place easier than coming back. Social artifacts such as genealogy charts and citation graphs are inherently directed. In reinforcement learning and control, optimal goal-reaching strategies are rarely reversible (symmetrical). Distance functions supported on these asymmetrical structures are called quasimetrics. Despite their common appearance, little research has been done on the learning of quasimetrics. Our theoretical analysis reveals that a common class of learning algorithms, including unconstrained multilayer perceptrons (MLPs), provably fails to learn a quasimetric consistent with training data. In contrast, our proposed Poisson Quasimetric Embedding (PQE) is the first quasimetric learning formulation that both is learnable with gradient-based optimization and enjoys strong performance guarantees. Experiments on random graphs, social graphs, and offline Q-learning demonstrate its effectiveness over many common baselines.