Near Optimal Behavior via Approximate State Abstraction

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.

• Publication year

  2016

• Venue

  International Conference on Machine Learning

• Publication date

  2016-06-19

• Fields of study

  Computer Science

• Identifiers
  arXiv 1701.04113
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Extreme state aggregation beyond Markov decision processes

  2016cited by this paper
• Efficient Bayesian Clustering for Reinforcement Learning

  2016cited by this paper
• Abstraction Selection in Model-based Reinforcement Learning

  2015cited by this paper
• Goal-Based Action Priors

  2015cited by this paper
• Improving UCT planning via approximate homomorphisms

  2014cited by this paper
• State Aggregation in Monte Carlo Tree Search

  2014cited by this paper
• Extreme State Aggregation beyond MDPs

  2014cited by this paper
• Reinforcement Learning in Finite MDPs: PAC Analysis

  2009cited by this paper
• GraphStream: A Tool for bridging the gap between Complex Systems and Dynamic Graphs

  2008cited by this paper
• Near-optimal Regret Bounds for Reinforcement Learning

  2008cited by this paper
• Towards a Unified Theory of State Abstraction for MDPs

  2006influential reference
• Transferring State Abstractions Between MDPs

  2006cited by this paper
• Methods for Computing State Similarity in Markov Decision Processes

  2006cited by this paper
• Bandit Based Monte-Carlo Planning

  2006cited by this paper
• Hierarchical Reinforcement Learning Based on Subgoal Discovery and Subpolicy Specialization

  2005cited by this paper
• State Abstraction Discovery from Irrelevant State Variables

  2005cited by this paper
• Metrics for Finite Markov Decision Processes

  2004cited by this paper
• Approximate Equivalence of Markov Decision Processes

  2003cited by this paper
• Recent Advances in Hierarchical Reinforcement Learning

  2003cited by this paper
• Recent Advances in Hierarchical Reinforcement Learning

  2003cited by this paper
• State abstraction for programmable reinforcement learning agents

  2002cited by this paper
• Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition

  1999cited by this paper
• Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning

  1999cited by this paper
• Reinforcement Learning: An Introduction

  1998cited by this paper
• Introduction to Reinforcement Learning

  1998cited by this paper
• Bayesian Q-Learning

  1998influential reference
• Abstraction and Approximate Decision-Theoretic Planning

  1997cited by this paper
• Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes

  1997cited by this paper
• Model Minimization in Markov Decision Processes

  1997cited by this paper
• Reinforcement Learning: A Survey

  1996cited by this paper
• On the Complexity of Solving Markov Decision Problems

  1995cited by this paper
• Feudal Reinforcement Learning

  1992cited by this paper
• The Complexity of Markov Decision Processes

  1987cited by this paper
• Aggregation in Dynamic Programming

  1987cited by this paper
• Noname manuscript No. (will be inserted by the editor) Adaptive Aggregation for Reinforcement Learning in Average Reward Markov Decision Processes

  year unknowncited by this paper

• Distributional Active Inference

  2026cites this paper
• From Pixels to Predicates: Learning Symbolic World Models via Pretrained VLMs

  2026cites this paper
• Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processes

  2025cites this paper
• Scalable Policy-Based RL Algorithms for POMDPs

  2025cites this paper
• Octopus: Alleviating Hallucination via Dynamic Contrastive Decoding

  2025cites this paper
• Abstraction for Bayesian Reinforcement Learning in Factored POMDPs

  2025influential citation
• Exploiting robot abstractions in episodic RL via reward shaping and heuristics

  2025cites this paper
• ATA: An Abstract-Train-Abstract approach for explanation-friendly deep reinforcement learning

  2025cites this paper
• Multi-Agent Reinforcement Learning in Cybersecurity: From Fundamentals to Applications

  2025cites this paper
• Trade-Offs Between Tasks Induced by Capacity Constraints Bound the Scope of Intelligence

  2025cites this paper
• J4R: Learning to Judge with Equivalent Initial State Group Relative Policy Optimization

  2025cites this paper
• Representative Action Selection for Large Action Space: From Bandits to MDPs

  2025influential citation
