BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

无痛的增强学习入门:差分时序法

| 作者 冯超 关注 7 他的粉丝 发布于 2017年11月3日. 估计阅读时间: 13 分钟 | QCon上海2018 关注大数据平台技术选型、搭建、系统迁移和优化的经验。

系列导读:《无痛的增强学习入门》系列文章旨在为大家介绍增强学习相关的入门知识,为大家后续的深入学习打下基础。其中包括增强学习的基本思想,MDP框架,几种基本的学习算法介绍,以及一些简单的实际案例。

作为机器学习中十分重要的一支,增强学习在这些年取得了十分令人惊喜的成绩,这也使得越来越多的人加入到学习增强学习的队伍当中。增强学习的知识和内容与经典监督学习、非监督学习相比并不容易,而且可解释的小例子比较少,本系列将向各位读者简单介绍其中的基本知识,并以一个小例子贯穿其中。

7 差分时序法

7.1 蒙特卡罗的方差问题

上一节我们介绍了蒙特卡罗法,它可以比较好地解决无模型场景下的蛇棋问题。当然,它也存在着一定的不完美,这些不完美体现在很多方面,接下来我们就来看一看其中的一个问题——估计值的方差问题。

前面我们已经知道,蒙特卡罗是用一系列的模拟游戏得到一些episode的回报信息,然后用这些回报信息求平均,就可以得到估计的价值函数。这个方法从理论上讲是没有问题的,它能够成立的根本在于概率论中的大数定理。大数定理也是没有问题的,可是大数定理只说明了收敛性,并没有说明收敛的速度。很显然,如果采样序列的方差比较大,那么想要让它收敛就需要更长的时间,如果采样序列的方差较小,那么收敛的速度也会相应地降低。

基于上面的分析,我们就来看看前面的蒙特卡罗法存不存在方差方面的问题。我们用上一节的方法进行计算,同时保存state=50,action=1的return值,将所有的值综合起来做成一个直方图,如图7-1所示。

图 7-1 蒙特卡罗法every-visit的return收集直方图

可以看出,return的跨度还是比较大,这样模型就不太容易收敛。

当然,跨度大和其他问题也有关系,其中一个关系就是episode中的采样频率。上一节采用的方法叫做"every-viist",也就是说episode中的每一个state-action对都会参与到计算当中,这样就为统计带来了困难。因为在蛇棋这个游戏中,由于有梯子的存在,某一个位置可能被走过两次。比方说例子中的位置“50”,我们在计算的过程中没有区分第一次到达“50”和第二次到达“50”,而且将这两个return直接加在了一起,由于这两次的return一定有差异,因此这样的统计方式会让方差增大,从而难以收敛。

那么该如何应对这个问题呢?一个解决方案是把"every-visit"方法换掉,改成"first-visit"法。所谓的"first-visit"法就是只统计第一次出现的状态,对于后面出现的同一状态则不再统计。从方法的理念来说,同一个episode内因多次出现同一状态而造成方差增大的问题将得到解决。下面就来看看"first-visit"的结果:

图7-2 蒙特卡罗法first-visit的return收集直方图

从结果来看,first-visit的效果稍有提高,但是并没有明显的提高。因为即使只取一个不重复的状态,我们仍然会遇到不同情况的first-visit,每种之间的数值差距依旧很大。

既然蒙特卡罗法存在着这样一些遗憾,那么我们就来看看接下来介绍的方法:差分时序法(Temporal Difference)。

7.2 差分时序

差分时序法是一种结合了蒙特卡罗法和动态规划法的方法。从算法的主体结构来看,它同蒙特卡罗法类似,同样通过模拟episode的方式进行求解;从算法的核心思想来说,它有用到了增强学习中的经典公式——Bellman公式进行自迭代更新。

前面提到状态-行动价值函数的Bellman公式的形式为:

\(q(s,a)=\sum_{s'}p(s'|s,a)[R + \sum_{a'} \pi(a|s')q(s',a')]\)

那么利用蒙特卡罗的方法,我们就可以将公式变为:

