David silver强化学习课程第五课 模型无关的控制
第五课 模型无关的控制
回顾上节课，主要讲了Model-free情况下如何解决预测问题，通过求解某一策略下的值函数评价该策略，主要有蒙特卡洛(MC)和时间差分(TD)两种方法。本节课主要讲Model-free情况下的控制问题，也就是如何找到一个最优策略，同样的利用到了蒙特卡洛和时间差分两种方法。
本节集中解决Model-free的控制问题，由于缺乏环境信息，因此这是学习(Learning)过程而不是规划(Planning)过程，根据学习过程中代理是否利用自身经验改善策略，可以将强化学习分为两类：
**同策略学习(On-policy learning)：**代理基于自身的策略进行采样，根据采样信息优化自身的策略。换句话说，代理想要改善策略，必须要和环境进行交互，其采样的策略和优化的策略是同一个策略。
**异策略学习(Off-policy learning)：**代理基于其它策略的采样结果，优化自身的策略。也就是说代理可以利用先前学习到的策略，或者其它代理的策略，利用其它策略采样得到的奖励等信息，更新在自己策略下的价值函数。
1 同策略蒙特卡洛控制
回顾一下在动态规划中提升策略的两种方法：策略迭代和值迭代
策略迭代的两个关键步骤是策略评估和策略提升，如图所示这两步交叉进行。策略评估时利用贝尔曼最优方程计算状态值，策略提升时利用贪婪策略选择使状态值最大的动作。
注意，动态规划解决的是完全可观测的MDP问题，在策略评估时已知状态转移概率和奖励函数。
策略迭代中的策略评估使用贝尔曼期望方程，但是在Model-free环境下，我们需要采用采样的方法进行策略评估。上一节讲了MC和TD方法，可以用来策略评估。由于MC不是自举的，所以MC控制的思想类似于DP中的策略迭代，而不是值迭代。
在利用MC进行策略改善时，我们需要完成两个步骤：策略评估和策略提升。
与MDP不同，在Model-free的环境下，我们不知道当前状态的所有后续状态，也就是不知道状态转移概率，不知道在当前状态下采取什么动作更为合适。
可以看到，在MDP中进行策略改善时，需要知道状态转移概率才可以选择最合适的动作，而采取状态动作值Q(s,a)来代替状态值是Model-free的。这样我们就不需要知道整个模型，只需要知道在某个状态下采取什么什么样的行为价值最大即可。所以在策略评估时，我们计算每个状态的q值，随后根据q值改善我们的策略。
同时我们不知道环境的全部状态，所以使用贪婪策略不一定得到的是最优的策略。在这里为了探索其他的未知情况，策略提升时采取ε-贪婪方法：
每次进行策略提升时，有ε的几率选择使得q值最大的动作，有1-ε的概率选择其他动作。这保证了在任何的状态下，所有的动作都可以被选择。如果加上一个条件，希望在学习开始时代理有足够的探索，但是最终我们需要得到一个确定性的策略，消除这种随机性。我们可以在逐渐的增加代理选择使q值最大的动作的概率，减小其他动作选择的概率这就是有限探索的贪婪（Greed in the with Infinite Exploration）：
简单的可以让ε=1/k，ε就可以慢慢的减小到0。
总结一下上面提到的内容，我们得到蒙特卡洛迭代方法：
在策略评估时，我们不一定要迭代很多次使得q值收敛到qπ，只需要得到近似的qπ就可以改善策略，课程中称为蒙特卡洛控制：
最后给出蒙特卡洛控制的算法（这里是每一个episode都更新一下q值，参考叶强的博客也可以多个episode后更新q值）：
2 同策略时间差分控制
在第四课中我们提到过，相对于MC方法而言，TD方法有着更低的方差，不需要完成整个episode就能对值函数进行更新，也就是说，可以在episode中的每一个timestep进行在线的值函数估计。说到同策略时间差分控制，一个很自然的想法就是，直接将同策略蒙特卡罗控制中对值函数估计的MC方法换为TD方法，然后将每一个episode对值函数更新一次换为每一个timestep更新一次。我们将这种方法叫做Sarsa，该名字的由来见下图：
类似于MC控制，迭代示意图如下：
下面给出Sarsa的算法（与MC两点不同：策略估计改成TD方法，每个时间步更新一次q值）：
n-step Sarsa（将TD-target 更换为n步的qt）：
Forward view Sarsa(λ)
Backward view Sarsa(λ)
Sarsa(λ)算法如下：
3 异策略学习
如前面所说，在异策略学习中，想要学习的是一个策略，而实际用于采样的又是另外一个策略，相比于同策略学习，优点有：
- 可以从人类给出的示教样本或其他智能体给出的引导样本中学习
- 可以重用由旧策略生成的经验
- 可以在使用一个探索性策略的同时学习一个确定性策略
- 可以用一个策略进行采样，然后同时学习多个策略
在介绍异策略学习方法之前，先了解重要性采样：
可以通过这篇博客了解一下重要性采样是干嘛的：https://zhuanlan.zhihu.com/p/78720910?utm_source=wechat_session
结合重要性采样得到Off-Policy的MC和TD：
从上面两张ppt可以看出，实质上是利用一个采样策略得到的target来估计我们想要学习的策略。此外，我们知道，MC方法的方差本来就很大，而重要性采样将会使得方差急剧增大，因此结合重要性采样的MC方法就很难用了。对于TD方法来说，其方差本来就比MC要小得多，并且我们仅仅需要行为策略和目标策略在单个时间步上较为相似，因此其加权之后的方差也较小，所以这种方法的实用性较强。
可以这样理解：在状态s下，基于策略u产生动作At，然后进入新的状态St+1。现在基于策略u的观察信息来提升策略π，策略π选择动作At与策略u选择动作At的概率之比的大小说明了两个策略的相似程度。比值较大，说明两个策略在状态s下有相似的概率选择动作At，使用St+1的值更新St得到两个策略的支持。比值较小，相对于策略u策略π有更小的几率选择动作At，此时在策略u下得到的St+1的值对St的影响就比较小。
Q-learning
Q-learning是典型的Off-police TD算法，但是Q-learning不需要重要性采样。选择动作时采取行为策略u
，在更新q值时采取待评估的策略π
。
现在行为策略选择带有探索性的ε-贪婪策略，评估策略选择贪婪策略，那么上式可以简化为：
Off-police 控制的q-leaning算法如下：
为什么q-leaning不需要重要性采样？
目前我的理解还有些问题，后续补上。。。
4 TD和DP的关系
为什么q-leaning不需要重要性采样？
在单步更新的q-learning中，更新状态-动作值时，行为策略u没有选择动作a之前，我们并不知道更新哪个状态-动作值q，只有在行为策略u选择动作a之后，我们才知道要更新的q(s,a)，此时采用目标策略π更新q值时已经不涉及行为策略u的动作选择概率。因为要更新的q(s,a)已经确定，不存在概率问题，所以不需要进行重要性采样。所以单步更新的q-learning不管行为策略u选择什么样的策略，它要更新的q(s,a)都是确定的，不需要重要性采样。
而在更新多步的的q-learning中，由于第二个及后续的奖励Rt都是根据ε-贪婪策略得到的，所以涉及概率选择的问题，此时要引入重要性采样。
4 TD和DP的关系
参考资料：https://blog.****.net/u013745804/article/details/78196834
https://zhuanlan.zhihu.com/p/55788587