Partially Observable Markov Decision Process

部分可观察马尔可夫决策过程（POMDP）

基础定义

一个 POMDP 模型 $\mathscr{M}$ 可以形式化定义为元组 $\langle \mathcal{S},\ \mathcal{A},\ \mathcal{O},\ \mathcal{P},\ \mathcal{Q},\ \mathcal{R},\ \gamma,\ b_{0} \rangle$：

1. 有限状态集合 $\mathcal{S} = \{ s_{1},\ s_{2},\ \cdots,\ s_{n} \}$
2. 有限动作集合 $\mathcal{A} = \{ a_{1},\ a_{2},\ \cdots,\ a_{m} \}$
3. 有限观测集合 $\Omega = \{ o_{1},\ o_{2},\ \cdots,\ o_{l} \}$
4. 状态转移概率矩阵 $\mathcal{P} = \{ p_{ij}^{(a)} = p(S_{t + 1} = s_{i} \mid S_{t} = s_{j},\ A_{t} = a) \}_{m \times n \times n}$
5. 观测状态激发概率矩阵 $\mathcal{O} = \{ p_{ij} = p(O_{t} = o_{i} \mid S_{t} = s_{j}) \}_{l \times n}$
6. 奖励函数 $\mathcal{R} : \mathcal{S} \times \mathcal{A} \mapsto \mathbb{R} = \mathcal{E}(R_{t + 1} \mid S_{t} = s,\ A_{t} = a)$
7. 衰减因子 $\gamma \in [0,\ 1)$
8. 初始状态概率分布 $b_{0} \in [0,\ 1]^{n}$

为了将 POMDP 转化为 MDP 问题，需要定义一个新的状态空间——信息状态空间 $\mathcal{I}$，使得该空间内的状态的转移行为可以看做是一个 MDP，信息状态 $I \in \mathcal{I}^{(t + 1)}$ 的更新可以形式化为映射：

$I_{t + 1} = \kappa (I_{0},\ I_{1},\ \cdots,\ I_{t}\ O_{t + 1},\ A_{t})$

信息状态通过每次采取的动作 $A_{t}$ 和新观测到的 $O_{t + 1}$ 进行更新，并且要求这种更新具有马尔可夫性，即：

$p(I_{t + 1} \mid I_{0},\ I_{1},\ \cdots,\ I_{t},\ O_{t + 1},\ A_{t}) = p(I_{t + 1} \mid I_{t},\ O_{t + 1},\ A_{t})$

通过信息状态得到的奖励函数：

$\mathcal{R}_{\mathcal{I}} : \mathcal{I} \times \mathcal{A} \mapsto \mathbb{R} = \mathcal{E}(R_{t + 1} \mid I_{t} = i,\ A_{t} = a) = \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) p(s \mid i,\ \xcancel{a}) = \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) p(s \mid i)$

构造信息状态最直接的方式是将所有的历史信息全部包含在 $I_{t}$ 中，即完全信息状态：

$I_{t}^{\mathrm{C}} = \langle b_{0},\ o_{0},\ \cdots,\ o_{t},\ a_{0},\ \cdots,\ a_{t - 1} \rangle$

但是完全信息状态空间复杂度随着规划步数线性增长，并且在形式上难以处理，因此可以将满足以下性质：

1. 马尔可夫性：$I_{t} = \tau(I_{t - 1},\ O_{t},\ A_{t})$
2. 隐状态条件概率等价性：$p(S_{t} \mid I_{t}) = p(S_{t} \mid I_{t}^{\mathrm{C}})$
3. 显状态激发概率等价性：$p(O_{t} \mid I_{t - 1},\ A_{t - 1}) = p(O_{t} \mid I_{t - 1}^{\mathrm{C}},\ A_{t - 1})$

的状态称为充分信息状态，即与完全信息状态的概率表现等价的信息状态。例如信念状态：

$B_{t}(s) = b \in \mathcal{B} : \mathcal{S} \mapsto \mathbb{R} = p(S_{t} = s \mid I_{t}^{\mathrm{C}})$

