蒙特卡洛树搜索方法介绍——规划与学习

引言

本节通过对动态规划方法、蒙特卡洛方法、时序差分方法进行归纳，介绍规划与学习两种思想。

环境与模型

在动态规划求解强化学习任务 中介绍过，动态规划方法使用的核心思想是自举(Boostrapping)方法： V k + 1 ( S t ) = ∑ a ∈ A ( s ) π ( a ∣ s ) ∑ s ’ , r P ( s ’ , r ∣ s , a ) ( r + γ V k ( s ’ ) ) V_{k+1}(S_t) = \sum_{a \in \mathcal A(s)} \pi(a \mid s) \sum_{s’,r}P(s’,r \mid s,a)(r + \gamma V_{k}(s’)) Vk+1​(St​)=a∈A(s)∑​π(a∣s)s’,r∑​P(s’,r∣s,a)(r+γVk​(s’)) 并且介绍了想要使用动态规划方法求解强化学习任务，就必须要已知 完备的迁移动态，即 任意有意义的状态-动作对的动态特性函数 P ( s ’ , r ∣ s , a ) P(s’,r \mid s,a) P(s’,r∣s,a) 均是已知的。我们称这种方法为有模型方法(Model-based Method)。 注：该模型指的是‘环境模型’，是基于环境自身的性质，通过动态特性函数表示出来。 有模型方法主要依赖的思想是规划(Planning);

针对像蒙特卡洛方法、时序差分方法这种 对动态特性函数未知或未完全可知 的情况，而通过真实样本进行采样得到的真实经验(Experience)对策略进行估计的方法，我们称为无模型方法(Model-free Method)。 无模型方法主要依赖的思想是学习(Learning);

规划思想与学习思想 规划与学习的相同点

基于已经介绍过的动态规划方法、蒙特卡洛方法、时序差分方法，它们三个之间的共同点：

• 对策略更新的过程中，它们都使用了价值函数这个概念作为媒介，对策略进行更新： 之所以将‘价值函数’称为‘媒介’——是因为这三种方法并没有直接对策略 π \pi π进行求解，而是通过‘价值函数’和‘策略’相互迭代的方式进行求解。相反，直接对策略 π \pi π进行求解参考‘策略梯度方法’。
• 回溯思想：其核心思想是没有办法在当前时刻 t t t更新价值函数，只能通过未来时刻更新当前时刻 t t t的价值函数。我们观察几种方法的策略评估过程：
  • 动态规划-策略评估(其中 R t + 1 + γ V π ( S t + 1 ) R_{t+1} + \gamma V_\pi(S_{t+1}) Rt+1​+γVπ​(St+1​)是由动态特性函数计算获得的)： E π [ R t + 1 + γ V π ( S t + 1 ) ∣ S t = s ] \mathbb E_{\pi}[R_{t+1} + \gamma V_{\pi}(S_{t+1}) \mid S_t =s] Eπ​[Rt+1​+γVπ​(St+1​)∣St​=s]
  • 蒙特卡洛评估： E π [ G t ∣ S t = s ] \mathbb E_{\pi}[G_t \mid S_t =s] Eπ​[Gt​∣St​=s]
  • 时序差分评估(其中 R t + 1 + γ V π ( S t + 1 ) R_{t+1} + \gamma V_\pi(S_{t+1}) Rt+1​+γVπ​(St+1​)是通过采样获得的)： E π [ R t + 1 + γ V π ( S t + 1 ) ∣ S t = s ] \mathbb E_{\pi}[R_{t+1} + \gamma V_{\pi}(S_{t+1}) \mid S_t = s] Eπ​[Rt+1​+γVπ​(St+1​)∣St​=s] 观察上述三个式子，没有一个能够实现在当前时刻 t t t完成更新。其中动态规划和时序差分方法至少需要执行 一次状态转移过程才能对当前时刻状态价值函数进行更新；蒙特卡洛方法甚至要完成 整个情节的遍历 才能对状态价值函数进行更新。
