最近在准备组内强化学习第5,6讲的分享，顺便回顾了前面的所有内容，所以这篇笔记姗姗来迟。本章的内容是介绍Planning，以及将Learning与Planning结合起来技术。前面的课程中谈到过Planning，即Dynamic Programming。Planning就是在已知Model的情况下计算最优的策略。Planning需要先要根据经验得到模型，大致形式如下

在强化学习领域内，模型就是P（转移概率）和R（奖励），所以模型就是根据状态S和动作A，估计出对应的P与R。这个是不是在哪里遇到过？没错，这个就是监督学习。定义模型为$M=\langle P,R \rangle$，最后求解下面的形式

\(S_{t+1} \sim P_\eta(S_{t+1} \vert S_t, A_t) \\ R_{t+1} = R_\eta(R_{t+1} | S_t,A_t)\) 一般假设状态转移和奖励相互独立。

既然是监督学习，那么就可以使用监督学习中的那些方法求解。当有模型后，可以用之前的动态规划方法求解最优策略。除此之外，还可以利用之前提到的Model Free的方法求解最优策略，把模型当做环境，不断生成样本，那么就是无缝使用MC-Control，SARSA和QLearning等方法。

但是模型一定有误差，基于有误差的模型，学习到的策略也不是最优的。所以，比较好的方法是集成Planning和Learning两个过程，model和policy一起学习，相互促进，而不是完全要Model引导Policy。这类方法称为Dyna,流程大体如下

在原始Planing的方法下，整合了Model Free的学习方法。最为基础的算法是Dyna-Q，其伪代码如下

当$n=0$时，Dyna-Q就退化成了Q-Learning。经过一些实验，可以看到Dyna-Q收敛速率比Q-Learing要快很多，因为一旦有了模型，可以自己生成样本自己学习，而不需要与环境交互，有点类似左右互搏的效果。

最后介绍MCTS: Monte Carlo Tree Search。该方法的核心思想就是采样。MCTS通过采样的方法，扩展树的结构，并且不断评估候选状态的值函数。在状态空间特备复杂的情况下，比如围棋。如果每次从起点开始模型，那么效率会非常低。MCTS使用启发式方法，每次在当前一个较好的状态下继续探索，探索方法即使随机样本，直到得到最优的方案。MCTS由于在AlphaGo中应用，被广为人知，下面这张动图可以形象解释MCTS的工作源里，

蒙特卡洛树是什么算法？ - fly qq的回答 - 知乎比较容易理解。更为学术资料，可以参考mcts.ai。

分享总结 2018-1-22

本次风向中，谈到了Dyna为什么会比非Dyna收敛快。因为在Dyna中，有个内部simulate，在此过程中，S和A是随机取的，可以尝试一些情况，而这些情况在与真实环境交互时，无法得到。同时，自我交互的过程相当于自己模拟，可以减少真实的交互次数，即减少step次数。

谈到了MCTS，该技术06年发明，后来很多围棋AI都是基于MCTS的优化和改进，最好的一个是日本开发的Zen，但是均没有达到人类冠军的段位，直到AlphaGo的出现，它在MCTS的基础上，融合了深度学习和强化学习，打败了人类冠军。

MCTS在探索的时候，起点是Current State，然后使用Tree Policy只搜索$d$层,$d$层以后的就用随机模拟和其他模拟方法快速的模拟，得到结果，然后更新到根节点。经过k轮后，从当前状态，找到一个最优的action进行扩展，然后继续这个循环。深度学习应用在d层以后，可以直接通过监督学习算出来，而不是模拟出来。如果不用深度学习，在最开始会比较弱，深度学习弥补了开始时比较弱的情况。