线性二次调节，微分动态规划，线性二次高斯分布

上面三个名词的英文原版分别为:

  1. Linear Quadratic Regulation，缩写为LQR；
  2. Differential Dynamic Programming，缩写为DDP；
  3. Linear Quadratic Gaussian，缩写为LQG。

15.1 有限范围马尔科夫决策过程(Finite-horizon MDPs)

前面关于强化学习(Reinforcement Learning)的章节中，我们定义了马尔科夫决策过程(Markov Decision Processes，缩写为MDPs)，还涉及到了简单情景下的值迭代(Value Iteration)和策略迭代(Policy Iteration)。还具体介绍了最优贝尔曼方程(optimal Bellman equation)， 这个方程定义了对应最优策略(optimal policy)15 强化学习算法 - 图1的最优值函数(optimal value function)15 强化学习算法 - 图2。

15 强化学习算法 - 图3%3DR(s)%2B%5Cmax%7Ba%20%5Cin%20%5Cmathcal%7BA%7D%7D%20%5Cgamma%20%5Csum%7Bs’%20%5Cin%20%5Cmathcal%7BS%7D%7D%20P%7Bsa%7D(s’)V%5E%7B%5Cpi%5E*%7D(s’)%0A#card=math&code=V%5E%7B%5Cpi%5E%2A%7D%28s%29%3DR%28s%29%2B%5Cmax%7Ba%20%5Cin%20%5Cmathcal%7BA%7D%7D%20%5Cgamma%20%5Csum%7Bs%27%20%5Cin%20%5Cmathcal%7BS%7D%7D%20P%7Bsa%7D%28s%27%29V%5E%7B%5Cpi%5E%2A%7D%28s%27%29%0A&height=33&width=245)

通过优化值函数，就可以恢复最优策略15 强化学习算法 - 图4:

15 强化学习算法 - 图5%3D%5Carg%5Cmax%7Ba%5Cin%20%5Cmathcal%7BA%7D%7D%20%5Csum%7Bs’%5Cin%20%5Cmathcal%7BS%7D%7D%20P%7Bsa%7D%20(s’)V%5E%7B%5Cpi%5E*%7D(s’)%0A#card=math&code=%5Cpi%5E%2A%28s%29%3D%5Carg%5Cmax%7Ba%5Cin%20%5Cmathcal%7BA%7D%7D%20%5Csum%7Bs%27%5Cin%20%5Cmathcal%7BS%7D%7D%20P%7Bsa%7D%20%28s%27%29V%5E%7B%5Cpi%5E%2A%7D%28s%27%29%0A&height=33&width=204)

本章的讲义将会介绍一个更通用的情景:

  1. 这次我们希望写出来的方程能够对离散和连续的案例都适用。因此就要用期望15 强化学习算法 - 图6%5D#card=math&code=E%7Bs%27%20%5Csim%20P%7Bsa%7D%7D%5BV%5E%7B%5Cpi%5E%2A%7D%28s%27%29%5D&height=20&width=92)替代求和15 强化学习算法 - 图7V%5E%7B%5Cpi%5E*%7D(s’)#card=math&code=%5Csum%7Bs%27%5Cin%20S%7D%20P%7Bsa%7D%28s%27%29V%5E%7B%5Cpi%5E%2A%7D%28s%27%29&height=33&width=107)。这就意味着在下一个状态中使用值函数的期望(exception)。对于离散的有限案例，可以将期望写成对各种状态的求和。在连续场景，可以将期望写成积分(integral)。上式中的记号15 强化学习算法 - 图8的意思是状态15 强化学习算法 - 图9是从分布15 强化学习算法 - 图10中取样得到的。
  2. 接下来还假设奖励函数(reward)同时依赖状态(states)和动作(actions)。 也就是说，15 强化学习算法 - 图11。这就意味着前面计算最优动作的方法改成了

15 强化学习算法 - 图12%3D%5Carg%5Cmax%7Ba%5Cin%20A%7D%20R(s%EF%BC%8Ca)%2B%5Cgamma%20E%7Bs’%5Csim%20P%7Bsa%7D%7D%5BV%5E%7B%5Cpi%5E*%7D(s’)%5D%0A#card=math&code=%5Cpi%5E%2A%28s%29%3D%5Carg%5Cmax%7Ba%5Cin%20A%7D%20R%28s%EF%BC%8Ca%29%2B%5Cgamma%20E%7Bs%27%5Csim%20P%7Bsa%7D%7D%5BV%5E%7B%5Cpi%5E%2A%7D%28s%27%29%5D%0A&height=27&width=261)

  1. 以前我们考虑的是一个无限范围马尔科夫决策过程(infinite horizon MDP)，这回要改成有限范围马尔科夫决策过程(finite horizon MDP)， 定义为一个元组(tuple):

15 强化学习算法 - 图13%0A#card=math&code=%28%5Cmathcal%7BS%7D%2C%5Cmathcal%7BA%7D%2CP_%7Bsa%7D%2CT%2CR%29%0A&height=16&width=94)

其中的15 强化学习算法 - 图14的时间范围(time horizon)， 例如15 强化学习算法 - 图15。这样的设定下，支付函数(payoff)就变成了:

15 强化学习算法 - 图16%2BR(s_1%2Ca_1)%2B%5Cdots%2BR(s_T%2Ca_T)%0A#card=math&code=R%28s_0%2Ca_0%29%2BR%28s_1%2Ca_1%29%2B%5Cdots%2BR%28s_T%2Ca_T%29%0A&height=16&width=227)

而不再是之前的:

15 强化学习算法 - 图17%2B%5Cgamma%20R(s1%2Ca_1)%20%2B%20%5Cgamma%5E2%20R(s_2%2Ca_2)%2B%5Cdots%5C%5C%0A%26%20%5Csum%5E%5Cinfty%7Bt%3D0%7DR(st%2Ca_t)%5Cgamma%5Et%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%26%20R%28s_0%2Ca_0%29%2B%5Cgamma%20R%28s_1%2Ca_1%29%20%2B%20%5Cgamma%5E2%20R%28s_2%2Ca_2%29%2B%5Cdots%5C%5C%0A%26%20%5Csum%5E%5Cinfty%7Bt%3D0%7DR%28s_t%2Ca_t%29%5Cgamma%5Et%0A%5Cend%7Baligned%7D%0A&height=59&width=249)

折扣因子(discount factor)15 强化学习算法 - 图18哪去了呢？还记得当初引入这个15 强化学习算法 - 图19的一部分原因就是由于要保持无穷项求和(infinite sum)是有限值( finite)并且好定义(well-defined)的么？如果奖励函数(rewards)绑定了一个常数15 强化学习算法 - 图20，则支付函数(payoff)也被绑定成:

