动态规划的故事（2022）

# 动态规划的故事 来源：https://iagoleal.com/posts/dynamic-programming/ 如果我告诉你，一些最常用的算法——比如在图中寻找最短路径、训练神经网络时计算梯度、以及解析上下文无关文法——本质上都是同一个原理的实现，你会怎么想？这个原理叫做*动态规划*，它是数学中那种简单的原理却能引发跨越众多领域的深刻结论的例子之一。事实上，我们甚至可以在第一段就引用理查德·贝尔曼（动态规划的创立者）的原话来总结这个思想： > 一个最优策略具有这样的性质：无论初始状态和初始决策是什么，其余的决策必须针对由第一个决策所产生的状态构成一个最优策略。 我必须承认，尽管在不同情境下遇到过动态规划，我还是花了好一段时间才最终“恍然大悟”，意识到它们其实是同一回事。在学习算法与数据结构时，它是一种基于记忆化的技术，通过先解决较容易的子问题并存储结果供以后使用，从而加速某些算法。后来在工作中，我主要处理大量用于长期调度问题的线性规划。1 (https://iagoleal.com/posts/dynamic-programming/#fn1)我们使用的主要算法叫做*随机对偶动态规划*，起初它看起来并不太像算法课上的那种编程技术。最后，基于模型的强化学习的主要方法之一又被称为动态规划，而它看起来也不太像其他那些实例。 那么，这到底是怎么回事？难道大家都只是因为动态规划这个名字很酷，才把自己的算法叫作动态规划吗？2 (https://iagoleal.com/posts/dynamic-programming/#fn2) 其实，从规划火箭的轨迹到 TeX 的自动换行，所有这些实例背后确实有一些共同的原理。而且这个列表还在不断延伸 (https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms_that_use_dynamic_programming)。 我想邀请你踏上一段跨越数学诸多领域的旅程。我们将从自动机一直到最优控制，途中经过马尔可夫链、动力系统、线性规划甚至度量空间。请坐好，享受这段旅程！ ## 关于决策与状态机 在深入讨论动态规划本身之前，我们首先要建立一些概念。毕竟，在学习解决问题的方法之前，先知道你想解决哪些问题总是最好的，对吧？ 作为动机，让我们从一个我非常喜欢的东西开始：老式平台游戏。在我们这个显然与某个意大利水管工无关的虚构游戏中，角色默认站立不动、无所事事。但通过按动手柄上的按钮，玩家可以命令角色做一些事情：射击、跳跃或行走。当然，这些动作各自会触发屏幕上的相应动画。以最经典的《生化危机》风格，这款游戏只允许角色在站立状态下射击，并且强制你在跳跃后必须先恢复站立状态才能执行任何其他动作。可以把这想象成落地后恢复平衡所需的时间。这种描述用文字来看似乎过于复杂，幸运的是，计算机科学系的友善人士已经发明了能很好地展示这些转换的图示。 我们上面的建模是一种叫做*状态机*（或者如果你喜欢希腊词的话，叫*自动机*）的实例。角色可能处于 4 种状态，而在每种状态下都有一组可用的动作，这些动作会使该状态发生转换。更抽象地说，自动机是一个系统，它可以处于多个*状态* s \in \mathcal{S} 之一，而在每个状态下，你可以从一组*动作* a \in \mathcal{A}(s) 中进行选择。每当你采取一个动作时，系统会根据一个*转移函数* T : (s : \mathcal{S}) \times \mathcal{A}(s) \to \mathcal{S}. 改变到一个新状态。 不幸的是，生活从来不会提供免费的午餐，一般来说，当在状态 s 下采取动作 a 时，需要支付一定的*成本*，这可以恰当地建模为另一个函数 c : (s : \mathcal{S}) \times \mathcal{A}(s) \to \mathbb{R}. 根据情境不同，这可以是一个真实的货币成本（在经济情境中）、某种总距离或经过的时间（用于规划），甚至可以是一个表示奖励的负成本。 ### 决策的动力学 迭代转移 T 为我们的系统建立了一种动力学：从初始状态 s_0 开始，并采取一系列动作 \{a_t\}，我们在状态空间上生成一条轨迹。 s_{t+1} = T(s_t, a_t). 从这个角度来看，我们的状态机被称为*可控动力系统*或*决策过程*，这又是几个值得记住的酷炫名字。 可以说，一个状态封装了你在选择动作时所需知道的关于系统的一切，无论之前的历史或时间步如何。事实上，如果任何其他事物影响你的选择，你可以不失一般性地将该过程建模为一个更大的自动机，其中状态也携带这些额外信息。因此，控制一个动态系统就相当于为每个状态选择一个有效的动作，即一个函数 \pi : (s : \mathcal{S}) \to \mathcal{A}(s). 在文献中，这被称为*策略*，类比于政府采取行动来控制国家的状态。 从状态 s_0 开始并遵循策略 \pi，会生成一个无需再选择控制的确定性动力系统： s_{t+1} = T(s_t, \pi(s_t)). 反过来，这个动力学在每个时间步都会产生一个成本 c(s_t, \pi(s_t))。我们可以把 \pi 的总成本定义为这些成本之和，但还有一个额外的细节需要注意。假设出于某种原因，你手头拮据，不得不借钱来付账。在这种艰难的条件下，你更愿意今天还钱还是明年再还？ 有时存在通货膨胀或利息等因素，使得未来成本的真实价值不同于其名义价值。这促使我们引入一个依赖于问题的*折扣因子* \gamma \in [0, 1]，它表示成本随时间而贬值的程度。遵循某个策略 \pi 的总成本，是我们遵循它所产生的所有经过适当折扣的成本的累计和。我们将与 \pi 相关联的*价值函数* v^\pi : \mathcal{S} \to \mathbb{R} 定义为从给定状态出发的总成本： \begin{array}{rl} v^\pi(s) = & c(s_0, \pi(s_0)) + \gamma c(s_1, \pi(s_1)) + \gamma^2 c(s_2, \pi(s_2)) + \ldots \\ \textrm{其中} & s_0 = s, \\ & s_{t+1} = T(s_t, \pi(s_t)), \\ \end{array} 除了实际解释之外，折扣因子 \gamma 在分析角度也扮演着重要角色。如果 |\gamma| < 1 且成本一致有界（例如在有限动作空间的情况下），我们可以保证定义 v^\pi 的级数对于任何动作选择和初始状态都收敛。也就是说，假设存在 M > 0 使得 \forall s \in \mathcal{S}, a \in \mathcal{A}(s),\, |c(s, a)| \le M. 这会将总成本限制在一个不会爆炸的几何级数内， \sum\limits_{t=0}^\infty \gamma^{t}|c(s_t, a_t)| \le \sum\limits_{t=0}^\infty \gamma^{t} M \le \frac{M}{1 - \gamma}, 从而保证价值函数是良定义的。 ### 最优决策 存在多种可能的行动方案，这促使我们思考哪一个是最好的。当编程让机器人逃离迷宫时，你希望它花费最少的时间；当控制飞船飞向月球时，重要的是保证它消耗最少的燃料；当在酒吧打架时，你想在受到最少伤害的同时击倒对手。最重要的是，最好的策略是在*所有时间*内成本最小的策略——既要考虑当下，也要考虑未来的后果。例如，有时某个策略在第一个状态上成本较高，但总体上却更好，因为它让我们进入一个更有利的状态。因此，我们的问题可以自然地表述为寻找*最优策略*： > 从状态 s 出发，找到一个策略 \pi，使得随时间的总成本最小。 或者等价地用数学语言表示： \begin{array}{rl} \min\limits_\pi v^\pi(s) = \min\limits_{a_t} & \sum\limits_{t=0}^\infty \gamma^{t}c(s_t, a_t) \\ \textrm{s.t.} & s_0 = s, \\ & s_{t+1} = T(s_t, a_t), \\ & a_t \in \mathcal{A}(s_t). \end{array} 现在，这可能看起来是一个又大又吓人的优化问题，但实际上它包含了很多我们可以利用的结构。这就是下一节的主题。不过，在继续之前，我们先稍微岔开一下，看看如何在这个决策框架中表述一些经典问题。 #### 示例：图中的最短路径 假设你在家乡，刚刚收到一位朋友发来的消息，告诉你库斯科（秘鲁）现在有唱歌的羊驼。这让你既感到怀疑又好奇，于是你跨上心爱的自行车，踏上了前往库斯科的路。不幸的是，没有直接的自行车道连接你的家和库斯科，这意味着你必须找到一条经过其他城市的路线。此外，羊驼有可能随时停止唱歌，并恢复它们在山间吃草的一贯行为。这促使你决定走一条前往库斯科的最短可能路径。 上述描述正是图中最短路径问题的一个实例。在其中，我们用一个图节点表示每个城市，将两个城市之间的直接路线表示为一条加权边，权重为距离。从家到库斯科，就相当于找到这两个节点之间总距离最小的路径。 从图描述到决策过程的转换非常直接。 - **状态**：图中的节点。 - 状态 s 下的**动作**：从 s 到另一个节点的边。 - **转移**：同一条边上的另一端节点。也就是说，给定一条边 s \to s'，T(s, s \to s') = s'。 - **成本**：c(s, a) 是边 a 的权重——即通过这条边所花费的时间。 寻找从 s 到 z 的最短路径，等同于将初始状态设为 s，并使 z 成为我们动力学中的终止状态。 好了，终于到了开始优化这些决策问题的时候了。最简单的想法是穷举搜索所有动作的空间，试图找到最佳解决方案。请注意，即使对于有限状态和有限时域，这也可能是极其昂贵的，因为可能的候选方案会随着时间步数呈指数增长。任何实用的方法都必须考虑到这类问题如何自然地分解为各个独立的阶段。 我们的方法将涉及著名的*贝尔曼最优性原理*，它是动态规划的基石。引用理查德·E·贝尔曼3 (https://iagoleal.com/posts/dynamic-programming/#fn3) 自己的话，它是这样说的： > 一个最优策略具有这样的性质：无论初始状态和初始决策是什么，其余的决策必须针对由第一个决策所产生的状态构成一个最优策略。 好，这是什么意思？最优性原理告诉我们，为了计算一个最优策略，我们应该把这个采取动作并计算成本的迭代过程变成一个递归过程。也就是说，在初始状态 s 下采取动作 a，会将我们带入一个新状态 s' = T(s, a)，而在这里我们再次面临同样的问题：寻找一个最优策略，只不过这次是从 s' 出发。让我们看看如何利用这个想法。 还记得我们把价值函数 v^\pi 定义为在给定状态下遵循策略 \pi 的总成本。让我们把*最优价值函数* v^\star 定义为从某个状态 s 出发时选择最佳行动方案的总成本。 \begin{array}{rl} v^\star(s) = \min\limits_{a_t} & \sum\limits_{t=0}^\infty \gamma^{t}c(s_t, a_t) \\ \textrm{s.t.} & s_0 = s, \\ & s_{t+1} = T(s_t, a_t), \\ & a_t \in \mathcal{A}(s_t). \end{array} 注意上面的优化问题中，初始状态只用于选择第一个动作。后面的动作并不直接依赖它，而是依赖它带来的后果。这意味着我们可以把问题分成两部分：计算一个只依赖初始状态的*即时成本*，以及计算一个依赖所有后续状态的*未来成本*。 \begin{array}{rl} v^\star(s) = \min\limits_{a,a_t} & \{c(s, a)\} + \left( \begin{array}{rl} \min\limits_{a_t} & \sum\limits_{t=1}^\infty \gamma^{t}c(s_t, a_t) \\ \textrm{s.t.} & s_1 = s', \\ & s_{t+1} = T(s_t, a_t), \\ & a_t \in \mathcal{A}(s_t) \end{array} \right) \\ \textrm{s.t.} & s' = T(s, a), \\ & a \in \mathcal{A}(s). \end{array} 这里面已经出现了一些递归结构！还缺少的，就是注意到由于未来成本中的求和从 t = 1 开始，我们可以提取出 \gamma。通过重命名 l = t - 1，我们得到 \sum\limits_{t=2}^\infty \gamma^{t-1}c(s_t, a_t) = \gamma \sum\limits_{t=2}^\infty \gamma^{t-2}c(s_t, a_t) = \gamma \sum\limits_{l=1}^\infty \gamma^{l-1}c(s_l, a_l), 并将其应用到 v^\star 的表达式中， \begin{array}{rl} v^\star(s) = \min\limits_{a} & c(s, a) + \gamma\left( \begin{array}{rl} \min\limits_{a_l} & \sum\limits_{l=0}^\infty \gamma^{l}c(s_l, a_l) \\ \textrm{s.t.} & s_0 = s', \\ & s_{l+1} = T(s_l, a_l), \\ & a_l \in \mathcal{A}(s_l) \end{array} \right) \\ \textrm{s.t.} & s' = T(s, a), \\ & a \in \mathcal{A}(s). \end{array} 虽然这是一个很长的表达式，但应该很容易看出，未来成本的表达式*恰好*就是从 s' = T(s, a) 出发启动动力学的最优价值 v^\star(s')。这样，最优性原理就在数学上表达为一个递归方程，最优策略的价值必须满足该方程。 \boxed{ \begin{array}{rl} v^\star(s) = \min\limits_{a} & c(s, a) + \gamma v^\star(s') \\ \textrm{s.t.} & s' = T(s, a), \\ & a \in \mathcal{A}(s). \end{array} } 这被称为*贝尔曼方程*，而所有动态规划都是求解该方程的方法。更进一步：我们可以把贝尔曼方程看作决策问题的递归规格说明，而把动态规划看作任何针对特定问题、用来求解该方程的实现。 ### 存在性、唯一性与不动点 现在是时候更深入地进入分析了。每当数学家看到像贝尔曼方程这样的递归关系时，他们会立刻开始问这类问题：我们对 v^\star 有什么保证？我能相信它是唯一的吗？它甚至存在吗？当然，我们数学家可能看起来有点过于焦虑，问这么多问题，但这些担心是有充分理由的。除了保证一切正常运转之外，在这种情况下证明解的存在性还教会我们如何构造它！所以要留心听讲，因为在下一节中，我们将把这里的定理改造成求解贝尔曼方程的算法。 递归与不动点有着深刻的关系。让我