Sergio Calo, Anders Jonsson, Gergely Neu, Ludovic Schwartz and Javier Segovia-Aguas (2024), Advances in Neural Information Processing Systems 37 (NeurIPS 2024).
Key takeaways
From the reading, NOTE-757.
- Bisimulation metrics are bicausal transport costs. In a bicausal coupling, given the joint past, each chain’s next state keeps its own law. For finite action-free chains with real labels, the bisimulation metric is the unique solution of U(xy) = (1−γ)|r(x)−r(y)| + γ inf over couplings p of P_X(·|x) and P_Y(·|y) of Σ p U. That is the Bellman equation of transport over bicausal couplings with that ground cost, so the two coincide (§2.2). The step is a comparison of two fixed points. The metric’s equality with its logical definition is van Breugel and Worrell’s theorem, cited.
- A finite LP (Lemma 1, Theorem 1). The discounted frequencies of state-pair transitions under a coupling are characterised exactly by a flow constraint and two coherence constraints. The transport cost is 1/(1−γ) times the minimum of ⟨µ, c⟩ over that polytope, with |X|²|Y|² variables.
- Sinkhorn Value Iteration. Mirror descent with a conditional-entropy regulariser, projecting alternately onto the two coherence sets, gets within ε after 324‖c‖²∞ log(|X||Y|)/((1−γ)⁵ε²) iterations (Theorem 2). That holds only if each inner soft-Bellman fixed point is solved exactly. With one inner step it still converges in experiments, and is up to ten times faster than earlier solvers, mostly through warm starts.
- Limits. There are no actions, γ < 1, and the kernels are known. The only statement relating bisimulation to trace distance is Bian and Abate’s, cited: near-bisimilar implies close finite-trace distributions, and the converse is not shown.
Standing in the record
Filed on 2026-10-12 from the owner’s papers-feed for QUESTION-008, and read
on 2026-10-14 in NOTE-757. The reading confirms the claim it was filed
for, that bisimulation metrics are optimal-transport distances between
Markov chains, and narrows it. The chains have real-valued labels and no
actions, so this is the formal object of approximate bisimulation for
action-free processes. A communicative system driven by utterances is
not covered. The paper also gives no judgement that observational
equivalence (TERM-033) gets wrong and bisimulation gets right, which is
what QUESTION-008 says an answer must name. The identification and the LP
are filed as THEORY-247, with no answers: relation, since the
question is Deferred. Its sequel, LIT-948, makes the same quantity
estimable from samples. The anthology-candidate flag stays: the paper’s
motivation is representation learning in reinforcement learning, though
the reading carries no instruction for practice.