Abstract
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.
Introduction: The Asymmetry of the Real World
Standard machine learning often relies on the assumption of symmetry: the distance from point A to point B is the same as from B to A. However, many real-world systems are fundamentally asymmetric. Walking uphill is harder than walking downhill; a citation graph only points backward in time; and in reinforcement learning, the cost to reach a goal state is rarely equal to the cost of returning.
These asymmetric distances are formally known as quasimetrics. A quasimetric $d(x, y)$ must satisfy the triangle inequality ($d(x, z) \leq d(x, y) + d(y, z)$) and the identity of indiscernibles ($d(x, y) = 0 \iff x = y$), but it does not require $d(x, y) = d(y, x)$.
The Failure of Unconstrained Learning
A critical finding of this research is that standard neural networks, such as unconstrained Multi-Layer Perceptrons (MLPs), are fundamentally ill-equipped to learn quasimetrics. The authors identify a class of "Orthogonal Equivariant" (OrthEquiv) algorithms that treat input pairs as generic concatenated vectors. Because these models lack structural priors, they struggle to distinguish between certain asymmetric configurations. Even if they fit the training data perfectly, they often produce "distances" that violate the triangle inequality on unseen pairs, leading to poor generalization in downstream tasks like path planning.
Poisson Quasimetric Embedding (PQE)
To address these limitations, the authors introduce Poisson Quasimetric Embedding (PQE). Instead of trying to regularize a standard network into behaving like a quasimetric, PQE defines the distance function such that it is a valid quasimetric by construction.
The core logic of PQE is based on a "race" between Poisson processes. It defines distance based on the probability of one process winning against another. Crucially, PQE is fully differentiable, allowing it to be optimized using standard gradient descent, and is a universal approximator for any quasimetric.
Experimental Evaluation
The effectiveness of PQE was tested across a variety of domains, including random directed graphs, the large-scale Berkeley-Stanford Web Graph, and offline Q-learning in a custom "Gridworld with one-way doors."
In the 3-element toy space, PQE remained within valid bounds defined by the triangle inequality, whereas MLPs significantly underestimated distances. In the Gridworld environment, PQE-based agents demonstrated superior sample efficiency, reaching a 90%+ success rate much faster than agents using standard unconstrained value functions. This suggests that incorporating the geometric structure of the environment directly into the model architecture provides a powerful inductive bias for reinforcement learning.
Conclusion
The transition from symmetric metrics to asymmetric quasimetrics is essential for modeling the real world accurately. By identifying the inherent flaws in unconstrained models and proposing the PQE framework, this work provides a robust foundation for learning in directed spaces. Future work may extend these principles to causal inference and complex robotic control, where asymmetry is a defining characteristic of the problem space.
Summary updated