IPAB Seminar-18/05/2023

Title: From bisimulation to learning via metrics

Abstract: In this talk I will review the concept of bisimulation and then discuss its probabilistic analogue. This was extended to systems with continuous state spaces. Surprisingly, it turned out that one could prove a striking logical characterization theorem: a theorem that pins down exactly what differences one can “see” in process behaviours when two systems are not bisimilar. However, it is questionable whether a concept like equivalence is the right one for quantitative systems. If two systems are almost, but not quite, the same, bisimulation would just say that they are not equivalent. One would like to say in some way that they are “almost” the same. Metric analogues of bisimulation were developed to capture a notion of behavioral similarity rather than outright equivalence. These ideas have been adopted by the machine learning community and a bisimulation-style metric was developed for Markov decision processes. Recent work has shown that variants of these bisimulation metrics can be useful in representation learning. I will tell the tale of this arc of ideas in as accessible a way as possible.

Prakash Panangaden School of Computer Science; McGill University Montreal Institute for Learning Algorithms and School of Informatics, University of Edinburgh