部分可观测马尔可夫决策过程(POMDP)是一种序贯决策数学模型,其中智能体能够影响不断变化的环境,却只能获得关于环境状态的不完整信息或带有噪声的信息。它在马尔可夫决策过程的基础上,将底层状态与智能体能够获得的观测区分开来。因此,决策不仅取决于当前观测,还取决于从以往动作和观测中积累的信息。POMDP 用于人工智能、运筹学等领域,描述采取行动与获取信息密不可分的问题。
数学表述
一种常见的有限状态表述由元组
以及初始信念 构成,其中:
- 是所有可能的环境状态组成的集合。
- 是可用动作的集合。
- 是所有可能的观测组成的集合。
- 是在状态 下采取动作 后转移到状态 的概率。
- 是动作 导致系统进入状态 后获得观测 的概率。
- 是在状态 下采取动作 的期望即时奖励。
- 是折扣因子;对于无限时域折扣问题,通常满足 。
初始信念 是初始状态上的概率分布。有限时域模型还会指定剩余的决策次数,并且可以包含终端奖励。
标准的时序约定如下:
- 环境处于未被观测到的状态 。
- 智能体选择动作 。
- 环境转移到 。
- 智能体获得观测 。
转移模型和观测模型满足
以及
这些假设体现了受控的马尔可夫性质以及观测的条件独立结构。隐状态必须包含足够的信息,才能使这些假设成立;如果状态描述不充分,一个名义上的 POMDP 模型就可能遗漏重要的依赖关系。
其他约定允许观测同时依赖前一状态和后一状态,或允许奖励依赖状态转移与观测。这些变体并不改变隐状态与可用信息之间的核心区别。如果观测到的奖励提供了关于状态的额外信息,那么这些信息也必须纳入智能体的观测历史。
信念状态与贝叶斯更新
单次观测通常无法确定当前状态。因此,智能体会维护一个信念状态:
其中, 表示智能体可用的历史信息,包括以往的动作和观测。
在 POMDP 模型已知的情况下,信念状态是预测未来状态和观测、评估未来动作所需的充分统计量。如果历史中的相关信息已由 精确表示,就不必保留完整历史。
采取动作 后,智能体首先预测下一状态:
获得观测 后,再应用贝叶斯定理:
分母为观测概率
对于在当前信念和模型下具有正概率的观测,这一更新才有定义。
这是贝叶斯推断的一种递归形式:利用观测似然更新预测信念,得到后验分布。即使 是有限集,所有可能的信念仍构成一个连续的概率单纯形:
因此,有限 POMDP 可以转化为一个以信念分布为状态的完全可观测决策过程,但这个新的状态空间通常是无限的。
策略与目标
策略规定智能体如何根据可用信息选择动作。它可以写成从历史到动作或动作分布的映射。采用信念状态表示后,有限时域策略也可以写为 ,其中时间下标用于反映剩余时域。
对于无限时域折扣准则,优化目标为
这里的期望值是对初始状态、状态转移、观测以及策略可能引入的随机性取平均。奖励有界且 ,即可保证折扣回报有限。
其他目标包括有限时域总奖励、长期平均奖励和带约束的准则。这些表述需要不同的假设,其策略结构或收敛保证也不一定相同。
信念为 时的期望即时奖励为
在状态集、动作集和观测集均有限、奖励有界的条件下,无限时域折扣优化问题存在最优的确定性平稳信念状态策略。“平稳”是指决策规则依赖当前信念,而不显式依赖时间;它并不意味着智能体总是选择同一个动作。
动态规划与价值函数结构
这个方程同时体现了动作对环境状态和信息的影响。动作不仅改变未来状态的分布,还会改变可能获得哪些观测,进而改变未来可以作出哪些决策。
有限时域的 α 向量表示
当状态集、动作集和观测集均有限,时域有限,且没有终端奖励或终端奖励关于信念呈线性关系时,最优价值函数是分段线性凸函数:
其中, 是由有限个 α 向量组成的集合。
每个向量表示一个条件策略在各个状态条件下的期望回报:该策略先采取一个动作,再根据观测结果分支选择后续动作。其期望回报关于初始信念呈线性关系。对这些策略取最大值,就得到由线性片段构成的凸函数。
在给定信念处,与取得最大值的向量对应的策略就是最优策略。有些向量从来都不是取得最大值所必需的,因此可以删除;可使用线性规划来检验这种支配关系。
有限表示并不意味着精确求解容易。候选策略树的数量,以及相应的候选向量数量,都可能随着规划时域的增长而迅速增加。无限时域折扣价值函数仍然是凸的,也可以用有限个 α 向量近似,但不能保证存在精确的有限表示。
信息获取动作
POMDP 的一个显著特征是:即使某个动作的即时奖励很低,它仍可能因改善后续决策而具有价值。
一个经典例子是老虎问题。一只老虎藏在两扇门中的某一扇后面。打开门时,如果老虎就在门后,就会遭受巨大损失;否则会获得奖励。倾听需要付出少量代价,但能够提供关于老虎位置的带噪声线索。
因此,智能体在开门前先倾听可能是理性的选择。倾听的益处不只是减少不确定性,更在于由此获得的观测可能改变应该打开哪扇门的判断。
这一区别将与决策有关的信息和单纯减少不确定性区分开来。最小化信息熵通常并不等同于最大化期望奖励。某个观测可能揭示大量与决策无关的状态信息,却几乎不影响当前可选动作中的最优选择。
求解方法
不同 POMDP 算法的区别,在于如何表示信念、策略以及未来可能出现的各种情况。
精确方法
精确的有限时域价值迭代通过动态规划回推构造 α 向量集合,并删除被支配的向量。更先进的剪枝方法能够减少中间计算量,但最坏情况下的规模增长仍然十分严重。
有限状态控制器提供了另一种表示方式。控制器具有内部记忆节点,每个节点对应一个动作,节点之间的转移取决于观测。这类控制器能够紧凑地表示实用的策略,但固定大小的控制器未必足以表示最优策略。
基于点的近似
基于点的方法只在选定的信念处近似价值函数,而不是在整个信念单纯形上均匀求解。通常从初始条件可达的区域中采样信念。
这些方法利用了这样一个事实:许多数学上可能的信念,对某个具体规划问题可能并不重要。其精度取决于所选信念、回推过程以及误差控制所依赖的假设。
在线规划
在线方法从当前信念出发进行规划,选定动作后再更新信念,并重新规划。搜索树在动作层与观测层之间交替展开。
基于仿真的规划器使用蒙特卡洛方法探索可能的未来。当精确滤波代价高昂时,可以用粒子表示来近似信念。这些方法的表现取决于仿真预算、探索策略、观测分支情况以及信念近似的质量。
学习得到的近似
对于大规模空间或连续空间,规划器可以使用函数逼近来表示信念、价值或策略。循环模型可以概括观测历史,而不必显式维护贝叶斯信念。
这种概括并不自动成为充分统计量。仅凭良好的实证表现,无法证明其与精确的信念状态解等价。
与其他模型的关系
完全可观测马尔可夫决策过程是一种特殊情形,其中观测能够揭示当前状态。从已知状态出发,每次观测后的信念都会集中在单一状态上。
隐马尔可夫模型描述隐状态转移和带噪声的观测,但不具有相同的动作选择目标。POMDP 加入了控制与奖励,因此必须在推断状态的同时选择动作。
卡尔曼滤波器用于计算线性高斯状态空间模型中的信念。在适当的部分可观测控制问题中,高斯信念可以由均值和协方差矩阵表示,而不必使用一般形式的分布。线性二次高斯控制中常见的估计与控制分离,是一种特殊的结构性结果,并非 POMDP 的普遍性质。
标准 POMDP 表述假定转移模型、观测模型和奖励模型均已知。未知的模型参数有时可以并入扩展后的隐状态,但这样做会引入学习问题,并可能大幅增加计算需求。
应用与局限
POMDP 用于建模带噪声传感器条件下的机器人导航、设备检查与维护、搜索任务、对话管理以及资源监测等问题。在这些应用中,隐状态表示与决策有关但无法直接观测的条件,而动作既可以影响这些条件,也可以影响可获得的相关信息。
其主要局限包括:
- 信念空间的复杂性。 当存在 个隐状态时,信念单纯形的维数为 ;随着 增大,要广泛覆盖这一空间会变得困难。
- 历史分支。 即使模型很小,可能的动作—观测序列数量也会随时域增长而迅速增加。
- 对模型的依赖。 信念更新和规划出的动作依赖于转移假设与观测假设的准确性。
- 表示误差。 近似信念、压缩后的历史以及受限的策略类别,都可能丢失作出良好决策所需的信息。
- 目标设定。 最大化期望奖励并不会自动保证满足安全约束、公平性要求或对罕见损失的限制。
前两种困难通常分别称为维数灾难和历史灾难。它们解释了为什么即使问题描述十分紧凑,所产生的规划问题仍可能需要大量计算。
历史发展
POMDP 源于随机控制、统计决策和动态规划领域的研究。卡尔·约翰·奥斯特伦在 20 世纪 60 年代的工作,推动确立了利用状态的条件分布来控制不完全可观测马尔可夫过程的方法。理查德·斯莫尔伍德和爱德华·桑迪克在 20 世纪 70 年代初的工作,则确立了重要的有限时域价值函数结果和计算方法。
后续研究发展出了精确剪枝算法、有限状态控制器、基于点的近似以及基于仿真的在线规划。这些方法拓展了该框架的实际应用,同时保留了其核心表述:根据可能状态的概率分布进行决策,而不是根据直接观测到的状态进行决策。