Sarsa-lambda

Sarsa-lambda
Q learning 和 Sarsa都是单步更新的算法。单步跟新的算法缺点就是在没有找到宝藏之前，机器人在原地打转的那些行动也被记录在案，并更新了Q表，即便那些行动都是没有意义的。
Lambda(λ)这个衰减系数的引入，就是为了解决这个问题的。与γ用来衰减未来预期Q的值一样，λ是当机器人获得宝藏之后，在更新Q表的时候，给机器人一个回头看之前走过的路程的机会。相当于，机器人每走一步就会在地上插一杆旗子，然后机器人每走一步旗子就会变小一点。

Sarsa(lambda)算法是Sarsa 的改进版，二者的主要区别在于：

在每次take action获得reward后，Sarsa只对前一步Q(s,a)进行更新，Sarsa(lambda) 则会对获得reward之前的步进行更新。
Sarsa(lambda)算法的流程如下：

从上图可以看出，和Sarsa相比，Sarsa(lambda)算法中多了一个矩阵E (eligibility trace)，它是用来保存在路径中所经历的每一步，因此在每次更新时也会对之前经历的步进行更新。

参数lambda取值范围为[0, 1] ，如果 lambda = 0，Sarsa(lambda) 将退化为Sarsa，即只更新获取到 reward 前经历的最后一步；如果 lambda = 1，Sarsa(lambda) 更新的是获取到 reward 前的所有步。lambda 可理解为脚步的衰变值，即离奶酪越近的步越重要，越远的步则对于获取奶酪不是太重要。

image.png

和Sarsa相比，Sarsa(lambda)算法有如下优势：

Sarsa虽然会边走边更新，但是在没有获得奶酪之前，当前步的Q值是没有任何变化的，直到获取奶酪后，才会对获取奶酪的前一步更新，而之前为了获取奶酪所走的所有步都被认为和获取奶酪没关系。Sarsa(lambda)则会对获取奶酪所走的步都进行更新，离奶酪越近的步越重要，越远的则越不重要（由参数lambda控制衰减幅度）。因此，Sarsa(lambda) 能够更加快速有效的学到最优的policy。
在算法前几回合，老鼠由于没有头绪, 可能在原地打转了很久，从而形成一些重复的环路，而这些环路对于算法的学习没有太大必要。Sarsa(lambda)则可解决该问题，具体做法是：在E(s,a)←E(s,a)+1这一步之前，可先令E(s)=0，即把状态s对应的行置为0，这样就只保留了最近一次到达状态s时所做的action。

image.png