线性二次型高斯(Linear Quadratic Gaussian (LQG))
在现实世界中，我们通常不能获取到所有的状态st。比如一个自动驾驶汽车可以通过摄像头获取图像，但这仅仅是一个观察(observation)，并不能反映真实世界的所有状态。我们之前的讨论都是基于状态是可以完全获得的。考虑到真实世界并不是这样，我们需要一个新工具来对真实世界建模，这个工具就是部分可观测的MDP(Partially Observable MDP (POMDP))。
一个POMDP是在MDP的基础上增加一个观察层。也就是说，我们引入一个新变量ot，在给定状态st下，ot遵循某个条件概率分布，即：
一个有界的POMDP由如下六元组构成：
在这个框架下，一般的策略是基于一组观察o1, ..., ot维护一个信念状态(belief state)(状态的概率分布)。而一个POMDP的策略将信念状态映射成行动。
这一小节我们将对LQR做一些扩展，假设我们观察到yt∈ Rm并且有：
其中C ∈ Rm×n是一个压缩矩阵(compression matrix)，vt是噪音(和wt一样都是服从高斯分布)。注意现在奖励函数的定义保持不变，依旧是关于状态和行动的一个函数。由于概率分布是高斯的，所以信念状态也服从高斯分布。在这个新设定下，我们来看下求解最佳策略的方法。
步骤1: 首先基于观察求出可能状态的概率分布
其中st|t和Σt|t分别为这个概率分布的均值和方差
步骤2: 使用均值st|t作为st的最佳近似
步骤3: 最佳行动at := Ltst，其中Lt的定义来自普通LQR算法
由于LQR中我们已经证明结果与噪音无关，所有步骤2中我们可以用st|t作为st的最佳近似。
其中步骤1我们需要详细展开讲一下。简单起见，我们先考虑动态模型与行动无关，假设：
由于噪音都服从高斯分布，因此它们的联合分布也服从高斯分布，即：
根据在因子分析中介绍的边缘概率分布公式，可得：
然而计算边缘分布非常耗时，这需要我们对t×t的矩阵进行计算。由于计算一个逆矩阵的时间复杂度是O(t3)，而这个计算需要重复t次，因此总的时间复杂度是O(t4)。
为了提高计算的速度，我们将采用卡尔曼滤波(Kalman filter)算法来计算均值和方差，这个算法的时间复杂度只有O(t)。
卡尔曼滤波算法只有两步：预测步(predict step)和更新步(update step)。假设我们知道st|y1, ..., yt的概率分布，即：
那么：
预测步: 下一个状态的概率也服从高斯分布，并且：
更新步: 给定st+1|t和Σt+1|t，并且满足：
我们可以证明：
其中：
矩阵Kt被称为卡尔曼增益(Kalman gain)。
如果我们仔细看一下上面的公式，会发现我们并不需要上一个时刻的观察值。更新步中只需要依赖上一步的概率分布。总的来说，这个算法首先进行向前推算(forward pass)计算出Kt, Σt|t和st|t，然后再进行向后推算(backward pass)(也就是LQR更新)计算出Φt, Ψt和Lt，最后根据公式at* = Ltst|t计算出最优策略。
总结
- 由于在现实世界中通常不能获取到所有的状态，我们只能获取到观察值，因此在MDP的基础上增加一个观察层，这个模型叫做POMDP
- 求解POMDP的最优策略需要用到卡尔曼滤波算法，该算法时间复杂度只有O(t)，可以大幅提高运算性能
参考资料
- 斯坦福大学机器学习课CS229讲义 LQR, DDP and LQG
- 网易公开课：机器学习课程 双语字幕视频
