在继续学习之前,我们先来回顾一下上一讲的内容:
其目标是$\displaystyle\max_a\mathrm E\left[R^{(0)}(s_0,a_0)+R^{(1)}(s_1,a_1)+\cdots+R^{(T)}(s_T,a_T)\right]$;
之后我们应用了动态规划算法: $$ \begin{align} V_T^*(s)&=\max_{a_T}R(s_T,a_T)\tag{1}\\ V_t^*(s)&=\max_a\left(R(s,a)+\sum_{s'}P_{sa}^{(t)}\left(s'\right)V_{t+1}^*\left(s'\right)\right)\tag{2}\\ \pi_t^*(s)&=\arg\max_a\left(R(s,a)+\sum_{s'}P_{sa}^{(t)}\left(s'\right)V_{t+1}^*\left(s'\right)\right)\tag{3} \end{align} $$ 其中$(1)$式是有限时域MDP的最后一步;得出最后一步后就可以使用$(2)$式向后递推每一个$V_{T-1},\cdots,V_{0}$;最后,在使用$\arg\max$对每一步价值函数最大化的部分做运算,就可以得到每一步的最优策略。
接下来我们介绍了一个具体的LQR问题:
上面定义中有了关于当前状态及动作的函数$s_{t+1}=f(s_t,a_t)$,我们就可以选择一个系统长时间保持的状态(系统通常都会都处于这种状态)$(\bar s_t,\bar a_t)$,在该点使用线性函数近似非线性函数$s_{t+1}=f(s_t,a_t)$,进而得到$\displaystyle s_{t+1}\approx f(\bar s_t,\bar a_t)+(\nabla_sf(\bar s_t,\bar a_t))^T(s_t-\bar s_t)+(\nabla_af(\bar s_t,\bar a_t))^T(a_t-\bar a_t)$。最终能够在$(\bar s_t,\bar a_t)$附近得到一个线性函数$s_{t+1}=A_ts_t+B_ta_t$。
LQR的奖励函数为$\displaystyle R^{(t)}(s_t,a_t)=-\left(s_t^TU_ts_t+a^TV_ta_t\right)$,其中矩阵$U,V$是半正定的,所以这个奖励函数总是非正数;
对LQR使用上面的动态规划得到求解方法:
这个算法中有趣的一点是,$L_t$不依靠$\varPsi_t$,$\varPhi_t$也不依赖于$\varPsi_t$。所以,即使我们从不考虑$\varPsi$也不会影响最终的结果。另一个有趣的地方在于$\varSigma_w$只在$\varPsi_t$中出现,再看LQR定义中的$s_{t+1}=A_ts_t+B_ta_t+w_t$可以得出,即使在不知道噪音项协方差的前提下,也可以正确的求出最优策略(但不要忘了最优价值函数是受$\varPsi$影响的)。最后,这两点都是对这个特殊LQR模型(非线性动力系统)独有的,一旦我们对模型做出改变,则这两个特性将不复存在,也就是只有在这个例子中才有“最优策略不受噪音项协方差影响”。在后面讨论Kalman滤波的时候会用到这个性质。
我们在第十一讲中,在关于机器学习算法的调试介绍过直升机模型提到:
现在,假设我们已经按照上述步骤得到了控制模型,但是发现该模型比人类直接操作差很多,接下来应该怎么办呢?我们可能会:
对于调整算法这样的任务,我们有太多的选择方向,如果选择错误,则将会浪费大量的时间精力。
接下来我们假设:
如果上述三条假设均正确,则可以推出$\pi_\mathrm{RL}$能够控制好真正的直升机。
于是,我们可以依次做出如下诊断:
以上仅是一个强化学习调试的例子,因为我们恰好找到了一个极优秀的直升机操纵者,如果没有的话则需要想出别的调试方法。在通常的问题中,我们都需要自己找出针对问题的有效的调试方法。
继续使用遥控直升机的例子,假设我们已经有模拟器并可以通过模拟器知道$s_{t+1}=f(s_t,a_t)$(即下一个状态是一个关于当前状态及动作的函数),而且这个模拟器是非线性、确定性的,噪音项也比较小。我们现在想要让直升机飞出一些特定轨迹,于是:
在实践中能够知道,这是一个非常有效的算法,DDP实际上是一种局部搜索算法,在每次迭代中,找到一个稍好的点进行线性化,进而得到一个稍好的策略,重复这个动作最终就可以得到一个比较好的策略了。(“微分”指的就是每次迭代我们都会选择一个点并通过求导做线性化。)
现在介绍另一种类型的MDP,在这种MDP中,我们并不能直接观察到每一步的状态(在前面的MDP中我们都会假设系统的状态已知,于是可以计算出策略,它是一个关于状态的函数;在LQR中我们也是计算$L_ts_t$,状态都是已知的)。
我们暂时先不谈控制,来说说普通的不能观察到状态信息的动态系统。举个例子,我们对“使用雷达追踪飞行器”的过程进行极其简化的建模:线性模型$s_{t+1}=As_t+w_t$,其中$s_t=\begin{bmatrix}x_t\\\dot x_t\\y_t\\\dot y_t\end{bmatrix},\ A=\begin{bmatrix}1&1&0&0\\0&0.9&0&0\\0&0&1&1\\0&0&0&0.9\end{bmatrix}$(这是一个非常简化的模型,可以理解为一架在2D空间中移动的飞机)。
在这个简化模型中我们无法观察到每一步的状态,但假设我们可以观察到另一个量——$y_t=Cs_t+v_t,\ v_t\sim\mathcal N(0,\varSigma_v)$:比如$C=\begin{bmatrix}1&0&0&0\\0&0&1&0\end{bmatrix}$,则有$Cs_t=\begin{bmatrix}x_t\\y_t\end{bmatrix}$。这个量可能是雷达追踪到的飞行器的位置(只能得到位置相关的状态,而不能得到加速度相关的状态)。比如说在$\mathrm{xOy}$平面上,有一个雷达位于$x$轴某点,其视角沿$y$轴正方向大致对着飞行器,并依次观察到一系列飞行器移动过程中的不连续的点,因为雷达视角沿$y$轴正半轴方向,所以得到的点的坐标的纵坐标的噪音(方差)应该大于横坐标的方差,可以说这些点分别位于一个个小的高斯分布中,而这些高斯分布的协方差矩阵应该型为$\varSigma=\begin{bmatrix}a&0\\0&b\end{bmatrix},\ a\gt b$(即因为在$y$轴方向上的观测结果更容易出现偏差,所以等高线图中椭圆的长轴会沿着$y$轴方向。)而我们想要做的就是通过观测到的一系列坐标估计飞行器在每个观测点的状态$P(s_t\mid y_1,\cdots,y_t)$。
$s_0,\cdots,s_t;\ y_0,\cdots,y_t$组成了一个高斯分布的联合分布(多元正态分布),可以用$z=\begin{bmatrix}s_0\\\vdots\\s_t\\y_0\\\vdots\\y_t\end{bmatrix},\ z\sim\mathcal N(\mu,\varSigma)$表示,再结合第十三讲中了解的多元正态分布的边缘分布与条件分布的计算方法,我们就可以对$P(s_t\mid y_1,\cdots,y_t)$进行求解。虽然这个思路在概念上是可行的,但是在实际中跟踪一个飞行器会得到成千上万个位置,于是就会有一个巨大的协方差矩阵(期望向量和协方差矩阵都会随着时间、步数的增长呈线性增长,在计算过程中需要用到的边缘分布、条件分布都可能会使用协方差的逆,而计算协方差的逆的复杂度是矩阵规模的平方级别),所以对于计算来说可行性较低。
于是我们引入Kalman滤波(Kalman Filter)算法来解决这个效率问题。这个算法实际上是一个隐式马尔可夫模型,使用递推的方式计算,下面写出算法的步骤,算法的思路可以在Hidden Markov Models中找到:
第一步称为预测(predict)步骤,使用$P(s_t\mid y_1,\cdots,y_t)$对$P(s_{t+1}\mid y_1,\cdots,y_t)$进行预测;
第二步称为更新(update)步骤,使用上一步预测的$P(s_{t+1}\mid y_1,\cdots,y_t)$更新$P(s_{t+1}\mid y_1,\cdots,y_{t+1})$,也就是有了预测结果之后再将对应的样本纳入模型:
Kalman滤波算法的复杂度比计算协方差矩阵的逆低很多,因为采用了递推的计算过程,每当步骤增加,则只需多执行一步迭代,而且无需保留太多数据在内存中,相比于求一个巨大矩阵的逆而言,算法复杂度低了很多: $$ \require{AMScd} \begin{CD} y_1 @. y_2 @. y_3 \\ @VVV @VVV @VVV \\ P\left(s_1\mid y_1\right) @>>> P\left(s_2\mid y_1,y_2\right) @>>> P\left(s_3\mid y_1,y_2,y_3\right) @>>> \cdots \end{CD} $$ 从这个草图可以看出来,当计算$P\left(s_3\mid y_1,y_2,y_3\right)$时,我们并不需要$y_1,y_2,P\left(s_1\mid y_1\right)$,每步计算只需要知道最新的观测值和上一步得出的概率估计即可。
将Kalman滤波与LQR结合起来就可以得到线性二次高斯(LQG: Linear Quadratic Gaussian)线性二次高速算法。在LQR问题中,我们将动作$a_t$加回到模型中:设非线性动力学系统为$s_{t+1}=As_t+Ba_t+w_t,\ w\sim\mathcal N(0,\varSigma_w)$,而且我们无法直接观测到状态,只能观测到$y_t=Cs_t+v_t,\ v\sim\mathcal N(0,\varSigma_v)$。现在使用Kalman滤波估计状态:
这个算法实际上是先设计了一个状态估计算法,然后再使用了一个控制算法,把两个算法结合起来就得到了LQG。