15 强化学习算法 - 图21%5Cgamma%5Et%7C%5Cle%20%5Cbar%20R%20%5Csum%5E%7B%5Cinfty%7D%7Bt%3D0%7D%5Cgamma%5Et%0A#card=math&code=%7C%5Csum%5E%7B%5Cinfty%7D%7Bt%3D0%7DR%28st%29%5Cgamma%5Et%7C%5Cle%20%5Cbar%20R%20%5Csum%5E%7B%5Cinfty%7D%7Bt%3D0%7D%5Cgamma%5Et%0A&height=40&width=140)

这就能识别是一个几何求和(geometric sum)！现在由于支付函数(payoff)是一个有限和(finite sum)了，那折扣因子(discount factor)15 强化学习算法 - 图22就没有必要再存在了。

在这种新环境下，事情就和之前不太一样了。首先是最优策略(optimal policy)15 强化学习算法 - 图23可能是非稳定的(non-stationary)，也就意味着它可能随着时间步发生变化。 也就是说现在有:

15 强化学习算法 - 图24%7D%3A%5Cmathcal%7BS%7D%5Crightarrow%5Cmathcal%7BA%7D%0A#card=math&code=%5Cpi%5E%7B%28t%29%7D%3A%5Cmathcal%7BS%7D%5Crightarrow%5Cmathcal%7BA%7D%0A&height=16&width=72)

上面括号中的15 强化学习算法 - 图25#card=math&code=%28t%29&height=16&width=15)表示了在第15 强化学习算法 - 图26步时候的策略函数(policy)。遵循策略15 强化学习算法 - 图27%7D#card=math&code=%5Cpi%5E%7B%28t%29%7D&height=16&width=20)的有限范围马尔科夫决策过程如下所示：开始是某个状态15 强化学习算法 - 图28，然后对应第15 强化学习算法 - 图29步时候的策略15 强化学习算法 - 图30%7D#card=math&code=%5Cpi%5E%7B%280%29%7D&height=16&width=21)采取某种行为15 强化学习算法 - 图31%7D(s0)#card=math&code=a_0%3A%3D%20%5Cpi%5E%7B%280%29%7D%28s_0%29&height=19&width=79)。然后马尔科夫决策过程(MDP)转换到接下来的15 强化学习算法 - 图32，根据![](https://g.yuque.com/gr/latex?P%7Bs0a_0%7D#card=math&code=P%7Bs_0a_0%7D&height=16&width=28)来进行调整。然后在选择遵循第15 强化学习算法 - 图33步的新策略15 强化学习算法 - 图34%7D#card=math&code=%5Cpi%5E%7B%281%29%7D&height=16&width=21)的另一个行为15 强化学习算法 - 图35%7D(s_1)#card=math&code=a_1%3A%3D%20%5Cpi%5E%7B%281%29%7D%28s_1%29&height=19&width=79)。依次类推进行下去。

为什么在有限范围背景下的优化策略函数碰巧就是非稳定的呢？直观来理解，由于我们只能够选择有限的应对行为，我们可能要适应不同环境的不同策略，还要考虑到剩下的时间(步骤数)。设想有一个网格，其中有两个目标，奖励值分别是15 强化学习算法 - 图36和15 强化学习算法 - 图37。那么开始的时候我们的行为肯定是瞄准了最高的奖励15 强化学习算法 - 图38这个目标。但如果过了几步之后，我们更靠近15 强化学习算法 - 图39这个目标而没有足够的剩余步数去到达15 强化学习算法 - 图40这个目标，那更好的策略就是改为瞄准15 强化学习算法 - 图41了。

  1. 这样的观察就使得我们可以使用对时间依赖的方法(time dependent dynamics):

15 强化学习算法 - 图42%7D%7Bs_t%2Ca_t%7D%0A#card=math&code=s%7Bt%2B1%7D%20%5Csim%20P%5E%7B%28t%29%7D_%7Bs_t%2Ca_t%7D%0A&height=21&width=71)

这就意味着变换分布(transition distribution)15 强化学习算法 - 图43%7D%7Bs_t%2Ca_t%7D#card=math&code=P%5E%7B%28t%29%7D%7Bs_t%2Ca_t%7D&height=21&width=29)随着时间而变化。对15 强化学习算法 - 图44%7D#card=math&code=R%5E%7B%28t%29%7D&height=16&width=22)而言也是如此。要注意，现在这个模型就更加符合现实世界的情况了。比如对一辆车来说，油箱会变空，交通状况会变化，等等。结合前面提到的内容，就可以使用下面这个通用方程(general formulation)来表达我们的有限范围马尔科夫决策过程(fi nite horizon MDP):

15 强化学习算法 - 图45%7D%7Bsa%7D%2CT%2CR%5E%7B(t)%7D)%0A#card=math&code=%28%5Cmathcal%7BS%7D%2C%5Cmathcal%7BA%7D%2CP%5E%7B%28t%29%7D%7Bsa%7D%2CT%2CR%5E%7B%28t%29%7D%29%0A&height=20&width=109)

备注： 上面的方程其实和在状态中加入时间所得到的方程等价。

在时间15 强化学习算法 - 图46对于一个策略15 强化学习算法 - 图47的值函数也得到了定义，也就是从状态15 强化学习算法 - 图48开始遵循策略15 强化学习算法 - 图49生成的轨道(trajectories)的期望(expectation)。

15 强化学习算法 - 图50%3DE%5BR%5E%7B(t)%7D(s_t%2Ca_t)%2B%5Cdots%2BR%5E%7B(T)%7D(s_T%2Ca_T)%7Cs_t%3Ds%2C%5Cpi%20%5D%0A#card=math&code=V_t%28s%29%3DE%5BR%5E%7B%28t%29%7D%28s_t%2Ca_t%29%2B%5Cdots%2BR%5E%7B%28T%29%7D%28s_T%2Ca_T%29%7Cs_t%3Ds%2C%5Cpi%20%5D%0A&height=19&width=302)

现在这个方程就是：在有限范围背景下，如何找到最优值函数(optimal value function):

15 强化学习算法 - 图51%3D%5Cmax%7B%5Cpi%7DV%5E%7B%5Cpi%7D_t(s)%0A#card=math&code=V%5E%2A_t%28s%29%3D%5Cmax%7B%5Cpi%7DV%5E%7B%5Cpi%7D_t%28s%29%0A&height=23&width=115)

结果表明对值迭代(Value Iteration)的贝尔曼方程(Bellman’s equation)正好适合动态规划(Dynamic Programming)。 这也没啥可意外的，因为贝尔曼(Bellman)本身就是动态规划的奠基人之一，而贝尔曼方程(Bellman equation)和这个领域有很强的关联性。为了理解为啥借助基于迭代的方法(iteration-based approach)就能简化问题，我们需要进行下面的观察:

  1. 在游戏终结（到达步骤15 强化学习算法 - 图52）的时候，最优值(optimal value)很明显就是

