Towards Scalable MDP Algorithms

Andrey Kolobov, Mausam, Daniel S. WeldIJCAI 2011 · OpenReview

Abstract

Planning under uncertainty is a fundamental challenge in Artificial Intelligence, typically modeled using Markov Decision Processes (MDPs). However, the practical application of MDPs is often hindered by the "curse of dimensionality," where state space sizes grow exponentially, leading to memory exhaustion in traditional solvers. This research advances the state of the art by introducing a novel generalization framework for Stochastic Shortest Path (SSP) problems. By automatically generating basis functions to represent state information compactly, the proposed approach enables efficient planning in environments previously considered computationally intractable. The work contributes new algorithms—RETRASE, GOTH, and SIXTHSENSE—and extends the mathematical theory of MDPs to handle Generalized Stochastic Shortest-Paths (GSSPs), demonstrating superior performance on international benchmarks and real-world urban traffic scenarios.

Introduction

Since the inception of AI, planning under uncertainty has been a primary objective. Markov Decision Processes (MDPs) provide a robust mathematical framework for this, specifying agent objectives, available actions, and probabilistic state transitions. Solving an MDP involves finding an optimal policy—a mapping of actions to states that maximizes a reward or minimizes a cost.

Despite their elegance, optimal solution methods often require analyzing the entire state space. In realistic scenarios, such as urban traffic routing, the number of possible states is astronomical. Traditional "Find-and-Revise" algorithms use heuristics to focus on relevant states, but even these eventually succumb to memory limits. To bridge this gap, this research proposes a shift from state-level analysis to a generalization-based approach that leverages the underlying structure of the problem.

The Scalability Challenge

Existing approaches to scaling MDPs generally fall into three categories, each with distinct limitations:

  1. Heuristic Search: While these methods focus on reachable states, they still store individual state values, leading to memory bottlenecks in large domains.
  2. Determinization: These techniques simplify the problem by ignoring probabilities. While fast, they often fail to account for high-risk, low-probability events that are crucial in stochastic environments.
  3. Function Approximation: This method compresses state information into "basis functions." However, these functions typically require manual engineering by domain experts, limiting their generalizability.

A Framework for Automatic Generalization

The core contribution of this work is a framework that automates the creation of basis functions, combining the speed of determinization with the accuracy of probabilistic planning. Instead of manual definition, the system discovers essential state features through a process of regression through trajectories.

Key Algorithms

  • RETRASE (REgression-TRajectory-based Asynchronous Value Iteration): This planner updates basis functions using Bellman-like backups. It learns probabilistic values across many states simultaneously without the need to store each state individually in memory.
  • GOTH: A memory-frugal heuristic that estimates state values based on the costs of the deterministic trajectories used to derive the basis functions. It serves as a more efficient alternative to standard heuristics like "Fast Forward" (FF).
  • SIXTHSENSE: A component designed to identify "dead ends"—states from which a goal is unreachable. By pruning these states early, it prevents the planner from wasting computational resources on hopeless paths.

Theoretical Extensions: GSSP

Beyond algorithmic improvements, this research addresses a theoretical gap in MDP classes. Standard SSP solvers often fail in the presence of "zero-cost loops," where an agent can cycle through states without accumulating cost, breaking convergence properties. This work develops the mathematical apparatus for Generalized Stochastic Shortest-Paths (GSSP), introducing new operators that ensure convergence and allow approximation techniques to be applied to a broader range of complex MDPs.

Experimental Results and Impact

The proposed framework was evaluated using benchmarks from the International Probabilistic Planning Competitions (IPPC) and real-world data from Stockholm’s urban traffic network.

  • Performance: RETRASE outperformed previous IPPC winners on several complex problems, demonstrating that automatic basis function generation can match or exceed the performance of state-based solvers.
  • Efficiency: The GOTH heuristic proved significantly more memory-efficient than traditional counterparts, while SIXTHSENSE appreciably reduced search times by identifying "nogood" states.
  • Real-World Application: In the context of urban traffic routing, the research suggests that scalable MDP algorithms can account for probabilistic fluctuations in traffic flow more effectively than deterministic models. Preliminary analysis indicates that such planning could reduce average travel times in major metropolitan areas by over 60%.

Conclusion

This research provides a path forward for scaling probabilistic planning to real-world dimensions. By integrating heuristic search, determinization, and automatic function approximation, the framework overcomes the memory constraints of state-level analysis. The extension of these techniques to GSSPs further broadens the applicability of AI planning, moving the field closer to fulfilling its vision of intelligent agents capable of navigating complex, uncertain environments.

Summary updated

Abstract

Since the emergence of Artificial Intelligence as a field, planning under uncertainty has been viewed as one of its crucial subareas. Accordingly, the current lack of scalability of probabilistic planning techniques is a major reason why the grand vision of AI has not been fulfilled yet. Besides being an obstacle to advances in AI, scalability issues also hamper the applicability of probabilistic planning to real-world problems. A powerful framework for describing probabilistic planning problems is Markov Decision Processes (MDPs). Informally, an MDP specifies the objectives the agent is trying to achieve, the actions the agent can perform, and the states in which it can end up while working towards the objective. Solving an MDP means finding a policy, i.e. an assignment of actions to states, that allows the agent to achieve the objective. Optimal solution methods, those that look for the “best” policy according to some criterion, typically try to analyze all possible states or a large fraction of them. Since state space sizes of realistic scenarios can be astronomical, these algorithms quickly run out of memory. Fortunately, the mathematical structure of some classes of MDPs has allowed for inventing more efficient algorithms. This is the case for Stochastic Shortest Path (SSP) problems, whose mathematical properties gave rise to a family of algorithms called Find-and-Revise. When used in combination with a heuristic, the members of this family can find a near-optimal, or even optimal, policy while avoiding the analysis of many states. Nonetheless, the sheer number of states in real-world problems forces algorithms based on state-level analysis to exhaust their capabilities much too early, calling for a fundamentally different approach. Moreover, several expressive and potentially useful MDP classes are currently not known to have a mathematical structure for creating efficient approximation techniques. This dissertation advances the state of the art in probabilistic planning in three complementary ways. For SSP MDPs, it derives a novel class of approximate algorithms based on generalizing state analysis information across many states. This information is stored in the form of basis functions that are generated automatically and the number of which is much smaller than the number of states. As a result, the proposed algorithms have a very compact memory footprint and arrive at high-quality solutions faster than their state-based counterparts. In a parallel effort, the dissertation also builds up mathematical apparatus for classes of MDPs that previously had no applicable approximation algorithms. The developed theory enables the extension of the powerful Find-and-Revise paradigm to these MDP classes as well, providing the first memory-efficient algorithms for solving them. Last but not least, the dissertation will apply the proposed theoretical techniques to a large-scale real-world problem, urban traffic routing being one of the candidates.
BibTeX
@inproceedings{kolobov2011towards,
  author = {Andrey Kolobov and Mausam and Daniel S. Weld},
  title = {{Towards Scalable MDP Algorithms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=H1452QMdbr},
}
Figure