17.4 部分可观察的MDP
在第17.1节的对马尔可夫决策过程的描述中，我们假设环境是完全可观察的。在这个假设下，智能体总是知道自己处于哪个状态。结合对于转移模型的马尔可夫假设，这意味着最优策略只取决于当前状态。当环境只是部分可观察的时候，可以说情况就不那么清晰了。智能体不一定知道自己所处的状态，所以无法执行π (s)为该状态推荐的行动。此外状态s的效用值和s中的最优行动都不仅仅取决于 s，还取决于当处于状态 s 时智能体知道多少。由于这些原因，部分可观察 MDP（或者简写成POMDP——发音为“pom-dee-pee”）通常被认为比一般的MDP复杂得多。然而因为现实世界就是部分可观察的，所以我们无法回避POMDP。
仍然考虑图17.1中4×3世界的例子，不过现在让我们假设智能体没有任何传感器，所以不知道它自己在哪里。更准确地讲，让我们假设智能体的初始状态等可能地是9个非终止状态之一（见图17.8（a））。显然，如果智能体知道它在（3,3），它将进行Right移动；如果它知道在（1,1），它将会进行Up移动；但是由于它可能在任何位置，它该怎么办？一种可能的答案是智能体应该先尽量向着减少不确定性的方向移动，然后才能走向+1出口。例如，如果智能体进行5次Left移动，那么它非常可能走到左侧的墙边（图17.8（b））。然后，如果它进行5次Up移动，它相当可能走到顶部，也许就在左上角（图17.8（c））。最后，如果它进行5次Right移动，它有很大机会——大约 77.5％——到达+1 出口（图 17.8（d））。之后继续向右移动可以把几率增加到 81.8％。因此这个策略令人惊讶的安全，不过采用它时智能体到达出口会很慢，期望的效用值只有大约 0.08。我们很快要描述的最优策略会比它做得更好。
图17.8（a）智能体位置的初始概率分布。（b）进行5次Left移动以后。（c）进行5次Up移动以后。（d）进行5次Right移动以后
在处理POMDP之前，我们首先必须恰当地定义它们。POMDP和MDP有同样的要素——转移模型T(s, a, s')和回报函数R(s)——不过它还具有一个观察模型O(s, o)，指定在状态s感知到o的概率[36]。例如，我们没有感知器的智能体只有一个可能的观察（空观察），并且这在每个状态中发生的概率为1。
在第三章和第十二章中，我们研究了不确定性和部分可观察的规划问题，明确了信度状态——智能体可能处于的实际状态集合——作为描述和计算解的关键概念。在POMDP中，这个状态多少要被重新定义。信度状态b这里是所有可能状态上的概率分布。例如，图17.8（a）中的初始信度状态可以记为
其中α 是使得信度状态和为1的归一化常数。我们把这个公式简写成b'=FORWARD(b, a, o)。
理解POMDP所要求的基本见解是：最优行动仅仅取决于智能体的当前信度状态。也就是说，最优策略可以被描述为从信度状态到行动的一个映射π*(b)。它不依赖于智能体所处的实际状态。这是件好事，因为智能体不知道自己的实际状态；它所知的全部只是信度状态。因此，一个POMDP智能体的决策周期如下：
① 给定当前的信度状态b，执行行动a=π*(b)。
② 得到观察o。
③ 设置当前的信度状态为FORWARD(b, a, o)，并反复。
现在我们可以认为POMDP需要在信度状态空间中进行搜索，正如第三章中用于无感知问题和偶发性问题的方法。主要的区别是POMDP的信度状态空间是连续的，这是由于一个POMDP信度状态就是一个概率分布。例如，4×3世界的一个信度状态就是 11维连续空间中的一个点。一个行动不仅仅改变物理状态，也改变了信度状态，所以它是根据智能体获得的作为结果的信息来评价的。因此POMDP把信息价值（第16.6节）包括进来作为决策问题的元素之一。
让我们仔细观察一下行动的结果。特别地，让我们计算在执行行动a之后智能体从信度状态b到达信度状态b'的概率。现在，如果我们已知行动以及后续的观察，那么公式（17.11）就为信度状态提供了确定性的更新：b'=FORWARD(b, a, o)。当然后续的观察尚不知道，所以智能体或许到达几个可能的信度状态之一b'，取决于出现的观察。假设行动a的执行起始于信度状态b，感知到o的概率通过对智能体可能到达的所有真实状态求和得到：
给定行动a，我们把从b到b'的概率记作τ (b, a, b')。那么我们得到：
其中如果b'=FORWARD(b, a, o)，那么P(b'|o, a, b)为1，否则为0。
公式（17.12）可以被看作为信度状态空间定义了一个转移模型。同样我们也可以为信度状态定义一个回报函数（即，智能体可能所处的真实状态的期望回报）：
于是看来τ (b, a, b')和ρ (b)共同在信度状态空间上定义了一个可观察的MDP。而且，可以证明这个MDP的最优策略π*(b)也是原始POMDP的一个最优策略。换句话说，在物理状态空间上求解POMDP可以归约为在信度状态空间上求解一个MDP。如果我们还记得，从定义上看信度状态对于智能体总是可观察的，这个事实也许就不那么令人吃惊了。
注意，尽管我们把 POMDP 简化成 MDP，不过我们得到的这个 MDP 是在连续（通常也是高维）空间上的。第17.2节和第17.3节中描述的MDP算法都无法直接用于这类MDP。解决办法是我们可以发展一个用于连续状态 MDP的价值和策略迭代算法。基本思想是策略π(b)可以被表示为信度状态空间的区域的一个集合，每个区域都与一个特定的最优行动相关联[37]。值函数把b的一个独特的线性函数与每个区域联系起来。每个价值迭代步骤或者策略迭代步骤改进区域的边界，并可能引入新的区域。
具体的算法超出了本书的范围，不过我们给出无传感器4 × 3世界的解。最优策略如下：
[Left, Up, Up, Right, Up, Up, Right, Up, Up, Right, Up, Right, Up, Right, Up, …]
这个策略是一个序列，因为这个问题在信度状态空间中是确定性的——没有观察。里面包含的“技巧”是先让智能体采用一次Left移动，以确保它不在（4, 1），然后就可以安全地保持Up和Right移动直到+1 出口。智能体到达+1 出口的几率是 86.6％，并且比这一节前面描述的策略快很多，所以它的期望效用是0.38，与原来的0.08相比较提高了不少。
对于更复杂的有观察的POMDP，找到近似最优策略是很难的（实际上是PSPACE难题——也就是说，确实非常困难）。即使求解只有数十个状态的问题也经常是不可行的。下一节描述一种不同的、基于前瞻搜索的求解POMDP的近似方法。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
