mlsanityData to 7 Oct 2026

Near Optimal Behavior via Approximate State Abstraction

arXiv 1701.04113 ↗First posted 15 Jan 2017cs.LG cs.AIcited by 63

Not on the map. Why?

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.

Key facts. Cited by 63 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jan 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 11; 2023: 10; 2024: 11; 2025: 6; 2026: 13.

63 papers.

Sort:

By area:

  1. 2022Learning Neuro-Symbolic Skills for Bilevel Planningcited by 55
  2. 2022Predicate Invention for Bilevel Planningcited by 49
  3. 2021Learning Markov State Abstractions for Deep Reinforcement Learningcited by 42
  4. 2021Provable Representation Learning for Imitation with Contrastive Fourier Featurescited by 34
  5. 2021Which Mutual-Information Representation Learning Objectives are Sufficient for Control?cited by 28
  6. 2021Metrics and continuity in reinforcement learningcited by 26
  7. 2022Continuous MDP Homomorphisms and Homomorphic Policy Gradientcited by 24
  8. 2025Octopus: Alleviating Hallucination via Dynamic Contrastive Decodingcited by 23
  9. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  10. 2023Simplified Temporal Consistency Reinforcement Learningcited by 17
  11. 2023Hierarchical State Abstraction Based on Structural Information Principlescited by 14
  12. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
38 more
  1. 2022Approximate Policy Iteration with Bisimulation Metricscited by 11
  2. 2024Learning with Language-Guided State Abstractionscited by 11
  3. 2024From Pixels to Predicates: Learning Symbolic World Models via Pretrained Vision-Language Modelscited by 11
  4. 2024iQRL -- Implicitly Quantized Representations for Sample-efficient Reinforcement Learningcited by 9
  5. 2025J4R: Learning to Judge with Equivalent Initial State Group Relative Policy Optimizationcited by 9
  6. 2023Embodied Active Learning of Relational State Abstractions for Bilevel Planningcited by 8
  7. 2023Policy Gradient Methods in the Presence of Symmetries and State Abstractionscited by 8
  8. 2024An Optimal Tightness Bound for the Simulation Lemmacited by 7
  9. 2023Reinforcement Learning by Guided Safe Explorationcited by 5
  10. 2024Learning Action-based Representations Using Invariancecited by 5
  11. 2022Continuous Monte Carlo Graph Searchcited by 4
  12. 2022Planning to the Information Horizon of BAMDPs via Epistemic State Abstractioncited by 4
  13. 2024Learning Abstract World Model for Value-preserving Planning with Optionscited by 4
  14. 2024Satisficing Exploration for Deep Reinforcement Learningcited by 4
  15. 2025Scalable Policy-Based RL Algorithms for POMDPscited by 4
  16. 2021On the Unreasonable Efficiency of State Space Clustering in Personalization Taskscited by 3
  17. 2023Accelerating Monte Carlo Tree Search with Probability Tree State Abstractioncited by 3
  18. 2021Shortest-Path Constrained Reinforcement Learning for Sparse Reward Taskscited by 2
  19. 2021An Adaptive State Aggregation Algorithm for Markov Decision Processescited by 2
  20. 2022An Analysis of Model-Based Reinforcement Learning From Abstracted Observationscited by 2
  21. 2022Towards A Unified Policy Abstraction Theory and Representation Learning Approach in Markov Decision Processescited by 2
  22. 2023Exploiting Multiple Abstractions in Episodic RL via Reward Shapingcited by 2
  23. 2024Off-policy Evaluation with Deeply-abstracted Statescited by 2
  24. 2026The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishabilitycited by 2
  25. 2021Dynamic neighbourhood optimisation for task allocation using multi-agentcited by 1
  26. 2021Option Transfer and SMDP Abstraction with Successor Featurescited by 1
  27. 2022Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstractioncited by 1
  28. 2023Safe Explicable Planningcited by 1
  29. 2023Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Groupingcited by 1
  30. 2024Model approximation in MDPs with unbounded per-step costcited by 1
  31. 2024On shallow planning under partial observabilitycited by 1
  32. 2025Multi-Agent Reinforcement Learning in Cybersecurity: From Fundamentals to Applicationscited by 1
  33. 2026Reinforcing the World's Edge: A Continual Learning Problem in the Multi-Agent-World Boundarycited by 1
  34. 2026Selecting Decision-Relevant Concepts in Reinforcement Learningcited by 1
  35. 2021Using Human-Guided Causal Knowledge for More Generalized Robot Task Planningcited by 0
  36. 2021Reducing Planning Complexity of General Reinforcement Learning with Non-Markovian Abstractionscited by 0
  37. 2022Learning Dynamic Abstract Representations for Sample-Efficient Reinforcement Learningcited by 0
  38. 2023Policy-Induced Self-Supervision Improves Representation Finetuning in Visual RLcited by 0

50 most cited of 63 All 63 (JSON)