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:
- $\mu_k$: The average (expected) number of steps the option takes.
- $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.
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.
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