Bisimulation through probabilistic testing (preliminary report)
By Kim Guldstrand Larsen, A. Skou. 1989
We propose a language for testing concurrent processes and examine its strength in terms of the processes that are distinguished by a test. By using probabilistic transition systems as the underlying semantic model, we show how a testing algorithm with a probability arbitrary close to 1 can distinguish processes that are not bisimulation equivalent. We also show a similar result (in a slightly stronger form) for a new process relation called 2/3-bisimulation — lying strictly between that of simulation and bisimulation. Finally, the ultimately strength of the testing language is shown to identify an even stronger process relation, called probabilistic bisimulation.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Sergey Levine
- Pieter Abbeel
- Yoshua Bengio
- Joelle Pineau
- Chelsea Finn
- Amy Zhang
- Ruslan Salakhutdinov
- Shagun Sodhani
Citations in the corpus
- Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learning (2022, methodology): “A more compact definition has a recursive form: two states are bisimilar if they share both the same immediate reward and equivalent distributions over the next bisimilar states (Larsen and Skou, 1989; Givan et al., 2003).”
- Learning Invariant Representations for Reinforcement Learning without Reconstruction (2020, background): “The strictest form, which generally preserves the most properties, is bisimulation [17].”
- Invariant Causal Prediction for Block MDPs (2020, background): “…(2006) discuss the merits of abstraction discovery as a way to solve re-lated MDPs. Bisimulation relations are a type of state abstraction that offers a mathematically precise definition of what it means for two environments to ‘share the same structure’ (Larsen and Skou, 1989; Givan et al., 2003).”