课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了LQR以及Ricatti方程。

Part XIV LQR,DDP和LQG

LQR,DDP和LQG分别代表线性二次调节，微分动态规划和线性二次高斯分布。

1.有限范围的MDP

在之前关于强化学习的讲义中，我们在简化的情形中定义了马尔可夫决策过程（MDP）并涵盖了价值迭代/策略迭代。更具体地说，我们引入了最优Bellman方程，该方程定义了最优策略$\pi’$的最优价值函数$V^{\pi’}$。

​ 回想一下，从最优价值函数，我们能够根据下式恢复最优策略$\pi’$

​ 在这部分讲义中，我们将把自己置于更一般的情形中：

  • 1.我们想要给出对离散和连续情况都有意义的公式。因此我们按照

    而不是

    来给出公式。上式表示对下一个状态的价值函数的期望。在有限状态的情形下，我们可以将期望重写为关于状态的求和。 在连续的情况下，我们可以将期望重写为一个积分。 符号$s’\sim P_{sa}$表示状态$s’$是从分布$P_{sa}$取样得来的。

  • 2.我们假设奖励取决于状态和行动。 换句话说，$R:\mathcal S\times \mathcal A \to \mathbb R$。这意味着先前用于计算最优行动的机制被改变为

  • 3.假设我们有一个有限范围的MDP而不是一个无限范围的MDP，它将被定义为如下一个元组

    其中$T>0$为时间范围（例如$T=100$）。在这种情形下，我们的对收益的定义将（略微）不同：

    而不是（无限范围的情形）

    折扣因子$\gamma ​$为什么消失了呢？ 请记住，$\gamma​$的引入（部分）是因为必须确保无限和是有限的并且是定义良好的。 如果奖励的上界为$\bar R​$，那么收益的上界为

    这里我们得到了几何级数！而在有限范围MDP中，由于收益是有限和，因此不再需要折扣因子。

    在新的假设下，事情表现非常不同。 首先，最优政策$\pi’ $可能是非平稳的，这意味着它会随着时间而变化。换句话说，现在我们有

​ 其中上标$(t)$表示第$t$步的策略。 有限范围MDP的动态根据策略$\pi^{(t)}$按如下方式进行：我们从某个状态$s_0$开始，根据我们在时间步骤$0$的策略采取某个动作$a_0:=\pi^{(0)}(s_0)$。MDP转移到后继状态$s_1$，$s_1$服从分布$P_{s_0a_0}$。 然后，我们可以根据我们在第$1$步的新政策选择另一个行动$a_1:=\pi^{(1)}(s_1)$，依此类推……

​ 为什么最优政策恰好在有限时间范围内不稳定？ 直观地说，由于我们要采取一些行动，我们可能希望根据我们在环境中的位置以及我们剩下多少时间采取不同的策略。 想象一个有$2​$个目标的网格，奖励分别为$+1​$和$+10​$。 一开始，我们可能希望采取行动以实现$+10​$目标。 但是如果经过一些步骤后，动态以某种方式推动我们更接近$+1​$目标并且我们没有足够的步骤来达到$+10​$目标，那么更好的策略是瞄准$+1​$目标。。

  • 4.这种观察允许我们使用依赖时间的动态

    这意味着转移分布$P^{(t)}_{s_t,a_t}$随时间改变。关于$R^{(t)}$可以说同样的事情。 请注意，这样的设定是现实生活中更好的模型。 结合之前的注记，我们将使用以下通用公式来表达我们的有限范围MDP

    注记：注意，上述公式相当于将时间加入状态。

    策略$\pi$在第$t$个时间戳的价值函数和之前的定义一样，作为策略$\pi$从状态$s$出发生成的轨迹的期望。

现在的问题是，在有限范围的设定下，我们如何找到最优价值函数

​ 事实证明，Bellman的值迭代方程是为动态规划而制定的。 这可能并不令人意外，因为贝尔曼是动态规划的先驱之一，而贝尔曼方程与该领域密切相关。 为了理解我们如何通过采用基于迭代的方法来简化问题，我们进行以下观察：

  • 1.注意到，在策略结束时（即在第$T$个时间戳），最优值是显而易见的

  • 2.对于其他的时间戳$0\le t <T​$，如果我们知道下一个时间戳的最优价值函数$V_{t+1}’​$，那么我们有

​ 有了这些观察结果，我们可以提出一个聪明的算法来求解最优值函数：

  • 1.利用公式$(1)$计算$V_T’$

  • 2.对$t= T-1,…,0$:

    ​ 根据公式$(2)$，利用$V_{t+1}’$计算$V_t’$

​ 旁注：我们可以将标准值迭代解释为这种一般情况不记录时间的特例。 事实证明，在标准设置中，如果我们进行$T$步值迭代，我们得到最优值迭代（几何收敛）的$\gamma^T$倍近似。 有关以下结果的证明，请参阅问题集4：

​ 定理：令$B$表示Bellman更新，$||f(x)||_{\infty}:=\sup_x |f(x)|$。如果$V_t$表示第$t$步的价值函数，那么：

​ 换句话说，Bellman算子$B$是$\gamma$-contracting算子。

2.线性二次调节(LQR)

