5 部分可观察马尔可夫决策过程-POMDP

5.1 定义

部分可观察马尔可夫决策过程（Partially Observable Markov Decision Process，缩写：POMDP）是一种决策模型，它用于描述在部分可观测环境中的决策制定过程。与传统的马尔可夫决策过程（MDP）相比，POMDP中的智能体无法直接观察到环境的真实状态，而只能通过一系列的观测来推断状态，并作出决策。

5.2 核心概念

5.2.1 基础元素

POMDP由以下几个核心组成部分构成：

状态空间：所有可能的状态集合，在POMDP中，有些状态量是不可直接观测的，例如障碍物的变道意图，是否避让等。

动作空间：在每个状态下智能体可以采取的所有可能动作。

状态转移概率：状态转移的概率模型，描述了执行动作后状态变化的概率。在POMDP中，状态转移概率通常表示为，即在当前状态下采取动作后转移到状态的概率。

观测空间：智能体可以接收到的观测集合。观测是状态的不完全信息，每个观测都与一个或多个状态相关连。观测空间下的所有量都是可以直接观测的，例如agent的位置，速度和加速度等信息。

观测概率：在特定状态下执行特定动作后获得某个观测的概率，通常表示为，即在状态下采取动作后观测到的概率。

奖励函数：在给定状态下采取动作的即时奖励，通常表示为，即从状态通过动作转移到状态所获得的奖励。

折扣因子：对未来奖励的折扣，平衡即时奖励和未来奖励的重要性，的取值范围在0到1之间。

5.2.2 信念状态

在POMDP中，信念状态（belief）是一个核心概念，它表示智能体对于环境当前状态的不确定性认知。由于在POMDP中，智能体不能直接观测到环境的真实状态，而只能通过一系列观测来推断状态，因此信念状态是智能体根据过去的观测和动作来估计环境状态的概率分布。

信念状态belief是一个概率分布，它定义在所有可能的状态上，表示为。信念状态捕捉了智能体对当前状态的不确定性，其中表示智能体相信系统处于状态的概率。在此过程，主体需要依赖过去的动作和观察信息来评估第时刻的状态的概率分布。我们把过去所有的动作和观察信息称为历史，定义为：

信念状态是历史的充分统计量，表示为：

在每个决策步骤，智能体执行的动作并接收观测。根据这个观测，智能体更新其信念状态，这个过程通常使用贝叶斯规则来完成，可以表示为：

其中：

：更新后的信念状态

：在状态下采取动作后观测到的概率。

：在状态下采取动作后转移到状态的概率。

：归一化因子，确保更新后的信念状态是一个有效的概率分布，其计算方式如下：

5.2.2 策略及策略价值

策略（Policy）:在POMDP中，策略是从信念空间（belief space）到动作空间（action space）A的一个映射，表示为。这意味着，给定一个信念状态，策略会指定一个动作。信念状态是智能体对环境状态的概率估计，而策略根据这个信念状态来选择动作。

策略的价值（Value of Policy）: 对于无限时域的POMDP，策略在信念的价值是智能体通过执行策略所能获得的预期总折扣奖励，其可以表示为：

其中：表示期望值，是折扣因子，是在时间的状态下执行策略所指定的动作而获取的奖励，表示初始信念状态。

折扣因子（Discount Factor）: 折扣因子是一个介于 0 和 1 之间的常数，用于表达对即时奖励相对于未来奖励的偏好。折扣因子越接近 1，表示未来奖励越重要；越接近 0，则表示智能体更偏好即时奖励。

5.2.3 POMDP决策过程

基本步骤和流程

初始化：智能体从一个初始信念状态开始，这是对环境初始状态的概率分布的估计。

动作选择：在每个时间步骤，智能体基于当前信念状态选择最优动作。

执行动作：智能体执行所选择的动作。

观测和奖励：执行动作后，智能体会观测到一个新的观测，并接收与此动作相关的奖励。

信念更新：基于观测到的和执行的动作，使用贝叶斯规则更新信念。

重复决策：将更新后的信念状态作为下一个时间步骤的当前信念状态，重复上述动作选择、执行、观测和奖励、信念更新的步骤。

寻找最优动作