• 广义策略迭代(GPI)：上述三种方法本质上都是使用广义策略迭代的思想，在整个迭代过程中并没有 将 Q − T a b l e Q-Table Q−Table中的全部元素更新一遍之后 再执行下一次迭代，而仅是 更新 Q − T a b l e Q-Table Q−Table中的部分元素即可进行下一次迭代。例如：
  • 蒙特卡洛方法仅更新了 Q − T a b l e Q-Table Q−Table中 某一完整情节对应一系列状态-动作对 上的价值函数信息；
  • 时序差分方法更是仅更新了 Q − T a b l e Q-Table Q−Table 在状态转移过程中的某一状态-动作对 上的价值函数信息；

规划与学习的不同点 规划的特点

规划首先和环境模型(Model)，和动态特性函数是密切相关的，其本质是从模拟经验中更新价值函数，从而实现改进策略的目的。

• 什么是模拟经验： 我们观察动态规划方法求解策略的过程，发现它并没有产生任何一个样本：它的状态转移结果 S t + 1 S_{t+1} St+1​是通过当前时刻状态 S t S_t St​的条件下，执行动作 A t A_t At​，通过动态特性函数 P ( R t + 1 , S t + 1 ∣ S t , A t ) P(R_{t+1},S_{t+1} \mid S_t,A_t) P(Rt+1​,St+1​∣St​,At​)得到关于转移至 S t + 1 S_{t+1} St+1​状态的各状态的概率分布，并从该分布中 随机选择一个状态 作为 S t + 1 S_{t+1} St+1​。 因此，该结果 S t + 1 S_{t+1} St+1​并不是真实环境真正选择的结果，而是通过动态特性函数模拟选择的结果。

通常将规划方法视为搜索(Search)方法。它的核心就是遍历。以动态规划方法为例，其本质上就是将当前时刻状态 S t S_t St​到下一时刻状态 S t + 1 S_{t+1} St+1​中所有状态转移的可能性全部找出来。 因此，规划的主要思想是：

• 所有规划方法都是 环境模型 产生的模拟经验来计算价值函数；
• 所有规划方法都是以计算价值函数作为策略迭代的中间关键步骤；

规划的基本流程可以表示如下： 环境模型 → \to → 模拟经验 → \to →(回溯)价值函数 → \to →(改进)策略

学习的特点

由于规划基于的条件是环境模型(Model)是给定的，但在真实环境中，环境模型可能存在 环境信息不完整甚至是完全未知 的情况。因此，我们如果想用规划方法来求解策略，首先需要 将模型求出来。

那么，模型要如何进行求解呢？ 我们仍然需要经验(experience)，但这次的经验并不是环境模型产生出的模拟经验，而是真实环境产生的真实经验。 什么是真实经验：

• 对比模拟经验，真实经验是在 t t t时刻状态 S t = s S_t = s St​=s条件下，选择了某一动作 A t = a A_t = a At​=a，并实实在在地执行了一次状态转移过程。我们将转移后的状态结果和对应的奖励结果看作关于 S t = s , A t = a S_t = s,A_t = a St​=s,At​=a的一个样本，因而每个状态-动作对 ( s , a ) (s,a) (s,a)都会产生大量的样本。最终通过这些样本反过来归纳每个状态-动作对的环境模型分布。最终将所有状态-动作对的环境模型分布合在一起来近似真实环境模型。

至此，我们已经通过样本近似得到环境模型，就可以继续使用规划的流程求解策略。

上述流程确实可以实现，但实际上我们发现，假设已经得到了关于状态-动作对的大量真实样本，我们完全可以直接去学习策略，而不是转成规划的方式。 蒙特卡洛方法、时序差分方法都是这么做的。

因此，我们将先通过采样学习环境模型 P P P，再通过环境模型 P P P进行规划来更新策略 π \pi π的方式称为间接强化学习。相反，通过真实经验样本直接更新策略或利用已知环境模型更新策略 的方式称为 直接强化学习。 因此，动态规划方法、蒙特卡洛方法、时序查分方法 都是 直接强化学习。

下一节将继续介绍规划与学习的差异和 Q Q Q规划。

相关参考： 深度强化学习 原理、算法与PyTorch实战——刘全、黄志刚编著