• Effective Reinforcement Learning Based on Structural Information Principles

  2024cites this paper
• Enhancing Proximal Policy Optimization in the Pendulum-v1 Environment Through Clustering-Based State Space Simplification

  2024cites this paper
• Seek Commonality but Preserve Differences: Dissected Dynamics Modeling for Multi-modal Visual RL

  2024cites this paper
• Adaptive Task and Motion Planning for Object-Invariant Stacking Operations

  2024cites this paper
• From Pixels to Predicates: Learning Symbolic World Models via Pretrained Vision-Language Models

  2024cites this paper
• Cross-Observability Learning for Vehicle Routing Problems

  2024cites this paper
• Approximate State Abstraction for Markov Games

  2024influential citation
• State Abstraction via Deep Supervised Hash Learning

  2024influential citation
• A Workflow for Building Computationally Rational Models of Human Behavior

  2024cites this paper
• A Multi-Agent View of Wireless Video Streaming with Delayed Client-Feedback

  2024cites this paper
• On shallow planning under partial observability

  2024influential citation
• Satisficing Exploration for Deep Reinforcement Learning

  2024cites this paper
• Off-policy Evaluation with Deeply-abstracted States

  2024cites this paper
• Learning Abstract World Model for Value-preserving Planning with Options

  2024cites this paper
• An Optimal Tightness Bound for the Simulation Lemma

  2024cites this paper
• iQRL - Implicitly Quantized Representations for Sample-efficient Reinforcement Learning

  2024cites this paper
• Progressive State Space Disaggregation for Infinite Horizon Dynamic Programming

  2024cites this paper
• Learning Action-based Representations Using Invariance

  2024cites this paper
• Model Approximation in MDPs With Unbounded Per-Step Cost

  2024cites this paper
• Information-Theoretic State Variable Selection for Reinforcement Learning

  2024cites this paper
• Learning with Language-Guided State Abstractions

  2024cites this paper
• Graph learning-based generation of abstractions for reinforcement learning

  2023cites this paper
• Exploiting Multiple Abstractions in Episodic RL via Reward Shaping

  2023cites this paper
• Policy-Induced Self-Supervision Improves Representation Finetuning in Visual RL

  2023cites this paper
• Weighted-Norm Bounds on Model Approximation in MDPs with Unbounded Per-Step Cost

  2023cites this paper
• Algorithmic Minimization of Uncertain Continuous-Time Markov Chains

  2023cites this paper
• Deep Reinforcement Learning for Autonomous Cyber Operations: A Survey

  2023cites this paper
• Accelerating Monte Carlo Tree Search with Probability Tree State Abstraction

  2023influential citation
• Reinforcement Learning by Guided Safe Exploration

  2023cites this paper
• Conditional abstraction trees for sample-efficient reinforcement learning

  2023cites this paper
• Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping

  2023influential citation
• Simplified Temporal Consistency Reinforcement Learning

  2023cites this paper
• Reinforcement Learning in Few-Shot Scenarios: A Survey

  2023cites this paper
• Policy Gradient Methods in the Presence of Symmetries and State Abstractions

  2023cites this paper
• Hierarchical State Abstraction Based on Structural Information Principles

  2023cites this paper
• Safe Explicable Planning

  2023cites this paper
• Scaling Up Q-Learning via Exploiting State–Action Equivalence

  2023cites this paper
• Safe Explicable Robot Planning

  2023cites this paper
• Hierarchical reinforcement learning for transportation infrastructure maintenance planning

  2023cites this paper
• Embodied Active Learning of Relational State Abstractions for Bilevel Planning

  2023cites this paper
• Boosting Verification of Deep Reinforcement Learning via Piece-Wise Linear Decision Neural Networks

  2023cites this paper
• Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction

  2022cites this paper
• A Low-Rank Approximation for MDPs via Moment Coupling

  2022influential citation
• Inventing Relational State and Action Abstractions for Effective and Efficient Bilevel Planning

  2022cites this paper
• Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning

  2022influential citation
