第3章 动态规划

为了准确地估算一个状态的价值v(s)，或者在一个状态下的某个动作的价值q(s,a)，人们还是想了不少办法的。在第2章中，讲完马尔可夫决策过程之后，我直接介绍了如何用策略迭代的方法来实现这个目标。

在从这一章开始的连续三章中，会分别介绍一种用于准确估算一个状态的价值vπ(s)或者在一个状态下做某个动作的价值qπ(s,a)的思维方法。因为在所有基于状态估值的方法中，只要能够计算每个状态下每个动作的估值，就可以得到一个完整的策略描述。虽然这三种思维方法是在同一个环境中通过不断做动作来收集S→A→R→S′ 的，但处理思路略有不同，因此，它们各自的优缺点也不尽相同。在这一章中，我们先来了解一下动态规划（Dynamic Programming, DP），也有人称它为值迭代（Value Iteration）。

动态规划是一门相对独立的学科，是运筹学的一个分支学科。运筹学本身的学科体系就很复杂，而且在不断地完善和壮大，包括线性规划、非线性规划、整数规划、组合规划、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、博弈论、搜索论、模拟等分支。动态规划关注的是如何用数学方法求解一个决策过程最优化的问题。20世纪50年代，美国著名的数学家理查德·贝尔曼提出了针对多阶段决策过程问题优化的思路，并创立了解决这类过程优化问题的新方法——动态规划。1957年，理查德·贝尔曼出版了Dynamic Programming一书，堪称该领域的开山之作。

3.1 状态估值

说到动态规划，我觉得，没必要纠结它“不动态”时的样子。简单地说，动态规划是一种建模和解题的思路。在这种思路的指导下，原始的问题（大的、复杂的问题）会被分解成多个可解的且结果可保存的子问题。一旦所有的子问题获解，原始的问题就获解了。

解决这个问题的思路，还是要从第2章中多次提及的表达式v(s)和q(s,a)开始说起。因为v(s)可以用q(s,a)表示，q(s,a)也可以用v(s)表示，所以，我们尝试用q(s,a)来代换v(s)，写出表达式

这种视角是合理的，并给出了优化方案。现在，反过来，把q(s,a)表示成v(s)，会得到什么呢？应该会得到表达式

第2章中机器人根据天气决定是否打伞的例子，也可以写成更为广义的由字母和数字角标组成的表达式。

对于一个状态的估值v(s)来说，可以寻求一种类似表达式qπ(s,a)的思路，如图3-1所示。

为了加C:\Users\ADMINI~1\AppData\Local\Temp\pdf2stream\figure_0052_0003.jpg深印象，这次我们用字母和数字角标来表示。当我们看到一个状态空间是一棵较为完整的树的时候——准确地说，是一棵完整的树的一个枝杈——在状态s下，动作空间a中有a1和a2两个动作，在做a1和a2这两个动作的时候，会分别转移到s′1、s′2及s′3、s′4。那么，根据状态估值的定义，v(s)应该等于什么呢？应该是某种加权平均值。什么是加权平均值？就是这4个状态各自的概率和这4个状态各自估值的积的平均值。打个比方，我有10000元，用其中的10% 的投资了一个收益率为5% 的理财产品，用其中的40% 投资了一个收益率为10% 的理财产品，分别用其中的25% 投资了收益率为8% 和6% 的理财产品，现在要评价我的投资盈利金额是多少。计算这个组合策略的收益：

.这个投资组合的收益率为8%。

这个投资组合的收益率为8%。

在这棵树上，计算过程几乎是一样的。前面这个公式的一个具象一些的写法是这样的：

公式写出来虽然简洁，但可读性降低了。在这里详细解释一下各个部分。vπ(s)是顶端节点的价值估值，也就是这个投资组合的最终收益。∑π(a|s)a∈A表示按照策略π(a|s)，输入s后输出动作a的概率，把这个概率和部分相乘，然后做求和运算。后面这个部分的意义是，在π(a|s)做动作时可以立刻得到的奖励值，加一个折扣系数γ与的积，也就是转移到其中一个状态s′的概率和该状态估值v(s′)的积——相当于用投资金额乘以相应的理财产品的收益率。整个公式的计算过程是一个二重嵌套的循环：遍历这棵树上的每一个分支，不管是1个动作，还是100个动作，不管是有100个不同的状态s′，还是有10000个不同的状态s′，总而言之，相当于一个加权平均的过程。平均计算在这个公式里面没有直接体现，因为它已经包含在概率计算里面了。

这样一来，求解vπ(s)就依赖于 π(a|s)、、′ 和v(s′)的准确值了。这意味着什么呢？聪明的读者朋友仔细想一下，很快就能得出结论。在这里，以下两件事情是明确的。

· 如果每一层都能够通过这样的方式逐级估算，这棵树不管有多高，都可以一层一层向上估算，直到把顶层的任何一个节点的vπ(s)估值都计算准确——大不了多花些时间，方法肯定是可行的。

· 毫无疑问，这个方法严重依赖Model（至少应该是一个满足MDP的对象）。如果π(a|s)、、′ 和v(s′)里面有任何一个不能直接使用这个方法，就没有办法进行计算。所以，这种方法的局限性很大，对条件的要求也比较苛刻。