为了搜索最优动作，可以通过构建信念树的方式进行（如下图所示）：以当前信念为树根，智能体在树上进行向前看搜索（lookahead search），寻找能够最大化初始信念价值的策略，并设置。在信念树中，每一个节点代表一个信念，并且从节点分支出个动作边，每个动作边进一步分支出个观测边。

为了获取近似最优策略，我们可以在最大深度处截断信念树，并在截断的树上搜索最优策略。

在每个叶节点处，我们使用一个默认策略进行前向模拟来获取该节点最优值的下界估计
在每个内部节点处，应用贝尔曼最优性原理（Bellman's principle of optimality）来计算该节点处的状态值。

然后对信念树执行后序遍历，并使用上述公式递归计算每个节点的最大值，从而得到根节点

处的最佳动作以供执行。

策略树

如果在信念树的每个内部节点处只保留一个动作分支，信念树将转变为策略树

策略树中每个内部节点只有一个动作分支，代表了在处所选择的动作

5.3 POMDP的求解

5.3.1 离线求解

离线算法在离线情况下完成模型求解，与决策主体的在线决策过程是分离的。离线求解算法可计算决策体每种信念状态下的最优策略，在决策主体进行决策时，只需要根据当前信念状态查询得到最优动作并执行即可。

离线算法的优势在最优策略的计算不占用在线决策的时间，可保证决策的实时性，但该算法需要处理大范围信念状态空间，求解时间较长，实用性较低，常用的离线求解算法有：

值迭代（Value Iteration）

通过对价值函数进行迭代来寻找最优策略。

计算过程复杂，但对于小型问题是可行的。

策略迭代（Policy Iteration）

通过交替执行策略评估和策略改进来寻找最优策略。

通常比值迭代更快收敛，但需要有效的策略表示和评估。

点基方法（Point-Based Methods）

通过选择一组代表性的状态点来近似整个状态空间，降低计算复杂度，如PBVI（Point-Based Value Iteration）等。

5.3.2 在线求解

基于动态规划的离线规划算法对大规模问题往往并不实用，因为离线规划算法要求遍历整个状态空间计算出完整的策略，而状态空间大小跟状态空间维度呈指数增加——所谓“维度诅咒”问题。另一方面，很多实际问题的环境模型（主要指状态转移函数和回报函数）会随时间而变化，使得离线计算得到的策略往往在在线执行时已经过时。

不同于离线算法计算每种信念状态下的最优策略，在线算法只考虑当前所处的信念状态及从当前信念状态可达的其它信念状态。在线算法分为两个阶段：规划阶段（策略计算）和执行阶段。整个决策过程中规划与执行交替进行。

规划阶段分为搜索树构建和回溯两步。POMDP构建的搜索树又称与或树，由与节点（AND-Nodes）和或节点（OR-Nodes）构成，一个典型的与或树如下图所示。以当前信念状态为根节点，基于根节点遍历所有动作，得到相应的OR-Nodes。基于每个OR-Nodes，考虑所有可能的观测，并更新信念状态，获取新的信念状态节点。以此类推，直到达到事先设定的搜索深度，搜索树构建完成。构建完成后利用贝尔曼最优性原则从叶子节点开始对搜索树进行回溯，对回溯路径上各个信念状态节点的最优值进行更新。

尽管相比离线算法，一般的在线算法计算量已大幅降低，并且对动态环境中的决策也有较好效果，但依然需要处理庞大的动作空间及观测空间，影响实时性。研究者们通常关注近似算法，在保证一定的决策准确度的前提下降低运算量。

在线近似算法主要分为3类：分支与边界裁剪算法、启发式算法、基于蒙特卡洛模拟的算法。

分支与边界裁剪算法：

基本思想：通过对比不同节点最优值函数的下界和上界，裁剪已知次优的树分支，减少不必要的搜索。

实现步骤：首先，利用离线算法计算叶子节点的上界（MDP，QMDP-net，FIB（Fast Informed Bound））和下界（启发式算法或蒙特卡罗模拟）；然后利用贝尔曼最优性准则，通过反向回溯更新搜索树内部节点的边界值；最后，在树搜索过程中，根据值函数的下界和上界裁剪次优动作及其分支。

优点：能有效降低搜索树的复杂度，提高搜索效率。

启发式算法：

基本思想：通过启发式信息选取最具有潜力的分支进行搜索，以扩展更少的节点获取更好的决策。