15 强化学习算法 - 图53%3A%3D%5Cmax%7Ba%5Cin%20A%7D%20R%5E%7B(T)%7D(s%2Ca)%20%5Cqquad(1)%0A#card=math&code=%5Cforall%20s%5Cin%20%5Cmathcal%7BS%7D%3A%20V%5E%2A_T%28s%29%3A%3D%5Cmax%7Ba%5Cin%20A%7D%20R%5E%7B%28T%29%7D%28s%2Ca%29%20%5Cqquad%281%29%0A&height=27&width=234)

  1. 对于另一个时间步15 强化学习算法 - 图54，如果假设已经知道了下一步的最优值函数15 强化学习算法 - 图55，就有:

15 强化学习算法 - 图56%3A%3D%20%5Cmax%7Ba%5Cin%20A%7D%20%5BR%5E%7B(t)%7D(s%2Ca)%2BE%7Bs’%5Csim%20P%5E%7B(t)%7D%7Bsa%7D%7D%5BV%5E*%7Bt%2B1%7D(s’)%5D%5D%20%5Cqquad%20(2)%0A#card=math&code=%5Cforall%20t%3CT%EF%BC%8Cs%20%5Cin%20%5Cmathcal%7BS%7D%3A%20V%5E%2At%20%28s%29%3A%3D%20%5Cmax%7Ba%5Cin%20A%7D%20%5BR%5E%7B%28t%29%7D%28s%2Ca%29%2BE%7Bs%27%5Csim%20P%5E%7B%28t%29%7D%7Bsa%7D%7D%5BV%5E%2A_%7Bt%2B1%7D%28s%27%29%5D%5D%20%5Cqquad%20%282%29%0A&height=27&width=395)

观察并思考后，就能想出一个聪明的算法来解最优值函数了:

  1. 利用等式15 强化学习算法 - 图57#card=math&code=%281%29&height=16&width=17)计算15 强化学习算法 - 图58。
  2. for 15 强化学习算法 - 图59:
      使用15 强化学习算法 - 图60利用等式15 强化学习算法 - 图61#card=math&code=%282%29&height=16&width=17)计算15 强化学习算法 - 图62。

备注: 可以将标准值迭代(standard value iteration)看作是上述通用情况的一个特例，就是不用记录时间(步数)。结果表明在标准背景下，如果对15 强化学习算法 - 图63步骤运行值迭代，会得到最优值迭代的一个15 强化学习算法 - 图64的近似(几何收敛，geometric convergence)。参考习题集4中有对下列结果的证明:

定理：设15 强化学习算法 - 图65表示贝尔曼更新函数(Bellman update)，以及15 强化学习算法 - 图66%7C%7C%5Cinfty%3A%3D%20%5Csup_x%7Cf(x)%7C#card=math&code=%7C%7Cf%28x%29%7C%7C%5Cinfty%3A%3D%20%5Csup_x%7Cf%28x%29%7C&height=24&width=129)。如果15 强化学习算法 - 图67表示在第15 强化学习算法 - 图68步的值函数，则有:

15 强化学习算法 - 图69-V%5E%7C%7C_%5Cinfty%5C%5C%0A%26%5Cle%20%5Cgamma%7C%7CV_t-V%5E%7C%7C%5Cinfty%5C%5C%0A%26%5Cle%20%5Cgamma%5Et%7C%7CV_1-V%5E*%7C%7C%5Cinfty%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%7C%7CV%7Bt%2B1%7D-V%5E%2A%7C%7C%5Cinfty%20%26%3D%7C%7CB%28Vt%29-V%5E%2A%7C%7C%5Cinfty%5C%5C%0A%26%5Cle%20%5Cgamma%7C%7CVt-V%5E%2A%7C%7C%5Cinfty%5C%5C%0A%26%5Cle%20%5Cgamma%5Et%7C%7CV1-V%5E%2A%7C%7C%5Cinfty%0A%5Cend%7Baligned%7D%0A&height=55&width=201)

也就是说贝尔曼运算器15 强化学习算法 - 图70成了一个15 强化学习算法 - 图71收缩算子(contracting operator)。

15.2 线性二次调节(Linear Quadratic Regulation，缩写为LQR)

在本节，我们要讲一个上一节所提到的有限范围(finite-horizon)背景下精确解(exact solution) 很容易处理的特例。这个模型在机器人领域用的特别多，也是在很多问题中将方程化简到这一框架的常用方法。

首先描述一下模型假设。考虑一个连续背景，都用实数集了:

15 强化学习算法 - 图72

然后设有噪音(noise)的线性转换(linear transitions):

15 强化学习算法 - 图73

上式中的15 强化学习算法 - 图74实矩阵，而15 强化学习算法 - 图75#card=math&code=w_t%5Csim%20N%280%EF%BC%8C%5CSigma_t%29&height=19&width=89)是某个高斯分布的噪音（均值为零）。我们接下来要讲的内容就表明：只要噪音的均值是15 强化学习算法 - 图76，就不会影响最优化策略。

另外还要假设一个二次奖励函数(quadratic rewards):

15 强化学习算法 - 图77%7D(s_t%2Ca_t)%3D-s_t%5ETU_ts_t-a_t%5ETW_ta_t%0A#card=math&code=R%5E%7B%28t%29%7D%28s_t%2Ca_t%29%3D-s_t%5ETU_ts_t-a_t%5ETW_ta_t%0A&height=20&width=192)

上式中的15 强化学习算法 - 图78都是正定矩阵(positive definite matrices)，这就意味着奖励函数总是负的(negative)。

要注意这里的奖励函数的二次方程(quadratic formulation)就等价于无论奖励函数是否更高我们都希望能接近原始值(origin)。例如，如果15 强化学习算法 - 图79就是15 强化学习算法 - 图80阶单位矩阵(identity matrix)，而15 强化学习算法 - 图81为一个15 强化学习算法 - 图82阶单位矩阵，那么就有15 强化学习算法 - 图83，也就意味着我们要采取光滑行为(smooth actions)（15 强化学习算法 - 图84的范数(norm)要小）来回溯到原始状态（15 强化学习算法 - 图85的范数(norm)要小）。这可以模拟一辆车保持在车道中间不发生突发运动。

接下来就可以定义这个线性二次调节(LQR)模型的假设了，这个LQR算法包含两步骤:

第一步设矩阵15 强化学习算法 - 图86都是未知的。那就得估计他们，可以利用强化学习课件中的值估计(Value Approximation)部分的思路。首先是从一个任意策略(policy)收集转换(collect transitions)。然后利用线性回归找到15 强化学习算法 - 图87%7D%7Bt%2B1%7D-%20(%20As%5E%7B(i)%7D_t%20%2BBa%5E%7B(i)%7D_t)%7C%7C%5E2#card=math&code=%5Carg%5Cmin%7BA%2CB%7D%5Csum%5Em%7Bi%3D1%7D%5Csum%5E%7BT-1%7D%7Bt%3D0%7D%7C%7Cs%5E%7B%28i%29%7D%7Bt%2B1%7D-%20%28%20As%5E%7B%28i%29%7D_t%20%2BBa%5E%7B%28i%29%7D_t%29%7C%7C%5E2&height=42&width=236)。最后利用高斯判别分析(Gaussian Discriminant Analysis，缩写为GDA)中的方法来学习15 强化学习算法 - 图88。

