Hierarchical Solution of Markov Decision Processes using Macro-actions

By Milos Hauskrecht, Nicolas Meuleau, Leslie Pack Kaelbling, Thomas L. Dean, Craig Boutilier. 1998

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.

Subfields: Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

Citations in the corpus

Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Macro actions (Hauskrecht et al., 1998) or skills (Thrun and Schwartz, 1995) are approaches for learning that side step the requirement to make decisions at each individual time step.”
Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition (1999, neutral): “They may in fact hinder it (Hauskrecht et al., 1998).)”
Bayesian Time Series Models: Expectation maximisation methods for solving (PO)MDPs and optimal control problems (2011, methodology): “For instance, in the eld of planning, they include work on Factored Markov Decision Processes (Boutilier et al., 1995; Koller and Parr, 1999; Guestrin et al., 2003; Kveton and Hauskrecht, 2005), abstractions ( Hauskrecht et al., 1998 ), and relational models of the environment (Zettlemoyer et al., 2”
Hierarchical Approaches (2012, background): “…we have seen above the stochastic nature of MDPs means that the condition under which an abstract action is appropriate may have changed after the action’s invocation and that another action may become a better choice because of the inherent stochasticity of transitions (Hauskrecht et al, 1998).”
Adaptive Skills Adaptive Partitions (ASAP) (2016, background): “A policy is a solution to a Markov Decision Process (MDP) and is defined as a mapping from states to a probability distribution over actions.”
Optimal Behavioral Hierarchy (2014, methodology): “[24], we define a region’s entrance vertices/ states as the set of all vertices within the region that have at least one neighbor outside of it.”
Automated Planning and Acting (2016, background): “[263] propose approximate solutions to large MDPs with macro actions, that is, local policies defined in particular regions of the state space.”
Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks (2011, methodology): “Hauskrecht et al. (1998) discuss various methods of generating macro actions.”
Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems (1998, methodology): “There is a reward in room , indicated with a $. Connecting states are identified with an X. Similar examples and pictures are used by Precup and Sutton (1997) and Hauskrecht et al. (1998) .”
Options of Interest: Temporal Abstraction with Interest Functions (2020, background): “The ﬁrst problem is often solved by providing shortcuts that skip over multiple time steps, for example, by using macro-actions (Hauskrecht et al. 1998).”
Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning (1999, unknown): “Primitive options”
An Introduction to Deep Reinforcement Learning (2018, unknown): “Similar ideas have also been denoted in the literature as macro-actions (McGovern et al., 1997) or abstract actions (Hauskrecht et al., 1998).”
Online Planning for Large Markov Decision Processes with Hierarchical Decomposition (2015, background): “…learning, there exist several ofﬂine MDP planning algorithms that also exploit the hierarchical structure to speed up the planning For instance, Hauskrecht et al. [1998] develop an abstract MDP model that works with macroactions and macrostates by treating macroactions as local policies that…”
Discovering Hierarchy in Reinforcement Learning with HEXQ (2002, unknown): “Many researchers have either ignored where decompositions come from or pointed to the desirability of automating this task (Boutilier et al., 1999; Hauskrecht et al., 1998; Dean & Lin, 1995).”