Scalable methods for computing state similarity in deterministic Markov Decision Processes

By Pablo Samuel Castro. 2019

184 citations recorded by the source corpus.

We present new algorithms for computing and approximating bisimulation metrics in Markov Decision Processes (MDPs). Bisimulation metrics are an elegant formalism that capture behavioral equivalence between states and provide strong theoretical guarantees on differences in optimal behaviour. Unfortunately, their computation is expensive and requires a tabular representation of the states, which has thus far rendered them impractical for large problems. In this paper we present a new version of the metric that is tied to a behavior policy in an MDP, along with an analysis of its theoretical properties. We then present two new algorithms for approximating bisimulation metrics in large, deterministic MDPs. The first does so via sampling and is guaranteed to converge to the true metric. The second is a differentiable loss which allows us to learn an approximation even for continuous state MDPs, which prior to this work had not been possible.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Software

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Software

Citations in the corpus

Provable Representation Learning for Imitation with Contrastive Fourier Features (2021, background): “Of these approaches, bisimulation is the most theoretically mature [17, 13], and several recent works apply bisimulation principles to derive practical representation learning objectives [20, 41, 6].”
Structural Similarity for Improved Transfer in Reinforcement Learning (2022, unknown): “[6] expanded upon the preexisting bisimulation metrics by creating two metrics that are less computationally intensive, with one having guaranteed convergence and the other being able to learn an approximation for continuous state MDPs.”
Offline Reinforcement Learning with Pseudometric Learning (2021, methodology): “Learning a bisimulation metric online (Castro, 2020; Comanici et al., 2012) has been shown to be beneficial to learn controllable representations that eliminates unnecessary details of the state (Zhang et al., 2021) or can be used as an auxiliary loss which leads to improvement performance on the…”
The Value Equivalence Principle for Model-Based Reinforcement Learning (2020, background): “More broadly, other notions of equivalence between MDPs have been proposed in the literature [12, 28, 20, 31, 17, 23, 41, 29, 8, 42].”
Learning Markov State Abstractions for Deep Reinforcement Learning (2021, background): “While bisimulation-based approaches have historically been computationally expensive and difficult to scale, recent work has started to change that (Castro, 2020; Lehnert & Littman, 2020; Van der Pol et al., 2020; Biza et al., 2021).”
Learning Interactive Real-World Simulators (2023, background): “Most systems choose to learn one dynamics model per system in the lower dimensional state space as opposed to in the pixel space [54, 55, 56, 57], which, despite being a simpler modeling problem, limits knowledge sharing across systems.”
Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learning (2022, methodology): “For this reason, Bisimulation Metrics (Ferns et al., 2011; Ferns and Precup, 2014; Castro, 2020) softens the concept of state partitions, and instead deﬁnes a pseudometric space ( , d ) , where a distance function d : S × S (cid:55)→ ≥ 0 measures the “behavioral similarity” between two states 1 .”
Value Function Spaces: Skill-Centric State Abstractions for Long-Horizon Reasoning (2021, methodology): “, 2019) and representing state similarity using the bisimulation metric (Castro, 2020; Zhang et al., 2021a; Agarwal et al., 2021).”
Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning (2021, background): “…a wide variety of approaches including standard regularization (Fare-brother et al., 2018; Cobbe et al., 2019), bisimulation (Castro & Precup, 2010; Castro, 2020; Zhang et al., 2021), out-of-distribution generalization (Arjovsky et al., 2019) and state-of-the-art data augmentation (Kostrikov et…”