arXiv:2310.01791v4 宣告类型：替换 摘要：在信息不完整的情况下，不确定环境下的决策是许多实际自主系统的关键方面。部分可观测马尔可夫决策过程（POMDP）提供了在这些条件下形式化决策问题的数学稳健框架。然而，找到POMDP的最优解通常是不可行的。近年来，使用在线树搜索求解器从小型问题扩展到中等规模问题的近似求解器的规模扩展取得了一定的进展。通常，这样的近似求解器仅提供最优解的概率性或渐近性保证。在本文中，我们为离散POMDP导出了近似解与最优解之间的确定性关系。我们证明，在任何时间点，都可以导出将现有解与最优解联系起来的界。我们展示了我们的推导为一组新的算法提供了途径，并可以附加到具有特定结构的现有算法上，以提供确定性的保证，且计算开销很小。通过这种方法，我们不仅证明了解决方案的质量，而且还展示了基于确定性保证进行决策可能会比未进行确定性认证的原算法在性能上更优。