Erel Kaplan, Tomer Bitan, Lian Ghrayeb, Le Chen, Tom Yotam, Niranjan Hasabnis, Gal Oren. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Decision making under uncertainty is at the heart of any autonomous system acting with imperfect information. The cost of solving the decision-making problem is exponential in the action and observation spaces, thus rendering it unfeasible for many online systems. This article introduces a novel approach to efficient decision making, by partitioning the high-dimensional observation space. Using the partitioned observation space, we formulate analytical bounds on the expected information-theoretic reward, for general belief distributions. These bounds are then used to plan efficiently while maintaining performance guarantees. We show that the bounds are adaptive and computationally efficient, and that they converge to the original solution. We extend the partitioning paradigm and present a hierarchy of partitioned spaces that allows greater efficiency in planning. We then propose a specific variant of these bounds for Gaussian beliefs and show a theoretical performance improvement of at least a factor of 4. Finally, we compare our novel method to other state-of-the-art algorithms in active simultaneous localization and mapping scenarios, in simulation and in real experiments. In both cases, we show a significant speedup in planning with performance guarantees.