(译者注:原文这里第一步的第二行公式中用的是15 强化学习算法 - 图89，应该是写错了，结合上下文公式推导来看，分明应该是15 强化学习算法 - 图90)

第二步假如模型参数已知了，比如可能是给出了，或者用上面第一步估计出来了，就可以使用动态规划(dynamic programming)来推导最优策略(optimal policy)了。

也就是说，给出了:

15 强化学习算法 - 图91%7D(st%EF%BC%8Ca_t)%26%3D%20-s_t%5ETU_ts_t-a%5ET_tW_ta_t%0A%5Cend%7Bcases%7D%0A#card=math&code=%5Cbegin%7Bcases%7D%0As%7Bt%2B1%7D%20%26%3D%20A_ts_t%2BB_ta_t%2Bw_t%5Cqquad%20%E5%B7%B2%E7%9F%A5A_t%2CB_t%2CU_t%2CW_t%2C%5CSigma_t%5C%5C%0AR%5E%7B%28t%29%7D%28s_t%EF%BC%8Ca_t%29%26%3D%20-s_t%5ETU_ts_t-a%5ET_tW_ta_t%0A%5Cend%7Bcases%7D%0A&height=43&width=366)

然后要计算出15 强化学习算法 - 图92。如果回到第一步，就可以利用动态规划，就得到了:

  1. 初始步骤(Initialization step)

  对最后一次步骤15 强化学习算法 - 图93，

15 强化学习算法 - 图94%26%3D%5Cmax%7Ba_T%5Cin%20A%7DR_T(s_T%2Ca_T)%5C%5C%0A%26%3D%5Cmax%7BaT%5Cin%20A%7D-s%5ET_TU_ts_T%20-%20a%5ET_TW_ta_T%5C%5C%0A%26%3D%20-s%5ET_TU_ts_T%5Cqquad%5Cqquad(%5Ctext%7B%E5%AF%B9%7Da_T%3D0%5Ctext%7B%E6%9C%80%E5%A4%A7%E5%8C%96%7D)%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AV%5E%2A_T%28s_T%29%26%3D%5Cmax%7BaT%5Cin%20A%7DR_T%28s_T%2Ca_T%29%5C%5C%0A%26%3D%5Cmax%7Ba_T%5Cin%20A%7D-s%5ET_TU_ts_T%20-%20a%5ET_TW_ta_T%5C%5C%0A%26%3D%20-s%5ET_TU_ts_T%5Cqquad%5Cqquad%28%5Ctext%7B%E5%AF%B9%7Da_T%3D0%5Ctext%7B%E6%9C%80%E5%A4%A7%E5%8C%96%7D%29%0A%5Cend%7Baligned%7D%0A&height=75&width=273)

  1. 递归步骤(Recurrence step)

  设15 强化学习算法 - 图95。加入已经知道了15 强化学习算法 - 图96。

定理1:很明显如果15 强化学习算法 - 图97是15 强化学习算法 - 图98的一个二次函数，则15 强化学习算法 - 图99也应该是15 强化学习算法 - 图100的一个二次函数。也就是说，存在某个矩阵15 强化学习算法 - 图101以及某个标量15 强化学习算法 - 图102满足:

15 强化学习算法 - 图103%20%26%3D%20s%5ET%7Bt%2B1%7D%5CPhi%7Bt%2B1%7Ds%7Bt%2B1%7D%2B%5CPsi%7Bt%2B1%7D%5C%5C%0A%5Ctext%7Bthen%7D%20%5Cquad%20V%5E*t(s_t)%26%3Ds%5ET_t%5CPhi_ts_t%2B%5CPsi_t%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Ctext%7Bif%7D%20%5Cquad%20V%5E%2A%7Bt%2B1%7D%28s%7Bt%2B1%7D%29%20%26%3D%20s%5ET%7Bt%2B1%7D%5CPhi%7Bt%2B1%7Ds%7Bt%2B1%7D%2B%5CPsi_%7Bt%2B1%7D%5C%5C%0A%5Ctext%7Bthen%7D%20%5Cquad%20V%5E%2A_t%28s_t%29%26%3Ds%5ET_t%5CPhi_ts_t%2B%5CPsi_t%0A%5Cend%7Baligned%7D%0A&height=37&width=220)

对时间步骤15 强化学习算法 - 图104，则有15 强化学习算法 - 图105。

定理2:可以证明最优策略是状态的一个线性函数。

已知15 强化学习算法 - 图106就等价于知道了15 强化学习算法 - 图107，所以就只需要解释如何从15 强化学习算法 - 图108去计算15 强化学习算法 - 图109，以及问题中的其他参数。

15 强化学习算法 - 图110%26%3D%20%20st%5ET%5CPhi_ts_t%2B%5CPsi_t%20%5C%5C%0A%26%3D%20%5Cmax%7Bat%7D%5BR%5E%7B(t)%7D(s_t%2Ca_t)%2BE%7Bs%7Bt%2B1%7D%5Csim%20P%5E%7B(t)%7D%7Bst%2Ca_t%7D%7D%5BV%5E*%7Bt%2B1%7D(s%7Bt%2B1%7D)%5D%5D%20%20%5C%5C%0A%26%3D%20%5Cmax%7Bat%7D%5B-s_t%5ETU_ts_t-a_t%5ETV_ta_t%2BE%7Bs%7Bt%2B1%7D%5Csim%20N(A_ts_t%2BB_ta_t%2C%5CSigma_t)%7D%20%20%5Bs%7Bt%2B1%7D%5ET%5CPhi%7Bt%2B1%7Ds%7Bt%2B1%7D%2B%5CPsi%7Bt%2B1%7D%5D%20%5D%20%20%5C%5C%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AV%5E%2A_t%28s_t%29%26%3D%20%20s_t%5ET%5CPhi_ts_t%2B%5CPsi_t%20%5C%5C%0A%26%3D%20%5Cmax%7Bat%7D%5BR%5E%7B%28t%29%7D%28s_t%2Ca_t%29%2BE%7Bs%7Bt%2B1%7D%5Csim%20P%5E%7B%28t%29%7D%7Bst%2Ca_t%7D%7D%5BV%5E%2A%7Bt%2B1%7D%28s%7Bt%2B1%7D%29%5D%5D%20%20%5C%5C%0A%26%3D%20%5Cmax%7Bat%7D%5B-s_t%5ETU_ts_t-a_t%5ETV_ta_t%2BE%7Bs%7Bt%2B1%7D%5Csim%20N%28A_ts_t%2BB_ta_t%2C%5CSigma_t%29%7D%20%20%5Bs%7Bt%2B1%7D%5ET%5CPhi%7Bt%2B1%7Ds%7Bt%2B1%7D%2B%5CPsi_%7Bt%2B1%7D%5D%20%5D%20%20%5C%5C%0A%5Cend%7Baligned%7D%0A&height=73&width=456)

