Hierarchical Solution of Markov Decision Processes using Macro-actions

Abstract

We investigate the use of temporally abstract actions, or macro-actions, in the solution of Markov decision processes. Unlike current models that combine both primitive actions and macro-actions and leave the state space unchanged, we propose a hierarchical model (using an abstract MDP) that works with macro-actions only, and that significantly reduces the size of the state space. This is achieved by treating macroactions as local policies that act in certain regions of state space, and by restricting states in the abstract MDP to those at the boundaries of regions. The abstract MDP approximates the original and can be solved more efficiently. We discuss several ways in which macro-actions can be generated to ensure good solution quality. Finally, we consider ways in which macro-actions can be reused to solve multiple, related MDPs; and we show that this can justify the computational overhead of macro-action generation.

Appears in Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI1998)

Cited by in corpus (31)

• An Introduction to Deep Reinforcement Learning
• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• A Deep Hierarchical Approach to Lifelong Learning in Minecraft
• Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems
• Distributed Planning in Hierarchical Factored MDPs
• Graying the black box: Understanding DQNs
• State Abstraction in MAXQ Hierarchical Reinforcement Learning
• Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks
• Existence of Multiagent Equilibria with Limited Agents
• Adaptive Skills, Adaptive Partitions (ASAP)
• Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition
• Visualizing Dynamics: from t-SNE to SEMI-MDPs
• Iterative Hierarchical Optimization for Misspecified Problems (IHOMP)
• Deep Reinforcement Learning With Macro-Actions
• Reinforcement Learning in Rich-Observation MDPs using Spectral Methods
• Robust Combination of Local Controllers
• Decision Making under Uncertainty: A Quasimetric Approach
• Proximity-Based Non-uniform Abstractions for Approximate Planning
• A Clustering Approach to Solving Large Stochastic Matching Problems
• Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstractions
• MDPs with Unawareness in Robotics
• Explainable Deterministic MDPs
• Options Discovery with Budgeted Reinforcement Learning
• Options of Interest: Temporal Abstraction with Interest Functions
• Modular self-organization
• MDPs with Unawareness
• A compact, hierarchical Q-function decomposition
• Bootstrapping Skills
• Hybrid Planning for Dynamic Multimodal Stochastic Shortest Paths
• Searching for Plannable Domains can Speed up Reinforcement Learning
• Macro-action Multi-time scale Dynamic Programming for Energy Management in Buildings with Phase Change Materials