不完全信息下的最优决策与可判定POMDP研究

不完全信息下的最优决策

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

程序合成的实际应用

Synthèse团队致力于解决程序合成这一挑战性问题——开发能够根据少量示例或预期规范自动生成其他算法的算法。这些强大算法在实际中有多种应用场景：

• 电子表格应用程序的自动填充功能：用户填写少量单元格后，系统即时合成小型算法完成剩余部分
• 机器人控制：操作员分配任务后，机器人算法自动确定达成目标的最佳动作序列

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

研究人员常用马尔可夫决策过程这一数学形式化方法解决合成问题。MDP是有限状态系统，其演化同时受决策（选择动作）和随机因素影响。以纸牌游戏为例：当部分纸牌背面朝上时，玩家需要在不完全信息下做出决策。

两类AI算法对比

启发式算法：实践表现良好但缺乏理论解释，包括大多数机器学习方法（如深度强化学习）

精确算法：始终保证正确答案但速度较慢，属于可信AI领域，基于图灵开创的可计算性和可判定性概念

获奖研究属于第二类：所提算法能可靠计算最优策略的精确解。

精确计算与AI学习的局限

基于深度强化学习的技术能处理高度复杂实例，而基于可计算性理论的精确技术目前限于较简单实例。例如：

• 某中心使用深度强化学习为《星际争霸》合成出色策略，但其策略并非最优
• 波尔多Rhoban团队使用精确方法解决小型MDP，在Robocup 2023获得金牌

信息可用性与决策复杂度

决策问题的难度高度取决于决策时可用的信息：

• 完美信息情况：所有数据可用，计算相对简单（如使用Dijkstra算法）
• 不完全信息情况：需要假设，通常无法精确解决（根据图灵可计算性理论）

研究成果与贡献

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

未来研究方向

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