上式中的第二行正好就是最优值函数(optimal value function)的定义，而第三行是通过代入二次假设和模型方法。注意最后一个表达式是一个关于15 强化学习算法 - 图111的二次函数，因此很容易就能优化掉15 强化学习算法 - 图112。然后就能得到最优行为(optimal action)15 强化学习算法 - 图113:

1 这里用到了恒等式(identity)15 强化学习算法 - 图114%EF%BC%8C%5Cquad%20%5Ctext%7B%E5%85%B6%E4%B8%AD%7D%20wt%5Csim%20N(0%EF%BC%8C%5CSigma_t)#card=math&code=E%5Bw_t%5ET%5CPhi%7Bt%2B1%7Dwt%5D%20%3DTr%28%5CSigma_t%5CPhi%7Bt%2B1%7D%29%EF%BC%8C%5Cquad%20%5Ctext%7B%E5%85%B6%E4%B8%AD%7D%20w_t%5Csim%20N%280%EF%BC%8C%5CSigma_t%29&height=19&width=303))。

15 强化学习算法 - 图115%5E%7B-1%7DBt%5CPhi%7Bt%2B1%7DAt%5D%5Ccdot%20s_t%5C%5C%0A%26%3D%20L_t%5Ccdot%20s_t%5C%5C%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0Aa%5E%2A_t%26%3D%20%5B%28B_t%5ET%5CPhi%7Bt%2B1%7DBt-V_t%29%5E%7B-1%7DB_t%5CPhi%7Bt%2B1%7DA_t%5D%5Ccdot%20s_t%5C%5C%0A%26%3D%20L_t%5Ccdot%20s_t%5C%5C%0A%5Cend%7Baligned%7D%0A&height=36&width=234)

上式中的

15 强化学习算法 - 图116%5E%7B-1%7DBt%5CPhi%7Bt%2B1%7DAt%5D%0A#card=math&code=L_t%20%3A%3D%20%5B%28B_t%5ET%5CPhi%7Bt%2B1%7DBt-V_t%29%5E%7B-1%7DB_t%5CPhi%7Bt%2B1%7DA_t%5D%0A&height=19&width=214)

这是一个很值得注意的结果(impressive result)：优化策略(optimal policy)是关于状态15 强化学习算法 - 图117的线性函数。 对于给定的15 强化学习算法 - 图118，我们就可以解出来15 强化学习算法 - 图119和15 强化学习算法 - 图120。最终就得到了离散里卡蒂方程(Discrete Ricatti equations):

15 强化学习算法 - 图121%5E%7B-1%7DBt%5CPhi%7Bt%2B1%7D)At-U_t%5C%5C%0A%5CPsi_t%26%3D%20-tr(%5CSigma_t%5CPhi%7Bt%2B1%7D)%2B%5CPsi%7Bt%2B1%7D%5C%5C%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5CPhi_t%26%3D%20A%5ET_t%28%5CPhi%7Bt%2B1%7D-%5CPhi%7Bt%2B1%7DB_t%28B%5ET_t%5CPhi%7Bt%2B1%7DBt-W_t%29%5E%7B-1%7DB_t%5CPhi%7Bt%2B1%7D%29At-U_t%5C%5C%0A%5CPsi_t%26%3D%20-tr%28%5CSigma_t%5CPhi%7Bt%2B1%7D%29%2B%5CPsi_%7Bt%2B1%7D%5C%5C%0A%5Cend%7Baligned%7D%0A&height=37&width=358)

定理3:要注意15 强化学习算法 - 图122既不依赖15 强化学习算法 - 图123也不依赖噪音项15 强化学习算法 - 图124！由于15 强化学习算法 - 图125是一个关于15 强化学习算法 - 图126的函数，这就暗示了最优策略也不依赖噪音！ （但15 强化学习算法 - 图127是依赖15 强化学习算法 - 图128的，这就暗示了最优值函数15 强化学习算法 - 图129也是依赖噪音15 强化学习算法 - 图130的。）

然后总结一下，线性二次调节(LQR)算法就如下所示:

  1. 首先，如果必要的话，估计参数15 强化学习算法 - 图131。
  2. 初始化15 强化学习算法 - 图132。
  3. 从15 强化学习算法 - 图133开始迭代，借助离散里卡蒂方程(Discrete Ricatti equations)来利用15 强化学习算法 - 图134来更新15 强化学习算法 - 图135，如果存在一个策略能朝着15 强化学习算法 - 图136方向推导状态，收敛就能得到保证。

利用定理3，我们知道最优策略不依赖与15 强化学习算法 - 图137而只依赖15 强化学习算法 - 图138，这样我们就可以只 更新15 强化学习算法 - 图139，从而让算法运行得更快一点！

15.3 从非线性方法(non-linear dynamics)到线性二次调节(LQR)

很多问题都可以化简成线性二次调节(LDR)的形式，包括非线性的模型。LQR是一个很好的方程，因为我们能够得到很好的精确解，但距离通用还有一段距离。我们以倒立摆(inverted pendulum)为例。状态的变换如下所示:

15 强化学习算法 - 图140

其中的函数15 强化学习算法 - 图141依赖于角度余弦等等。然后这个问题就成了：

15 强化学习算法 - 图142

15.3.1 模型的线性化(Linearization of dynamics)

假设某个时间15 强化学习算法 - 图143上，系统的绝大部分时间都处在某种状态15 强化学习算法 - 图144上，而我们要选取的行为大概就在15 强化学习算法 - 图145附近。对于倒立摆问题，如果我们达到了某种最优状态，就会满足：行为很小并且和竖直方向的偏差不大。

这就要用到泰勒展开(Taylor expansion)来将模型线性化。简单的情况下状态是一维的，这时候转换函数15 强化学习算法 - 图146就不依赖于行为，这时候就可以写成:

15 强化学习算法 - 图147%5Capprox%20F(%5Cbar%20st)%2B%20F’(%5Cbar%20s_t)%5Ccdot%20(s_t-%5Cbar%20s_t)%0A#card=math&code=s%7Bt%2B1%7D%3DF%28s_t%29%5Capprox%20F%28%5Cbar%20s_t%29%2B%20F%27%28%5Cbar%20s_t%29%5Ccdot%20%28s_t-%5Cbar%20s_t%29%0A&height=17&width=238)

对于更通用的情景，方程看着是差不多的，只是用梯度(gradients)替代简单的导数(derivatives):

