14.md

# Lecture 14 Model Based RL, Monte-Carlo Tree Search

# 课时14 基于模型的强化学习，蒙特卡洛树搜索 2019.03.06

## 1. 介绍（Introduction）

本节课我们讨论基于模型的强化学习与基于仿真的树搜索方法。到目前为止我们已经讨论了从经历中尝试学习值函数或策略的方法，与这些方法相反，基于模型的方法首先从经历中学习环境的模型，然后使用这个模型做出规划和行动。基于模型的方法在某些情况下有更高的采样效率和更快的收敛速度。我们还将讨论 MCTS 及其变体，它们可以用于针对给出的模型做出规划。MCTS 是 AlphoGo 成功背后的主要思想之一。

**图一**

## 2. 模型学习（Model Learning）

我们用 $<S,A,R,T,\gamma>$ 来表示一个 MDP 的模型，由 $\mu$ 参数化。在模型学习中，我们假设状态空间 $S$ 和 动作空间 $A$ 已知，并且通常还假设状态转移与奖励是相互独立的，即

$$
P[s_{t+1},r_{t+1}|s_t,a_t] = P[s_{t+1}|s_t,a_t]P[r_{t+1}|s_t,a_t]。
$$

因此，模型学习包括两个部分，分别为奖励函数 $R(\cdot|s,a)$ 和转移分布 $P(\cdot|s,a)$。