• Learning Neuro-Symbolic Skills for Bilevel Planning

  2022cites this paper
• Learning Path Constraints for UAV Autonomous Navigation Under Uncertain GNSS Availability

  2022cites this paper
• Information Optimization and Transferable State Abstractions in Deep Reinforcement Learning

  2022cites this paper
• An Analysis of Abstracted Model-Based Reinforcement Learning

  2022influential citation
• Continuous MDP Homomorphisms and Homomorphic Policy Gradient

  2022cites this paper
• Towards Applicable State Abstractions: a Preview in Strategy Games

  2022cites this paper
• Continuous Monte Carlo Graph Search

  2022cites this paper
• Learning Dynamic Abstract Representations for Sample-Efficient Reinforcement Learning

  2022cites this paper
• A taxonomy for similarity metrics between Markov decision processes

  2022cites this paper
• Planning to the Information Horizon of BAMDPs via Epistemic State Abstraction

  2022influential citation
• Approximate Policy Iteration with Bisimulation Metrics

  2022cites this paper
• Predicate Invention for Bilevel Planning

  2022cites this paper
• Learning Skills Diverse in Value-Relevant Features

  2022cites this paper
• A Cross-Field Review of State Abstraction for Markov Decision Processes

  2022cites this paper
• An Analysis of Model-Based Reinforcement Learning From Abstracted Observations

  2022influential citation
• Model-Based Reinforcement Learning with State Abstraction: A Survey

  2022influential citation
• Provable Representation Learning for Imitation with Contrastive Fourier Features

  2021cites this paper
• WDIBS: Wasserstein deterministic information bottleneck for state abstraction to balance state-compression and performance

  2021cites this paper
• Provably Efficient Representation Learning in Low-rank Markov Decision Processes

  2021influential citation
• Which Mutual-Information Representation Learning Objectives are Sufficient for Control?

  2021cites this paper
• Option Transfer and SMDP Abstraction with Successor Features

  2021cites this paper
• Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL

  2021influential citation
• Using Human-Guided Causal Knowledge for More Generalized Robot Task Planning

  2021cites this paper
• Hierarchical multiagent reinforcement learning schemes for air traffic management

  2021cites this paper
• State-Temporal Compression in Reinforcement Learning With the Reward-Restricted Geodesic Metric

  2021cites this paper
• Dynamic neighbourhood optimisation for task allocation using multi-agent

  2021cites this paper
• Shortest-Path Constrained Reinforcement Learning for Sparse Reward Tasks

  2021cites this paper
• Task-Oriented Communication Design in Cyber-Physical Systems: A Survey on Theory and Applications

  2021cites this paper
• Metrics and continuity in reinforcement learning

  2021cites this paper
• An Adaptive State Aggregation Algorithm for Markov Decision Processes

  2021cites this paper
• MDP Abstraction with Successor Features

  2021influential citation
• Reducing the Information Horizon of Bayes-Adaptive Markov Decision Processes via Epistemic State Abstraction

  2021influential citation
• Scaling Power Management in Cloud Data Centers: A Multi-Level Continuous-Time MDP Approach

  2021cites this paper
• Explicable Reward Design for Reinforcement Learning Agents

  2021influential citation
• On the Unreasonable Efficiency of State Space Clustering in Personalization Tasks

  2021cites this paper
• Reducing Planning Complexity of General Reinforcement Learning with Non-Markovian Abstractions

  2021cites this paper
• Reward Machines for Vision-Based Robotic Manipulation

  2021cites this paper
• Energy Management in Data Centers with Server Setup Delay: A Semi-MDP Approximation

  2021cites this paper
• Task-oriented Communication System Design in Cyber-Physical Systems: A Survey on Theory and Applications

  2021cites this paper
• AlwaysSafe: Reinforcement Learning without Safety Constraint Violations during Training

  2021cites this paper
• Learning Markov State Abstractions for Deep Reinforcement Learning

  2021cites this paper
• Learning discrete state abstractions with deep variational inference

  2020cites this paper
• Domain Concretization From Examples: Addressing Missing Domain Knowledge Via Robust Planning

  2020cites this paper