15 强化学习算法 - 图148%2B%5Cnabla%20sF(%5Cbar%20s_t%2C%5Cbar%20a_t)%5Ccdot%20(s_t-%5Cbar%20s_t)%2B%5Cnabla_aF(%5Cbar%20s_t%2C%5Cbar%20a_t)%5Ccdot%20(a_t-%5Cbar%20a_t)%20%5Cqquad%20%5Ctext%7B(3)%7D%0A#card=math&code=s%7Bt%2B1%7D%5Capprox%20F%28%5Cbar%20s_t%2C%5Cbar%20a_t%29%2B%5Cnabla%20_sF%28%5Cbar%20s_t%2C%5Cbar%20a_t%29%5Ccdot%20%28s_t-%5Cbar%20s_t%29%2B%5Cnabla_aF%28%5Cbar%20s_t%2C%5Cbar%20a_t%29%5Ccdot%20%28a_t-%5Cbar%20a_t%29%20%5Cqquad%20%5Ctext%7B%283%29%7D%0A&height=16&width=428)

现在15 强化学习算法 - 图149就是关于15 强化学习算法 - 图150的线性函数了，因为可以将等式15 强化学习算法 - 图151#card=math&code=%283%29&height=16&width=17)改写成下面的形式：

15 强化学习算法 - 图152

(译者注:原文这里的公式应该是写错了，写成了15 强化学习算法 - 图153)

上式中的15 强化学习算法 - 图154是某个常数，而15 强化学习算法 - 图155都是矩阵。现在这个写法就和在LQR里面的假设非常相似了。这时候只要摆脱掉常数项15 强化学习算法 - 图156就可以了!结果表明只要任意增长一个维度就可以将常数项吸收进15 强化学习算法 - 图157中区。这和我们在线性回归的课程里面用到的办法一样。

15.3.2 微分动态规划(Differential Dynamic Programming，缩写为DDP)

如果我们的目标就是保持在某个状态15 强化学习算法 - 图158，上面的方法都能够很适合所选情景（比如倒立摆或者一辆车保持在车道中间）。不过有时候我们的目标可能要更复杂很多。

本节要讲的方法适用于要符合某些轨道的系统（比如火箭发射）。这个方法将轨道离散化称为若干离散的时间步骤，然后运用前面的方法创建中间目标!这个方法就叫做微分动态规划(Differential Dynamic Programming，缩写为DDP)。 主要步骤包括：

第一步利用简单控制器(naive controller)创建一个标称轨道(nominal trajectory)，对要遵循轨道进行近似。也就是说，我们的控制器可以用如下方法来近似最佳轨道：

15 强化学习算法 - 图159

第二步在每个轨道点(trajectory point)15 强化学习算法 - 图160将模型线性化，也就是:

15 强化学习算法 - 图161%2B%5Cnablas%20F(s%5E_t%2Ca%5E_t)(s_t-s%5E_t)%2B%5Cnabla_aF(s%5E_t%2Ca%5E_t)(a_t-a%5E_t)%0A#card=math&code=s%7Bt%2B1%7D%5Capprox%20F%28s%5E%2A_t%2Ca%5E%2A_t%29%2B%5Cnabla_s%20F%28s%5E%2A_t%2Ca%5E%2A_t%29%28s_t-s%5E%2A_t%29%2B%5Cnabla_aF%28s%5E%2A_t%2Ca%5E%2A_t%29%28a_t-a%5E%2A_t%29%0A&height=17&width=370)

上面的15 强化学习算法 - 图162是当前的状态和行为。现在已经在每个轨道点都有了线性估计了，就可以使用前面的方法将其改写成:

15 强化学习算法 - 图163

（要注意在这个情况下，我们可以使用在本章一开头所提到的非稳定动力学模型背景。）

注意， 这里我们可以对奖励函数(reward)15 强化学习算法 - 图164%7D#card=math&code=R%5E%7B%28t%29%7D&height=16&width=22)推导一个类似的积分(derivation)，使用一个二阶泰勒展开(second-order Taylor expansion)就可以了。

15 强化学习算法 - 图165%26%20%5Capprox%20R(s%5E_t%EF%BC%8Ca%5Et)%2B%5Cnabla_s%20R(s%5E_t%EF%BC%8Ca%5E_t)(s_t-s%5E_t)%20%2B%5Cnabla_a%20R(s%5E_t%EF%BC%8Ca%5E_t)(a_t-a%5E_t)%20%5C%5C%0A%26%20%2B%20%5Cfrac%7B1%7D%7B2%7D(s_t-s%5E*_t)%5ETH%7Bss%7D(st-s%5E_t)%2B(s_t-s%5E_t)%5ETH%7Bsa%7D(at-a%5E_t)%5C%5C%0A%26%20%20%2B%20%5Cfrac%7B1%7D%7B2%7D(a_t-a%5E_t)%5ETH%7Baa%7D(at-a%5E*_t)%20%5C%5C%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0AR%28s_t%EF%BC%8Ca_t%29%26%20%5Capprox%20R%28s%5E%2A_t%EF%BC%8Ca%5E%2A_t%29%2B%5Cnabla_s%20R%28s%5E%2A_t%EF%BC%8Ca%5E%2A_t%29%28s_t-s%5E%2A_t%29%20%2B%5Cnabla_a%20R%28s%5E%2A_t%EF%BC%8Ca%5E%2A_t%29%28a_t-a%5E%2A_t%29%20%5C%5C%0A%26%20%2B%20%5Cfrac%7B1%7D%7B2%7D%28s_t-s%5E%2A_t%29%5ETH%7Bss%7D%28st-s%5E%2A_t%29%2B%28s_t-s%5E%2A_t%29%5ETH%7Bsa%7D%28at-a%5E%2A_t%29%5C%5C%0A%26%20%20%2B%20%5Cfrac%7B1%7D%7B2%7D%28a_t-a%5E%2A_t%29%5ETH%7Baa%7D%28a_t-a%5E%2A_t%29%20%5C%5C%0A%5Cend%7Baligned%7D%0A&height=82&width=428)

上式中的15 强化学习算法 - 图166表示的 15 强化学习算法 - 图167 的海森矩阵(Hessian)项，对应的15 强化学习算法 - 图168和15 强化学习算法 - 图169是在15 强化学习算法 - 图170#card=math&code=%28s%5E%2A_t%2Ca%5E%2A_t%29&height=17&width=42)中得到的（略去不表）。这个表达式可以重写成:

15 强化学习算法 - 图171%3D%20-s_t%5ETU_ts_t-a_t%5ETW_ta_t%0A#card=math&code=R_t%28s_t%EF%BC%8Ca_t%29%3D%20-s_t%5ETU_ts_t-a_t%5ETW_ta_t%0A&height=19&width=191)

对于某些矩阵15 强化学习算法 - 图172，可以再次使用扩展维度的方法。注意:

15 强化学习算法 - 图173

第三步现在你就能够相信这个问题可以严格写成LQR框架的形式了吧。然后就可以利用线性二次调节(LQR)来找到最优策略15 强化学习算法 - 图174。这样新的控制器就会更好些！

