The Expected-Length Model of Options

David Abel, John Winder, Marie desJardins, Michael L. Littman

Abstract

Hierarchical reinforcement learning (HRL) utilizes "options" to represent macro-actions, but traditional Multi-Time Models (MTM) for these options are computationally expensive due to their high parameterization. This paper introduces the Expected-Length Model (ELM), a radical simplification that models option duration using only its expected value. While ELM introduces a theoretical bias, it significantly improves sample efficiency and reduces memory requirements. We demonstrate that ELM achieves near-optimal performance across various benchmarks, with its primary limitation being sensitivity to extremely high-variance environments.

Introduction

In Reinforcement Learning (RL), "options" allow agents to think in terms of macro-actions (e.g., "exit the room") rather than just primitive movements. To plan with these options, an agent needs a model of what happens when an option is executed: where will it end up, and how long will it take?

The traditional approach, the Multi-Time Model (MTM), requires the agent to estimate the probability of the option terminating at every possible time-step. This "highly parameterized" nature makes learning option models from experience slow and memory-intensive, especially in complex hierarchies where an agent might need to track an immense set of probabilities for a single macro-action.

Methods

The authors propose the Expected-Length Model (ELM) as a solution to this complexity. Instead of modeling the full distribution of time-steps, ELM only tracks two parameters:

  1. $\mu_k$: The average (expected) number of steps the option takes.
  2. $Pr(s'|s, o)$: A categorical distribution over the potential terminal states.

The transition model is simplified to: $T(s'|s, o) = \gamma^{\mu_k} Pr(s'|s, o)$, where $\gamma$ is the discount factor. While this is a biased estimator, the authors provide a mathematical proof showing that in Stochastic Shortest Path (SSP) problems, the error in the resulting value function is bounded, supporting near-optimal behavior.

Comparison of ELM and MTM on a simple MDP, showing model and value differences.

Key Insights and Ideas

  • The Curse of Parameters: MTM's complexity is its downfall. By attempting to be perfectly accurate about every possible duration, it requires significantly more data to converge. ELM's simplicity allows it to be learned much faster.
  • Bias-Variance Trade-off: ELM introduces a small amount of bias by assuming the option always takes its average time, but it drastically reduces the variance in model estimation. In many RL tasks, this trade-off favors faster learning.
  • Hierarchy Amplifies Benefits: As options are stacked into deeper hierarchies (e.g., in the Taxi or Playroom tasks), the efficiency gains of ELM become even more pronounced.

Key Results

The authors evaluated ELM and MTM across several classic RL benchmarks, including Four Rooms, Taxi Domain, and Playroom.

  • Sample Efficiency: In the Four Rooms and Taxi domains, ELM reached near-optimal performance significantly faster than MTM.
  • Asymptotic Equivalence: In most tests, ELM eventually converged to the same performance level as MTM, proving the theoretical bias rarely impacts the final policy.
  • Stochasticity Sensitivity: The primary weakness identified was high-variance environments like the Bridge Room. If an option's duration is highly multi-modal (e.g., taking 5 or 100 steps with equal probability), the average is a poor representation that can lead to suboptimal, risky decision-making.
Cumulative reward performance in the Bridge Room environment.

Limitations and Future Work

The strongest theoretical bounds for ELM are currently limited to Stochastic Shortest Path problems. Extending these proofs to general Markov Decision Processes (MDPs) is a critical next step. Additionally, while ELM excels in efficiency, its sensitivity to high-variance duration distributions suggests it may be best used as a "fitness function" for discovering options with simple, low-variance models to further simplify hierarchical planning.

Summary updated

Abstract

Effective options can make reinforcement learning easier by enhancing an agent's ability to both explore in a targeted manner and plan further into the future. However, learning an appropriate model of an option's dynamics in hard, requiring estimating a highly parameterized probability distribution. This paper introduces and motivates the Expected-Length Model (ELM) for options, an alternate model for transition dynamics. We prove ELM is a (biased) estimator of the traditional Multi-Time Model (MTM), but provide a non-vacuous bound on their deviation. We further prove that, in stochastic shortest path problems, ELM induces a value function that is sufficiently similar to the one induced by MTM, and is thus capable of supporting near-optimal behavior. We explore the practical utility of this option model experimentally, finding consistent support for the thesis that ELM is a suitable replacement for MTM. In some cases, we find ELM leads to more sample efficient learning, especially when options are arranged in a hierarchy.
BibTeX
@inproceedings{abel2019expected,
  author = {David Abel and John Winder and Marie desJardins and Michael L. Littman},
  title = {{The Expected-Length Model of Options}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/270},
}
Figure