这种方法的形式非常简单，也很容易理解，但是对条件的要求比较苛刻。也就是说，很多不满足MDP的模型根本不能使用这种方法。可能有人要说：“我可以让机器人在环境里不断自己尝试啊。尝试得足够多了，是不是就能通过统计得到、′和v(s′)了？而且，对策略π(a|s)，也可以人为确定，或者随机做一个策略，通过动态规划来评估这个策略在某个状态下的价值啊。”这个方法不能说是错的，不过，它不符合动态规划的使用原则。而且，一旦使用这种方法，那就不是动态规划了，而是另一种方法——先卖个关子，在后面会提到。

3.2 策略优化

使用动态规划（或者说值迭代）的方法，怎么做优化呢？方法也是非常简单的，有下面3个步骤。

①以一种策略π开始在环境中做动作，这个时候，就会得到相应的vπ(s)和qπ(s,a)。这个步骤与策略迭代的第一步没什么区别。

②因为在时序上属于树遍历问题，所以，要想准确估算树上部的状态节点的值，就要先估算树下部的状态节点的值。树下部的状态节点的值容易估算吗？节点位置越靠下，邻近时间终点的位置越近，计算的代价就越小（节点位置越靠上，就表示距离开始的时间越长，在计算估值的时候要参考的时间就更长一些）。从下向上，逐层估算vπ(s)，用类似递归的方式向上传递。表达式写出来是这样的：

表示，一个由动作a引发的“现世报”的奖励值加上它达到各个状态的概率和各个状态的估值——仍然可以通过本章开头提到的那个投资组合的例子来理解。

的意思是，在众多不同的a里，只取那个能保证后面的外层括号里的表达式的值最大的a。也就是说，如果有一个动作“力压群雄”，比其他的动作都要好，那么，上一层的s的估值，就可以考虑只做这一个动作，并以这个前提进行迭代更新。道理很容易理解：如果知道有一个动作比其他动作都要好，为什么还要做其他动作？这就是这个表达式的基本含义。

③持续以这个逻辑进行更新，vπ(s)就会不断地变化。直到最后，vπ(s)基本上不再变化了，就停止更新。此时的策略，就是每次都选择能够导致状态迁移到最有价值状态的动作a。

3.3 本章小结

在本章中，我们一起认识了动态规划。可以看出，这种方法的局限性还是非常明显的。我们已经反复强调，动态规划要求研究对象满足MDP，因此，在实际工作中，这种方法的应用并不广泛，我在编写程序的时候，一般也不使用动态规划的方法计算估值。

作为一种非常典型的针对状态估值进行计算的方法，动态规划的思路是非常容易理解的。所以，将动态规划作为状态估值和策略优化的入门方法来学习，也是非常合适的。通过类似于递归求解的方式，逐层估算，如果每一层的估算都是准确的，就能迭代向上传递，把上面各层的各个状态的值估算准确。只要按照这个规则，就能把每个状态的值估算准确——这是一个有“远见”的估值。因此，用简单的树广度优先遍历的方式进行查找（只查找一层，工作量不大），很快就能够确定一个动作了。

如果你仍然觉得这些内容不够生动，那就来看一个形象但不够恰当的比喻吧。现在，我们手里有一个课题：研究孩子在某一时刻吃什么食物，能使他在小学阶段的各种评测中得到更高的分数。例如，在孩子即将入学的时候，他吃什么食物，会对他未来的发展产生影响？作为家长，如果想以科学的态度来解答这个问题，就要研究一下，入学的下一时刻会有哪些状态，以及在这些状态下孩子吃什么才好。因学校而异，在入学的下一时刻，有30% 的可能是上文化课，有50% 的可能是上体育课，有20% 的可能是参加义务劳动。开个玩笑，就算只能吃馒头，也可以选择吃1到10个不等。

· 如果只吃1个馒头，很快就饿了。结果是，在这三种课程安排里，都只能得到0分。

· 如果吃5个馒头：上文化课，很快就饿了，只能得60分，不过比只吃1个馒头强；上体育课，能跑能跳，能得90分；参加义务劳动，力气十足，能得90分。这样一来，这一时刻的瞬时得分的数学期望值是60×0.3+90×0.5+90×0.2=81。

· 如果吃10个馒头：虽然很撑，但是上文化课坚持的时间长一些，学到的东西也多一些，能得70分；上体育课，可行性严重降低（此时如果做剧烈运动，容易导致阑尾炎或者其他疾病），只能得20分；参加义务劳动（不是剧烈运动），不仅可以完成，还比吃5个馒头持续的时间长，得到100分。这样一来，这一时刻的瞬时得分的数学期望值就是70×0.3+20×0.5+100×0.2=51。

根据下一刻的课程安排概率（我们无法预测具体的课程安排），仍然可以得到吃下去的食物与得分的值，从而确定在某种饮食策略下，这一时刻、下一时刻、下下一时刻的得分的数学期望值，据此反推在入学的时候吃什么才好。

如果动态规划的方法不适用，该怎么办呢？在第4章中我们就来聊聊，对于不满足 MDP的对象，应该用什么方法来做状态估值。