动态规划

概述

Bellman 于 1957 年提出最优性原理和动态规划方法，将多阶段决策问题分解为一系列简单子问题，通过值函数的递推关系（Bellman 方程）求解最优策略——这一框架后来成为强化学习的数学基石。

关键内容

1. 历史背景：1950 年代冷战期间，RAND 公司作为美国空军智库聚集顶尖数学家解决军事战略问题。Bellman 1952 年加入 RAND，开始系统发展动态规划理论。

2. 最优性原理：一个最优策略具有这样的性质——无论初始状态和初始决策如何，其余决策必须构成关于由第一个决策所产生的状态的最优策略。

3. Bellman 方程：V(s) = max_a [R(s,a) + γ·V(s')]，将复杂多阶段决策分解为递归子问题。值迭代和策略迭代是两种基本求解算法。

4. 维度灾难：Bellman 首次指出状态空间维度增长导致计算复杂度指数爆炸的问题，这一挑战至今仍是强化学习和最优控制的核心难题。

5. 命名趣闻："动态规划"名称是政治策略——"规划"在军事语境中易获资助，"动态"比"数学"更不惹怒政客。

6. 影响：MDP 框架、值函数方法成为强化学习的数学基础。与 Pontryagin 极大值原理构成最优控制理论两大支柱。

来源

• 09-bellman-dynamic-programming — Dynamic Programming

相关

• 极大值原理（Pontryagin Maximum Principle） — compares_to
• 强化学习 — extends
• 马尔可夫链 — depends_on