On Efficiency in Hierarchical Reinforcement Learning

Zheng Wen, Doina Precup, Morteza Ibrahimi, André Barreto, Benjamin Van Roy, Satinder SinghNeurIPS 2020 · OpenReview

This paper provides a rigorous theoretical foundation for why Hierarchical Reinforcement Learning (HRL) works. While HRL has long shown empirical success, this work formalizes the intuition that HRL's power lies in its ability to exploit repeating structures and "bottleneck" states within an environment. By formalizing how agents can decompose a large problem into repeating "subMDPs," the authors prove that HRL can achieve significantly lower regret (faster learning) and lower computational complexity (faster planning) than standard RL methods.

The Curse of Dimensionality in RL

Reinforcement Learning (RL) agents often struggle with "the curse of dimensionality"—as the state space grows, the data and computation required to find an optimal policy explode. Hierarchical RL aims to solve this by allowing agents to plan at multiple levels of temporal abstraction (e.g., "go to the kitchen" instead of "move left leg 5 degrees").

While we know HRL works well in practice for complex tasks, we have historically lacked a clear theoretical understanding of why and when it is more efficient. The authors tackle two specific gaps:

  1. Statistical Efficiency: How much less data does an HRL agent need if the environment has repeating structures?
  2. Computational Efficiency: How much faster can an agent plan if it can solve small sub-problems and "stitch" them together?

Formalizing Hierarchical Structure

The authors introduce several formal definitions to bridge the gap between intuition and theory. They use a conceptual "garbage collecting robot" in a multi-floor building as a motivating example to illustrate these definitions:

  • Induced subMDPs: The environment is modeled as a collection of smaller Markov Decision Processes (subMDPs). A large building might be the overarching MDP, while individual rooms are the subMDPs.
  • Equivalent subMDPs: This formalizes "repeating structure." If two rooms have the same layout and rewards, they are equivalent. An agent only needs to learn how to navigate one "type" of room to navigate all rooms of that type.
  • Exit Profiles: This acts as the "interface" between sub-problems. An exit profile summarizes the value of leaving a subMDP through various exits (e.g., doors).
  • PSHRL (Posterior Sampling for HRL): A Thompson sampling-style algorithm that uses a prior distribution reflecting the hierarchical structure. It learns about entire classes of subMDPs simultaneously.
  • PEP (Planning with Exit Profiles): A planning algorithm that first solves subMDPs for various exit profiles to create "options," then plans at a high level using these options.

Key Insights

  • The Power of Symmetry: The most significant gain in learning speed comes from equivalence classes. If an environment has many identical sub-problems (like a hotel with 100 identical rooms), the agent can pool data from all of them.
  • Insulating Sub-problems: Planning becomes efficient when sub-problems are "well-insulated." If a subMDP has only a few "exit states" (bottlenecks), the agent doesn't need to know the state of the entire world to make a good decision inside that subMDP.
  • Regret Decomposition: The authors successfully separate the "regret" (the cost of learning) into two parts: errors due to sub-optimal planning and errors due to the learning process itself. This allows them to show that even if planning is slightly approximate, the statistical gains from hierarchy can still make the agent superior overall.

Key Results: Quantifying Efficiency

The paper’s primary contribution is a new Bayesian Regret Bound that mathematically proves the efficiency gains of HRL.

Comparison of regret bounds and computational complexity for standard PSRL versus the proposed PSHRL algorithm.

As shown in the table above, a standard RL agent's (PSRL) regret scales with the total number of states $|\mathcal{S}|$. In contrast, the proposed HRL agent (PSHRL) achieves a bound that scales with $M\sqrt{K}$, where $M$ is the size of the largest sub-problem and $K$ is the number of unique types of sub-problems.

If an environment is highly repetitive ($K \ll |\mathcal{S}|$), the HRL agent learns dramatically faster. For example, in a building with many identical rooms, the HRL agent's regret doesn't care how many rooms there are, only how many types of rooms exist.

On the planning side, they show that the PEP algorithm is computationally efficient if the number of exit states is small, providing a formal justification for the "bottleneck" theory of option discovery.

Limitations and Future Work

  • Known Structure: The biggest limitation is that the algorithm assumes the agent already knows the state partition and which subMDPs are equivalent. In the real world, an agent must discover this hierarchy (the "Option Discovery" problem).
  • Strict Equivalence: The theory currently relies on subMDPs being exactly identical. The authors suggest that future work could relax this to "similar" subMDPs using metrics like bisimulation or MDP homomorphisms.
  • Deterministic Exits: Some of the strongest planning results assume "deterministic exiting" (an option always leads to the same exit), which may not hold in very noisy environments.

Summary updated

Abstract

Hierarchical Reinforcement Learning (HRL) approaches promise to provide more efficient solutions to sequential decision making problems, both in terms of statistical as well as computational efficiency. While this has been demonstrated empirically over time in a variety of tasks, theoretical results quantifying the benefits of such methods are still few and far between. In this paper, we discuss the kind of structure in a Markov decision process which gives rise to efficient HRL methods. Specifically, we formalize the intuition that HRL can exploit well repeating "subMDPs", with similar reward and transition structure. We show that, under reasonable assumptions, a model-based Thompson sampling-style HRL algorithm that exploits this structure is statistically efficient, as established through a finite-time regret bound. We also establish conditions under which planning with structure-induced options is near-optimal and computationally efficient.
BibTeX
@inproceedings{wen2020efficiency,
  author = {Zheng Wen and Doina Precup and Morteza Ibrahimi and André Barreto and Benjamin Van Roy and Satinder Singh},
  title = {{On Efficiency in Hierarchical Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=YsSzziDIU0},
}
Figure