动态规划的局限性

本章早前介绍的策略迭代和价值迭代等动态规划方法，提供了强大的理论工具。它们能保证为有限马尔可夫决策过程找到最优价值函数（$V^*$ 或 $Q^*$），进而得到最优策略（$\pi^*$）。然而，这些方法在实际应用中常遇到显著困难。这些局限性主要源于两个重要要求：需要完整的环境模型，以及处理大型问题所需的计算成本。

完整模型的要求

动态规划在强化学习 (reinforcement learning)中最重要的实际局限性在于它依赖于一个完整且准确的环境模型。请记住，策略评估（在策略迭代中）和价值迭代都依赖于知道所有状态 $s$、动作 $a$、下一个状态 $s'$ 和奖励 $r$ 的转移概率 $p(s', r | s, a)$。

思考这意味着什么：

1. 动态机制的认知： 我们需要确切了解环境如何运作。对于我们所处的任何状态以及我们可能采取的任何动作，我们都必须知道转移到每个其他可能状态的概率以及获得每个可能奖励的概率。
2. 模型的可用性： 这种完整的模型信息必须以可用格式提供给算法。

在许多有关情况下，拥有如此理想的模型简直不现实：

• 未知环境： 我们常希望智能体能在规则事先未知的环境中学习。例如，一个机器人在学习在新建筑中导航，或一个算法在无权访问游戏源代码的情况下学习玩一个复杂视频游戏。其转移概率和奖励结构并未明确提供。
• 模型建立的复杂性： 即使潜在动态由物理定律支配（如在机器人技术中），创建一个能捕捉所有相关细节（包括噪声和不确定性）的准确仿真模型也可能极其困难、耗时且容易出错。
• 非平稳环境： 在某些情况下，环境的动态可能会随时间变化。昨天准确的模型今天可能不准确，从而导致基于旧模型的动态规划计算次优。

这一要求本质上意味着，动态规划方法是在拥有理想地图时用于规划的工具，而非在需要自己弄清地图时用于学习的工具。

计算可扩展性挑战

即使我们足够幸运拥有一个理想模型，动态规划方法也面临另一个主要障碍，常被称为“维度灾难”。这与随着问题规模增长所需的计算资源有关。

策略迭代和价值迭代的核心操作都涉及遍历整个状态空间 $\mathcal{S}$（通常也包括每个状态的动作空间 $\mathcal{A}$），以基于贝尔曼方程执行更新。

• 策略评估： 需要重复遍历所有状态，根据后继状态的价值更新 $V(s)$。
• 价值迭代： 需要遍历所有状态，计算所有动作上的最大期望价值。单次迭代的复杂度通常与 $O(|\mathcal{S}|^2 |\mathcal{A}|)$ 等成比例，或者取决于转移密度，可能更差。

考虑其影响：

• 内存： 存储价值函数 $V(s)$ 或 $Q(s,a)$ 需要与状态数量 $|\mathcal{S}|$ 或状态-动作对数量 $|\mathcal{S}| \times |\mathcal{A}|$ 成比例的内存。存储模型 $p(s', r | s, a)$ 可能需要更多空间，可能与 $|\mathcal{S}|^2 |\mathcal{A}|$ 成比例。
• 计算时间： 每次迭代所需的时间随状态空间和动作空间的大小迅速增长。

虽然对于小型离散问题（如示例中常用的网格世界）是可行的，但这种计算成本对于以下问题很快就变得高得令人望而却步：

• 大量离散状态： 考虑像国际象棋或围棋这样的游戏，其中可能的棋盘配置数量（$|\mathcal{S}|$）极其庞大。
• 连续状态空间： 如果状态由连续变量表示（例如，机器人关节角度、传感器读数），则状态空间在技术上是无限的。动态规划的基本形式无法直接处理这种情况。离散化连续空间常导致状态数量呈指数级膨胀。

演示了动态规划方法每次迭代的计算成本如何随状态数量迅速扩展。像 $O(|\mathcal{S}|^2)$ 或 $O(|\mathcal{S}|^2|\mathcal{A}|)$ 这样的常见复杂度使得动态规划对于非常大的状态空间不切实际。两个轴都使用对数刻度。

摆脱动态规划

“这些局限性说明了为什么动态规划，尽管在建立贝尔曼方程方面具有理论重要性，但通常不能直接应用于许多复杂的强化学习 (reinforcement learning)问题。我们需要能够做到以下几点的方法：”

1. 在不要求事先了解环境动态机制的情况下，学习有效策略（无模型方法）。
2. 高效处理大或连续的状态和动作空间。

这促使了我们将在接下来的章节中考察的无模型算法的发展，例如蒙特卡洛方法（第四章）和时序差分学习（第五章），它们直接从与环境交互中收集的经验中学习。此外，我们还将考察函数逼近技术（第六章），这些技术使我们能够将价值估计推广到大型状态空间，摆脱基本动态规划中固有的表格表示的限制。