)
【强化学习】第五章：蒙特卡洛学习、时序差分学习、TD(λ)
本篇开启无模型(Model-free)强化学习方法：蒙特卡洛学习、时序差分学习、TD(λ)。其中，TD(λ)方法可以看作是蒙特卡洛方法和时序差分方法的混合。
这三个方法的最终目的都是用来评估和优化价值函数的，通俗的说就是计算状态价值的。评估价值函数就是计算出那个收敛的Vπ，有了Vπ就可以算出Qπ，有了Qπ就可以用贪婪的方法去提升策略了，如此循环就可以找到最优策略。也就是智能体从小白变成了高手。
说明：本章理解起来有些抽象，要想彻底弄懂，第二章的增量式均值计算、指数移动平均，第三章的贝尔曼期望方程，第四章动态规划中的迭代策略评估，这些内容务必要弄明白，本章才容易理解。
一、蒙特卡洛强化学习(Monte-Carlo Reinforcement Learning)
1、蒙特卡洛强化学习是解决什么问题的？
我们前面第三、四章学的是有模型的强化学习问题，就是现实问题可以抽象成一个完备的MDP。完备的MDP就是我们是知道环境中的状态的，而且知道状态之间的转移概率，并且知道系统的即时奖励。此时我们用贝尔曼期望方程+动态规划就可以解决。
但是无模型的强化学习问题是一个非完备的MDP，我们是不知道系统背后的状态转移矩阵，也不知道系统奖励。此时就得用无模型强化学习方法。其中蒙特卡洛强化学习方法(简称MC)就是一个典型的无模型算法。
2、MC的基本描述和基本思想
（1）MC方法是需要agent和环境进行交互的，交互了就可以获得交互数据，然后从交互数据中寻找经验。
（2）MC方法要求agent得从头打到游戏结束。所以MC只能用于有分幕的情况，就是要有游戏结束的情况。
（3）通俗理解：MC就是用样本均值估计总体均值的方法，就是用样本均值逼近总体均值，或者说就是用频率逼近概率的逻辑。在完备的MDP中我们是有状态转移矩阵的，所以可以用概率算出状态价值，但是这里不知道状态是如何转移的，所以只能通过实际走出的一条条幕，通过这些幕中的状态实际回报的均值来估计状态价值。
3、MC具体是如何计算状态价值的？
（1）MC是通过两种方法来计算状态价值的：first-visit或者every-visit来计算的。
（2）上左图：意思就是agent实实在在的打了6轮游戏，所以产生了6条分幕。上左图就是利用这6条分幕来计算状态s0的价值值的示例。具体做法是：
首先在每条分幕中找到状态s0第一次出现的地方。比如分幕1中，s0第一出现在a处，虽然b处也出现了s0，但是不用管b处，我们只计算a处s0的价值。那a处s0的价值=其后所有状态的系统奖励和。这就算出了第一个s0的价值值。
同理，观察分幕2中s0出现的位置，发现分幕2中压根就没出现状态s0，那就弃用这条分幕！
同理计算分幕3、分幕4、分幕6中的s0价值值。这样就又得到3个s0的价值值。
最后求这4个s0价值值的均值，就得到状态s0的价值值。
如此方法计算其他状态的价值。
（3）上右图：方法2示例的也是如何计算状态s0的价值值。但是every-visit采用的是，只要幕中出现状态s0，就统统计算其价值值，然后求平均，平均值就是s0的价值值。
（4）我们大多数是用every-visit方式。anyway，不管是first-visit还是every-visit，很多时候都是可以收敛的，所以这两种方法差别不大，你随便选一种即可。
4、小结
至此，我们使用蒙特卡洛方法就计算出了状态价值，有了状态价值就可以算出动作价值，有了动作价值就可以局部贪婪化的选取局部最优动作(也就是进行策略提升了)，局部最优动作就是新的策略，在新策略下又可以计算新的状态价值->新的动作价值->策略提升->新新策略->新新状态价值->....如此循环，当策略收敛后，就是我们要寻找的最优策略。
这就是蒙特卡洛强化学习的基本内容。现在回看其原理是不是特别特别简单和通俗易懂！
但是这里要重点说明的是，蒙特卡洛方法在工程实现上还有两个技巧：对于稳态环境问题，工程上一般是用增量来计算价值均值的；对于非稳态环境问题，一般是用指数移动平均来计算价值均值的。
至于什么是稳态、非稳态、什么是增量、什么是指数移动平均等概念，请参考我这篇文章：https://blog.csdn.net/friday1203/article/details/155787017?spm=1001.2014.3001.5501
一定一定得完全理解如何用增量和指数移动平均来计算价值均值，下面的时序差分和TD(λ)你才能看懂！
二、时序差分学习(Temporal-Difference Learning)
1、时序差分是用来解决什么问题的？
MC方法最大的缺点就是需要agent打完每一轮游戏，才能从游戏序列中计算状态价值。这样是非常低效的，比如有的游戏需要打10万轮才能策略收敛，一轮游戏需要1小时，那不要等到天荒地老了嘛。而且有的游戏是没有结束状态的，那MC就没法用了。所以此时时序差分学习诞生了。
所以时序差分是用来解决那种无法进行分幕的、非完备的MDP问题的。也所以时序差分学习也是一个无模型强化学习方法。
2、时序差分的基本描述和基本思想
（1）上图左边是时序差分的基本描述。中间是增量式every-visit的蒙特卡洛算法。右边是时序差分算法。将TD和MC放一起是因为TD是对MC的改进算法，二者对比讲比较好理解。
（2）A处：前面讲动态规划时的迭代策略评估中，当时就说那个迭代过程叫自举bootstrapping，就是从一组非收敛的状态价值迭代到一组收敛的状态价值！直白的说就是，通过一组预测值来预测另外一组预测值，就这样不断地预测，最后还能预测正确值。其实这也是强化学习最大的缺点，也是导致强化学习的收敛性一直都是一个行业问题。所以在很多复杂情况下，强化学习的收敛性一直是无法证明的。
那时序差分TD又是如何自举的呢？就是上图C处灰框中的式子，这个式子就是TD自举的过程。
（3）B处：上图B处是增量式蒙特卡洛算法的迭代过程。里面的α你可以看作第α步：
（4）C处：由于B处的计算得agent实实在在地打了很多步游戏，游戏中的每个状态都需要出现很多次，才能求出的才是期望Gt。所以MC算法是用实际回报来更新迭代状态价值的。但是很多时候，尤其是有些复杂游戏，状态个数非常多的游戏，是没法通过打很多很多步游戏来逼近真实的Gt的。
所以上图C处的TD算法就非常高明了，我想它大概是借鉴了贝尔曼期望方程的思路：整体无法求解，那我观察局部，我找出局部之间的关系，让一个无限循环的东西变成了一个递推式，就是无限变成了有限。就是游戏的步数是无限的，但游戏中的状态是有限的，我无法从无数的步数中算出Gt，那我可以列出有限状态之间的Gt的关系！所以TD迭代的是状态价值的递推式！所以TD用的是估计回报来更新迭代状态价值的。就类似动态规划中的迭代策略评估，通过预测值来预测另外一组预测值，一轮轮预测，最后也能收敛到真正的状态价值。
也所以TD算法的优点是只要采集当下动作的系统奖励和下一个转移状态即可。而MC的计算不仅需要当下动作的系统奖励还有当下状态以后的所有状态的奖励。当我们无法采集到很多后续状态奖励时，MC算法就无能为力了，此时TD算法就可堪大任。
3、小结
待续。。。。。
