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 equiva- lence on the states of a transition system. Its defi- nition has been extended to Markov decision pro- cesses, 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 opti- mal coupling of two copies of the original model. We prove the result in the general case of con- tinuous state spaces. This result has important implications in understanding the complexity of computing such metrics, and opens up the possi- bility 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 equiva- lence on the states of a transition system. Its defi- nition has been extended to Markov decision pro- cesses, 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 opti- mal coupling of two copies of the original model. We prove the result in the general case of con- tinuous state spaces. This result has important implications in understanding the complexity of computing such metrics, and opens up the possi- bility 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 equiva- lence on the states of a transition system. Its defi- nition has been extended to Markov decision pro- cesses, 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 opti- mal coupling of two copies of the original model. We prove the result in the general case of con- tinuous state spaces. This result has important implications in understanding the complexity of computing such metrics, and opens up the possi- bility 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