Autonomous agents operating in real-world scenarios frequently encounter
uncertainty and make decisions based on incomplete information. Planning under
uncertainty can be mathematically formalized using partially observable Markov
decision processes (POMDPs). However, finding an optimal plan for POMDPs can be
computationally expensive and is feasible only for small tasks. In recent
years, approximate algorithms, such as tree search and sample-based
methodologies, have emerged as state-of-the-art POMDP solvers for larger
problems. Despite their effectiveness, these algorithms offer only
probabilistic and often asymptotic guarantees toward the optimal solution due
to their dependence on sampling. To address these limitations, we derive a
deterministic relationship between a simplified solution that is easier to
obtain and the theoretically optimal one. First, we derive bounds for selecting
a subset of the observations to branch from while computing a complete belief
at each posterior node. Then, since a complete belief update may be
computationally demanding, we extend the bounds to support reduction of both
the state and the observation spaces. We demonstrate how our guarantees can be
integrated with existing state-of-the-art solvers that sample a subset of
states and observations. As a result, the returned solution holds deterministic
bounds relative to the optimal policy. Lastly, we substantiate our findings
with supporting experimental results.

通过简化解决方案与理论上最优解之间的确定性关系，解决了在计算上昂贵的部分可观测马尔可夫决策过程（POMDPs）困难，为自主代理在不完全信息环境下的规划提供了确定性界限。