Skip to content
返回搜索结果

确定性动态规划 — 在参数已知情况下的精确序贯优化

提出者
Richard E. Bellman
年份
1957
类型
Exact sequential optimization algorithm
类别
Simulation / optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

确定性动态规划(DDP)是一种数学优化技术,它将多阶段决策问题分解为一系列更简单的子问题,并在所有系统参数——转移函数、成本和奖励——都确定已知时精确求解。它通过贝尔曼最优性原理保证了全局最优策略。

方法背后的直觉

设想规划一条穿过城市网络的最低成本路线,其中所有道路成本都预先已知。动态规划不是评估所有可能的完整路径,而是向后工作:在每个城市,它记录从该城市到达目的地的最低成本。一旦所有城市都被标记,向前追踪最优路径就变得微不足道。这种向后推理——贝尔曼最优性原理——是确定性动态规划的核心:最优路径的任何子路径本身也必须是最优的。

历史学

Richard Bellman 在其 1957 年普林斯顿专著中将动态规划形式化,推导出了支撑所有动态规划方法的最优性原理。确定性情况——其中转移和奖励是已知的——是原始公式。它源于 Bellman 战时的运筹学工作,并成为控制论、经济学和组合优化中的基础。后来 Bertsekas 在多卷书中扩展和系统化了该理论。

何时使用

当系统具有明确定义的序贯阶段、所有转移成本和结果都确定已知且最优性原理(最优子结构)适用时,使用确定性动态规划。它在库存管理、时间资源分配、最短路径路由以及具有固定参数的生产调度方面表现出色。当参数不确定或随机时,请勿使用它——而应切换到随机动态规划。当状态空间非常大或连续且缺乏解析结构时,也应避免使用 DDP,因为维度灾难使其在计算上不可行。它不适用于没有序贯或递归结构的问题。

局限与注意事项

  • 严重受维度灾难影响:计算和内存需求随状态变量数量呈指数增长。
  • 需要对转移函数和奖励结构有完整且精确的了解;任何参数不确定性都会使确定性模型失效。
  • 对连续状态或动作空间进行离散化会引入近似误差,并可能错过真正的最优解。
  • 假设马尔可夫结构——每个阶段的最优决策仅取决于当前状态,而不取决于达到该状态的历史。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 当问题满足最优性原理且参数已知时,保证全局最优解。
  • 自然地处理多阶段序贯决策,这些决策作为一个大型优化问题将难以处理。
  • 一旦计算出值函数,所有状态的最优决策即可同时获得,从而能够跨起始条件进行敏感性分析。
  • 适用于离散和连续状态-动作空间(通过适当的离散化或解析处理)。
  • 概念上透明:向后归纳过程易于审计和逐步验证。

应用

  • 在规划范围有限且需求计划已知的情况下,最优库存补充策略。
  • 最短路径和网络路由问题(例如,Dijkstra 算法是动态规划的一个特例)。
  • 在确定性需求和产能约束下,制造业的生产调度和批量定价。
  • 经济学中确定性条件下的资源开采和资本投资规划。
  • 序列比对和生物信息学(例如,Needleman-Wunsch 算法)。
  • 具有已知成本和退化函数的设备更换和维护计划。

使用方式

使用方式

1

定义优化目标、规划范围(有限或无限)以及决策序列。确定构成阶段、状态、动作、即时奖励或成本 r(s, a) 以及确定性转移函数 s' = f(s, a) 的要素,该函数将状态-动作对确定性地映射到下一个状态。

2

枚举或参数化所有可行状态 S 和每个状态的所有允许动作 A(s)。对于离散问题,这会产生一个有限的状态-动作表;对于连续问题,则使用离散化或解析解形式。内存需求随此空间的大小而扩展——这是关键的计算瓶颈。

3

编写贝尔曼最优性方程:V_t(s) = max_{a ∈ A(s)} [r(s,a) + V_{t+1}(f(s,a))]。对于有限范围问题,用终端值初始化 V_T(s) 并从阶段 T-1 向后递归到阶段 0。对于无限范围问题,迭代值更新直到收敛(值迭代)。

公式
V_t(s) = \max_{a \in A(s)} \bigl[ r(s, a) + V_{t+1}(f(s, a)) \bigr]
4

分阶段从最终周期到初始周期(向后归纳)求解递归。在每个阶段,每个状态都被分配其最优值,并记录实现该值的动作。这保证了子问题解在确定性转移模型下是一致的且全局最优的。

5

通过前向传递构建最优策略:从初始状态 s_0 开始,在每个阶段应用 π*(s) = argmax_a [r(s,a) + V*(f(s,a))],遵循记录的最优动作。由此产生的决策序列是在已知固定参数下的全局最优计划。

公式
\pi^*(s) = \arg\max_{a \in A(s)} \bigl[ r(s, a) + V^*(f(s, a)) \bigr]

常见陷阱

  • 将确定性动态规划与随机动态规划混淆:如果任何系统参数不确定,确定性模型的结果将过于乐观,并可能产生误导。
  • 选择过于粗糙(丢失最优性)或过于精细(导致状态空间爆炸)的状态表示;仔细的状态空间设计至关重要。
  • 忽略边界条件:不正确的终端阶段值 V_T(s) 会将错误传播到整个向后递归。
  • 将动态规划应用于缺乏最优子结构的问题,其中局部最优性不能保证全局最优性。
  • 假设有限范围,而问题实际上是无限的,反之亦然,导致不恰当的递归公式。

常见问题

确定性动态规划与随机动态规划有何不同?

在确定性动态规划中,下一个状态 s' = f(s, a) 是一个已知函数——没有随机性。随机动态规划用概率分布 P(s'|s, a) 替换 f 并最大化期望值。确定性动态规划更简单且精确;随机动态规划适用于结果不确定的情况。

什么是维度灾难,为什么它很重要?

Bellman 创造了这个术语来描述状态空间如何随着状态变量数量呈指数增长。例如,10 个状态变量,每个变量有 100 个离散级别,会产生 10^20 个状态——远远超出任何计算机的内存。这使得精确动态规划对于高维问题不可行,从而促使了近似动态规划或强化学习等近似方法。

何时应使用线性规划而不是动态规划?

当问题可以表示为具有线性约束和目标的单周期优化时,请使用线性规划。当决策在多个阶段展开,并且每个阶段的最优动作取决于系统在该时间的状态时,首选动态规划。

确定性动态规划是否等同于博弈论中的向后归纳?

它们共享相同的递归逻辑——从末尾向后求解——但博弈论中的向后归纳涉及多个玩家和策略互动。确定性动态规划是一个单一代理人的优化问题,没有策略对手。

确定性动态规划能否处理连续状态和动作空间?

是的,当存在解析解(例如,线性二次问题)或值函数具有已知的函数形式时。否则,连续空间必须离散化,这会引入近似误差并大大增加计算负担。

相关方法

参考文献

  1. Bellman, R. E. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.

    ISBN:9780691079516
    已复制。
  2. Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control (4th ed., Vol. 1). Athena Scientific, Belmont, MA.

    打开出版物文献
    已复制。