上一期的笔记是确定性问题的动态规划，忘记的小伙伴可以再复习一下：

0 写在前面的

上周我更新了第一篇关于强化学习与最优控制的笔记，整体反响还不错。我打算大约一周更新一篇文章。不得不说这本教材写得还真是蛮好的，推荐大家购买纸质版的（这个是影印版的，比英文原本要便宜不少），因为电子版的内容不是非常完整。

1 离散时间动态系统（随机性问题）

离散时间动态系统形式如下：

 (1.1)

其中  是时间索引，  表示时间步  系统的状态 也被称为状态变量（state variable），  表示时间步  的控制量或者决策变量 (control variable or decision variable)，一般来说  要满足一定的约束 表示为  ，  是随机变量，其概率分布为 

相比上一节讲过的确定性系统来说主要是增加了  这个随机变量，并且这个随机变量沿着时间是iid(独立同分布的)，也就是说  之间是iid的。

2 随机性问题和确定性问题的主要区别

那么采用动态规划来求解随机性问题和上节所讲的确定性问题有何不同呢？主要有两点不同：

其一，随机性问题是要求解的是最优的 policies 序列（在控制理论中被称为 反馈控制或者闭环控制），而确定性问题仅仅需要求解一个最优的值即可。

policies 序列定义如下  ，其中  ,  是一个映射，将  映射到  ，对于所有的  都成立。

也就是说在随机性问题里边，我们要找出的是一个决策的规则和法则，这个法则就是policy（在控制理论中就叫做control law），而并不是直接给出决策变量的值。那为什么在带有随机性的问题里边我们要找的是policy呢？而不能像之前确定性问题那样直接去找决策变量的值呢，而是要绕一个弯子呢？

答案就是因为整个系统有干扰（随机）因素的存在，我们就必须要利用当前系统的状态信息  来辅助我们进行决策。这个思想在控制理论中是一个非常非常经典和常用的思想。

我这里举个蒸馒头的例子来说明这个问题：在没有任何干扰一切的一切都非常完美的情况下，需要蒸十分钟馒头就熟了。那此时我们只需要设置一个定时器让炉子加热十分钟，十分钟后断掉，馒头就熟了。

但实际系统总是会有一些干扰存在的，例如蒸馒头的时候蒸汽把锅盖顶歪了，让锅盖没有盖好很多蒸汽漏了出来，如果还是按照十分钟来蒸，很可能馒头就还没有熟，又例如蒸馒头的过程中 火力突然比预想的变大或者变小了，那同样也会影响蒸馒头的时间。这些意外干扰是在蒸馒头的过程中产生的，并不能预先知晓，所以就可以看做是  。那遇到这些干扰因素我们又改如何解决呢？那在生活中的话 我们会采用反馈的思想来解决，那就是例如蒸了九分钟的时候，我们会来尝一下这个馒头蒸得怎么样。如果馒头熟了，就停止，如果没熟，就继续蒸，甚至我们还可以进一步根据馒头熟的程度来估计还需要蒸多长时间。

蒸了九分钟的时候 就尝一下馒头熟了没 从本质上来说就是去拿系统当前  的信息，通过  来辅助我们修正我们的决策。我们的决策在蒸馒头的例子中是一个 if-else的形式：如果馒头熟了，就停止，如果没熟，就继续蒸，其实这就是一个规则也就是我们说的policy，本质上也就是一个映射了，如下所示：

policy的精髓在于我们可以利用当前的系统信息  使得我们的决策可以动态的去应对干扰的发生，而不是把所有的决策在事先就完全决定好了，此后发生任何的干扰和噪音都一成不变了。如果没有干扰，没有噪音，整个动态系统非常非常的理想，那这么搞的意义就不大了。

熟悉控制理论的童鞋也大致会知道这个  可以是PID，也可以是LQR，说破大天去这些基本的思想都是相通的。需要记住一点就是，每个时刻都有一个policy，它们并不一定是相同的，因此我们实际上最终是要求一个policy的序列 

其二，随机性问题的目标函数是带有期望的，而确定性问题是没有期望的。

这一点很好理解了，有随机变量肯定就有期望了。若给定初始状态  和  ，则动态系统可以表示为

 (2.1)

则在  处的cost function为

 (2.2)

这里需要看清楚期望里边  是随机变量，  是随机变量，而  不是随机变量。那么我们通过求解如下优化问题，找到最优的policy 

 (2.3)

3 动态规划算法求解随机性有限时间问题

由此给出确定性有限时间问题的动态规划算法如下

对于  有

 (3.1)

对于  有

 (3.2)

若  是式（3.2）的解，则  是最优的policy。

算法部分和确定性问题其实差异不大，主要的区别在本文第2节已经介绍过了，所以我就不再把教科书的公式都抄过来了。关于动态规划算法求解确定性有限时间问题可以看上一篇笔记：

其余部分对照教材1.2节Stochastic Dynamic Programming去看都没有什么难度。

需要注意的是针对大多数问题而言，无论是随机还是确定性问题 ，想要精确计算出 都非常耗费时间。对于规模稍大点的问题，这几乎是不可能办到的事情。所以本书的后几章将围绕如何将  用  来近似，进而达到降低计算量的目的。

下一期笔记：