给定一个真实轨迹的集合 $\{S_t^k,A_t^k,R_t^k,...,S_T^k\}_{k=1}^{K}$，模型学习可以被视为一个监督学习问题，学习奖励函数 $R(s,a)$ 是一个回归问题，而学习转移函数 $P(s'|s,a)$ 是一个密度估计问题。首先我们选取一类合适的参数化模型，如查表模型、线性期望、线性高斯、高斯过程、深度神经网络等，然后我们选择一个恰当的损失函数，如均方误差、KL 散度等，通过最小化这个损失来优化参数。

## 3. 规划（Planning）

给定一个学习到的环境的模型，规划可以由基于值的方法、策略搜索的方法或树搜索的方法来实现。

一种比较的规划方法的思路为：仅使用该模型来生成采样轨迹，并使用 Q-学习、蒙特卡洛控制或 SARSA 等方法进行控制。这种基于样本的规划方法通常更具数据效率。

学习得到的模型可能是不准确的，因此，通过规划所学习的缩略也可能是次优的，即基于模型的 RL 的质量依赖于所学习的模型的质量。基于探索/利用的技术可用于在规划时明确解释模型中的这种不确定性。或者，如果我们确定模型在某些情况下是错误的，无模型 RL 方法也可以作为我们的后备方案。

## 4. 基于仿真的搜索（Simulation Based Search）

不管给出的模型是学习到的近似模型，还是像围棋这样的精确模型，这些方法都试图基于向前搜索或模拟来寻找最优动作。搜索树以当前的状态为根，使用模型生成其他节点。因为不需要求解整个 MDP 而只需要从当前状态开始求解子 MDP，所以这种方法可以节省大量的资源。一般来说，当我们收集了仿真经历 $\{S_T^K,A_t^k,R_t^k,...,S_T^K\}_{k=1}^{K}$后，我们可以将无模型方法应用于控制，如蒙特卡洛给出了蒙特卡洛搜索算法或 SARSA 给出了 TD 搜索算法。

更具体地说，在一个简单的 MC 搜索算法中，给出了一个模型 M 和一个模拟策略 $\pi$，对于每个动作 $a\in A$，我们模拟 $K$ 个 $\{S_T^K,a,R_t^k,...,S_T^K\}_{k=1}^{K}$ 形式的片段（在第一动作后遵循策略 $\pi$）。$Q(s_t,a)$ 值被估计为上述轨迹的平均回报，随后我们选择最大化这个估计的 $Q(s_t,a)$ 值的动作。

### 4.1 蒙特卡洛树搜索（Monte Carlo Tree Search）

这类算法基于两个原则：（1）状态的真实价值可以通过随机模拟的平均回报值来估计；（2）这些值可以用于迭代地调整策略，从而使我们能够关注搜索空间的高价值区域。

我们逐步构造一个以当前节点为根的部分搜索树。树由对应于状态 $s$ 的节点组成，此外，每个节点还存储统计信息，如总访问次数 $N(s)$、每个状态-动作对的访问次数 $N(s,a)$ 以及蒙特卡洛 $Q(s,a)$ 值估计等。一种典型的方法是一直构造这种树，直到某些预先定义的计算耗尽，价值估计会变得越来越准确。每个迭代大致可以分为四个阶段：

1. 选择：从根节点开始，我们在树中循环地选择子节点，直到达到非终结叶节点；

2. 扩展：将被选中的叶节点添加到搜索树中；

3. 仿真：从这一节点开始仿真来生成输出的估计值；

4. 反向传播：通过反向沿着根到选中叶节点的路径，更新遇到的节点的统计信息，从而将仿真中获得的值在树中反向传播。

MCTS 的变体通常包含对涉及的两个主要策略的修改：

$\bullet$ 树策略：根据存储的统计信息为树的节点选择动作，变体包括贪婪策略、UCB

$\bullet$ 仿真策略：用于树中叶节点的仿真，变体包括随机模拟、AlphaGo 的默认策略网络

**算法一**

这些步骤总结在了算法 1 中，我们从当前状态开始，迭代地生长搜索树，在每次迭代时使用树策略来选择要模拟的叶节点，然后对仿真结果进行反向传播，最后输出从根节点估计得到最大值的动作。

该算法的一个简单变体如算法 2 所示，在第一阶段中贪婪地在树节点之间选择动作，并在仿真阶段使用随机策略进行仿真。

**算法二**

还有一些基于上述方案的修改，如通过添加有限的节点集到树、智能修剪来提升存储器的使用，通过使用节点中存储的更复杂的统计数据来改善树策略。

从[图 2](#fig2) 中可以看到整个的运行过程。我们从根节点开始，仿真一个轨迹，图中的情况下，这个轨迹返回一个 1 的奖励；然后我们使用树策略，即贪婪地选择要添加到树的节点，然后从它开始使用仿真（默认）策略仿真一个片段，这个片段返回一个 0 的奖励，我们更新树节点中的统计信息；然后重复此过程。为了检查你的理解，你应该在下面的示例中验证统计信息已经正确更新，以及树策略选择了正确的节点来扩展。

MCTS 的主要优点包括：

$\bullet$ 树结构使它具有很大的并行性

$\bullet$ 状态评估是动态的，即从当前状态开始解决 MDP 问题，与 DP 不同

$\bullet$ 不需要模型，只需要样本

$\bullet$ 有效地结合规划和抽样来打破维度灾难（如围棋）

**图2**

### 4.2 置信上界树搜索（Upper Confidence Tree Search）

类似多臂老虎机，使用贪婪策略作为树策略往往是次优的，这会使我们即使是在一个糟糕的结果之后也避免采取行动，尽管其真实价值存在着很大的不确定性。作为一个例子，考虑[图 2](#fig2) 中最右边的节点，我们从该节点执行一个单独的仿真，收到一个值为 0 的奖励，然后再也不访问该节点，即使这个奖励可能只是因为运气不好（才是 0）。为了解决这个问题，我们可以使用 UCB 算法将不确定性下的乐观原则应用于 MCTS，更具体地说，树策略选择最大化动作值置信上界（$Q(s,a)+\sqrt{\frac{2\log N(s)}{N(s,a)}}$）的动作，而非贪婪地选择动作。

算法 3 为 UCT 中使用树策略的伪代码，该算法可以插入到前面描述的通用 MCTS 算法。 $nextState(s,a)$ 函数使用了 MDP 模型在从状态 $s$ 选择动作 $a$ 时采样下一状态。