8注意:* 如果LQR轨道和线性近似的轨道偏离太远，可能会出现一些问题，不过这些都可以通过调节奖励函数形态来进行修正…

第四步现在就得到了一个新的控制器了（新的策略15 强化学习算法 - 图175），使用这个新控制器来产生一个新的轨道:

15 强化学习算法 - 图176%5Crightarrow%20s%5E_1%2C%5Cpi_1(s%5E_1)%5Crightarrow%20%5Cquad%20%5Crightarrow%20s%5E*_T%0A#card=math&code=s%5E%2A_0%2C%5Cpi_0%28s%5E%2A_0%29%5Crightarrow%20s%5E%2A_1%2C%5Cpi_1%28s%5E%2A_1%29%5Crightarrow%20%5Cquad%20%5Crightarrow%20s%5E%2A_T%0A&height=17&width=194)

注意当我们生成了这个新的轨道的时候，使用真实的15 强化学习算法 - 图177而不是其线性估计来计算变换，这就意味着:

15 强化学习算法 - 图178%0A#card=math&code=s%5E%2A_%7Bt%2B1%7D%3DF%28s%5E%2A_t%EF%BC%8Ca%5E%2A_t%29%0A&height=19&width=100)

然后回到第二步，重复，直到达到某个停止条件(stopping criterion)。

15.4 线性二次高斯分布(Linear Quadratic Gaussian，缩写为LQG)

在现实是集中我们可能没办法观测到全部的状态15 强化学习算法 - 图179。例如一个自动驾驶的汽车只能够从一个相机获取一个图像，这就是一次观察了，而不是整个世界的全部状态。目前为止都是假设所有状态都可用。可是在现实世界的问题中并不见得总是如此，我们需要一个新工具来对这种情况进行建模：部分观测的马尔科夫决策过程(Partially Observable MDPs，缩写为POMDP)。

POMDP是一个带有了额外观察层的马尔科夫决策过程(MDP)。也就是说要加入一个新变量15 强化学习算法 - 图180，在给定的当前状态下这个15 强化学习算法 - 图181遵循某种条件分布:

15 强化学习算法 - 图182%0A#card=math&code=o_t%7Cs_t%5Csim%20O%28o%7Cs%29%0A&height=16&width=82)

最终，一个有限范围的部分观测的马尔科夫决策过程(finite-horizon POMDP)就是如下所示的一个元组(tuple):

15 强化学习算法 - 图183%0A#card=math&code=%28%5Cmathcal%7BS%7D%2C%5Cmathcal%7BO%7D%2C%5Cmathcal%7BA%7D%2CP_%7Bsa%7D%2CT%2CR%29%0A&height=16&width=111)

在这个框架下，整体的策略就是要在观测15 强化学习算法 - 图184的基础上，保持一个置信状态（belief state，对状态的分布）。 这样在PDMDP中的策略就是从置信状态到行为的映射。

在本节，我们队LQR进行扩展以适应新的环境。假设我们观测的是15 强化学习算法 - 图185，其中的15 强化学习算法 - 图186，且有:

15 强化学习算法 - 图187

上式中的15 强化学习算法 - 图188是一个压缩矩阵(compression matrix)，而15 强化学习算法 - 图189是传感器噪音（和15 强化学习算法 - 图190类似也是高斯分布的）。要注意这里的奖励函数15 强化学习算法 - 图191%7D#card=math&code=R%5E%7B%28t%29%7D&height=16&width=22)是左侧不变的，因为是关于状态（而不是观察）和行为的函数。另外，由于分布都是高斯分布，置信状态就也将是高斯分布的。在这样的新框架下，看看找最优策略的方法:

第一步首先计算可能装填（置信状态）的分布，以已有观察为基础。也就是说要计算下列分布的均值15 强化学习算法 - 图192以及协方差15 强化学习算法 - 图193:

15 强化学习算法 - 图194%0A#card=math&code=st%7Cy_1%20%2C%5Cdots%2C%20y_t%20%5Csim%20%5Cmathcal%7BN%7D%28s%7Bt%7Ct%7D%2C%5CSigma_%7Bt%7Ct%7D%29%0A&height=19&width=155)

为了进行时间效率高的计算，这里要用到卡尔曼滤波器算法(Kalman Filter algorithm)（阿波罗登月舱上就用了这个算法）。

第二步然后就有了分布了，接下来就用均值15 强化学习算法 - 图195来作为对15 强化学习算法 - 图196的最佳近似。

第三步然后设置行为15 强化学习算法 - 图197，其中的15 强化学习算法 - 图198来自正规线性二次调节算法(regular LQR algorithm)。

从直觉来理解，这样做为啥能管用呢？要注意到15 强化学习算法 - 图199是滴15 强化学习算法 - 图200的有噪音近似（等价于在LQR的基础上增加更多噪音），但我们已经证明过了LQR是独立于噪音的!

第一步就需要解释一下。这里会给出一个简单情境，其中在我们的方法里没有行为依赖性（但整体上这个案例遵循相同的思想）。设有:

15 强化学习算法 - 图201%5C%5C%0Ayt%20%20%26%3D%20C%5Ccdot%20s_t%2Bv_t%2C%5Cquad%20v_t%5Csim%20N(0%2C%5CSigma_y)%5C%5C%0A%5Cend%7Bcases%7D%0A#card=math&code=%5Cbegin%7Bcases%7D%0As%7Bt%2B1%7D%20%20%26%3D%20A%5Ccdot%20s_t%2Bw_t%2C%5Cquad%20w_t%5Csim%20N%280%2C%5CSigma_s%29%5C%5C%0Ay_t%20%20%26%3D%20C%5Ccdot%20s_t%2Bv_t%2C%5Cquad%20v_t%5Csim%20N%280%2C%5CSigma_y%29%5C%5C%0A%5Cend%7Bcases%7D%0A&height=36&width=230)

由于噪音是高斯分布的，可以很明显证明联合分布也是高斯分布:

15 强化学习算法 - 图202%20%5Cquad%5Ctext%7Bfor%20some%20%7D%20%5Cmu%2C%5CSigma%0A#card=math&code=%5Cbegin%7Bpmatrix%7D%0As_1%5C%5C%0A%5Cvdots%5C%5C%0As_t%5C%5C%0Ay_1%5C%5C%0A%5Cvdots%5C%5C%0Ay_t%0A%5Cend%7Bpmatrix%7D%20%5Csim%20%5Cmathcal%7BN%7D%28%5Cmu%EF%BC%8C%5CSigma%29%20%5Cquad%5Ctext%7Bfor%20some%20%7D%20%5Cmu%2C%5CSigma%0A&height=125&width=203)

然后利用高斯分布的边缘方程(参考因子分析(Factor Analysis)部分的讲义)，就得到了:

15 强化学习算法 - 图203%0A#card=math&code=st%7Cy_1%2C%5Cdots%EF%BC%8Cy_t%5Csim%20%5Cmathcal%7BN%7D%28s%7Bt%7Ct%7D%2C%5CSigma_%7Bt%7Ct%7D%29%0A&height=19&width=161)