在本节中，我们将介绍第$1​$节中描述的有限范围情形的特殊情况，其精确解（易于）处理。 该模型广泛用于机器人技术，许多问题的常用技术是将公式简化为这个框架。（具体处理方法为泰勒展开）

​ 首先，让我们描述模型的假设。 我们将自己置身于连续的情形中，其中

​ 然后我们假设线性变换（带噪声）

​ 其中$A_t \in \mathbb R^{n\times n}, B_t \in \mathbb R^{n\times d}$为矩阵，$w_t \sim \mathcal N(0,\Sigma_t)$是高斯噪声（$0$均值）。正如我们将在下文中展示的那样，只要它具有$0$均值，噪声就不会影响最优策略！

​ 我们还假设二次奖励

​ 其中$U_t\in\mathbb R^{n\times n},W_t\in\mathbb R^{d\times d}$为正定矩阵（这意味着奖励总是负的）。

​ 注记：注意奖励为二次型等同于说我们希望我们的状态接近原点（此时奖励更高）。 例如，如果$U_t=I_n​$（单位矩阵）并且$W_t= I_d​$，那么$R_t=-||s_t||^2-||a_t||^2​$，意味着我们想要采取平滑动作（使$a_t​$范数较小）回到原点（使$s_t ​$范数较小）。 这可以模拟一辆试图保持在车道中间而不会产生冲动动作的车……

​ 现在我们已经定义了LQR模型的假设，让我们来看看LQR算法的两个步骤

步骤1

  • 假设我们不知道矩阵$A,B,\Sigma​$。 为了估计它们，我们可以遵循RL讲义中值近似部分的想法。 首先，从任意策略中收集状态转移。 然后，使用线性回归找到$\arg \min_{A,B} \sum_{i=1}^m \sum_{t=0}^{T-1}
    \Big |\Big| s_{t+1}^{(i)}- \Big(As_{t}^{(i)}+B a_t^{(i)} \Big)\Big |\Big|^2​$。最后，使用高斯判别分析中的技术来学习$\Sigma​$。

步骤2

  • 假设我们的模型的参数是已知的（给出或通过步骤$1$估计），我们可以使用动态规划推导出最优策略。换句话说，给定

​ 我们希望计算$V_t’​$。如果我们回到第$1​$部分，我们可以应用动态规划，从而产生

  • 1.初始步骤

    对于最后一个时间戳$T​$，

  • 2.递归步骤

    令$t<T​$，假设已知$V_{t+1}’​$。

    事实1：可以证明，如果$V_{t+1}’$是关于$s_t$的二次函数，那么$V_t$也是二次函数。 换句话说，存在某个矩阵$\Phi$和某个标量$\Psi$使得

    对于时间戳$t=T​$，我们有$\Phi_t =-U_T, \Psi_t =0​$

    事实2：我们可以证明最优政策只是状态的线性函数。

    知道$V_{t+1}’$相当于知道$\Phi_{t+1}$和$\Psi_{t+1}$，所以我们只需要解释我们如何从​$\Phi_{t+1}$和​$\Psi_{t+1}$及问题的其他参数计算​$\Phi_{t}$和​$\Psi_{t}$。

    其中第二行是最优价值函数的定义，第三行是通过插入模型的动态和二次假设得到的。接下来先求解上述期望，注意到

    以及如果$x\sim N(\mu,\Sigma)​$，$x​$为向量，那么

    所以

    上面的推导过程利用到如下几个事实：

    因此上式可以化为

    记

    对$S$关于$a_t$求梯度可得

    令上式为$0$可得

    其中

    这是一个令人印象深刻的结果：我们的最优政策和$s_t$有线性关系。

    将$a_t’$带入$S$可得

    由$L_t := (W_t -B_t^T\Phi_{t+1}B_t)^{-1}B_t^T\Phi_{t+1}A_t​$可得

    带入上式可得

    结合$V_t’(s_t)​$的计算式，我们得到

    对比$V_{t}’(s_{t})= s_{t}^T \Phi_{t} s_{t} +\Psi_{t}$，不难得到如下计算式

    上式被称为离散Ricatti方程。

    备注：这里推导的结果和老师的讲义上不同，但暂时没找出问题。

    事实3：注意到$\Phi_t$既不依赖$\Psi_t$也不依赖噪音$\Sigma_t$！又因为$L_t$是$A_t,B_t$和$\Phi_{t+1} $的函数，这意味着最优策略也不依赖于噪声！ （但由于$\Psi_t $依赖于$\Sigma_t $，这意味着$V_t’ $依赖于$\Sigma_t $。）

现在，总结一下，LQR算法的工作原理如下

  • 1.(如果有必要)估计参数$A_t,B_t,\Sigma_t$
  • 2.初始化$\Phi_T:= -U_T, \Psi_T:=0​$
  • 3.遍历$t= T-1…0$来使用离散Ricatti方程，利用$\Phi_{t+1},\Psi_{t+1}$来更新$\Phi_{t},\Psi_{t}$。 如果存在使状态变趋于$0$的策略，则保证收敛！

使用事实3，我们可以使我们的算法运行地更快！ 由于最优策略不依赖于$\Psi_t ​$，并且$\Phi_t ​$的更新仅依赖于$\Phi_{t+1} ​$，因此仅更新$\Phi_t ​$ 是足够的！