\(q(s,a)=\frac{1}{N} \sum_{i=1}^N [R(s'_i)+q(s'_i,a'_i)]\)

当然,这个公式还可以变成前面蒙特卡罗法中实际应用的形式:

\(q_t(s,a)=q_{t-1}(s,a)+\frac{1}{N}[R(s')+q(s',a')-q_{t-1}(s,a)]\)

从这个公式我们可以看出这个方法和蒙特卡罗、动态规划的关系来。下面我们就来实现这个方法,我们首先要实现的方法被称为"SARSA",这个名字看上去有些奇怪,其实它来自于这个方法的五个关键因子:S(待求状态),A(待求行动),R(模拟得到的奖励),S(模拟进入的下一个状态),A(模拟中采取的下一个行动)。

7.3 On-policy:SARSA

接下来就来实现这个算法,其实它的实现过程也比较简单,这里只展现评估的过程:

for i in range(episode_num):
env.start()
state = env.pos
prev_act = -1
while True:
act = self.policy_act(state)
reward, state = env.action(act)
if prev_act != -1:
return_val = reward + (0 if state == -1 else self.value_q[state][act])
self.value_n[prev_state][prev_act] += 1
self.value_q[prev_state][prev_act] += (return_val - \
self.value_q[prev_state][prev_act]) / \
self.value_n[prev_state][prev_act]

prev_act = act
prev_state = state

if state == -1:
break

那么这个代码的实现效果如何呢?我们同样写一段测试的代码。

def td_demo():
np.random.seed(0)
env = Snake(10, [3,6])
agent = MonteCarloAgent(100, 2, env)
with timer('Timer Temporal Difference Iter'):
agent.td_opt()
print 'return_pi={}'.format(eval(env,agent))
print agent.policy

agent2 = TableAgent(env.state_transition_table(), env.reward_table())
with timer('Timer PolicyIter'):
agent2.policy_iteration()
print 'return_pi={}'.format(eval(env,agent2))
print agent2.policy

为了试验效果,我们将SARSA算法中的迭代轮数增加到2000,最终的结果为:

Timer Temporal Difference Iter COST:3.8632440567
return_pi=80
[0 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0]
policy evaluation proceed 94 iters.
policy evaluation proceed 62 iters.
policy evaluation proceed 46 iters.
Iter 3 rounds converge
Timer PolicyIter COST:0.330899000168
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]

从结果可以看出,SARSA算法的效果并不够好,当然我们还没有加入更多的策略来提升效果。不过看上去它的结果还不及蒙特卡罗,那么它和蒙特卡罗相比有什么优势呢?我们来看看前面提到的方差问题,再来看一看SARSA算法的结果图:

图7-3 TD法的return收集直方图

可以看出,这个方法的数值变动和前面相比要更为稳定一些,跨度比之前要小一些。

那么为什么TD系列的方法会在方差方面控制得更好一些呢?答案就在它的更新公式上。蒙特卡罗的计算方法由于使用了精确的return,所以在对价值的估计上更精确一些,但是同时它要一个序列的信息,而序列的信息存在更多的波动,所以方差会比较大;而TD方法只考虑了一步的计算,其余的计算均使用了之前的估计,所以当整体系统没有达到最优时,这样的估计都是存在偏差的,但是由于它只估计了一步,所以它在估计值方面受到的波动比较少,因此带来的方差也会相应减少许多。

所以前人们发现,蒙特卡罗法和TD法象征着两个极端——一个为了追求极小的误差而放松了方差,一个为了缩小方差而放松了误差。这个问题仿佛回到了机器学习的经典问题——bias和variance的权衡问题。

那么,除了SARSA这一种方法,还有没有别的算法呢?最后一节我们再来看看TD的另一种算法。

作者介绍

冯超,毕业于中国科学院大学,猿辅导研究团队视觉研究负责人,小猿搜题拍照搜题负责人之一。2017年独立撰写《深度学习轻松学:核心算法与视觉实践》一书,以轻松幽默的语言深入详细地介绍了深度学习的基本结构,模型优化和参数设置细节,视觉领域应用等内容。自2016年起在知乎开设了自己的专栏:《无痛的机器学习》,发表机器学习与深度学习相关文章,收到了不错的反响,并被多家媒体转载。曾多次参与社区技术分享活动。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT