不完全信息下的最优决策

论文《Revelations: A Decidable Class of POMDP with Omega-Regular Objectives》荣获AAAI 2025会议杰出论文奖，这是人工智能领域的顶级国际会议。今年在12,000篇投稿和3,000篇录用论文中仅有3篇获此殊荣。该研究成果源于波尔多计算机科学研究实验室Synthèse团队的工作，涉及来自法国、比利时和荷兰的研究人员。

程序合成与决策问题

Synthèse团队致力于解决程序合成这一挑战性问题——开发能够根据少量示例或预期规范自动生成其他算法的算法。实际应用中，这类强大算法被用于多种场景。例如，现代电子表格应用程序大多提供自动填充功能：用户填写少量单元格后，系统即根据这些示例实时合成小型算法完成剩余填充（DeepSynth）。另一个例子是机器人控制：操作员给机器人分配任务（如在Robocup比赛中重新控球），机器人的算法会确定实现目标的最佳动作序列。

马尔可夫决策过程（MDP）基础

研究人员常用马尔可夫决策过程这一数学形式化方法解决合成问题。MDP是一种有限状态系统，其演化同时受决策（选择动作）和随机因素影响。在实际场景中（如纸牌游戏），决策者常面临部分信息不可见的情况，需要在卡片逐步揭示的过程中不断调整策略。

两类AI算法对比

解决MDP的AI算法主要分为两类：

启发式算法：实践效果良好但缺乏理论成功解释，大多数机器学习方法（特别是使用神经网络的DeepRL）属于此类

精确算法：始终保证提供正确答案，但通常比启发式算法慢，属于可信AI领域，基于艾伦·图灵开创的可计算性和可判定性概念

本研究属于第二类：所提算法能可靠计算精确解（即最优策略），可完全放心使用。

精确计算与AI学习的局限

基于DeepRL的学习技术能计算高度复杂实例的策略，而基于可计算性理论的精确技术目前仅限于较简单实例。例如，某中心使用DeepRL技术为《星际争霸》合成出色策略，这款流行视频游戏需要基于数百万参数每秒做出数十次决策。虽然该AI最初击败了世界最佳玩家，但其策略并非最优——后来发现了未预料到的反制策略。

精确方法目前难以解决《星际争霸》这类复杂问题，但在实践中仍然有效。例如，波尔多Rhoban团队通过使用精确方法解决小型MDP，依靠多协作机器人间的信息共享，在Robocup 2023中获得金牌。

信息揭示与可判定类突破

获奖研究识别出一类可判定的MDP：具有"强揭示"特性的决策问题，即在每一步都存在非零概率完全揭示世界状态。论文还提供了"弱揭示"的可判定性结果，即保证最终会揭示确切状态但不一定在每一步都揭示——类似于纸牌游戏中隐藏卡片逐渐被揭开的情况。

该算法能分析具有揭示特性（特别是强揭示）的MDP。一个有趣的前景是逆转问题：当算法用于任何游戏（无论是否有揭示特性）时会发生什么？这可能通过限制玩家可使用策略类型或可处理信息量，实现对所有游戏（即使最复杂的）的分析。