Equivalence notions and model minimization in Markov decision processes

By Robert Givan, Thomas L. Dean, Matthew Greig. 2003

445 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Reinforcement Learning

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 Reinforcement Learning

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…”
RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “proved these properties [34] by bisimulations (stochastically bisimilar MDPs).”
Metrics for Finite Markov Decision Processes (2004, background): “…an easily computable value function, that could provide information about the value function of the original MDP. Givan, Dean, and Greig (2003) In (Givan et al., 2003) it was shown that the stochastic bisimulation (henceforth simply “bisimulation”) partition could be found by iteratively…”
Automatic Construction of Temporally Extended Actions for MDPs Using Bisimulation Metrics (2011, background): “Bisimulation captures behavioral equivalence between states in an MDP [Givan et al., 2003].”
Towards a Unified Theory of State Abstraction for MDPs (2006, background): “Givan et al. [11] voiced such concerns regarding abstraction measures based on Q-functions.”
Representation Discovery for MDPs Using Bisimulation Metrics (2015, methodology): “One approach for this problem is to use bisimulation relations (Givan, Dean, and Greig 2003), also known as MDP homomorphisms (Ravindran and Barto 2002), or their relaxation as bisimulation metrics (Ferns, Panangaden, and Precup 2004).”
Deictic Image Maps: An Abstraction For Learning Pose Invariant Manipulation Policies (2018, background): “The MDP Homo-morphism framework is speciﬁcally relevant to this situation because, unlike other abstraction frameworks (Givan, Dean, and Greig 2003; Dean, Givan, and Leach 1997), it allows for state dependent action abstraction.”
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 deﬁnition of what it means for two environments to ‘share the same structure’ (Larsen and Skou, 1989; Givan et al., 2003).”
Inventing Relational State and Action Abstractions for Effective and Efficient Bilevel Planning (2022, methodology): “A baseline that learns abstractions by approximately optimizing the bisimulation criteria [37], as in prior work [17].”
Scalable methods for computing state similarity in deterministic Markov Decision Processes (2019, background): “…in search of the optimal value function (Bellman 1957): Bisimulation relations, originally introduced in the ﬁeld of concurrency theory, were adapted for MDPs by Givan, Dean, and Greig (2003), capture a strong form of behavioral equivalence: if s, t ∈ S are bisimilar, then V ∗ ( s ) = V ∗ ( t ) .”
Learning Invariant Representations for Reinforcement Learning without Reconstruction (2020, background): “Definition 1 (Bisimulation Relations [9]).”
Provably efficient RL with Rich Observations via Latent State Decoding (2019, background): “The most popular notion of abstraction in model-based RL is bisimulation (Whitt, 1978; Givan et al., 2003), which is more general than our setup since our context is sampled i.i.d. conditioned on the hidden state (the irrelevant factor discarded by a bisimulation may not be i.i.d.).”
EFFICIENT ABSTRACTION SELECTION IN REINFORCEMENT LEARNING (2013, methodology): “Exact methods aggregate states for which the transition and reward functions are equal (Givan et al. 2003; Boutilier et al. 2000; Ravindran and Barto 2003).”
SMDP homomorphisms: an algebraic approach to abstraction in semi-Markov decision processes (2003, unknown): “This framework extended the MDP minimization framework proposed by [Dean and Givan , 1997] and enabled the accommodation of redundancies arising from symmetric equivalence of the kind illustrated in Figure 1.”
Offline Reinforcement Learning with Pseudometric Learning (2021, background): “State-action similarity in MDPs. Bisimulation relations are a form of state abstraction (Li et al., 2006), introduced in the context of MDPs by Givan et al. (2003), where states with the same rewards and transitions are aggregated.”
A unifying framework for computational reinforcement learning theory (2009, background): “, bisimulation [Givan et al. 2003]); φQπ preserves the state–action value function for all policies; φQ∗ preserves the optimal state–action value function (e.”