Behavioral Pseudometrics for Probabilistic Systems

92 concepts56 papers1 proposal

In traditional formal methods, two systems are either equivalent or they are not. This binary view is governed by bisimulation, a rigorous notion of behavioral identity: two states are bisimilar if they can match each other's transitions and land in states that are again bisimilar. However, in probabilistic and quantitative systems, this "all-or-nothing" approach is notoriously brittle. A tiny change in a transition probability—say, from $0.5$ to $0.5001$—breaks exact bisimulation entirely, even though the systems remain nearly identical in practice.

To solve this, researchers have developed behavioral pseudometrics. Instead of a binary "yes/no," these metrics assign a real number between 0 and 1 to represent the "distance" between two states. As Desharnais et al. established in their foundational work, a distance of zero corresponds exactly to traditional bisimulation, while larger values quantify the degree of behavioral divergence.

The Recursive Logic of Distance

The core intuition behind these metrics is that state similarity is recursive. Two states are close if:

  1. Their immediate outputs (or rewards) are similar.
  2. Their future transitions lead to states that are also close.

This recursive structure is typically captured as the fixed point of a functional operator. For Markov Decision Processes (MDPs), Ferns et al. defined this distance by combining the difference in immediate rewards with a discounted measure of the distance between transition probability distributions.

To compare these distributions, the framework often relies on the Kantorovich (or Wasserstein) metric. This metric views the transition probabilities as "piles of dirt" and calculates the minimum work required to transform one distribution into the other, where the "cost" of moving probability mass is determined by the distance between the destination states. This creates a mutually reinforcing definition: the distance between states depends on the distance between their distributions, which in turn depends on the distance between the states they transition to.

Robustness and Performance Bounds

The primary value of a metric over an equivalence relation is robustness. In real-world applications like robotics or finance, models are often approximations derived from noisy data. Feng et al. and Jansen et al. argue that quantitative metrics provide a noise-tolerant alternative to binary equivalence, ensuring that small numerical perturbations in transition probabilities lead to only proportional changes in the measured distance.

This robustness has a direct impact on system performance. Majumdar et al. demonstrated that these metrics provide a fundamental bound on the difference in long-term rewards between states. If two states are close in the metric space, they are guaranteed to yield similar optimal values. This property allows for state aggregation: Ferns et al. showed that one can compress massive, continuous state spaces by grouping together states with small distances, providing theoretical guarantees that the simplified model will behave like the original.

Logical and Temporal Perspectives

The connection between distance and logic provides another layer of intuition. In classical logic, two states are bisimilar if they satisfy the exact same set of formulas. In the quantitative setting, this is replaced by real-valued modal logic.

Thrane and Fahrenberg proved that the difference in how much two states satisfy a quantitative formula is bounded by their bisimulation distance. Essentially, the metric measures the maximum possible difference in "satisfaction level" across all possible logical properties. Mardare extended this to approximate reasoning, showing that if a sequence of model approximations converges in the metric space, the logical properties of those approximations also converge to the properties of the limit system.

Beyond Discrete Time

While much of the early work focused on discrete-time systems, the field has expanded to more complex domains:

  • Continuous Time: Chen et al. developed pseudometrics for continuous-time Markov processes, replacing step-by-step comparisons with a supremum of discounted distances across an infinite timeline.
  • Weighted Automata: Balle et al. formulated behavioral distance as a seminorm on state spaces, allowing for the comparison of systems that process infinite input strings.
  • Inter-MDP Comparison: Moving beyond comparing states within a single system, Tao et al. introduced metrics that satisfy the triangle inequality across different environments, facilitating better policy transfer in reinforcement learning.

By shifting from the rigid constraints of bisimulation to the flexible geometry of pseudometrics, this research direction provides the mathematical tools necessary to reason about systems that are "close enough" to be useful, even if they aren't perfectly identical.

Key Foundational Work

Bisimulation indexes and their applications (2002) — contributed 3 concept elements to this direction.
Metrics for Labeled Markov Systems (1999) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 60 papers
  2. Version 1 · 2026-10-04 · 42 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_quantitative_bisimulation_33db5cb7,
  title = {quantitative bisimulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantitative-bisimulation/rdr_33db5cb7310040ff9c7969746e1c4ed4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_quantitative_bisimulation_33db5cb7_v2,
  title = {quantitative bisimulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantitative-bisimulation/rdr_33db5cb7310040ff9c7969746e1c4ed4/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake