【强化学习】区分理解： 时序差分（TD）、蒙特卡洛（MC）、动态规划（DP）

📢本篇文章是博主强化学习（RL）领域学习时，用于个人学习、研究或者欣赏使用，并基于博主对相关等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在👉强化学习专栏： 【强化学习】- 【强化学习进阶】（3）---《 区分理解： 时序差分（TD）、蒙特卡洛（MC）、动态规划（DP）》

区分理解： 时序差分（TD）、蒙特卡洛（MC）、动态规划（DP）

一、前言

在强化学习（Reinforcement Learning, RL）的领域，如何有效地评估和优化策略一直是研究的核心问题之一。强化学习的目标是让智能体通过与环境的交互，学习到如何最大化其获得的长期回报。在这一过程中，估计每个状态或状态-动作对的价值函数，成为了智能体进行决策的重要依据。

在过去的几十年中，时序差分（Temporal Difference, TD）、蒙特卡洛方法（Monte Carlo, MC） 和 动态规划（Dynamic Programming, DP） 这三种方法，作为强化学习中最常用的价值估计技术，为我们提供了不同的思路和工具来解决这一问题。每种方法都有其独特的优势和应用场景，从完全基于经验学习的TD，到依赖于完整回合回报的MC，再到要求已知环境模型的DP，它们在不同的任务中发挥着重要作用。

本篇文章将深入探讨这三种方法的基本原理、优缺点以及适用场景。通过对比它们的异同，我们可以更好地理解在实际应用中如何选择合适的方法。

二、时序差分（Temporal-Difference，TD）

1. 背景

在强化学习中，智能体需要通过与环境交互，逐步学习如何最大化长期回报。常见的两类方法是：

• 蒙特卡洛方法（MC）：通过完整的一条轨迹（从开始到终止）来估计状态或状态-动作的价值函数。
• 动态规划（DP）：需要已知环境的完整模型（转移概率与奖励函数），通过贝尔曼方程进行迭代计算。

TD方法处于这两者之间：

• 不需要环境模型（像MC一样）。
• 不必等到回合结束才更新（比MC更高效）。
• 可以在线、逐步更新（比DP更适合大规模问题）。

2. TD方法的核心思想

TD方法的核心是利用**“当前的估计来更新估计”**，即：

• 基于某个状态的即时奖励和下一状态的价值估计，来更新当前状态的价值估计。

其关键更新公式是：

V(S_t) \leftarrow V(S_t) + \alpha \big[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \big]

其中：

V(S_t)

：状态

S_t

的价值估计；

\alpha

：学习率；

R_{t+1}

：从

S_t

转移到

S_{t+1}

时获得的即时奖励；

\gamma

：折扣因子；

\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)

：称为 TD误差。

3. TD与其他方法的对比

• 与蒙特卡洛方法相比：
  • MC需要等到整个回合结束才能更新；TD可以在每一步更新。
  • TD更适合持续性任务（continuing tasks）。
• 与动态规划相比：
  • DP需要完整的环境模型；TD可以直接在与环境交互过程中学习。

4. 常见的TD算法

TD(0)

最简单的TD方法，只使用一步预测（bootstrapping）。

更新公式就是上面提到的。

n步TD

结合了MC和TD的思想，不只依赖下一步的价值，而是使用未来n步的回报来更新。

TD(λ)（又称 Eligibility Traces，资格迹方法）

将不同步长的TD方法加权结合，形成一个从TD(0)到MC之间的连续谱。

通过一个衰减参数λ控制短期与长期回报的平衡。

三、 蒙特卡洛（Monte Carlo， MC）

1. 蒙特卡洛方法简介

蒙特卡洛方法（Monte Carlo Method）是一类基于统计学的算法，其核心思想是通过多次随机抽样来进行估计。它特别适用于不完全知道环境动态（即没有环境模型）的情况。

在强化学习中，蒙特卡洛方法主要用于通过多次模拟（即从状态到终止状态的一次完整轨迹）来估计状态价值函数或状态-动作价值函数。

2. 蒙特卡洛方法的关键特点

2.1 基本定义

蒙特卡洛方法通过对多个完整回合（episodes）进行采样来估计某个状态的期望回报。在强化学习中，每个回合都包含从初始状态开始，直到达到终止状态为止的一系列状态、动作和奖励。

• 状态价值函数 V(S)：表示在状态 S下，按照某种策略进行下去时，所能期望获得的回报的平均值。 通过回合的总回报进行估计：

V(S) \approx \frac{1}{N(S)} \sum_{i=1}^{N(S)} G_i

其中，G_i 是回合 i 中从状态 S 开始的回报，N(S) 是访问状态 S 的次数。

• 状态-动作价值函数 Q(S, A)：表示在状态 S 下采取动作 A，然后按照某种策略进行下去时的期望回报。

2.2 蒙特卡洛的核心思想

蒙特卡洛方法并不依赖于环境的动态模型（转移概率和奖励函数）。它通过直接观察环境与智能体的交互结果（轨迹），从而推导出状态或状态-动作对的价值。

它的更新过程是基于每次回合的回报，而不是通过时间差分来逐步更新。

3. 蒙特卡洛方法的步骤

3.1 估计状态价值函数 V(S)

收集多次回合的数据：

在每一回合中，从初始状态 S_0 开始，按照当前策略进行探索，直到终止状态。

计算回报：

对于回合中的每一个状态 S_t，计算从该状态开始直到终止状态的总回报 G_t)。

更新状态的价值：

对于每个访问过的状态 S_t，根据回合中所有该状态的出现，更新其价值估计：

V(S_t) \leftarrow \frac{1}{N(S_t)} \sum_{i=1}^{N(S_t)} G_i

这里，N(S_t) 表示状态 S_t 出现的次数。

3.2 估计状态-动作价值函数 Q(S, A)

收集多次回合的数据：

与状态价值估计相同，首先从初始状态 S_0 开始，按照当前策略进行探索。

计算回报：

对于回合中的每个状态-动作对 (S_t, A_t)，计算从该状态-动作对开始直到终止状态的回报 (G_t)。

更新状态-动作价值：

对于每个访问过的状态-动作对 (S_t, A_t)，根据回合中所有该状态-动作对的出现，更新其价值估计：

Q(S_t, A_t) \leftarrow \frac{1}{N(S_t, A_t)} \sum_{i=1}^{N(S_t, A_t)} G_i

其中，N(S_t, A_t) 表示状态-动作对 (S_t, A_t) 出现的次数。

4. 蒙特卡洛方法的优点与缺点

4.1 优点

简单易懂：

蒙特卡洛方法基于直接采样和回报计算，概念简单，容易实现。

无需模型：

不需要环境的转移概率或奖励函数，因此能够在完全未知的环境中进行学习。

无偏估计：

在足够多的回合下，蒙特卡洛方法提供的是无偏的状态或状态-动作价值估计。

4.2 缺点

需要完整回合：

蒙特卡洛方法依赖于完整的回合，因此不适用于需要逐步更新的环境。

收敛速度慢：

相比其他方法（如TD方法），蒙特卡洛方法需要更多的回合来进行估计，收敛速度较慢。

高方差：

每个回合的回报可能有较大的波动，导致更新过程的方差较高，从而影响学习稳定性。

5. 蒙特卡洛方法的应用

蒙特卡洛方法在许多强化学习算法中都有应用，尤其是在一些策略评估和优化的场景中。它最常用于以下几种情况：

离线学习：当系统可以暂停、存储轨迹并进行后续分析时，蒙特卡洛方法非常适合。

策略评估：通过蒙特卡洛方法，可以估计给定策略下各个状态的价值，从而评估策略的好坏。

策略改进：在蒙特卡洛的基础上，结合贪心策略（或软策略）进行策略优化，得到强化学习中的策略迭代。

6. 常见的蒙特卡洛算法

蒙特卡洛控制算法：通过与策略改进结合，使用蒙特卡洛方法优化策略。

蒙特卡洛策略评估：用蒙特卡洛方法评估一个固定策略的价值函数。

四、动态规划（Dynamic Programming，DP）

1. 动态规划概述

动态规划（Dynamic Programming，简称DP） 是一种求解最优化问题的算法策略。它通过将复杂的问题分解成较小的子问题，并利用子问题的解来构建原问题的解。DP方法广泛应用于强化学习中，尤其是当我们拥有环境的完整模型（即转移概率和奖励函数已知）时。

在强化学习中，动态规划的核心任务是通过已知的环境模型来求解最优策略或评估某一策略。DP方法通常是离线算法，需要对整个状态空间进行处理，因此更适用于已知环境模型的场景。

2. 动态规划的关键概念

2.1 贝尔曼方程

DP方法基于 贝尔曼方程（Bellman Equation），它是强化学习中用来描述状态价值（或状态-动作价值）的核心方程。贝尔曼方程将一个状态的价值分解为当前奖励和未来状态的价值。

• 状态价值函数 V(s)：表示从状态 s 出发，按照某一策略执行，能获得的期望回报。贝尔曼方程为：

V(s) = \mathbb{E} \left[ R_{t+1} + \gamma V(S_{t+1}) \mid S_t = s \right]

其中：

R_{t+1}

：从状态

S_t

转移到

S_{t+1}

时获得的即时奖励；

\gamma

：折扣因子，用于控制未来回报的权重；

S_{t+1}

：下一状态，

\gamma V(S_{t+1})

是未来的预期回报。

• 状态-动作价值函数 Q(s, a)：表示从状态 s 出发采取动作 a 后，所能获得的期望回报。贝尔曼方程为：

Q(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \sum_{s'} P(s'|s, a) V(s') \right]

其中，P(s'|s, a) 表示从状态 s 采取动作 a 后，转移到状态 s' 的概率。

2.2 动态规划的核心方法

动态规划中有两种核心方法：

• 策略评估（Policy Evaluation）：给定一个策略，计算其状态价值函数 (V(s)) 或状态-动作价值函数 (Q(s, a))。
• 策略改进（Policy Improvement）：基于当前的状态价值函数或状态-动作价值函数来优化策略。

3. 动态规划的算法

动态规划包含几个重要的算法，常见的有以下两种：

3.1 值迭代（Value Iteration）

值迭代是一种基于贝尔曼方程的动态规划方法。它通过反复更新状态价值函数来逼近最优值函数。其步骤如下：

1. 初始化所有状态的价值 V(s) = 0 或一个随机值。
2. 对于每个状态 s，根据贝尔曼方程更新状态价值：

V(s) \leftarrow \max_a \sum_{s'} P(s'|s, a) [R(s, a, s') + \gamma V(s')]

1. 直到状态价值函数 V(s) 收敛。

值迭代不仅可以计算状态价值，还可以通过每一步选择具有最大价值的动作来得到最优策略。

3.2 策略迭代（Policy Iteration）

策略迭代分为两个主要步骤：

1. 策略评估：计算给定策略下每个状态的价值函数 V(s)，可以使用贝尔曼方程进行迭代更新。
2. 策略改进：基于计算出的状态价值函数来改进策略。选择在每个状态下能够最大化期望回报的动作，更新策略。

策略迭代的步骤如下：

1. 初始化一个随机策略。
2. 策略评估：计算当前策略的状态价值函数。
3. 策略改进：在每个状态下，选择使价值最大的动作。
4. 如果策略没有变化，则结束；否则，重复第2步和第3步。

策略迭代的优点是通常比值迭代收敛更快，因为每次策略改进都会使策略变得更好。

4. 动态规划的应用

动态规划方法适用于已知环境模型的情况。具体来说，DP常用于以下场景：

小规模状态空间：对于小规模的状态空间，动态规划是求解强化学习问题的理想方法。它通过对所有状态进行精确计算，能快速得到最优策略。

模型已知的环境：动态规划要求我们已知环境的转移概率 (P(s'|s, a)) 和奖励函数 (R(s, a, s'))，因此适用于模型已知的强化学习任务。

策略优化和评估：动态规划是经典的策略评估和策略优化方法，可以用于多种强化学习算法中，尤其是在动态环境模型已知的情况下。

5. 动态规划的优缺点

5.1 优点

精确性：DP方法通过使用环境的完整模型，能得到最优解，是一种精确的求解方法。

理论完备性：动态规划为强化学习问题提供了理论上的完整解决方案，能够通过贝尔曼方程进行推导和优化。

收敛性：在适当的条件下，DP方法能够确保收敛，保证找到最优策略。

5.2 缺点

状态空间的维度：对于大规模的状态空间，动态规划的计算成本非常高，无法在大规模问题中高效执行。

对模型的依赖：DP方法要求我们已知环境的转移概率和奖励函数，这对于许多实际问题而言往往是不可行的。它依赖于环境的模型已知。

计算复杂度高：动态规划需要对整个状态空间进行计算，因此对于大规模状态空间，计算量会非常大，导致效率低下。

6. 动态规划与强化学习的结合

在强化学习中，动态规划方法为许多重要算法提供了理论基础。虽然实际应用中很少使用纯DP算法（因为环境模型往往不可得），但是它仍然是强化学习理论中的核心部分，尤其是在算法设计和改进过程中。例如：

• 策略评估与改进：在策略迭代过程中，DP为策略评估与改进提供了计算框架。
• 值函数逼近：在某些情况下，动态规划的思想可以与值函数逼近方法结合，从而用于大规模问题。

五、三者比较

六、 结论

• 时序差分（TD）：通过结合当前估计与即时反馈来进行在线学习，适用于没有环境模型的任务，效率高，收敛速度较快，但可能面临高方差和过度估计问题。
• 蒙特卡洛（MC）：依赖于完整回合的回报来进行学习，适合离线学习，但收敛速度慢且具有较大的方差。
• 动态规划（DP）：则需要已知的环境模型，通过贝尔曼方程进行精确的价值计算，适用于小规模状态空间的问题，能够快速收敛，但计算开销较大。

更多强化学习文章，请前往：【强化学习（RL）】专栏

博客都是给自己看的笔记，如有误导深表抱歉。文章若有不当和不正确之处，还望理解与指出。由于部分文字、图片等来源于互联网，无法核实真实出处，如涉及相关争议，请联系博主删除。如有错误、疑问和侵权，欢迎评论留言联系作者，或者添加VX：Rainbook_2，联系作者。✨