1. Model-Based RL

1.1 Introduction

之前我们学习的都是Model-Free的方法，即我们需要通过一些来自真实环境的experience来学习 value function 以及 Policy来解决某个问题。而Model-Based的方法则是借助来自真实环境的experience来学习一个model（图中卡通的地球），然后借助这个学到的model进行决策。

具体来说，下图右边所示，我们有一些真实世界的experience，Agent通过model learning算法来构建一个内部的model，然后借助这个model去进行plan以得到value和policy，然后根据policy去真实环境中进行acting，再得到一些experience，如此循环往复。

Model-Based RL的好处在于可以通过监督学习的方式去进行model learning，同时对于model的uncertain可以很好的去解释。缺点也很明显，这种方法的误差来源有value function和model learning，所以估计的偏差可能会更多一点。

1.2 Learning a Model

首先给出model的定义，model就是用参数 $\eta$ 来表述一个 MDP，这里我们假定状态空间和动作空间都是已知的，因此我们使用 $\eta$ 来表示状态之间的转移概率以及Reward：

$$
\begin{array}{l}
S_{t+1} \sim \mathcal{P}_{\eta}\left(S_{t+1} \mid S_{t}, A_{t}\right) \\
R_{t+1}=\mathcal{R}_{\eta}\left(R_{t+1} \mid S_{t}, A_{t}\right)
\end{array}
$$

其实Model Learning是一个监督学习：从 $s,a \to r$ 是一个回归问题，从 $s,a \to s^{\prime}$ 是一个密度估计问题（需要得出一个概率分布）。这样，model learning就可以从传统机器学习的套路思考了，即选择一个合适的损失函数，然后梯度下降更新参数。

1.3 Planning with a Model

所谓Planning，其实我们之前也都学到了，比如Value iteration，Policy iteration，Tree search都属于Planing算法。下面举个例子Sample-Based Planning：

2. Integrated Architectures

Model-free RL直接从真实样本中学习value function，Model-Based RL直接从真实样本中学习model，然后借助model生成虚拟的样本，借助虚拟样本来plan获得value function。那能否结合一下？这就是Dyna的思想，即从真实样本中学习一个model，model生成虚拟样本，再同时借助虚拟和正式样本进行learning和planing以获得value function，算法流程如下：

3. Simulation-Based Search

3.1 Forward search

前向搜索算法通过向前预测来选取最佳的动作
通过建立基于目前状态st𝑠𝑡作为根的搜索树（Search Tree）
通过一个MDP的模型来向前预测
其实并不需要整个MDP，只是从目前出发的一部分MDP

3.2 Simulation-Based Search

上面的前向搜索如果使用sample-based planning，就称为Simulation-Based Search，即借助虚拟的Episode来构建树，首先基于模型模拟从目前状态开始的经验序列：

$$
\{{s^k_t},A^k_t,R^k_{t+1},\dots,S^k_T\}^K_{k=1}\sim\mathcal{M_v}

然后在模拟出来的序列中应用无模型强化学习（按你喜欢的即可）

蒙特卡罗·控制→蒙特卡罗搜索（Monte-Carlo Search）
SARSA→→TD搜索

3.3 Simple Monte-Carlo Search

给定模型 $\mathcal{M_v}$ 以及一个虚拟策略 $\pi$ ，对于任意属于动作空间中的动作 $a$，基于目前的真实状态 $s_t$ 生成 $K$ 个虚拟的序列，即每个 $(s_t,a)$ 都生成 $K$ 个序列：

$$
\{{s_t,a},R^k_{t+1},S^k_{t+1},A^k_{t+1},\dots,S^k_T\}^K_{k=1}\sim \mathcal{M_v,\pi}
$$

然后借助MC evaluation去计算Q-value：

$$
Q({s_t,a})=\frac{1}{K}\sum^K_{k=1}G_t\mathop{\rightarrow}^P q_\pi(s_t,a)
$$

选择具有最大价值的动作：

$$
a_t=\mathop{\arg\max}_{a\in A}Q(s,a)
$$

简单蒙特卡罗搜索和起前向搜索比起来，对于状态动作数量的处理能力上了一个数量级,可以处理中等规模的问题。但是假如我们的状态动作数量达到非常大的量级，比如围棋的级别,那么简单蒙特卡罗搜索也太慢了。

3.4 Monte-Carlo Tree Search

MCTS摒弃了简单蒙特卡罗搜索里面对当前状态 $S_t$ 每个动作都要进行 $K$ 次模拟采样的做法，而是总共对当前状态 $S_t$ 进行 $K$ 次采样，这样采样到的动作只是动作全集 $A$ 中的一部分。这样做大大降低了采样的数量和采样后的搜索计算。当然，代价是可能动作全集中的很多动作都没有采样到，可能错失好的动作选择，这是一个算法设计上的折衷。

在MCTS中，基于一个强化学习模型和一个模拟策略，当前状态对应的完整的状态序列(episode)是这样的：

$$
\{S_t,A_t^k, R_{t+1}^k,S_{t+1}^k,A_{t+1}^k,……S_T^k\}_{k=1}^K \sim M_v,\pi
$$

采样完毕后，我们可以基于采样的结果构建一颗MCTS的搜索树，然后近似计算Q-value得到最优的动作：

$$
Q(S_t,a) = \frac{1}{N(S_t,a)}\sum\limits_{k=1}^K\sum\limits_{u=t}^T1(S_{uk}=S_t, A_{uk} =a)G_u\\
a_t =\arg\max_{a \in A}Q(S_t,a)
$$

蒙特卡罗树搜索的优点在于：

高度选择性的最优优先搜索
动态评估所有状态（不像例如动态规划那样）
通过采样来破坏维度曲线（curse dimensionality）*大概指的是状态随着树分支的增加以几何级数的趋势爆发
黑箱模型的杰作（只需采样）
计算处理上地高效，支持并行处理