Metrics for Finite Markov Decision Processes
By N. Ferns, Prakash Panangaden, Doina Precup. 2004
373 citations recorded by the source corpus.
We present metrics for measuring the similarity of states in a finite Markov decision process (MDP). The formulation of our metrics is based on the notion of bisimulation for MDPs, with an aim towards solving discounted infinite horizon reinforcement learning tasks. Such metrics can be used to aggregate states, as well as to better structure other value function approximators (e.g., memory-based or nearest-neighbor approximators). We provide bounds that relate our metric distances to the optimal values of states in the given MDP.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Reinforcement Learning, Game & Decision Theory
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
- Sergey Levine
- Pieter Abbeel
- Yoshua Bengio
- Ofir Nachum
- Chelsea Finn
- Ruslan Salakhutdinov
- Mohit Bansal
- Joelle Pineau
In Computational Theory and Mathematics
- Sergey Levine
- Ofir Nachum
- Pablo Samuel Castro
- Doina Precup
- Pieter Abbeel
- Joelle Pineau
- Marc G. Bellemare
- Michael L. Littman
In Reinforcement Learning
- Sergey Levine
- Ofir Nachum
- Pieter Abbeel
- Doina Precup
- Marc G. Bellemare
- Lihong Li
- Shixiang Shane Gu
- Chelsea Finn
In Game & Decision Theory
- Pablo Samuel Castro
- Doina Precup
- Michael L. Littman
- Ofir Nachum
- Prashant Doshi
- Mengjiao Yang
- Gheorghe Comanici
- Saurabh Arora
Citations in the corpus
- DeepMDP: Learning Continuous Latent Space Models for Representation Learning (2019, methodology): “Prior work on representation learning, such as state aggregation with bisimulation metrics (Givan et al., 2003; Ferns et al., 2004; 2011) or feature discovery algorithms (Co-manici & Precup, 2011; Mahadevan & Maggioni, 2007; Bellemare et al., 2019), has resulted in algorithms with good theoretical…”
- 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].”
- Representation Matters: Offline Pretraining for Sequential Decision Making (2021, methodology): “Motivated by similar intuitions, research into bisimulation metrics has aimed to devise or learn similarity functions between states (Ferns et al., 2004; Castro & Precup, 2010).”
- The Bottleneck Simulator: A Model-based Deep Reinforcement Learning Approach (2018, methodology): “This state-value similarity is closely related to metrics based on the notion of bisimulation (Dean et al., 1997; Ferns et al., 2004; 2012; Abel et al., 2016).”
- 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.”
- Measuring the Distance Between Finite Markov Decision Processes (2016, background): “The solution, fixed point df (s, s ′), for Equation (2) always exists and is unique, which can be derived from the property of metric d [12].”
- Learning Markov State Abstractions for Deep Reinforcement Learning (2021, background): “Subsequent work on approximate MDP homomorphisms (Ravindran & Barto, 2004) and bisimulation metrics (Ferns et al., 2004, 2011) relaxed these strict assumptions and allowed ground states to have varying degrees of “bisimilarity.””
- Using Bisimulation for Policy Transfer in MDPs (2010, background): “(From Ferns et al., 2004) Let M be the set of all semimetrics on S and define F : M → M by F(d)(s,s′) = maxa∈A(|R(s,a) − R(s′,a)| + γTK(d)(P(s,a),P(s′,a))).”
- Learning Invariant Representations for Reinforcement Learning without Reconstruction (2020, methodology): “We show this using the property that the optimal value function is Lipschitz with respect to the bisimulation metric, see Theorem 5 in Appendix [5].”
- Bounding Performance Loss in Approximate MDP Homomorphisms (2008, methodology): “We prove that the difference in the optimal value function of different states can be upper-bounded by the value of this metric, and that the bound is tighter than previous bounds provided by bisimulation metrics (Ferns et al. 2004, 2005).”
- Value Preserving State-Action Abstractions (2020, methodology): “Many subsequent works have explored bisimulation for abstraction, including defining metrics for finite (Ferns et al., 2004; Castro and Precup, 2011; Castro, 2019) and infinite MDPs (Ferns et al., 2006; Taylor et al., 2008).”
- Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learning (2022, methodology): “These results are simple extensions of existing results on bisimulation metrics (Ferns et al., 2004).”
- Structural Similarity for Improved Transfer in Reinforcement Learning (2022, neutral): “Model-based metrics tend to focus on similarities in the structures of the MDPs, e.g. bisimulation metrics [9].”
- Automatic Construction of Temporally Extended Actions for MDPs Using Bisimulation Metrics (2011, methodology): “We use bisimulation metrics [Ferns et al., 2004] to relate states in the two different problems, from the point of view of behavior similarity.”
- Bisimulation Metrics for Continuous Markov Decision Processes (2011, background): “Thus , our metrics have a potential use in reasoning about logical properties of continuous MDPs too .”
- Scalable methods for computing state similarity in deterministic Markov Decision Processes (2019, methodology): “These theoretical properties render them appealing for planning and learning, and they have previously been used for state aggregation (Ferns, Panangaden, and Precup 2004; Ferns et al. 2006), policy transfer (Castro and Precup 2010), representation discovery (Ruan et al. 2015), and exploration…”
- Transfer of samples in batch reinforcement learning (2008, background): “In (Ferns et al., 2004), distance metrics for MDP similarity are introduced in the context of bisimulation to aggregate states with similar dynamics and reward.”