前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >《强化学习》中的时序差分控制:Sarsa、Q-learning、期望Sarsa、双Q学习 etc.

《强化学习》中的时序差分控制:Sarsa、Q-learning、期望Sarsa、双Q学习 etc.

作者头像
Piper蛋窝
发布2020-11-19 17:24:04
1K0
发布2020-11-19 17:24:04
举报
文章被收录于专栏:Piper蛋窝Piper蛋窝

前言: 学习了 Sutton 的《强化学习(第二版)》第6章时序差分学习的控制部分,将笔记提炼如下。

笔者阅读的是中文书籍,所提到的公式,笔者将给出其在英文书籍上的页码。英文书籍见 Sutton 个人主页:http://incompleteideas.net/book/the-book.html

本次笔记内容:

  • 6.4 Sarsa:同轨策略下的时序差分控制
  • 6.5 Q 学习:离轨策略下的时序差分控制
  • 6.6 期望 Sarsa
  • 6.7 最大化偏差与双学习
  • 6.8 游戏、后位状态和其他特殊例子
  • 6.9 本章小结

在上一次笔记中,我们讨论了 动态规划( Dynamic Programming, DP )、蒙特卡洛方法( Monte Carlo Method, MC )与时序差分学习( Temporal Difference Learning, TD )的异同,以及时序差分学习中的预测算法。本次笔记中我们讨论其控制部分算法,其概述如下。

  • Sarsa 是同轨策略下的时序差分控制,;
  • Q-learning 是离轨策略下的时序差分控制;
  • 期望 Sarsa 的表现比上述二者表现都更好( van Hasselt, 2011),并且被称为“广义 Q 学习”;
  • 然而,单纯的最大化操作带来了“最大化偏差”,因此我们提出“双学习”来消除“最大化偏差”;
  • 此外,我们还引出了如“后位状态”的概念,没有具体讨论。

书中展示了4段实例, Zhang 都有相应代码进行实现,分别介绍如下知识点:

  • 有风的网格世界(Example 6.5: Windy Gridworld)介绍 Sarsa 的性能;
  • 在悬崖边行走(Example 6.6: Cliff Walking)对比了基于-贪心方法的 Sarsa 与 Q-learning 的控制效果;
  • 接着,在介绍 期望 Sarsa 时也使用了 Cliff Walking 实例对其效果进行展示;
  • 最大化偏差实例(Example 6.7: Maximization Bias Example)用于表达:双 Q 学习优于 Q 学习。

我对其代码进行了标注,请见https://github.com/PiperLiu/Reinforcement-Learning-practice-zh/blob/master/practice/05-02-Temporal-Difference-Control.ipynb。并且,我还由代码及实验结果,复述了我对于书上提出的算法对比特性的理解。

Sarsa

基于同轨策略,其更新公式为:

可以看出与之前“时序差分预测”中的价值预测公式很像。

如果 是终止状态,那么则定义为0。这个公式用到了元组,因此该算法命名为 Sarsa 。

Sarsa 想要以1的概率收敛到最优的策略和动作价值函数,需要满足2个条件:

  1. 所有的“状态-动作”二元组都被无限多次访问到;
  2. 贪心策略在极限情况下能够收敛(收敛过程可以通过令 来实现)。

算法框架中,每幕中的每步都要更新 Q ,不具体展示框架了,可见书第6章。

Q-learning

更新公式为:

只是变了个更新公式而已,连算法框图都没变,为什么说 Q-learning 是离轨策略呢?

  • 书上的解释:In this case, the learned action-value function, Q, directly approximates q*, the optimal action-value function, independent of the policy being followed.
  • 我的理解:在公式中用于更新的动作为 ,而下一步却未必是 ,因此为离轨策略。

我的理解方式没有错,并且,这个理解会辅助对于“最大化偏差”部分的学习。

期望 Sarsa

虽然计算上更为复杂,但它消除了 Sarsa 中因为随机选择 而带来的方差。并且,对于 cliff walking 中的情况,期望 Sarsa 将保持 Sarsa 相对于 Q-learning 的“能学到迂回策略”的优势。

最大化偏差与双学习

最大化偏差

上述算法中,通常是基于 贪心 来产生策略的,这其中都用到了“最大化操作”。

但是,如果在估计值的基础上进行最大化操作,就是隐式地对最大值进行估计,而这就会产生一个显著的正偏差。例子如下。

如图的MDP,A为起点,做动作 left ,则0收益;做动作 right ,之后获得的收益服从 正态分布 N(-0.1, 1)。

我们知道最优策略应该是 100% 做动作 left 。

但是,如果使用了最大化操作,动作 right 的估计值是不确定的,有些可能大于0,则估计值的最大值就产生了正数,就产生了正偏差。就是最大化偏差。

双学习

双学习可以消除最大化偏差。双学习使用了2倍的内存,但计算量无需双倍。

以双Q学习为例:

使用 来估计 ,而 负责估计 ,由于 ,因此这个估计是无偏的。

即更新公式换为:

后位状态

后位状态我读了两遍,差不多明白了其意思:类似下棋的游戏中,可以由不同的状态,经过不同的动作,达到同一状态(棋盘摆放位置同),我们叫这个为后位状态。在这种情况中,后位状态显然更为重要。这很有趣,应该找些实例继续了解。

Van Roy, Bertsekas, Lee, Tsitsiklis, 1997; Powell, 2011 对其进行了研究。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-01-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Piper蛋窝 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Sarsa
  • Q-learning
  • 期望 Sarsa
  • 最大化偏差与双学习
    • 最大化偏差
      • 双学习
      • 后位状态
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档