经过动作 $a$ 的执行并且观测到显状态 $o$ 后信念状态 $B_{t}(s) = b(s)$ 确定性地转移（$\mathcal{I} \times \mathcal{A} \times \Omega \mapsto \mathcal{I}$）为：

$\begin{aligned} b_{o}^{a}(s') &= p(S_{t + 1} = s' \mid B_{t} = b,\ A_{t} = a,\ O_{t + 1} = o) = \frac{p(s',\ b,\ a,\ o)}{p(b,\ a,\ o)} \\[5mm] &= \cancel{p(b,\ a)} p(s' \mid b,\ a) \underset{\mathcal{O}}{\underbrace{p(o \mid s',\ \xcancel{b,\ a})}} \bigg/ \cancel{p(b,\ a)} p(o \mid b,\ a) \\[5mm] &= p(o \mid s') \sum_{s \in \mathcal{S}} p(s',\ S_{t} = s \mid b,\ a) \bigg/ \sum_{s'' \in \mathcal{S}} p(o,\ S_{t + 1} = s'' \mid b,\ a) \\[7mm] &= p(o \mid s') \sum_{s \in \mathcal{S}} \underset{\mathcal{P}}{\underbrace{p(s' \mid s,\ \xcancel{b},\ a)}} p(s \mid b,\ \xcancel{a}) \bigg/ \sum_{s'' \in \mathcal{S}} \underset{\mathcal{O}}{\underbrace{p(o \mid s'',\ \xcancel{b,\ a})}} p(s'' \mid b,\ a) \\[7mm] &= p(o \mid s') \sum_{s \in \mathcal{S}} p(s' \mid s,\ a) \underset{b(s)}{\underbrace{p(s \mid I_{t}^{\mathrm{C}})}} \bigg/ \sum_{s'' \in \mathcal{S}} p(o \mid s'') \sum_{s \in \mathcal{S}} p(s'',\ S_{t} = s \mid b,\ a) \\[7mm] &= p(o \mid s') \sum_{s \in \mathcal{S}} p(s' \mid s,\ a) b(s) \bigg/ \sum_{s'' \in \mathcal{S}} p(o \mid s'') \sum_{s \in \mathcal{S}} p(s''\mid s,\ \xcancel{b},\ a) \underset{b(s)}{\underbrace{p(s \mid b,\ a)}} \\[7mm] &= p(o \mid s') \sum_{s \in \mathcal{S}} p(s' \mid s,\ a) b(s) \bigg/ \sum_{s'' \in \mathcal{S}} p(o \mid s'') \sum_{s \in \mathcal{S}} p(s''\mid s,\ a) b(s) \end{aligned}$

从上式中还可以看出：

$p(o \mid b,\ a) = \sum_{s'' \in \mathcal{S}} p(o \mid s'') \sum_{s \in \mathcal{S}} p(s''\mid s,\ a) b(s)$

现在来说明信念状态是充分信息状态，首先从定义和上式中可以得出信念状态满足性质 1、2，对于性质 3：

$\begin{aligned} p(O_{t + 1} = o \mid B_{t} = b,\ A_{t} = a) &= \sum_{s'' \in \mathcal{S}} p(o \mid s'') \sum_{s \in \mathcal{S}} p(s'' \mid s,\ a) b(s) \\[7mm] &= \sum_{s'' \in \mathcal{S}} p(o \mid s'') \sum_{s \in \mathcal{S}} p(s'' \mid s,\ a) p(s \mid I_{t}^{\mathrm{C}} = i) \\[7mm] &= \sum_{s'' \in \mathcal{S}} p(o \mid s'') \sum_{s \in \mathcal{S}} p(s'' \mid s,\ a,\ i) p(s \mid a,\ i) \\[7mm] &= \sum_{s'' \in \mathcal{S}} p(o \mid s'',\ a,\ i) p(s'' \mid a,\ i) \\[7mm] &= p(O_{t + 1} = o \mid I_{t}^{\mathrm{C}} = i,\ A_{t} = a) \end{aligned}$

因此建立在动作的基础之上的信念状态之间的转移（$\mathcal{I} \times \mathcal{A} \overset{p}{\to} \mathcal{I}$）概率为：

$p(b' \mid b,\ a) = \sum_{o \in \Omega} p(b',\ o \mid b,\ a) = \sum_{o \in \Omega} p(b' \mid b,\ a,\ o) p(o \mid b,\ a) = \sum_{o \in \Omega} \mathbb{I} \{ b' = b_{o}^{a} \} p(o \mid b,\ a)$

基于信念状态定义的奖励函数为：

$\mathcal{R}_{\mathcal{B}} : \mathcal{B} \times \mathcal{A} \mapsto \mathbb{R} = \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) p(s \mid b) = \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) b(s)$

策略与价值

尽管通过信念状态可以将 POMDP 模型转化为 MDP 模型，但是考虑到信念状态的状态空间 $\mathcal{B} = \mathbb{R}^{n}$ 是无限且连续的，因此难以通过有限离散状态集的 MDP 理论进行求解。另外，由于隐状态的存在，POMDP 模型的策略只能定义在信息状态上，可用的表示方法有策略树（有限期规划）和策略自动机（无限期规划）：

以上表示方法均为确定性策略，类似地，定义信息状态价值函数，并且满足贝尔曼期望方程：

$v_{\pi}(i) = \mathcal{R}_{\mathcal{I}} \bigg( i,\ \pi(i) \bigg) + \gamma \sum_{i' \in \mathcal{I}} p \bigg( i' \mid i,\ \pi(i) \bigg) v_{\pi}(i')$

对应的贝尔曼最优方程为：

$\begin{aligned} v^{\star}(i) &= \max_{a \in \mathcal{A}} \left\{ \mathcal{R}_{\mathcal{I}}(i,\ a) + \gamma \sum_{i' \in \mathcal{I}(i,\ a)} p(i' \mid i,\ a) v^{\star}(i') \right\} = \max_{a \in \mathcal{A}} \left\{ \mathcal{R}_{\mathcal{I}}(i,\ a) + \gamma \sum_{o \in \Omega} p(o \mid i,\ a) v^{\star} \bigg( \tau(i,\ o,\ a) \bigg) \right\} \\[7mm] &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) p(s \mid i) + \gamma \sum_{o \in \Omega} \sum_{s' \in \mathcal{S}} p(o,\ s' \mid i,\ a) v^{\star} \bigg( \tau(i,\ o,\ a) \bigg) \right\} \\[7mm] &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) p(s \mid i) + \gamma \sum_{o \in \Omega} \sum_{s' \in \mathcal{S}} p(o \mid s',\ \xcancel{i,\ a}) p(s' \mid i,\ a) v^{\star} \bigg( \tau(i,\ o,\ a) \bigg) \right\} \\[7mm] &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) p(s \mid i) + \gamma \sum_{o \in \Omega} \sum_{s' \in \mathcal{S}} p(o \mid s',\ \xcancel{i,\ a}) \sum_{s \in \mathcal{S}} p(s',\ s \mid i,\ a) v^{\star} \bigg( \tau(i,\ o,\ a) \bigg) \right\} \\[7mm] &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) p(s \mid i) + \gamma \sum_{o \in \Omega} \sum_{s' \in \mathcal{S}} p(o \mid s',\ \xcancel{i,\ a}) \sum_{s \in \mathcal{S}} p(s' \mid s,\ \xcancel{i},\ a) p(s \mid i,\ \xcancel{a}) v^{\star} \bigg( \tau(i,\ o,\ a) \bigg) \right\} \\[7mm] &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) p(s \mid i) + \gamma \sum_{o \in \Omega} \left[ \sum_{s' \in \mathcal{S}} \sum_{s \in \mathcal{S}} p(o \mid s') p(s' \mid s,\ a) p(s \mid i) \right] v^{\star} \bigg( \tau(i,\ o,\ a) \bigg) \right\} \end{aligned}$

最优状态价值函数表示

对于任一 PWLC 函数，经过算子 $\mathscr{L}$ 的变换后依然是一个 PWLC 函数：

$\begin{aligned} \mathscr{L} \{ v \} &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) b(s) + \gamma \sum_{o \in \Omega} p(o \mid b,\ a) v(b_{o}^{a}) \right\} \\[7mm] &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) b(s) + \gamma \sum_{o \in \Omega} p(o \mid b,\ a) \max_{\theta \in \Theta} \sum_{s' \in \mathcal{S}} \theta(s') b_{o}^{a}(s') \right\} \end{aligned}$

其中

$b_{o}^{a}(s') = \frac{p(s',\ o \mid b,\ a)}{p(o \mid b,\ a)} = \frac{1}{p(o \mid b,\ a)} p(o \mid s') \sum_{s \in \mathcal{S}} p(s' \mid s,\ a) b(s)$

进而得到

$\begin{aligned} \mathscr{L} \{ v \} &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) b(s) + \gamma \sum_{o \in \Omega} p(o \mid b,\ a) \max_{\theta \in \Theta} \sum_{s' \in \mathcal{S}} \theta(s') b_{o}^{a}(s') \right\} \\[7mm] &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) b(s) + \gamma \sum_{o \in \Omega} p(o \mid b,\ a) \max_{\theta \in \Theta} \sum_{s \in \mathcal{S}} \theta(s) b_{o}^{a}(s) \right\} \\[7mm] &= \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) b(s) + \gamma \sum_{o \in \Omega} \max_{\theta \in \Theta} \sum_{s \in \mathcal{S}} b(s) \sum_{s' \in \mathcal{S}} \theta(s') p(o \mid s') p(s' \mid s,\ a) \right\} \end{aligned}$

令

$\theta_{o}^{a}(s) = \sum_{s' \in \mathcal{S}} \theta(s') p(o \mid s') p(s' \mid s,\ a) \qquad \hat{\theta} = \argmax_{\theta \in \Theta} \sum_{s \in \mathcal{S}} b(s) \theta_{o}^{a}(s)$

原式可以重写为：

$\mathscr{L} \{ v \} = \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) b(s) + \gamma \sum_{o \in \Omega} \sum_{s \in \mathcal{S}} b(s) \hat{\theta}_{o}^{a}(s) \right\} = \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} b(s) \left[ \mathcal{R}(s,\ a) + \gamma \sum_{o \in \Omega} \hat{\theta}_{o}^{a}(s) \right] \right\}$