可是这里使用这些方程计算边缘分布的参数需要很大的算力开销!因为这需要对规模为15 强化学习算法 - 图204的矩阵进行运算。还记得对一个矩阵求逆需要的运算时15 强化学习算法 - 图205#card=math&code=O%28t%5E3%29&height=18&width=32)吧，这要是在时间步骤数目上进行重复，就需要15 强化学习算法 - 图206#card=math&code=O%28t%5E4%29&height=18&width=32)的算力开销!

卡尔曼滤波器算法(Kalman filter algorithm) 提供了计算均值和方差的更好的方法，只用在时间15 强化学习算法 - 图207上以一个固定的时间(constant time) 来更新！卡尔曼滤波器算法有两个基础步骤。加入我们知道了分布15 强化学习算法 - 图208:

15 强化学习算法 - 图209%20%E8%AE%A1%E7%AE%97%7D%20%26%20s%7Bt%2B1%7D%7Cy_1%2C%5Cdots%2Cy_t%0A%5C%5C%0A%5Ctext%7B%E6%9B%B4%E6%96%B0%E6%AD%A5%E9%AA%A4(update%20step)%20%E8%AE%A1%E7%AE%97%7D%20%26%20s%7Bt%2B1%7D%7Cy1%2C%5Cdots%2Cy%7Bt%2B1%7D%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Ctext%7B%E9%A2%84%E6%B5%8B%E6%AD%A5%E9%AA%A4%28predict%20step%29%20%E8%AE%A1%E7%AE%97%7D%20%26%20s%7Bt%2B1%7D%7Cy_1%2C%5Cdots%2Cy_t%0A%5C%5C%0A%5Ctext%7B%E6%9B%B4%E6%96%B0%E6%AD%A5%E9%AA%A4%28update%20step%29%20%E8%AE%A1%E7%AE%97%7D%20%26%20s%7Bt%2B1%7D%7Cy1%2C%5Cdots%2Cy%7Bt%2B1%7D%0A%5Cend%7Baligned%7D%0A&height=41&width=257)

然后在时间步骤上迭代！预测和更新这两个步骤的结合就更新了我们的置信状态，也就是说整个过程大概类似:

15 强化学习算法 - 图210%5Cxrightarrow%7Bpredict%7D%20(s%7Bt%2B1%7D%7Cy_1%2C%5Cdots%2Cy_t)%0A%20%5Cxrightarrow%7Bupdate%7D%20(s%7Bt%2B1%7D%7Cy1%2C%5Cdots%2Cy%7Bt%2B1%7D)%5Cxrightarrow%7Bpredict%7D%5Cdots%0A#card=math&code=%28s%7Bt%7D%7Cy_1%2C%5Cdots%2Cy_t%29%5Cxrightarrow%7Bpredict%7D%20%28s%7Bt%2B1%7D%7Cy1%2C%5Cdots%2Cy_t%29%0A%20%5Cxrightarrow%7Bupdate%7D%20%28s%7Bt%2B1%7D%7Cy1%2C%5Cdots%2Cy%7Bt%2B1%7D%29%5Cxrightarrow%7Bpredict%7D%5Cdots%0A&height=24&width=425)

预测步骤 假如我们已知分布:

15 强化学习算法 - 图211%0A#card=math&code=s%7Bt%7D%7Cy_1%2C%5Cdots%2Cy_t%5Csim%20%5Cmathcal%7BN%7D%28s%7Bt%7Ct%7D%2C%5CSigma_%7Bt%7Ct%7D%29%0A&height=19&width=155)

然后在下一个状态上的分布也是一个高斯分布:

15 强化学习算法 - 图212%0A#card=math&code=s%7Bt%2B1%7D%7Cy_1%2C%5Cdots%2Cy_t%5Csim%20%5Cmathcal%7BN%7D%28s%7Bt%2B1%7Ct%7D%2C%5CSigma_%7Bt%2B1%7Ct%7D%29%0A&height=19&width=192)

其中有:

15 强化学习算法 - 图213

更新步骤 给定了15 强化学习算法 - 图214和15 强化学习算法 - 图215，则有:

15 强化学习算法 - 图216%0A#card=math&code=s%7Bt%2B1%7D%7Cy_1%2C%5Cdots%2Cy_t%5Csim%20%5Cmathcal%7BN%7D%28s%7Bt%2B1%7Ct%7D%2C%5CSigma_%7Bt%2B1%7Ct%7D%29%0A&height=19&width=192)

可以证明有:

15 强化学习算法 - 图217%0A#card=math&code=s%7Bt%2B1%7D%7Cy_1%2C%5Cdots%2Cy%7Bt%2B1%7D%5Csim%20%5Cmathcal%7BN%7D%28s%7Bt%2B1%7Ct%2B1%7D%2C%5CSigma%7Bt%2B1%7Ct%2B1%7D%29%0A&height=19&width=229)

其中有:

15 强化学习算法 - 图218%5C%5C%0A%5CSigma%7Bt%2B1%7Ct%2B1%7D%20%26%3D%5CSigma%7Bt%2B1%7Ct%7D-Kt%5Ccdot%20C%5Ccdot%20%5CSigma%7Bt%2B1%7Ct%7D%0A%5Cend%7Bcases%7D%0A#card=math&code=%5Cbegin%7Bcases%7D%0As%7Bt%2B1%7Ct%2B1%7D%26%3D%20s%7Bt%2B1%7Ct%7D%2BKt%28y%7Bt%2B1%7D-Cs%7Bt%2B1%7Ct%7D%29%5C%5C%0A%5CSigma%7Bt%2B1%7Ct%2B1%7D%20%26%3D%5CSigma%7Bt%2B1%7Ct%7D-K_t%5Ccdot%20C%5Ccdot%20%5CSigma%7Bt%2B1%7Ct%7D%0A%5Cend%7Bcases%7D%0A&height=37&width=240)

上式中的

15 强化学习算法 - 图219%5E%7B-1%7D%0A#card=math&code=Kt%3A%3D%20%5CSigma%7Bt%2B1%7Ct%7D%20C%5ET%20%28C%20%5CSigma_%7Bt%2B1%7Ct%7D%20C%5ET%20%2B%20%5CSigma_y%29%5E%7B-1%7D%0A&height=20&width=208)

这个矩阵15 强化学习算法 - 图220就叫做卡尔曼增益(Kalman gain)。

现在如果我们仔细看看方程就会发现根本不需要对时间步骤 15 强化学习算法 - 图221 有观测先验。更新步骤只依赖与前面的分布。综合到一起，这个算法最开始向前运行传递计算15 强化学习算法 - 图222（有时候可能值得是15 强化学习算法 - 图223）。然后就向后运行（进行LQR更新）来计算变量15 强化学习算法 - 图224了，最终就得到了最优策略15 强化学习算法 - 图225。