定义

一个部分可观测马尔科夫决策过程（POMDP）描述一个代理与环境的关系，由一个7元组$(S,A,T,R,\Omega,O,\gamma)$表示，其中

$S$是状态集合；
$A$是动作集合；
$T$是转移概率函数；
$R: S \times A \to \mathbb{R}$是报酬函数；
$\Omega$是观测集合；
$O$是条件观测概率函数；
$\gamma \in [0, 1]$是折扣因子。

在每个时间，环境处于某个状态$s\in S$。代理采取了行动$a\in A$，导致了环境以概率$T(s’\mid s,a)$转移到状态$s’$。同时，代理观测到的是$o\in \Omega$，$o$依赖于行动$a$以及新状态$s’$, 概率为$O(o\mid s’,a)$。最后，代理接收到报酬$r=R(s, a)$。这个过程一直重复下去。POMDP的目标是最大化未来的期望总报酬$\mathbb{E}\left[\sum _{t=0}^{\infty }\gamma^{t}r_{t}\right]$，其中$r_{t}$ 是时间$t$得到的报酬。折扣因子$\gamma$决定了对即时报酬与未来报酬的不同重视程度。

当$\gamma =0$时，代理制关注会产生最大即时报酬的行动；当$\gamma =1$时，代理会着眼于最大化未来报酬之和。

$\begin{align*} \text{Underlying Model}\qquad&s_0\rightarrow s_1\rightarrow \cdots \qquad\qquad\\ &\downarrow\ \ \ \ \downarrow \qquad\qquad\\ \text{Observation}\qquad &o_0\rightarrow o_1\rightarrow \cdots \qquad\qquad\\ &\downarrow\ \ \ \ \downarrow \qquad\qquad\\ \text{Belief}\qquad&b_0\rightarrow b_1\rightarrow \cdots \qquad\qquad \end{align*}$

信念马尔科夫决策过程

代理的信念$b(s)$是一个描在某一时刻述处于状态$s$概率的函数。在采取行动$a$、观测到$o$之和，代理需要更新它的信念函数。因为状态转移服具有马尔科夫性，对于信念函数的计算只涉及前一时刻的信念、采取的动作以及目前的观测。更新的操作记为$b’ = \tau(b,a,o)$

在到达$s’$之和，代理以概率$O(o\mid s’,a)$观测到$o\in \Omega$。令$b$为状态空间$S$上的概率分布。$b(s)$代表环境处于状态$s$的概率。给定$b(s)$，在采取行动$a$、观测到$o$之后，

$b'(s')=\eta O(o\mid s',a)\sum _{s\in S}T(s'\mid s,a)b(s)$

其中$\eta =\frac{1}{\mathbb{P}(o\mid b,a)}$是一个归一化常数，使得$\mathbb{P}(o\mid b,a)=\sum _{s’\in S}O(o\mid s’,a)\sum _{s\in S}T(s’\mid s,a)b(s)$。

马尔科夫信念状态使得我们可以用MDP来描述POMDP。这个信念马尔科夫决策过程会定义到连续状态空间，因为有信念空间$B$是无限的。

正式地，信念马尔科夫决策过程由元组$(B,A,\tau,r,\gamma)$定义，其中

$B$是POMDP状态集上的信念空间；
$A$是与原POMDP相同的动作集合；
$\tau$是信念状态的转移函数；
$r:B \times A \to \mathbb{R}$是信念状态上的保存函数；
$\gamma$是与原POMDP相同的折扣因子。

$\tau$和$r$需要从原POMDP中计算得到：

$\tau(b,a,b') = \sum_{o\in \Omega} \mathbb{P}(b'|b,a,o) \mathbb{P}(o | a, b),$

其中

$\begin{align*} \mathbb{P}(o\mid b,a)&=\sum_{s'\in S}O(o\mid s',a)\sum_{s\in S}T(s'\mid s,a)b(s)\\ \mathbb{P}(b'|b,a,o)&=\begin{cases} 1&\text{if the belief update with arguments }b,a,o\text{ returns }b'\\ 0&\text{otherwise } \end{cases}. \end{align*}$

报酬函数$r$定义为：

$r(b,a) = \sum_{s\in S} b(s) R(s,a).$

信念马尔科夫决策过程不再是部分可观测，因为在任意时刻，代理知道它的信念状态。

策略和价值函数

与原POMDP不同的是，信念马尔科夫决策过程的所有信念状态运行多种动作发生，因为信念函数的输出是一个概率分布。因此，$\pi$对任意信念$b$输出动作$a=\pi(b)$。

这里我们假设目标函数是最大化无限阶段的期望总折扣报酬。当定义代价为$R$时，目标变为最小化期望代价。

给定初始信念$b_{0}$，策略$\pi$的期望报酬定义为

$V^\pi(b_0) = \sum_{t=0}^\infty \gamma^t r(b_t, a_t) = \sum_{t=0}^\infty \gamma^t \mathbb{E}\Bigl[ R(s_t,a_t) \mid b_0, \pi \Bigr]$

其中$\gamma<1$是折扣因子。最优策略$\pi^\ast$是由优化长期报酬得到：

$\pi^{\ast}=\underset{\pi }{\mbox{argmax}}\ V^{\pi}(b_{0})$

最优策略$\pi^\ast$对每一个信念状态产生最高期望报酬，即最优值函数$V^{\ast}$。这个值函数是贝尔曼方程的解：

$V^{\ast}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }\mathbb{P}(o\mid b,a)V^{\ast}(\tau (b,a,o)){\Bigr ]}$

对有限阶段的POMDPs，最优值函数是分段线性、凸的。它可以用有限的向量集合表示。对无限阶段的POMDPs，最优值函数可以由有限向量集合任意逼近，并且保持凸性。值迭代应用动态规划更新，逐渐改善值函数，直到收敛到$\epsilon$-最优的值函数，保持分段线性和凸性。通过改善值函数，策略也间接得到改善。另外也可以用策略迭代直接改善策略。这与MDP的值迭代和策略迭代相同。