“AI 技术+人才”如何成为企业增长新引擎?戳此了解>>> 了解详情
写点什么

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

  • 2017-11-02
  • 本文字数:3303 字

    阅读完需:约 11 分钟

系列导读:《无痛的增强学习入门》系列文章旨在为大家介绍增强学习相关的入门知识,为大家后续的深入学习打下基础。其中包括增强学习的基本思想,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]
{1}
prev_act = act
prev_state = state
{1}
if state == -1:
break
{1}

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

复制代码
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 年起在知乎开设了自己的专栏:《无痛的机器学习》,发表机器学习与深度学习相关文章,收到了不错的反响,并被多家媒体转载。曾多次参与社区技术分享活动。

公众号推荐:

2024 年 1 月,InfoQ 研究中心重磅发布《大语言模型综合能力测评报告 2024》,揭示了 10 个大模型在语义理解、文学创作、知识问答等领域的卓越表现。ChatGPT-4、文心一言等领先模型在编程、逻辑推理等方面展现出惊人的进步,预示着大模型将在 2024 年迎来更广泛的应用和创新。关注公众号「AI 前线」,回复「大模型报告」免费获取电子版研究报告。

AI 前线公众号
2017-11-02 17:502664

评论

发布
暂无评论
发现更多内容

为什么选择华为云CDN?这些案例告诉你

轶天下事

阿里技术官神作!大厂亿级流量性能调优学习手册,堪称保姆级教学

做梦都在改BUG

Java 性能优化 性能调优

mac上好用的效率软件:Alfred 5 激活版

真大的脸盆

Mac Mac 软件 效率软件

亿级日活业务稳如磐石,华为云CodeArts PerfTest发布

华为云开发者联盟

云计算 后端 华为云 华为云开发者联盟 企业号 4 月 PK 榜

HashData认证云原生数据仓库管理工程师培训报名开启!

酷克数据HashData

Spring Boot 整合 Redis 基于 Stream 消息队列 实现异步秒杀下单

Java你猿哥

Java redis stream ssm 消息队列

本铯智能科技是家怎样的共享电动车厂家?

共享电单车厂家

共享电动车厂家 共享电单车厂商 本铯智能科技 本铯智能电动车厂家

使用Pinia:让Vue状态管理更简单

格斗家不爱在外太空沉思

Pinia 三周年连更

终于可以彻底告别手写正则表达式了

Java你猿哥

Java ssm 表达式 GPT

openEuler NFS+协议全新发布:实现NAS存储性能与可靠性倍增

openEuler

Linux 操作系统 存储 openEuler

算法题每日一练: 青蛙跳台阶

知心宝贝

数据结构 算法 前端 后端 三周年连更

聊聊 IP packet 的 TTL 与 tcp segment 的 MSL

明哥的IT随笔

TCP/IP TTL MSL

华为云智能云接入ICA,让世界距离更近

YG科技

华为云文字识别OCR-助力企业办公智能化不断发展

轶天下事

华为云CDN助力企业网速腾飞!

轶天下事

与全球开发者创新共赢,全球首个“开发者村” 正式落成

Geek_2d6073

华为云搜索服务CSS,助力企业挖掘数据价值

轶天下事

区块链基础设施 NFTScan 新增支持 Aptos 网络

NFT Research

区块链+ NFT

运维报表有哪些内容?有什么用?

行云管家

运维 报表 IT运维 容器化部署

逆天!腾讯大神纯手撸“架构师速成手册”Github狂获4.5kstar

Java你猿哥

Java 架构 ssm 架构设计 架构师

华为云医疗智能体,助力医疗健康加速智能化

YG科技

华为云,用科技开启智慧化生活

轶天下事

人脸活体检测初识

六月的雨在InfoQ

人脸活体检测 三周年连更 人脸数据库 人脸辨识度

从此脱离CRUD!Github热榜第三架构师速成手册成功颠覆了我的认知

Java你猿哥

架构 ssm 架构设计 架构师 微服务实战

一文详解多模态认知智能

华为云开发者联盟

人工智能 华为云 AIGC 华为云开发者联盟 企业号 4 月 PK 榜

裸辞底气!GitHub飙升“java面试笔记2023” 了解下八股文天花板

Java你猿哥

Java 面试 Spring Boot ssm 八股文

devops|中小公司效率为王,没必要度量

laofo

DevOps 研发效能 工程效率 效能度量 研发效能度量

设计模式的故事之三:责任链模式

Java你猿哥

Java 设计 ssm 责任链模式 责任链

爆肝Java九大核心专题,666页内容,我收割了5个大厂offer

Java你猿哥

Java MySQL JVM 消息队列

华为云云速建站,助力企业搭建网站省心又省力

YG科技

阿里限量的性能调优+微服务+高并发设计,真的太香了!

做梦都在改BUG

Java 微服务架构 系统设计 性能调优 亿级并发

无痛的增强学习入门:差分时序法_语言 & 开发_冯超_InfoQ精选文章