Warning: session_start() expects parameter 1 to be array, string given in /www/wwwroot/blog/wp-includes/class-wp-hook.php on line 288
强化学习——时序差分算法 | 野风
  • 欢迎访问我的个人博客,如遇博客图片无法显示,请用IE浏览器访问。
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧!

强化学习——时序差分算法

强化学习 野风同学 1年前 (2020-06-22) 1756次浏览 0个评论 扫描二维码

学习目标

  1. 理解TD(0)的预测(prediction)问题;
  2. On-policy控制(control)算法SARSA;
  3. Off-policy控制(control)算法Q-learning;
  4. TD算法相对于MC算法和DP算法的优势;

简介

这次要介绍的时序差分(Temporal-Difference)算法应该是强化学习中最为核心的算法了,它结合了前面讲到的动态规划和蒙特卡洛算法。如蒙特卡洛算法一样,它不需要知道具体的环境模型,可以直接从经验中学习;另一方面,继承了DP算法的自举(bootstrap)方法,可以利用学到的估计值来更新,而不用等到一个episode结束后再更新。三种算法的control问题,即找到最优策略都是使用广义的策略迭代,主要不同在于prediction问题,即根据当前策略估计值函数。

TD算法的Prediction问题

如果还不清楚prediction和control问题具体指什么,可以看看我上一篇文章。TD算法和MC算法都是基于经验去解决预测问题,给出一些基于策略\pi 的样本估计状态 S_{t} 下的值函数 v_{\pi}MC算法是等到一个episode结束得到return以后再借此更新 V\left(S_{t}\right),如下图所示

TD算法在这里就不同,它是每过一个time step就更新一次,利用奖励 R_{t+1} 和值函数V\left(S_{t+1}\right),当然,这里所说的one-step TD 方法,也可以两步一更新,三步一更新…..是不是等到N步以后再更新就是蒙特卡洛算法了?对,就是这么一回事。


既然这两种方法的backup图都贴出来了,也把DP算法的图贴出来对比着看吧。

TD(0)算法的伪代码如下

其中\delta=R+\gamma V\left(S^{\prime}\right)-V(S)称为TD误差(error)。

比较了三种算法的不同,那TD算法的优势何在?要回答这个问题,可能得写本书了,我这里只简单提几点,更多的还得去看书和看文献。很显然,TD算法相对于DP算法优势在于它不需要知道环境的模型,这也是符合实际问题的,绝大部分情况下我们都不可能建立一个精确的模型来描述一个问题。相较于MC算法,TD算法不需要等到episode最后才能更新值函数,而是一个time step就可以更新一次。因为有可能一个episode会花很长时间,比如玩一个游戏,需要几个小时才能结束一个回合,那么我几个小时才能得到一个回报,训练完一个算法不知道要花多久了。换句话说,MC算法训练成本太高,这点上TD算法就显得很有优势了。

那在有限的数据下,TD算法一定能收敛吗?答案是一定会收敛,经过证明只要step size足够小,对于任何策略\pi,TD(0)都能收敛到 v_{\pi} 。那么这三种方法谁收敛的更快一些呢?这就不一定了,好像没有谁在数学上证明过在收敛速度上谁更有优势。

TD算法的Control问题

Sarsa算法

在面对exploration和exploitation的两难时,算法又分为了两类:on-policy和off-policy算法。Sarsa是一种on-policy TD算法。我们去学习一个最优的动作-状态值函数而不是状态值函数。

Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma Q\left(S_{t+1}, A_{t+1}\right)-Q\left(S_{t}, A_{t}\right)\right]

Sarsa算法的原始策略和更新策略是一致的,而其更新策略和MC不一样的是其策略更新不需要采样一个完整的轨迹,在执行完一个动作后就可以更新其值函数。如果 S_{t+1} 是终止状态,则Q\left(S_{t+1}, A_{t+1}\right)定义为0。之所以叫Sarsa,是因为迭代算法中的五个元素 \left(S_{t}, A_{t}, R_{t+1}, S_{t+1}, A_{t+1}\right) 。其伪代码如下图:

Q-learning算法

Q-learning是一种off-policy算法,更新方法如下

Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha\left[R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)\right]


与Sarsa只有一点不同,就是在更新 S_{t} 的动作值函数的时候需要 S_{t+1} 的动作值函数,那状态 S_{t+1}下的动作怎么选呢?Sarsa用的是\varepsilon- greed y 方法,和选择S_{t}下的动作一样;而Q-learning是用的 greed 方法,和选择 S_{t} 下的动作不一样,因此称为off-policy。

总结

本文简单地介绍了时序差分算法,在prediction问题方面着重与MC和DP方法作比较,因为它就是两者的结合。在control问题上分别介绍了on-policy方法:Sarsa和off-policy方法:Q-learning。当然,算法肯定不只有这两种,比如还有Expected Sarsa和Double Q-learning等等。除了on-policy和off-policy方法外,还有一种actor-critic方法,这是后面要学习的内容,具体到更为细分的算法,那就太多太多了……

学习资料

[1] Reinforcement Learning: An Introduction- Chapter 6 Temporal-Difference Learning
[2] David Silver's RL Course Lecture 4&5


《Reinforcement Learning: An Introduction 第二版》PDF书籍与David Silver课程,欢迎关注我的公众号“野风同学”,回复“RL”即可获取。
一个程序员的自我成长之路,持续分享机器学习基础与应用、LeetCode面试算法和Python基础与应用等技术干货文章,同时也经常推荐高质量软件工具、网站和书籍。


本站提供的一切软件、教程和内容信息仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑或手机中彻底删除上述内容。如果您喜欢该程序,请支持正版,购买注册,得到更好的正版服务。如有侵权请邮件与我们联系处理。敬请谅解!
喜欢 (0)
[打赏赞助]
分享 (0)
野风同学
关于作者:
我是野风同学,这是我的主页。
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址