Bisimulation Metrics are Optimal Value Functions

Norm Ferns École Normale Supérieure, Doina Precup
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:332-341, 2014.

Abstract

Bisimulation is a notion of behavioural equivalence on the states of a transition system. Its definition has been extended to Markov decision processes, where it can be used to aggregate states. A bisimulation metric is a quantitative analog of bisimulation that measures how similar states are from a the perspective of long-term behavior. Bisimulation metrics have been used to establish approximation bounds for state aggregation and other forms of value function approximation. In this paper, we prove that a bisimulation metric defined on the state space of a Markov decision process is the optimal value function of an optimal coupling of two copies of the original model. We prove the result in the general case of continuous state spaces. This result has important implications in understanding the complexity of computing such metrics, and opens up the possibility of more efficient computational methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-superieure14a, title = {Bisimulation Metrics are Optimal Value Functions}, author = {Sup{\'e}rieure, Norm Ferns {\'E}cole Normale and Precup, Doina}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {332--341}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/superieure14a/superieure14a.pdf}, url = {https://proceedings.mlr.press/r12/superieure14a.html}, abstract = {Bisimulation is a notion of behavioural equivalence on the states of a transition system. Its definition has been extended to Markov decision processes, where it can be used to aggregate states. A bisimulation metric is a quantitative analog of bisimulation that measures how similar states are from a the perspective of long-term behavior. Bisimulation metrics have been used to establish approximation bounds for state aggregation and other forms of value function approximation. In this paper, we prove that a bisimulation metric defined on the state space of a Markov decision process is the optimal value function of an optimal coupling of two copies of the original model. We prove the result in the general case of continuous state spaces. This result has important implications in understanding the complexity of computing such metrics, and opens up the possibility of more efficient computational methods.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Bisimulation Metrics are Optimal Value Functions %A Norm Ferns École Normale Supérieure %A Doina Precup %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-superieure14a %I PMLR %P 332--341 %U https://proceedings.mlr.press/r12/superieure14a.html %V R12 %X Bisimulation is a notion of behavioural equivalence on the states of a transition system. Its definition has been extended to Markov decision processes, where it can be used to aggregate states. A bisimulation metric is a quantitative analog of bisimulation that measures how similar states are from a the perspective of long-term behavior. Bisimulation metrics have been used to establish approximation bounds for state aggregation and other forms of value function approximation. In this paper, we prove that a bisimulation metric defined on the state space of a Markov decision process is the optimal value function of an optimal coupling of two copies of the original model. We prove the result in the general case of continuous state spaces. This result has important implications in understanding the complexity of computing such metrics, and opens up the possibility of more efficient computational methods. %Z Reissued by PMLR on 04 October 2026.
APA
Supérieure, N.F.É.N. & Precup, D.. (2014). Bisimulation Metrics are Optimal Value Functions. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:332-341 Available from https://proceedings.mlr.press/r12/superieure14a.html. Reissued by PMLR on 04 October 2026.

Related Material