AI学习笔记——Sarsa算法

in ai •  6 years ago  (edited)

上一篇文章介绍了强化学习中的Q-Learning算法,这篇文章介绍一个与Q-Learning十分类似的算法——Sarsa算法。

1. 回顾Q Learning

还是同样的例子,红色机器人在4x4的迷宫中寻找黄色的宝藏。找到宝藏,将会的到+1的奖励,如果掉进黑色陷阱就回的到-1的奖励(惩罚)。
image.png

首先回顾一下Q表如下

Q table (States\Actions)left (A1)right (A2)up (A3)down (A4)
S0-13-12
S112-11
..............

Q(S0,A2) = Q(S0,A2) + α[R(S1) + γ*maxa Q(S1,a)-Q(S0,A2)]

在Q Learning 算法中,当机器人处于S0的状态时,它的目标Q值是: R(S1) + γ*maxa Q(S1,a)。此时他还在S0的位置上,但是已经在计算S1上的最大Q值了。但是此时它并没有行动,也不一定会在S1采取Q值最大Q(S1, A2)的行动。因为我们提到,它还有10%的概率随机选择其他的行动 (ε贪婪方法(ε -Greedy method))。

2. Sarsa 行动派

在Sarsa算法中,机器人的目标是 R(S1) + γ* Q(S1,A),至于A是多少,完全取决于机器人实际上选择的哪一个Action。机器人有90%的概率会选择Q值最大的Action(A2),还有10%的概率会随机选择一个Action。

所以,Sarsa的算法是这样的。
image.png

除了其目标Q值与Q learning 有所不同之外,其他的都是一模一样的。

所以Sarsa是在线学习(On Policy)的算法,因为他是在行动中学习的,使用了两次greedy方法来选择出了Q(S,A)和q(S',A')。而Q learning离线学习(Off Policy)的算法,QLearning选择Q(S,A)用了greedy方法,而计算A(S',A')时用的是max方法,而真正选择的时候又不一定会选择max的行动。

Q learning 通过Max的函数,总是在寻找能最快获得宝藏的道路,所以他比较勇敢。而Sarsa 却相对谨慎。

3. Sarsa-lambda

Q learning 和 Sarsa都是单步更新的算法。单步跟新的算法缺点就是在没有找到宝藏之前,机器人在原地打转的那些行动也被记录在案,并更新了Q表,即便那些行动都是没有意义的。

Lambda(λ)这个衰减系数的引入,就是为了解决这个问题的。与γ用来衰减未来预期Q的值一样,λ是当机器人获得宝藏之后,在更新Q表的时候,给机器人一个回头看之前走过的路程的机会。相当于,机器人每走一步就会在地上插一杆旗子,然后机器人每走一步旗子就会变小一点。
Sarsa-lambda 的完整算法在这里:
image.png

注意,该算法与Sarsa 算法不同的地方就是多乘了一个E(s, a) (Eligibility Trace"不可或缺性值"),而这个E(s, a)又同时受γ和λ调控。并且在更新Q表的时候,不仅仅是更新一个Q(S,A),而是整个Q表所有的Q值都被更新了。


Thanks for reading my posts and welcome to comment. If you like my post , please upvote , resteem and follow me @hongtao
感谢您的阅读,欢迎留言,如果您喜欢我的帖子,请帮忙点赞、推送及关注我 @hongtao

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!