Abstract
In goal-based Markov Decision Problems (MDPs), agents typically generate a policy and value function for a single fixed goal. However, many tasks require an agent to be ready to navigate to any possible goal state. This paper introduces the Airport Hierarchy, a novel data structure and algorithm that automatically generates abstract action hierarchies. By designating certain states as "airports" (landmarks), the system can solve for all $N$ possible goals much more efficiently than traditional all-pairs approaches. We demonstrate that building these multi-value functions is computationally cheaper and requires significantly less memory while maintaining near-optimal performance.
Introduction
Standard reinforcement learning usually solves an MDP for a single, fixed goal. In contrast, many real-world applications require an agent to be "ready for anything"—capable of navigating to any state on demand. The naive approach of pre-calculating a value function for every possible goal state requires $O(N^2)$ memory and massive computational overhead. While hierarchical methods like Hierarchical Distance to Goal (HDG) exist, they often rely on human-provided heuristics or pre-defined state partitions. The authors propose a method to build these hierarchies automatically, using only the true dynamics and costs of the MDP itself.
The Airport Hierarchy
The core of the proposed method is the Airport Hierarchy, where specific states are designated as "airports" at varying levels of seniority. Senior airports (Level 0) act as global hubs, while junior airports handle local navigation.
The algorithm selects airport locations by identifying states furthest from existing airports in terms of expected cost. Because this hierarchy is built using actual MDP transition probabilities and costs rather than geometric proxies like Euclidean distance, it remains robust in environments with non-spatial features like one-way walls or "teleporters."
Methodology
Instead of a standard value function $V(x)$, the system utilizes a multi-value function $J^*(x, y)$, representing the minimum expected cost to reach goal $y$ from state $x$. To efficiently compute these values, the authors employ a branch-and-bound procedure that maintains optimistic lower bounds ($J^{opt}$) and pessimistic upper bounds ($J^{pess}$) for costs.
This construction is integrated with prioritized sweeping to focus updates on states with significant cost changes. When an agent is distant from its goal, it does not plan a direct path; instead, it targets the most senior airport it "knows" how to reach that lies on the path to the goal. This approach exploits the sparsity of real-world MDPs, allowing the hierarchy to scale logarithmically rather than quadratically.
Experimental Evaluation
The authors evaluated the Airport Hierarchy across several stochastic environments:
- Stochastic Grid-worlds: Mazes with noisy movement (e.g., 10% chance of random transitions).
- Expand Mazes: Increasingly large environments (up to 7,275 states) to test scalability.
- One Way Maze: A maze with non-reversible actions to test handling of asymmetric costs.
- Inventory Management: A non-spatial MDP demonstrating the algorithm's general applicability.
Key Results
Empirical results demonstrate substantial efficiency gains over traditional methods:
- Memory Efficiency: In the largest "Expand15" maze, the Airport Hierarchy required 72x less memory than a full all-pairs table.
- Computational Speed: Construction was up to 48x faster than traditional MDP solvers for large state spaces.
- Near-Optimality: The "regret" (additional cost over the optimal policy) was remarkably low, typically between 1% and 2%.
- Scalability: Time and memory requirements grew much more slowly than the total number of states, suggesting viability for very large environments.
Conclusion
The Airport Hierarchy provides a powerful, automatic way to create action hierarchies for multi-goal MDPs. By leveraging the inherent locality of most state spaces, it enables efficient planning for any goal state. Future work may involve integrating this hierarchy into more complex frameworks like MAXQ or utilizing the short plan sequences for real-time exhaustive search and replanning.
Summary updated