Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

在人工智能领域，决策过程通常被视为在一块规则完全已知的棋盘上进行的概率游戏。想象一个机器人在迷宫中导航；如果工程师们确切知道地板有多滑，以及机器人的轮子会如何转动，他们就能计算出通往出口的最佳路径。这是许多决策系统的标准模型。然而，现实世界很少如此精确。传感器会失效，材料会磨损，数据也存在噪声，这意味着机器人打滑或汽车漂移的确切概率永远无法真正知晓，只能在一定的可能范围内进行估计。当这些不确定性加入其中时，问题变得更加困难：当你无法确定地形的行为特征时，该如何规划一条安全的路径？此外，在自动驾驶或医疗机器人等安全至上的领域，目标不仅是快速到达目的地，还要保证系统永远不会进入危险状态，或永远遵循某种特定的逻辑事件序列。

印度理工学院孟买分校与南洋理工大学的研究人员解决了这种不确定性与严格逻辑安全性交织在一起的难题。他们专注于一类问题，即智能体必须在只能部分观察世界的情况下做出决策，且运动规则并非固定的数值，而是属于一组可能的取值范围。研究团队证明，解决这类复杂的、具有不确定性的决策问题，在数学上等同于解决另一种研究充分的、涉及两个拥有隐藏信息的对立玩家的游戏。通过建立这种双向联系，他们能够借鉴数十年来现有的博弈论知识，从而立即确定解决这些不确定机器人问题的计算难度。他们的工作揭示了在这些场景下保证安全性的难度究竟有多大，表明对于某些类型的逻辑目标，该问题可以通过已知方法解决；而对于另一些类型，其复杂程度之高，以至于没有任何算法能在合理的时间内求解。

他们发现的核心在于架起了两个不同数学世界之间的桥梁。一方面是鲁棒部分可观测马尔可夫决策过程（robust partially observable Markov decision process），这是一种用于描述智能体（如自动驾驶汽车）在不知道确切位置且不知道移动到新状态的确切概率时，必须选择行动的模型。在这种模型中，系统并非运行在单一概率之下，而是运行在一个可能概率的“云团”之中。另一方面是部分可观测随机博弈（partially observable stochastic game），这是一个由两名玩家组成的模型，一名玩家试图成功，另一名玩家试图阻止其成功，双方在仅掌握部分信息的情况下轮流行动。多年来，研究人员已知如果目标仅仅是最大化奖励，这两个模型可以相互转化。然而，当目标转向严格的逻辑规则时——例如“绝不撞到行人”或“最终到达医院并永远停留在那里”——这种联系就中断了。这项新研究证明，即使面对这些复杂的逻辑规则，这两个模型仍然是完全等价的。

为了证明这一点，研究人员构建了一个可以双向工作的精确转换机制。首先，他们展示了如何将一个具有不确定概率的鲁棒决策问题转换为一个双人博弈。在这个新博弈中，智能体成为了其中一名玩家，而世界的这种不确定性则变成了第二名对手玩家。这名第二名玩家并非随机行动，而是会从可用选项中主动选择最坏的情况，试图击败智能体。研究人员证明，如果智能体能在这种对抗聪明对手的博弈中获胜，它也能在原始的不确定世界中取得成功。更令人惊讶的是，他们实现了反向转换。他们展示了任何带有隐藏信息的双人博弈都可以转换回一个鲁棒决策问题。这一反向步骤在技术上非常困难，因为在博弈中，对手会在行动前看到智能体的动作，而在决策问题中，环境会立即提交其行为。团队通过在博弈结构中插入一个短暂且不可见的停顿解决了这个问题，从而有效地让环境获得了与原问题中相同的观测信息。这种双向桥梁意味着，任何关于解决某一类问题难度的计算机科学结论，都会自动适用于另一类问题。

这项研究对于理解自动化推理的极限具有直接且深远的影响。通过利用这座桥梁，研究人员能够绘制出解决各类逻辑目标问题的精确计算复杂度图谱。他们发现，对于简单的目标，例如到达目标点或避开危险区域，这些问题是可解的，尽管它们需要随着系统规模呈指数级增长的巨大计算能力。然而，研究也识别出了一个硬性限制。对于某些复杂的逻辑目标，特别是那些在双侧不确定环境下涉及“始终”和“最终”混合条件的逻辑目标，该问题是不可判定的。这意味着，无论多么强大的计算机程序，都无法针对每一种可能的情况保证给出答案。研究人员还阐明了单侧不确定性下的难度，即只有智能体是盲目的，而环境能看到一切，结果显示这类情况通常比全盲场景更容易解决。

这项工作为设计处于不确定性下的安全自主系统提供了完整的可能性景观。它证实了虽然我们可以构建算法来处理许多安全关键型任务，但在隐藏信息、对抗性不确定性和复杂逻辑规则相结合的情况下，存在着使解决方案变得不可能实现的根本边界。该研究并非提供一种能解决所有案例的新算法，而是提供了一张明确的地形图，告诉工程师哪些问题是可以解决的，而哪些问题则需要完全不同的处理方法。通过证明这两个数学框架是相同的，研究人员解锁了一个庞大的现有工具和理论库，使该领域能够在清晰了解未来挑战的基础上向前迈进。