不完全信息下的最优决策

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

研究背景与团队工作

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

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

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

在解决综合问题时，工程师和AI研究人员通常使用马尔可夫决策过程这一数学形式化方法。核心问题是：在需要序列决策的情境中，如何做出良好决策？如何自动计算最佳决策序列（即最优策略）？

MDP是有限状态系统，其演化由决策（选择动作）和随机因素共同决定。日常生活中，MDP可用于纸牌游戏等场景，玩家需要在不完全信息下做出决策。

两类AI算法对比

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

启发式算法：实践表现良好但缺乏理论解释，包括大多数机器学习方法（特别是使用神经网络的DeepRL）

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

本研究属于第二类：提出的算法可靠地计算精确解，形成可完全信赖的最优策略。

精确计算与AI学习的局限性

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

• 某中心使用DeepRL技术为《星际争霸》游戏合成出色策略，但并非最优策略
• 精确方法虽不适用于《星际争霸》等复杂问题，但在实践中仍然有效：波尔多团队在Robocup 2023中获得金牌，使用精确方法解决小型MDP，依赖多协作机器人间的信息共享

决策问题复杂性与信息作用

决策问题的解决难度很大程度上取决于决策时可用信息的多少：

• 完美信息场景：所有数据可用（如机器人导航已知布局的迷宫），相对容易解决
• 不完全信息场景：实际问题的常见情况（如纸牌游戏中的隐藏牌），通常无法精确解决

根据图灵可计算性理论，没有任何算法能始终精确解决所有MDP控制问题。但这并不阻止计算机科学家寻找问题变得更简单的特殊情况——即可判定类。

获奖研究的贡献

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

未来研究方向

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