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)$ 值的动作。