# Near Optimal Behavior via Approximate State Abstraction

arXiv: https://arxiv.org/abs/1701.04113 · HTML: https://mlsanity.com/paper/1701.04113/

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2017.

## Built on by (most cited first, 30 of 66)

- [Learning Neuro-Symbolic Skills for Bilevel Planning](https://mlsanity.com/paper/2206.10680/) (2022)
- [Predicate Invention for Bilevel Planning](https://mlsanity.com/paper/2203.09634/) (2022)
- [Learning Markov State Abstractions for Deep Reinforcement Learning](https://mlsanity.com/paper/2106.04379/) (2021)
- [Provable Representation Learning for Imitation with Contrastive Fourier Features](https://mlsanity.com/paper/2105.12272/) (2021)
- [Which Mutual-Information Representation Learning Objectives are Sufficient for Control?](https://mlsanity.com/paper/2106.07278/) (2021)
- [Continuous MDP Homomorphisms and Homomorphic Policy Gradient](https://mlsanity.com/paper/2209.07364/) (2022)
- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [Octopus: Alleviating Hallucination via Dynamic Contrastive Decoding](https://mlsanity.com/paper/2503.00361/) (2025)
- [Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning](https://mlsanity.com/paper/2206.02072/) (2022)
- [Simplified Temporal Consistency Reinforcement Learning](https://mlsanity.com/paper/2306.09466/) (2023)
- [Hierarchical State Abstraction Based on Structural Information Principles](https://mlsanity.com/paper/2304.12000/) (2023)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (2021)
- [Approximate Policy Iteration with Bisimulation Metrics](https://mlsanity.com/paper/2202.02881/) (2022)
- [Learning with Language-Guided State Abstractions](https://mlsanity.com/paper/2402.18759/) (2024)
- [From Pixels to Predicates: Learning Symbolic World Models via Pretrained Vision-Language Models](https://mlsanity.com/paper/2501.00296/) (2024)
- [Policy Gradient Methods in the Presence of Symmetries and State Abstractions](https://mlsanity.com/paper/2305.05666/) (2023)
- [iQRL -- Implicitly Quantized Representations for Sample-efficient Reinforcement Learning](https://mlsanity.com/paper/2406.02696/) (2024)
- [J4R: Learning to Judge with Equivalent Initial State Group Relative Policy Optimization](https://mlsanity.com/paper/2505.13346/) (2025)
- [Embodied Active Learning of Relational State Abstractions for Bilevel Planning](https://mlsanity.com/paper/2303.04912/) (2023)
- [An Optimal Tightness Bound for the Simulation Lemma](https://mlsanity.com/paper/2406.16249/) (2024)
- [Reinforcement Learning by Guided Safe Exploration](https://mlsanity.com/paper/2307.14316/) (2023)
- [Learning Action-based Representations Using Invariance](https://mlsanity.com/paper/2403.16369/) (2024)
- [Remember the Decision, Not the Description: A Rate-Distortion Framework for Agent Memory](https://mlsanity.com/paper/2605.10870/) (2026)
- [Continuous Monte Carlo Graph Search](https://mlsanity.com/paper/2210.01426/) (2022)
- [Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction](https://mlsanity.com/paper/2210.16872/) (2022)
- [Learning Abstract World Model for Value-preserving Planning with Options](https://mlsanity.com/paper/2406.15850/) (2024)
- [Off-policy Evaluation with Deeply-abstracted States](https://mlsanity.com/paper/2406.19531/) (2024)
- [Satisficing Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/2407.12185/) (2024)
- [Scalable Policy-Based RL Algorithms for POMDPs](https://mlsanity.com/paper/2510.06540/) (2025)
- [On the Unreasonable Efficiency of State Space Clustering in Personalization Tasks](https://mlsanity.com/paper/2112.13141/) (2021)

## Abstract (arXiv)

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.