Near Optimal Behavior via Approximate State Abstraction

Abstract

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.

Earlier version published at ICML 2016

References in corpus (2)

• On the Complexity of Solving Markov Decision Problems
• Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes

Cited by in corpus (33)

• Near-Optimal Representation Learning for Hierarchical Reinforcement Learning
• Information-Theoretic Considerations in Batch Reinforcement Learning
• A Geometric Perspective on Optimal Representations for Reinforcement Learning
• Agent-Agnostic Human-in-the-Loop Reinforcement Learning
• Approximate information state for approximate planning and reinforcement learning in partially observed systems
• A Sufficient Statistic for Influence in Structured Multiagent Environments
• Explainable Artificial Intelligence (XAI) for 6G: Improving Trust between Human and Machine
• Adaptive Temporal Difference Learning with Linear Function Approximation
• Which Mutual-Information Representation Learning Objectives are Sufficient for Control?
• Approximate Exploration through State Abstraction
• Provable Representation Learning for Imitation with Contrastive Fourier Features
• Reinforcement Learning by Guided Safe Exploration
• Learning Markov State Abstractions for Deep Reinforcement Learning
• Learning Discrete State Abstractions With Deep Variational Inference
• Green Deep Reinforcement Learning for Radio Resource Management: Architecture, Algorithm Compression and Challenge
• Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
• Provably Safe PAC-MDP Exploration Using Analogies
• Disentangled Planning and Control in Vision Based Robotics via Reward Machines
• Model-Based Reinforcement Learning Exploiting State-Action Equivalence
• Loss Bounds for Approximate Influence-Based Abstraction
• Learning State Abstractions for Transfer in Continuous Control
• Online Planning with Lookahead Policies
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Multi-Tenant Cross-Slice Resource Orchestration: A Deep Reinforcement Learning Approach
• Fast Online Reinforcement Learning Control using State-Space Dimensionality Reduction
• CAMPs: Learning Context-Specific Abstractions for Efficient Planning in Factored MDPs
• Unsupervised Basis Function Adaptation for Reinforcement Learning
• TOMA: Topological Map Abstraction for Reinforcement Learning
• An Adaptive State Aggregation Algorithm for Markov Decision Processes
• Exploiting Multiple Abstractions in Episodic RL via Reward Shaping
• Using Human-Guided Causal Knowledge for More Generalized Robot Task Planning
• Environment Shaping in Reinforcement Learning using State Abstraction
• Object Exchangeability in Reinforcement Learning: Extended Abstract