优化|什么是动态规划（Dynamic Programming）？

↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』原创

作者：覃含章

编者按

本文讲述了关于动态规划的抽象模型（Abstract Dynamic Programming Models），来源于Dimitri Bertsekas教授（MIT）。并个人向地探讨了当下研究动态规划的意义。

本文简单讲讲关于动态规划的抽象模型，来源于搞了动态规划几十年（也算是理论奠基人之一了）的Dimitri Bertsekas，他所称之为Abstract Dynamic Programming Models。在文章最后，我基于个人的观点谈谈学习研究动态规划的意义。

一、定义：两个集合 ;一个映射；两个算子;

二、抽象动态规划模型

三、两个重要性质：单调性与压缩性

本节我们介绍常见动态规划模型需要满足的两个重要性质，也即前一段末尾所说的“合理的条件”。只有满足了这两个条件，我们的动态规划模型才可以化为上述唯一确定的基于Bellman's equation的不动点求解问题。

不过这个压缩性的话可能就不如前面那个单调性，没什么特别直观的道理。然而如果你认同“折旧”（discount）的会计概念，比如未来的单位成本相比今天的单位成本要按照日期以固定比例 α 打个折扣 --- 放到我们的模型来说就是在从时间 k 到 k+1 的过程当中我们产生的额外成本都要乘以一个属于0,1之间的系数 α ，那么容易验证在这种情况下我们的模型一般就会满足这里的压缩性了。

好那么有没有什么直观的解释为什么我们的动态规划模型最好要满足这两个性质呢？

回忆：Bellman's equation的本质便是寻找 T 的不动点。而上图左，我们的 T 虽然单调但并不具有压缩性，因此实际上存在不止一个不动点（蓝线与黑虚线的交点）。相比之下，上图右的 T 既单调又有压缩性，我们便很容易知道这个时候Bellman's equation有唯一的不动点。因此，可以认为问题的性质就要好很多了。

四、马尔可夫决策问题（Markov Decision Problem）

五、动态规划的意义

动态规划是非常强大的建模工具。基本上，一个多阶段的决策问题，如果你无法把他至少写成一个动态规划模型，那很可能你也无法找到办法求解它。

比如在运营管理界，所谓的动态库存控制问题就是一个十分经典的动态规划问题。而在物流运输界，作为核心问题之一的最短路径问题也是一个经典的动态规划问题。事实上，任何一个有限状态空间的MDP问题都可以写成最短路问题，反之亦然（不过本回答不再讨论这些抽象概念之间的联系了，打住打住）。

作为强大建模能力的代价便是，往往你很容易写出各种眼花缭乱的动态规划递推，但是可能花了很久也找不到一个“高效”的算法求解之。这是因为在我看来，动态规划是一种数学规划的建模思想，可以对各种各样的多阶段决策问题进行建模，但本身却只蕴含了一个和暴力枚举差不多的基本算法。尤其在决策空间维度很大时，动态规划算法会遭受著名的维数诅咒（curse of dimensionality），即算法求解时间随着问题规模指数级增长。

因此为了真正求解复杂的动态规划问题，我们实际上只能近似求解，这也是所谓的近似动态规划。这几年，伴随着机器学习的热潮，数据驱动的近似动态规划也渐渐再度被人熟悉，尤其是其中的一类近似算法，所谓的强化学习（reinforcement learning）算法。当然，一些CS背景的同学，可能会觉得RL和动态规划已经不是一类问题了，这里我们也不多展开了。

总之，作为研究领域动态规划已经存在了超过半个世纪。在目前的当下又受到了一波关注：而它的研究难点就在于作为泛用的建模工具，针对高维问题的算法设计和求解。

参考文献

Bertsekas, Dimitri P. Abstract dynamic programming. Belmont, MA: Athena Scientific, 2013.

相关文章推荐

现代科学的研究越来越强调学科之间的交叉，然而学科交叉不可避免的产生着很大的壁垒。Richard Bellman也曾经面临这样的问题，本文详细介绍了他如何通过起一个好名字来使动态规划的研究被广泛接受。

点击蓝字标题，即可阅读《【学界】论名字的重要性之Bellman动态规划的命名》

其他推荐

【学界】0-1背包问题的动态规划算法

主编推荐 | 深度学习和强化学习在组合优化方面有哪些应用？

【优化】在线学习(MAB)与强化学习(RL)入门系列

招聘信息：

【优化】版块目前招募副主编，要求：