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 (10)

• Information-Theoretic Considerations in Batch Reinforcement Learning
• A Geometric Perspective on Optimal Representations for Reinforcement Learning
• Agent-Agnostic Human-in-the-Loop Reinforcement Learning
• Explainable Artificial Intelligence (XAI) for 6G: Improving Trust between Human and Machine
• Green Deep Reinforcement Learning for Radio Resource Management: Architecture, Algorithm Compression and Challenge
• Learning State Abstractions for Transfer in Continuous Control
• Model-Based Reinforcement Learning Exploiting State-Action Equivalence
• TOMA: Topological Map Abstraction for Reinforcement Learning
• Object Exchangeability in Reinforcement Learning: Extended Abstract
• Environment Shaping in Reinforcement Learning using State Abstraction