Bisimulation Metrics are Optimal Value Functions

Norman Ferns 1 Doina Precup 2
1 ANTIQUE - Analyse Statique par Interprétation Abstraite
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt
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.
Type de document :
Communication dans un congrès
Nevin L. Zhang; Jin Tian. The 30th Conference on Uncertainty in Artificial Intelligence, Jul 2014, Quebec City, Canada. AUAI Press, pp.10, 〈http://auai.org/uai2014/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01101180
Contributeur : Jérôme Feret <>
Soumis le : jeudi 8 janvier 2015 - 09:23:32
Dernière modification le : vendredi 25 mai 2018 - 12:02:07

Identifiants

  • HAL Id : hal-01101180, version 1

Collections

Citation

Norman Ferns, Doina Precup. Bisimulation Metrics are Optimal Value Functions. Nevin L. Zhang; Jin Tian. The 30th Conference on Uncertainty in Artificial Intelligence, Jul 2014, Quebec City, Canada. AUAI Press, pp.10, 〈http://auai.org/uai2014/〉. 〈hal-01101180〉

Partager

Métriques

Consultations de la notice

86