Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition

By Thomas G. Dietterich. 1999

This paper presents a new approach to hierarchical reinforcement learning based on decomposing the target Markov decision process (MDP) into a hierarchy of smaller MDPs and decomposing the value function of the target MDP into an additive combination of the value functions of the smaller MDPs. The decomposition, known as the MAXQ decomposition, has both a procedural semantics--as a subroutine hierarchy--and a declarative semantics--as a representation of the value function of a hierarchical policy. MAXQ unifies and extends previous work on hierarchical reinforcement learning by Singh, Kaelbling, and Dayan and Hinton. It is based on the assumption that the programmer can identify useful subgoals and define subtasks that achieve these subgoals. By defining such subgoals, the programmer constrains the set of policies that need to be considered during reinforcement learning. The MAXQ value function decomposition can represent the value function of any policy that is consistent with the given hierarchy. The decomposition also creates opportunities to exploit state abstractions, so that individual MDPs within the hierarchy can ignore large parts of the state space. This is important for the practical application of the method. This paper defines the MAXQ hierarchy, proves formal results on its representational power, and establishes five conditions for the safe use of state abstractions. The paper presents an online model-free learning algorithm, MAXQ-Q, and proves that it converges with probability 1 to a kind of locally-optimal policy known as a recursively optimal policy, even in the presence of the five kinds of state abstraction. The paper evaluates the MAXQ representation and MAXQ-Q through a series of experiments in three domains and shows experimentally that MAXQ-Q (with state abstractions) converges to a recursively optimal policy much faster than flat Q learning. The fact that MAXQ learns a representation of the value function has an important benefit: it makes it possible to compute and execute an improved, non-hierarchical policy via a procedure similar to the policy improvement step of policy iteration. The paper demonstrates the effectiveness of this nonhierarchical execution experimentally. Finally, the paper concludes with a comparison to related work and a discussion of the design tradeoffs in hierarchical reinforcement learning.

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

1. Sergey Levine
2. Pieter Abbeel
3. Shimon Whiteson
4. Chelsea Finn
5. Ofir Nachum
6. Yuxi Li
7. Lihong Li
8. Doina Precup

Citations in the corpus

• Benchmarking Deep Reinforcement Learning for Continuous Control (2016, background): “Many real-world tasks exhibit hierarchical structure, where higher level decisions can reuse lower level skills (Parr & Russell, 1998; Sutton et al., 1999; Dietterich, 2000).”
• Neural Approaches to Conversational AI (2018, neutral): “aking policy optimization much harder. Cuay´ahuitl et al. (2010) proposed to use hierarchical reinforcement learning to optimize a composite task’s dialogue policy, with tabular versions of the MAXQ (Dietterich, 2000) and Hierarchical Abstract Machine (Parr and Russell, 1998) approaches. While promi”
• Neural Programmer-Interpreters (2015, background): “Related problems have been studied in the literature on hierarchical reinforcement learning ( e.g. , Dietterich (2000); Andre & Russell (2001); Sutton et al. (1999) and Schaul et al. (2015)), imitation and apprenticeship learning ( e.g. , Kolter et al. (2008) and Rothkopf & Ballard (2013)) and…”
• Graying the black box: Understanding DQNs (2016, background): “Given a good representation of the states, varying levels of convergence guarantees has been promised (Dean & Lin, 1995; Parr, 1998; Hauskrecht et al., 1998; Dietterich, 2000).”
• Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation (2016, methodology): “Other related work for hierarchical formulations include the MAXQ framework [6], which decomposed the value function of an MDP into combinations of value functions of smaller constituent MDPs, as did Guestrin et al.”
• Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “Existing and widely used benchmarks, such as classical small MDP environments (e.g. Mountain Car, Cartpole, and Taxi), OpenAI’s Gym (Brockman et al., 2016), and the Arcade Learning Environment (ALE) (Bellemare et al., 2013), have been instrumental to the progress made in RL over the years.”
• Continual Learning of Control Primitives: Skill Discovery via Reset-Games (2020, background): “The goal of acquiring primitives for the purpose of enabling efficient learning on downstream tasks is also a central goal of hierarchical reinforcement learning (HRL), which has been a long-standing area of research [11, 51, 32, 43, 12].”
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation (2019, methodology): “To back up this theoretical finding, we also conduct experiments in the Taxi environment (Dietterich, 2000) following Liu et al. (2018, Section 5), and show that MWL performs significantly better than MSWL in the tabular setting; see Appendix D.3 for details.”
• DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, methodology): “We begin with a tabular task, the Taxi domain [10].”
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation (2018, background): “Taxi Environment Taxi [6] is a 2D grid world simulating taxi movement along the grids.”
• Relay Policy Learning: Solving Long-Horizon Tasks via Imitation and Reinforcement Learning (2019, methodology): “Solutions like the options framework [6, 10], HAM [11], max-Q [12], and feudal networks [13, 14] present promising algorithmic frameworks for HRL.”
• Multi-Agent Common Knowledge Reinforcement Learning (2018, background): “(2001) extend the MAXQ single-agent hierarchical framework (Dietterich, 2000) to the multi-agent domain.”
• FeUdal Networks for Hierarchical Reinforcement Learning (2017, neutral): “Building hierarchical agents is a long standing topic in re-inforcement learning (Sutton et al., 1999; Precup, 2000; Dayan & Hinton, 1993; Dietterich, 2000; Boutilier et al., 1997; Dayan, 1993; Kaelbling, 2014; Parr & Russell, 1998; Precup et al., 1997; 1998; Schmidhuber, 1991; Sutton, 1995;…”
• The Option-Critic Architecture (2016, methodology): “A typical approach for learning options is to use pseudo-rewards [Dietterich, 2000; Precup, 2000] or subgoal methods Sutton et al.”
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning (2010, methodology): “The original taxi domain [Dietterich, 2000] is a 5x5 grid, with 4 possible pickup and dropoff destinations, and 6 actions (pickup, dropoff, and navigating North, South, East, West).”