α-min: A Compact Approximate Solver For Finite-Horizon POMDPs

Yann Dujardin, Tom Dietterich, Iadine ChadesIJCAI 2015

Introduction

Partially Observable Markov Decision Processes (POMDPs) provide a robust framework for sequential decision-making under uncertainty. However, they are plagued by the "complexity curse." While standard solvers prioritize near-optimal performance, they often produce policies consisting of thousands of $\alpha$-vectors—mathematical decision rules that are virtually impossible for human stakeholders to interpret or implement manually. In fields like conservation biology or public policy, there is a critical demand for compact solvers that can find high-performing policies within a strict budget of rules.

The α-min Algorithm

The authors propose $\alpha$-min, a solver specifically designed for finite-horizon POMDPs that treats policy compactness as a primary constraint. The algorithm's efficiency stems from its approach to value function improvement:

  1. Gap Minimization: Instead of the standard point-based approach of random belief sampling, $\alpha$-min identifies the belief point where the gap between the current lower bound and the theoretical upper bound is maximized.
  2. MILP Formulation: To overcome the NP-hard nature of finding this "maximum gap" point, the authors reformulate the search as a Mixed Integer Linear Program (MILP). This allows the use of high-performance solvers like CPLEX to efficiently find the most impactful $\alpha$-vectors to add to the policy.
Illustration of the gap minimization process in α-min.

The algorithm offers two modes: $\epsilon$-min, which adds vectors until a target error tolerance is met, and $\alpha$-min, which operates within a fixed budget of $N$ vectors. Notably, because it is designed for finite horizons, $\alpha$-min can handle non-stationary problems where the environment changes over time.

Key Results and Benchmarks

The algorithm was evaluated against standard POMDP benchmarks (aloha.10, learning.c3, cheng.D4-5, milos-aaai97) and a large-scale randomized problem (random30).

Comparison of α-min and SARSOP across various benchmarks.

As shown in the results table, $\alpha$-min consistently produces policies that are significantly more compact than those from state-of-the-art solvers like SARSOP, while maintaining competitive lower bounds. For instance, on the milos-aaai97 problem, $\alpha$-min achieved a lower bound of 50.31 using only 20 vectors, whereas SARSOP required 122 vectors for a lower bound of 41.48 within the same time horizon.

In a real-world case study involving Sumatran tiger conservation, $\alpha$-min generated a policy with just 7 vectors that remained within 10% of the optimal strategy, demonstrating its utility for practical, human-interpretable decision-making.

Limitations and Future Work

While the MILP approach is efficient for small-to-medium problems, it is itself NP-hard, potentially limiting scalability as state spaces grow. Additionally, the current version does not assume knowledge of the starting belief state ($b_0$); incorporating this could lead to even more compact, tailored policies. Finally, extending the MILP-gap-minimization logic to infinite-horizon problems remains an area for future research.

Conclusion

$\alpha$-min demonstrates that for many complex problems, the marginal utility of adding more decision rules decreases rapidly. By explicitly managing the number of $\alpha$-vectors, researchers can trade a negligible amount of accuracy for a massive gain in model interpretability, providing a powerful tool for generating transparent, implementable policies.

Summary updated

BibTeX
@inproceedings{dujardin2015min,
  author = {Yann Dujardin and Tom Dietterich and Iadine Chades},
  title = {{α-min: A Compact Approximate Solver For Finite-Horizon POMDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure