POMDP中的信念空间

POMDP（Partially Observable Markov Decision Process，部分可观测马尔可夫决策过程）可以表示为：

$$\mathcal{M}=(\mathcal{S,A,O,T,Z})$$

相比于MDP，POMDP引入了对环境状态的不完全观测。在POMDP中，智能体无法直接观察到环境的真实状态，而是通过观测获得部分信息。因此，智能体需要维护一个信念状态（belief state），即对环境状态的概率分布，以便在不确定性下进行决策。观测$\mathcal{Z}$是所有观测量$z$构成的集合，观测函数$\mathcal{O}$得到观测$z$的概率分布：

$$\mathcal{O}(z|s',a)=P(z|s',a)$$

MDP问题的求解

MDP问题的求解目标是找到最优策略对应的状态值函数和动作值函数。

策略的定义为：

$$\pi(a|s)$$

代表策略在状态$s$下选择动作$a$的概率。对应的状态值函数和动作值函数分别为：

$$V^{\pi}(s)=E_{\pi}[G_t|s]$$

$$Q^{\pi}(s,a)=E_{\pi}[G_t|s,a]$$

其中，$E$代表期望，$G_t$表示从时间步$t$开始的累积折扣奖励，$\gamma$为折扣因子：

$$G_t=\sum_{k=0}^{\infty}\gamma^k r_{t+k+1}$$

不同的策略会导致不同的状态值函数和动作值函数。最优策略$\pi^*$对应的最优状态值函数和动作值函数分别为：

$$V^*(s)=\max_{\pi} [R(s,a)+\gamma\sum_{s'}\Pr(s'|s,a)V^*(s')]$$

$$Q^*(s,a)=R(s,a)+\gamma\sum_{s'}\Pr(s'|s,a)\max_{a'}Q^*(s',a')$$

贝尔曼方程为求解最优策略提供了递归关系。

贝尔曼期望方程

贝尔曼方程用于计算给定策略$\pi$时价值函数在策略指引下所采轨迹上的期望。考虑如下随机轨迹：

$$S_t \xrightarrow{A_t} R_{t+1}, S_{t+1} \xrightarrow{A_{t+1}} R_{t+2}, S_{t+2} \xrightarrow{A_{t+2}} R_{t+3}$$

累积汇报$G_t$定义为：

$$\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots, \\ &= R_{t+1} + \gamma(R_{t+2} + \gamma R_{t+3} + \dots), \\ &= R_{t+1} + \gamma G_{t+1}. \end{aligned}$$

状态值函数的贝尔曼方程为：

$$\begin{aligned} v_\pi(s) &\doteq \mathbb{E}_\pi[G_t \mid S_t = s] \\ &= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ &= \sum_a \pi(a|s) \sum_{s',r} p(s', r|s, a)\left[r + \gamma v_\pi(s')\right], \quad \forall s \in \mathcal{S}. \end{aligned}$$

推导：

$$\begin{aligned} v_\pi(s) &= \mathbb{E}[G_t \mid S_t = s] \\ &= \mathbb{E}[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ &= \mathbb{E}[R_{t+1} \mid S_t = s] + \gamma \mathbb{E}[G_{t+1} \mid S_t = s]. \end{aligned}$$

考虑第一部分$\mathbb{E}[R_{t+1} \mid S_t = s]$，应用全概率公式：

$$P(A)=\sum_{i} P(A|B_i)P(B_i),$$

得到：

$$\begin{aligned} \mathbb{E}[R_{t+1} \mid S_t = s] &= \sum_a \pi(a|s) \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a] \\ &= \sum_a \pi(a|s) \sum_r p(r|s,a) r. \end{aligned}$$

考虑第二部分$\mathbb{E}[G_{t+1} \mid S_t = s]$，应用全概率公式和马尔可夫性质（在给定当前状态的情况下，未来状态的条件概率分布仅依赖于当前状态，而与过去状态无关）：

$$\begin{aligned} \mathbb{E}[G_{t+1} \mid S_t = s] &= \sum_{s'} \mathbb{E}[G_{t+1} \mid S_t = s, S_{t+1} = s'] p(s' \mid s) \\ &= \sum_{s'} \mathbb{E}[G_{t+1} \mid S_{t+1} = s'] p(s' \mid s) \\ &= \sum_{s'} v_\pi(s') p(s' \mid s) \\ &= \sum_{s'} v_\pi(s') \sum_a p(s' \mid s, a) \pi(a \mid s). \end{aligned}$$

合并两个部分：

$$\begin{aligned} v_\pi(s) &= \mathbb{E}[R_{t+1} \mid S_t = s] + \gamma \mathbb{E}[G_{t+1} \mid S_t = s], \\ &= \underbrace{\sum_a \pi(a|s) \sum_r p(r|s,a) r}_{\text{mean of immediate rewards}} + \gamma \underbrace{\sum_a \pi(a|s) \sum_{s'} p(s'|s,a) v_\pi(s')}_{\text{mean of future rewards}}, \\ &= \sum_a \pi(a|s) \left[ \sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) v_\pi(s') \right], \quad \forall s \in \mathcal{S} \\ &= \sum_a \pi(a|s) \sum_{s',r} p(s', r|s,a) \left[ r + \gamma v_\pi(s') \right], \quad \forall s \in \mathcal{S}. \end{aligned}$$

策略迭代算法

给定策略$\pi$，利用贝尔曼期望方程，对状态值函数进行更新：

$$V^{k+1}(s) = \sum_a \pi(a|s) \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^k(s') \right]$$

也就是使用第$k$轮的值函数，更新第$k+1$轮的值函数。重复该过程，直到值函数收敛至$V^\pi$。

当拿到$V^\pi(s)$后，可根据状态值函数对原有策略进行改进。也就是在每一个状态下都选择最优的动作：

$$\pi'(s) = \arg\max_a Q^\pi(s,a) = \arg\max_a \left\{ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^\pi(s') \right\}$$

值迭代算法

价值迭代算法单独维护一个状态值函数，不维护策略，并且直接利用贝尔曼最优方程进行状态价值函数的更新：

$$V^{k+1}(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^k(s') \right]$$

价值迭代算法就是直接利用上述方程对状态值函数进行迭代更新，直到收敛至最优状态值函数$\left\| V^{k+1} - V^k \right\| \leq \Delta$。

POMDP问题的求解

MDP问题的求解结果是得到了值函数$V^*(s)$或$Q^*(s,a)$，相当于两个大表格，但是POMDP中智能体无法直接观测到环境状态$s$，因此无法直接使用MDP的求解方法，同时最优决策依赖的是历史信息的统计汇总，而不是当前的观测。在POMDP中，智能体需要维护一个信念状态(Belief State)$b(s)$，表示在当前观测$z$下环境状态为$s$的概率分布：

$$b_t(s)=\Pr(s_t=s|z_{1:t},a_{1:t-1})$$

$b(s)$存在无限多情况，不能通过表格来描述，引入信念空间后，POMDP的求解目标变成了计算信念状态下的最优值函数$V^*(b)$或动作值函数$Q^*(b,a)$，即在信念状态$b$下采取最优策略所能获得的最大期望累积奖励。

信念状态的更新

根据马尔可夫性质，根据上一时刻的信念状态$b_{t-1}$、采取的动作$a_{t-1}$和当前观测$z_t$，可以计算当前时刻的信念状态$b_t$：

$$\begin{aligned} b_t(s') &= \tau(b_{t-1}, a_{t-1}, z_t)(s') \\ &= \frac{1}{\Pr(z_t|b_{t-1}, a_{t-1})} \Pr(z_t|a_{t-1}, s') \sum_{s \in S} \Pr(s'|s, a_{t-1}) b_{t-1}(s) \end{aligned} \\ \Pr(z_t | b_{t-1}, a_{t-1}) = \sum_{s' \in S} \Pr(z_t | a_{t-1}, s') \sum_{s \in S} \Pr(s' | s, a_{t-1}) b_{t-1}(s)$$

其中，$\Pr(z_t|a_{t-1}, s')$是观测函数$\mathcal{O}$，$\Pr(s'|s, a_{t-1})$是转移函数$\mathcal{T}$。

Belief MDP

通过引入信念状态，POMDP可以转换为一个等价的MDP，称为Belief MDP。在Belief MDP中，状态空间是信念空间$\mathcal{B}$，动作空间仍然是$\mathcal{A}$。转移函数$\tau$和奖励函数$R$需要根据信念状态进行定义。

奖励函数定义为：

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

Belief MDP的状态值函数和动作值函数满足的贝尔曼方程为：

$$V^*(b) = \max_{a \in A} \left[ R_B(b, a) + \gamma \sum_{z \in Z} \Pr(z | b, a) V^*(\tau(b, a, z)) \right] \\ Q^*(b, a) = R_B(b, a) + \gamma \sum_{z \in Z} \Pr(z | b, a) V^*(\tau(b, a, z))$$

POMCP(Partially Observable Monte Carlo Planning)