Preprint
Reinforcement Learning

Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition

Tom Dietterich(Oregon State University)
November 1, 2000Journal of Artificial Intelligence Research1,877 citations
arXivPDFDOI

1.9k

Citations

213

Influential Citations

Journal of Artificial Intelligence Research

Venue

2000

Year

Abstract

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 non-hierarchical execution experimentally. Finally, the paper concludes with a comparison to related work and a discussion of the design tradeoffs in hierarchical reinforcement learning.

Analysis

Why This Paper Matters

This paper addresses a critical bottleneck in reinforcement learning: the curse of dimensionality. By introducing a principled hierarchical decomposition, it enables RL agents to learn policies in large state spaces that would be intractable for flat methods. The MAXQ framework provides both a theoretical foundation and a practical algorithm, making it a cornerstone of hierarchical RL research.

The paper's key insight is that domain knowledge—in the form of subgoals and subtask hierarchies—can be leveraged to decompose the value function additively. This not only speeds learning but also allows state abstractions that ignore irrelevant parts of the state space within each subtask. The formal treatment of safe abstraction conditions ensures that the decomposition does not compromise optimality, which is a major theoretical contribution.

Technical Contributions

  • MAXQ Decomposition: Defines a hierarchy of MDPs where the value function of the root MDP is the sum of value functions of subtask MDPs, enabling modular learning.
  • Recursive Optimality: Introduces the concept of recursively optimal policies—policies that are optimal for each subtask given the policies of its children—and proves convergence to such policies.
  • Five Safe Abstraction Conditions: Identifies conditions (e.g., subtask irrelevance, termination, and reward invariance) under which state abstractions can be applied without losing optimality.
  • MAXQ-Q Algorithm: A model-free, online learning algorithm that updates value functions for each subtask using Q-learning-like updates, with convergence guarantees.
  • Non-Hierarchical Execution: Shows that the learned value representation can be used to compute an improved flat policy via a procedure analogous to policy iteration, demonstrating that hierarchical learning can benefit even non-hierarchical execution.

Results

The paper evaluates MAXQ-Q in three domains: a taxi domain, a resource allocation problem, and a robot navigation task. In the taxi domain, MAXQ-Q with state abstractions converges to a recursively optimal policy in about 2000 episodes, whereas flat Q-learning requires over 10,000 episodes to reach comparable performance. Similar speedups are reported in the other domains. The non-hierarchical execution procedure further improves the policy, achieving near-optimal performance with fewer steps. These results empirically validate the theoretical claims of faster convergence and effective state abstraction.

Significance

MAXQ has had a lasting impact on reinforcement learning by formalizing hierarchical decomposition and state abstraction. It influenced later frameworks like options (Sutton, Precup, Singh) and hierarchical abstract machines (Parr, Russell). The paper's rigorous theoretical analysis—including convergence proofs and abstraction conditions—set a standard for subsequent work. Practically, it demonstrated that domain knowledge can be integrated into RL in a principled way, paving the path for applications in robotics, game AI, and autonomous systems where large state spaces are common. The idea of recursively optimal policies remains relevant in multi-agent and transfer learning settings.

reinforcement-learninghierarchical-rlvalue-function-decompositionstate-abstractionmaxqmodel-freesubgoal
Reinforcement Learning

Related Papers