Bisimulation metrics are optimal transport distances, and can be computed efficiently

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Calo Oliveira, Sergio
• dc.contributor.author Jonsson, Anders
• dc.contributor.author Neu, Gergely
• dc.contributor.author Schwartz, Ludovic
• dc.contributor.author Segovia-Aguas, Javier
• dc.date.accessioned 2025-01-27T13:53:44Z
• dc.date.available 2025-01-27T13:53:44Z
• dc.date.issued 2024
• dc.description.abstract We propose a new framework for formulating optimal transport distances between Markov chains. Previously known formulations studied couplings between the entire joint distribution induced by the chains, and derived solutions via a reduction to dynamic programming (DP) in an appropriately defined Markov decision process. This formulation has, however, not led to particularly efficient algorithms so far, since computing the associated DP operators requires fully solving a static optimal transport problem, and these operators need to be applied numerous times during the overall optimization process. In this work, we develop an alternative perspective by considering couplings between a “flattened” version of the joint distributions that we call discounted occupancy couplings, and show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program (LP) in this reduced space. This LP formulation allows us to port several algorithmic ideas from other areas of optimal transport theory. In particular, our formulation makes it possible to introduce an appropriate notion of entropy regularization into the optimization problem, which in turn enables us to directly calculate optimal transport distances via a Sinkhorn-like method we call Sinkhorn Value Iteration (SVI). We show both theoretically and empirically that this method converges quickly to an optimal coupling, essentially at the same computational cost of running vanilla Sinkhorn in each pair of states. Along the way, we point out that our optimal transport distance exactly matches the common notion of bisimulation metrics between Markov chains, and thus our results also apply to computing such metrics, and in fact our algorithm turns out to be significantly more efficient than the best known methods developed so far for this purpose.
• dc.description.sponsorship Neu was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 950180). Anders Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR, and the Spanish grant PID2019-108141GB-I00. Javier Segovia-Aguas is supported by MCIN/AEI /10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M).
• dc.format.mimetype application/pdf
• dc.identifier.citation Calo S, Jonsson A, Neu G, Schwartz L, Segovia-Aguas J. Bisimulation metrics are optimal transport distances, and can be computed efficiently. Poster presented at: 38th Conference on Neural Information Processing Systems (NeurIPS 2024); Dec 10-15,21144; Vancouver, Canada.
• dc.identifier.doi https://doi.org/10.48550/arXiv.2406.04056
• dc.identifier.uri http://hdl.handle.net/10230/69307
• dc.language.iso eng
• dc.publisher NeurIPS
• dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/PID2019-108141GB-I00
• dc.rights © The Author
• dc.rights CC BY Attribution 4.0 International
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri http://creativecommons.org/licenses/by/4.0/
• dc.subject.keyword Optimal transport
• dc.subject.keyword Markov chains
• dc.subject.keyword Bisimulation metrics
• dc.subject.keyword Markov decision processes
• dc.title Bisimulation metrics are optimal transport distances, and can be computed efficiently
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/publishedVersion