Multi-Value-Functions: Efficient Automatic Action Hierarchies for Multiple Goal MDPs

Andrew W. Moore, Leemon C. Baird Iii, Leslie Pack Kaelbling

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.

A simple maze with airports of different seniority levels. Larger disks represent more senior airports.

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.

The shaded regions show the set of states $INS(y)$ that "know" how to reach a specific airport $y$.

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

Abstract

If you have planned to achieve one particular goal in a stochastic delayed rewards problem and then someone asks about a different goal what should you do? What if you need to be ready to quickly supply an answer for any possible goal? This paper shows that by using a new kind of automata caily generated abstract action hierarchy that with N states, preparing for all of N possible goals can be much much cheaper than N times the work of preparing for one goal. In goal-based Markov Decision Problems, it is usual to generate a policy π(x) mapping states to actions, and a value function J(x) mapping states to an estimate of minimum expected cost-to-goal, starting at x. In this paper we will use the terminology that a multipolicy π*(x, y) (for all state-pairs (x, y)) maps a state x to the first action it should take in order to reach y with expected minimum cost and a multi-valuefunction J*(x, y) is a definition of this minimum cost. Building these objects quickly and with little memory is the main purpose of this paper, but a secondary result is a natural, automatic, way to create a set of parsimonious yet powerful abstractactions for MDPs. The paper concludes with a set of empirical results on increasingly large MDPs.
BibTeX
@inproceedings{moore1999multi,
  author = {Andrew W. Moore and Leemon C. Baird III and Leslie Pack Kaelbling},
  title = {{Multi-Value-Functions: Efficient Automatic Action Hierarchies for Multiple Goal MDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure