Towards a Unified Theory of State Abstraction for MDPs

By Lihong Li, Thomas J. Walsh, Michael L. Littman. 2006

577 citations recorded by the source corpus.

How researchers see this paper

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

In Reinforcement Learning

Citations in the corpus

DeepMDP: Learning Continuous Latent Space Models for Representation Learning (2019, methodology): “State aggregation methods (Abel et al., 2017; Li et al., 2006; Singh et al., 1995; Givan et al., 2003; Jiang et al., 2015; Ruan et al., 2015) attempt to reduce the dimensionality of the state space by joining states together, taking the perspective that a good representation is one that reduces the…”
RUDDER: Return Decomposition for Delayed Rewards (2018, background): “give an overview over state abstraction and state aggregation for Markov decision processes, which covers homomorphic MDPs [73].”
Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “…that can be preserved while learning abstractions is the underlying reward and transition model, resulting in a model-irrelevance abstraction (Li et al., 2006). ϕmodel is a model-irrelevance abstraction if for any action a and any abstract state ŝ, ϕmodel(s1) = ϕmodel(s2) implies R a s1 = R…”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, methodology): “Throughout the paper, we make novel connections to two subareas of RL: state abstractions (Whitt, 1978; Li et al., 2006) and PAC exploration under function approximation (Krishnamurthy et al.”
Near-Optimal Representation Learning for Hierarchical Reinforcement Learning (2018, methodology): “While some of the prior work also focuses on learning state abstractions (Li et al., 2006; Sorg & Singh, 2009; Abel et al., 2017), they often exclusively apply to simple MDP domains as they rely on techniques such as state partitioning or Q-value based aggregation, which are difficult to scale to ou”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “The former approach is similar to the use of state abstractions [25], and typically incurs exponential sample complexity in state dimension.”
Inventing Relational State and Action Abstractions for Effective and Efficient Bilevel Planning (2022, background): “For example, in a small problem with 5 blocks where the hand is initially empty, the hAdd values of the states in the plan found are [9, 13, 9, 11, 6, 8, 4, 5, 2, 1, 0] when planning with the standard operators, and [14, 16, 11, when planning with our learned operators.”
From pixels to policies: A bootstrapping agent (2008, methodology): “Our method of discovering irrelevant features falls into the class of π-irrelevant (policy irrelevant) abstraction methods [15].”
State Abstractions for Lifelong Reinforcement Learning (2018, methodology): “Of growing interest in the RL literature is lifelong learning, in which an agent must interact with and solve many tasks over the course of a lifetime, as in Brunskill & Li (2014); Isele et al. (2016); Walsh et al. (2006) and Wilson et al. (2007).”
Invariant Causal Prediction for Block MDPs (2020, methodology): “State abstractions have been studied as a way to distinguish relevant from irrelevant information (Li et al., 2006) in order to create a more compact representation for easier decision making and planning.”
Bisimulation Metrics for Continuous Markov Decision Processes (2011, background): “Li, Walsh, and Littman [42], for example, survey a number of state aggregation techniques for finite MDPs in an attempt to unify the theory of state abstraction: these include aggregation of states based on bisimulation, homomorphisms, value equivalence, and policy equivalence, to name a few.”
Learning Markov State Abstractions for Deep Reinforcement Learning (2021, background): “It is common to view state abstraction as aggregating or partitioning ground states into abstract states in this way (Li et al., 2006).”
Markov Decision Processes (2004, unknown): “Inspired by the state abstraction theory (Li et al., 2006), in this section, we make the first effort in proposing a unified policy abstraction theory.”
Toward Good Abstractions for Lifelong Learning (2017, background): “We note that predicates defining other existing abstraction types such as φa [20] have natural translations to transitive predicates, too.”
Using dimensionality reduction to exploit constraints in reinforcement learning (2010, background): “Abstractions [5] have been suggested as a general term describing a mapping of state space to a S. Bitzer (s.bitzer@ed.ac.uk), M. Howard and S. Vijayakumar are with the School of Informatics, University of Edinburgh, Informatics Forum, 10 Crichton Street, EH8 9AB, UK.”
A Geometric Perspective on Optimal Representations for Reinforcement Learning (2019, background): “(2008) studies the particular case of linear representations, while (Li et al., 2006; Abel et al., 2016) consider the approximation error that arises from state abstraction.”