Near Optimal Behavior via Approximate State Abstraction

By David Abel, D. E. Hershkowitz, Michael L. Littman. 2016

186 citations recorded by the source corpus.

The combinatorial explosion that plagues planning and reinforcement learning (RL) algorithms can be moderated using state abstraction. Prohibitively large task representations can be condensed such that essential information is preserved, and consequently, solutions are tractably computable. However, exact abstractions, which treat only fully-identical situations as equivalent, fail to present opportunities for abstraction in environments where no two situations are exactly alike. In this work, we investigate approximate state abstractions, which treat nearly-identical situations as equivalent. We present theoretical guarantees of the quality of behaviors derived from four types of approximate abstractions. Additionally, we empirically demonstrate that approximate abstractions lead to reduction in task complexity and bounded loss of optimality of behavior in a variety of environments.

Subfields: Artificial Intelligence, Information Systems, Reinforcement Learning, Statistical Learning 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

In Information Systems

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

DeepMDP: Learning Continuous Latent Space Models for Representation Learning (2019, methodology): “Furthermore, state aggregation techniques, whether based on bisimulation or other 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), suffer from poor compatibility with function approximation methods.”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “It is known that certainty-equivalence with Q ⋆ -irrelevant abstraction is consistent and enjoys polynomial sample complexity when each state-action pair receives enough data (Li, 2009; Hutter, 2014; Jiang et al., 2015; Abel et al., 2016; Jiang, 2018).”
Provable Representation Learning for Imitation with Contrastive Fourier Features (2021, background): “For one, many of the bisimulation results rely on defining a representation error which holds globally on all states and actions [1].”
Near-Optimal Representation Learning for Hierarchical Reinforcement Learning (2018, methodology): “Exact state abstractions (Li et al., 2006) incur no performance loss (Dean et al., 1997; Ravindran & Barto, 2002), while their approximate variants generally have bounded sub-optimality (Bertsekas & Castanon, 1989; Dean et al., 1997; Sorg & Singh, 2009; Abel et al., 2017).”
Agent-Agnostic Human-in-the-Loop Reinforcement Learning (2017, methodology): “Other methods have focused on state abstraction functions to decrease learning time and preserve the quality of learned behavior, as in [26, 33, 12, 20, 7, 3, 13].”
A Geometric Perspective on Optimal Representations for Reinforcement Learning (2019, background): “Parr et al. (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.”
Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, methodology): “One of the earliest methods for aggregating different states and generating a compressed representation for those states is state aggregation [Michael and Jordan, 1995, Dean and Givan, 1997, Ravindran and Barto, 2002, Abel et al., 2016]. In deep RL, deep neural networks have been used to learn good ”
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).”
Value Preserving State-Action Abstractions (2020, methodology): “As some motivating evidence, a claim closely related to Assumption 1 is proven by Abel et al. (2016) as Claim 1, and Assumption 2 is of similar structure to our own Theorem 1.”
Toward Good Abstractions for Lifelong Learning (2017, background): “[1] where the goal can appear in any cell in the top row, and 15 × 15 lifelong variant of the Four Rooms domain from Sutton et al.”
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.”
State Abstractions for Lifelong Reinforcement Learning (2018, background): “Table 1: A few existing state abstraction types (Li et al., 2006; Abel et al., 2016) and our transitive Qd abstraction type.”
Learning Markov State Abstractions for Deep Reinforcement Learning (2021, background): “value preservation (Abel et al., 2016), symbol construction (Konidaris et al.”