深度学习和强化学习（八） 蒙特卡洛树搜索

基于模拟的搜索概述

基于强化学习模型进行采样，得到样本数据。但是这是数据不是基于和环境交互获得的真实数据，所以是“模拟”。先看看最简单的前向搜索(forward search)。前向搜索算法从当前我们考虑的状态节点StSt开始考虑，怎么考虑呢？对该状态节点所有可能的动作进行扩展，建立一颗以StSt为根节点的搜索树，这个搜索树也是一个MDP，只是它是以当前状态为根节点，而不是以起始状态为根节点，所以也叫做sub-MDP。我们求解这个sub-MDP问题，然后得到StSt状态最应该采用的动作AtAt。前向搜索的sub-MDP如下图

这很精确，而且这在状态动作数量都很少的时候没有问题，但是只要稍微状态动作数量多一点，每个状态的选择就都特别慢了，因此不太实用，此时基于模拟的搜索就是一种比较好的折衷。

简单蒙特卡罗搜索：

简单蒙特卡罗搜索基于一个强化学习模型Mv和一个模拟策略π.在此基础上，对于当前我们要选择动作的状态St, 对每一个可能采样的动作a∈A,都进行K轮采样，这样每个动作a都会得到K组经历完整的状态序列(episode)。即：

现在对于每个(St,a)组合，我们可以基于蒙特卡罗法来计算其动作价值函数并选择最优的动作了。

简单蒙特卡罗搜索和起前向搜索比起来，对于状态动作数量的处理能力上了一个数量级,可以处理中等规模的问题。但是假如我们的状态动作数量达到非常大的量级，比如围棋的级别,那么简单蒙特卡罗搜索也太慢了。同时，由于使用蒙特卡罗法计算其动作价值函数，模拟采样得到的一些中间状态和对应行为的价值就被忽略了

MCTS：蒙特卡洛树搜索

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

当前状态St对应的完整的状态序列(episode)是这样的