一条咸鱼的强化学习之路5之无模型控制（On-policy & Off-policy）
一条咸鱼的强化学习之路<5>
之无模型控制（On-policy[MC,TD] & Off-policy[Q-Learning]）
上节课中，我们主要学习了基于MC和TD的无模型预测方法，当你在无model情况下对一个策略进行完评估以后，那么问题来了，我们下一步如何去优化？如何去找更好的策略？通过前边的课程，我们知道，control的方法主要就是by acting greedy，在价值评估的基础上通过使用贪婪策略可以保证我们不断的能选取更好的策略继而最终收敛到π*,V*。那么我们这里同样也使用贪婪策略行不行？答案是否定的，原因有两个，第一：运用原来的greedy policy，我们需要往前走一步看其状态价值函数（V），但这次我们是无model的，不清楚MDP，所以下个状态的价值函数也就不得而知了，第二：我们在没有环境model的情况下取值都是通过sample的方式，而如果就在我们sample取值的基础上就直接acting greedy的话，最终得到的策略可能只是一个局部最优的，因为全局最优的可能我们就根本没探索到！正所谓才疏学浅，眼界如井底之蛙，仅可窥天空一斑尔。
不过话又说回来，这些也都不是问题，针对第一个问题，我们可以用动作价值函数Q来代替状态价值函数V，这样就不用考虑MDP的状态价值函数问题啦！针对第二个问题，我们提出了greedy policy的变种ε-greedy policy, 其实说白了就是把原来这个greedy policy分成了两部分，一部分还继续按照原方法贪婪着找最优（概率为1-ε），另一部分就负责随机探索着未知的区域（概率为ε），这样一来就能够去平衡Exploitation和Exploration的问题了。其中有一张ppt还证明了为啥在ε-greedy 下的π’要优于之前的π。这里边也许会有人想整个过程的速率估计太慢了，特别是对于MC而言，要先完全评估下当前的策略再control，简直是磨磨唧唧的，不能忍，那么其实我们也可以不用完全的去评价一个策略，可以走几步看看，如果已经获取了足够的信息来引导进入下一个更好的策略中的话，那就可以直接采用ε-greedy优化就好，如图1。
图 1: 对MC Control过程的优化
恩，这么看的话的确也是个蛮不错的方法，既可以保持不断探索，又可以在探索到的策略基础上进行优化，那么理论上我们肯定可以最终找到个不错的策略，不是么？Too young too naive...其实问题又来了，我们的确是希望他最终能收敛到一个最好的策略，但是他只要还在探索就木有个头啊……所以我们引入了GLIE的概念，即Greedy in the Limit with Infinite Exploration，顾名思义啊，就是探索也要有个限度，它有两个特征，一个所有的（s，a）都要探索数次，保证小角落也能探索到，再一个就是最终要能收敛，找到最优的policy就别探索啦。举个列子来说，如果在ε-greedy policy里边，我们令ε= 1/k，那么在k足够大时候，探索的概率就接近0，此时的ε-greedy就是GLIE。也可能这只是个简单的例子吧，因为谁知道当ε趋近0时候到底整个状态空间它探索完了没呢……或许还有更好的方法。
所以吧，我们的第一个完整算法就这样产生了，GLIE-MC Control，具体的过程描述见下表，但是这种算法不算完美，别忘了我们还有更加灵活的TD，相比较MC而言，TD的方差更低，可以进行在线学习（online，应该就是指TD可实时更新的特点，对应的是MC的整个episode才更新的offline方式），所以我们考虑用TD来做Control，也用行动价值函数Q（S，A）来做评估，用ε-greedy policy来提升，然后每步都更新，这种方法根据其行动特点也有另外一个名字：“Sarsa”，具体见下表。理论上，Sarsa最终也会收敛到最优的行动价值函数，但要注意的两点是，第一，要确保用的是ε-greedy policy，第二，要主要步距的大小，一方面要足够大继而保证Q值能扩展到任何你所期望的位置，另一方面要保证Q的变化越来越小最终稳定，否则会一直有噪音浮动。尽管理论如此，DS又说实际上我们有时候并不考虑以上因素，Sarsa照样坚挺……无语……
Sarsa就是往前看了一步，根据前几节的尿性，你觉得他们会满足于只往前看一步么？要是只看一步不靠谱咋办？所以，你懂的，n-step Sarsa应运而生，所以这里边的n-step Q-return就成了:
然后往前看了n步还是觉得不靠谱，所以还要把往前看的这n步加权平均下心里才舒服，那么Forward View Sarsa（λ）又出现了！这里边，Q(St, At) ← Q(St , At) + α q t λ− Q(St , At)
。接下来，向前的Sarsa（λ）已经有了，它还是需要等到走完一遍才能进行更新Q的算法，所以也不算是online的，我们想要能实时更新的。那么向后的Sarsa（λ）（Backward View Sarsa(λ)）还会远么？不远了！这不跟着资格跟踪（Eligibility Traces）就来了嘛！eligibility
trace算是online的，对应着每一个s，a都会有一个eligibility trace，刚开始为0（E0(s,a) = 0），然后Et(s,a) = γλEt−1(s,a) + 1(St = s, At=a)，即每次在某个状态s执行某个动作a，其对应的Eligibility trace就会加1，然后随着步数的增加，又会不断地decay（因为前边的系数），这就相当于我们真的是在标记我们走过的路啊，然后最后拿到奖励的时候就能第一时间分析出来我们这条路中到底哪个行动起了作用。这里边，TD-error δt = Rt+1 + γQ(St+1, At+1)− Q(St,At)，然后Q(s,a) ← Q(s, a) + αδtEt(s, a)，整体来看，这个形式和Forward View Sarsa（λ）其实基本一致，只不过多了个Eligibility Traces，具体算法过程见下表。
话说到这里，也基本上到了分水岭。上边讲的都是on-policy control，那么对应的也会有off-policy control，也就是我们标题所反应的。我个人理解，on-policy就是采用我们自己的策略进行采样评估学习，MC，TD都是这范畴里边的，就是下一步的action就是基于当前待评估的策略选出来的，而off-policy就是在我们自己策略的基础上对别人的策略进行采样评估学习，再具体一点，就是评估目标策略policy π（a|s）以计算Vπ(s)或者qπ(s,a)，但是采取行动的话确实根据policyµ(a|s)，{S1,A1, R2, ..., ST } ∼µ，这样做的好处有很多，通俗的讲就是可以提升开拓我们的眼界，我们可以去学其他人是怎么做的。然后这里又涉及到一个叫Importance
Sampling的概念，是用来评估另外一个不同的分布的期望的方法。当用在OffPolicy的MC上时会极大的增加方差，所以实际中也没什么卵用。对于TD来说会好一点。
我们着重想讲的是Q-Learning，没错，就是那个大名鼎鼎的Q-Learning。Q-Learning主要思想是对行动价值函数Q(s,a)进行off-policy学习，而且不需要什么importance sampling。它的下个行动的选取是基于policy At+1∼ µ(·|St)，但我们同时也考虑可选的后续的行动A’ ∼ π(·|St),并且向着该方向更新Q值：Q(St,At)← Q(St, At)+ α (Rt+1 + γQ(St+1,A’ ) − Q(St , At) )。接下来我们要同时优化行为和目标策略。对目标策略π使用greedy，π(St+1) = argmaxQ(St+1,a’ )，对行动策略µ使用ε-greedy，所以Q-Learning target就可写为Rt+1 + max γQ(St+1, a’ ),具体比较见下表。
本节课大致内容如此，感觉讲了不少东西，一篇心得下来脑子快转不动了……还没来得及看代码，不过Q-Learning的可以参照之前第二篇中的迷宫寻宝例子进行理解，基本原理就 Bellman
Optimality Equation，欢迎讨论，咸鱼天。
本节课中文字幕DS视频：David Silver深度强化学习课程 第5课 - 免模型控制
github大神代码实现：dennybritz/reinforcement-learning