如果令：

$\theta \langle a,\ b \rangle (s) = \mathcal{R}(s,\ a) + \gamma \sum_{o \in \Omega} \hat{\theta}_{o}^{a}(s)$

变换式又可以写作 PWLC 函数的形式

$\mathscr{L} \{ v \} = \max_{a \in \mathcal{A}} \left\{ \sum_{s \in \mathcal{S}} \theta \langle a,\ b \rangle (s) b(s) \right\}$

同时对于所有的 $a \in \mathcal{A}$ 和 $b \in \mathcal{B}$，由 $\theta \langle a,\ b \rangle$ 构成的新的向量集合 $\Theta'$ 的大小的上界为 $| \mathcal{A} | |\Theta|^{|\Omega|}$（给定 $o$ 可以得到 $|\Theta|$ 种不同的 $\theta_{o}^{a}$，而对于变换后的参数 $\theta \langle a,\ b \rangle$ 包含求和项 $\sum_{o \in \Omega} \hat{\theta}_{o}^{a}(s)$，至多有 $|\Theta|^{\Omega}$ 种求和序列）。对于有限期规划问题，其后序初始最优状态价值函数即为一个 PWLC 函数：

$v^{\star} \langle 0 \rangle (b) = \max_{a \in \mathcal{A}} \sum_{s \in \mathcal{S}} \mathcal{R}(s,\ a) b(s)$

在有限期规划时需要通过后序遍历来不断地对价值函数 $v$ 进行备份操作，表示为向量集合就有了可计算性。