实现步骤：每个叶子节点存储启发值，表示扩展该节点的价值；内部节点存储最优启发值节点的索引及最优值；在每次迭代过程中选取启发值最大的节点进行扩展（一般扩展一层），再采用动态规划算法，对拓展节点的祖先节点进行启发值更新。

算法变体：如Satia and Lave、BI-POMDP、AEMS、HSVI等，主要区别在于启发函数的设计。

启发函数：基于规则的启发式和基于学习的启发式

优点：计算效率高，能够快速找到一个可行解，但缺点是无法保证找到最优解，解的质量依赖于启发式函数的设计。

基于蒙特卡洛模拟的算法：

基本思想：使用大量随机事件逼近真实情况，评估当前策略的优劣。

蒙特卡洛树搜索：包含选择、扩展、仿真和反向传播四个步骤，选择最具有潜力与价值的节点进行蒙特卡洛模拟。

POMCP：交替进行蒙特卡洛树搜索和信念状态更新，通过采样信念状态空间避免POMDP的维度灾难和历史灾难。

DESPOT：在POMCP基础上进一步优化，限制采样场景数，生成稀疏搜索树，并在较小的动作空间内进行前向模拟。

优点：能处理复杂、难以准确建模的POMDP问题，但可能表现过于贪婪，且在最坏情况下表现糟糕。

5.3.3 离线求解和在线求解的优缺点对比

5.4 POMDP与MDP的区别

信息完全性

在MDP模型中，智能体在每个状态下都能完全观测到环境的真实状态。这意味着智能体拥有一个完美的传感器，能够准确无误地读取当前状态的所有信息。因此，MDP的决策过程可以直接基于当前状态进行，无需考虑其他不确定性因素。

相比之下，POMDP模型中的智能体无法直接观测到环境的真实状态，只能通过一系列不完全的观测来推断状态。这些观测可能是模糊的、延迟的，甚至是误导性的。因此，POMDP模型需要引入额外的机制来处理这种不确定性，如信念状态的更新和维护。

观测与信念状态

MDP模型中，智能体的观测与状态是一致的，即智能体总能准确知道当前状态。而在POMDP模型中，智能体的观测是状态的不完全表示，需要通过观测概率来推断当前状态的可能性。这种推断过程涉及到信念状态的更新，信念状态是智能体对环境状态的概率估计，反映了智能体对环境状态不确定性的认知。

决策复杂性

由于POMDP模型需要处理部分可观测性带来的额外不确定性，其决策过程通常比MDP更为复杂。在MDP中，智能体可以直接基于当前状态选择最优动作。而在POMDP中，智能体需要基于当前的信念状态来选择动作，这涉及到对所有可能状态的考虑和价值函数的迭代计算。

求解方法

MDP的求解方法相对简单，常用的方法包括值迭代、策略迭代和线性规划等。这些方法通常假设智能体能够完全观测到状态，因此可以直接计算状态的价值函数或最优策略。

POMDP的求解方法则更为复杂，需要考虑信念状态的更新和维护。常见的求解方法包括点基价值迭代、信念空间规划、蒙特卡洛方法和各种近似动态规划方法。这些方法试图在处理部分可观测性的同时，寻找最优或近似最优的决策策略。

总的来说，POMDP与MDP的主要区别在于信息的完全性和观测的可靠性。POMDP模型通过引入信念状态和观测概率，能够更好地模拟现实世界中的不确定性和部分可观测性，但也带来了更高的决策复杂性和求解难度。

5.5 求解器

github中开源了比较多的POMDP求解器：

python版本

PBVI (Point-Based Value Iteration) and POMCP (Partially Observable Monte Carlo Planning)：https://github.com/namoshizun/PyPOMDP

POMCP、Value Iteration and Linear Value Function Approximation：https://github.com/pemami4911/POMDPy

c++版本

Despot、POMCP和aems：https://github.com/AdaCompNUS/despot/

HyP-DESPOT：https://github.com/AdaCompNUS/hyp-despot

Is-Despot：https://github.com/luo-yuanfu/is-despot

5.6 参考文献

柏爱俊. 2014. “基于马尔科夫理论的不确定性规划和感知问题研究.” Doctoral dissertation, 中国科学技术大学.

https://cloud.tencent.com/developer/article/2266370?areaId=106001

https://zhuanlan.zhihu.com/p/156823478

http://www.pomdp.org/