免费下载案例集|20+数字化领先企业人才培养实践经验 了解详情
写点什么

无痛的增强学习入门:蒙特卡罗方法

  • 2017-10-12
  • 本文字数:3984 字

    阅读完需:约 13 分钟

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

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

无痛的增强学习入门:基本概念篇

无痛的增强学习入门: 增强学习形式化

无痛的增强学习入门:策略迭代

无痛的增强学习入门:价值迭代

无痛的增强学习入门:泛化迭代

下面是第六篇。

6 蒙特卡罗方法

6.1 真正的增强学习

本节我们来看看无模型的一种简单解决方法——蒙特卡罗法。从名字可以看出,当我们无法得到模型内容时,就需要通过不断模拟的方式得到大量相关的样本,并通过样本得到我们预期得到的结果。通过这样的方式,我们似乎又可以前进了。

在前面的策略迭代中,我们曾经总结了一轮迭代过程中的几个主要步骤:

  1. 策略评估
  2. 策略改进

其中与模型相关的是策略评估部分,既然没有了模型,我们就需要使用蒙特卡罗的方法得到。因为在之前的策略迭代法有模型信息,所以它只需要评估状态价值函数——也就是 v(s),然后根据 Bellman 公式:

\(q(s,a)=\sum_{s’}p(s’|s,a)(R+v(s’))\)

求出状态 - 行动价值函数,并进行策略改进。现在我们没有了模型,不知道状态转移的情况,于是就需要对状态 - 行动价值函数进行估计。我们将

\(q(s,a)=E_{\pi}[R_1+R_2+R_3+…]\)

变换为:

\(q(s,a)=\frac{1}{N}\sum_{i=1}^N [R_1^i+R_2^i+…]\)

也就是说,只要这个 MDP 是有终点的,我们就可以计算出每一个状态下的 Return,然后利用大数据的力量求出估计值,然后得出策略评估的结果。

听上去是不是挺简单的?没错,精彩的还在后面。

6.2 蒙特卡罗法

接下来我们就实现一个简单的蒙特卡罗法的代码,更重要的是,我们最终还要拿这个算法的结果和策略迭代法进行比较,看看在不知道环境模型的情况下,蒙特卡罗法能否做到和策略迭代一样的效果。

前面对算法的流程已经有了介绍,我们的整理算法如下所示:

复制代码
def monte_carlo_opt(self):
while True:
self.monte_carlo_eval()
ret = self.policy_improve()
if not ret:
break

其中包含了两个子算法。其中 _policy_improve_ 和前面的算法类似,都是完成:

\(\pi(s)=argmax_a q(s,a)\)

所以这里不再赘述,下面来看看 _monte_carlo_eval_,这个方法又分成几个部分,首先要用当前的策略玩游戏,产生一系列的 episode:

复制代码
env.start()
state = env.pos
episode = []
prev_state = env.pos
while True:
reward, state = env.action(self.policy_act(state))
episode.append((reward, prev_state))
prev_state = state
if state == -1:
break

产生 episode 之后,我们再来计算每一个状态的长期回报:

复制代码
value = []
return_val = 0
for item in reversed(episode):
return_val = return_val * self.gamma + item[0]
value.append((return_val, item[1]))

最后,我们将每一个状态 - 行动对应的 return 记录在状态 - 行动价值函数上:

复制代码
# every visit
for item in reversed(value):
act = self.policy_act(item[1])
self.value_n[item[1]][act] += 1
self.value_q[item[1]][act] += (item[0] - \
self.value_q[item[1]][act]) / \
self.value_n[item[1]][act]

这里涉及到一个小的改变,因为我们要计算期望价值价值,将所有观测到的 return 进行平均,那么假设价值为 V,数量为 N,那么有

这样每一时刻我们都可以求出当前所有观测值的平均数,而且这个公式和我们常见的梯度下降法也十分类似,其中的

像学习率,而\(R_t-V_{t-1}\) 像目标函数的梯度。那么是不是真的可以这么考虑呢?当然是的。

以上就是我们进行一轮游戏的运算过程,实际上我们会有多轮游戏,我们先将游戏轮数设置为 100,也就是说,每一次策略评估,我们都来玩 100 轮游戏,并根据这一百轮游戏的结果完成估计。这样,蒙特卡罗算法的基本框架就搭起来了。大家一定非常想看看它的效果,于是我们就来和策略迭代进行一次对比,:

复制代码
def monte_carlo_demo():
np.random.seed(0)
env = Snake(10, [3,6])
agent = MonteCarloAgent(100, 2, env)
with timer('Timer Monte Carlo Iter'):
agent.monte_carlo_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

最终的结果为:

复制代码
Timer Monte Carlo Iter COST:0.128234863281
return_pi=81
[0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 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.329040050507
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]

可以看出,蒙特卡罗的结果比策略迭代还是要差一些,下面我们就来看看它们差距的原因。

6.3 探索与利用

一直以来我们没有花大篇幅做增强学习原理方面的讨论,是因为前面的算法虽然漂亮,但它们并不能帮我们直接解决实际问题,我们遇到的实际问题大多数都是不知道环境模型,或者环境模型太过于复杂的。所以这涉及到增强学习的一个思路,用英文讲就是“try and error”。

由于不知道完整的环境信息,我们只能通过不断地尝试去增加对环境和问题的理解,并通过这些理解帮助我们做出更好的决策。这里面肯定会走不少弯路,而且有一些弯路甚至不易发觉。所以增强学习遇到的一个问题是,如何找到更好的解决问题的路径,并确认这样路径应该就是最优的路径。

回到蛇棋的问题上来,在前面的问题中,我们可以看到棋盘,所以我们可以精确求出每一个状态 - 行动的价值函数。但是对于无模型的问题,我们能不能保证遍历所有的状态行动呢?

对于这个问题,我们可以想象,一开始所有的价值函数都初始化为 0,所有的策略均使用第一种投掷手法,如果我们固定这种手法不变,那么我们只能得到这种手法的 return,那么除非这种手法估计得到的价值函数为负,不然新的手法将不会被选中,也不会进行任何的模拟尝试,这就为我们带来了麻烦。

所以,为了“雨露均沾”,我们必须让其他没有被选为最优策略的行动也参与到模拟游戏的过程中来,这样才能让每一个 q(s,a) 都有值,这样做策略改进菜有意义。

基于这个想法,我们改进了我们的策略模块,我们采用一种叫\(\epsilon-greedy\) 的方法,首先用一个 0 到 1 的随机数进行判断,如果随机数小于某个\(\epsilon\),那么我们将采用完全随机的方式产生行动,而在其他情况下将选择当前的最优策略。代码如下:

复制代码
def policy_act(self, state):
if np.random.rand() < 0.05:
return np.random.randint(self.act_num)
else:
return self.policy[state]

在这里,我们设定的\(\epsilon\) 是 0.05,完成了这一步的修改,我们结果将会如何呢?

复制代码
Timer Monte Carlo Iter COST:0.486936807632
return_pi=84
[0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 0 0
0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 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.325078964233
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]

可以看出,虽然两种方法的最终策略不同,但是模拟得到的分数几乎相同。说明在增加了对不同方法的尝试后,算法真的会有大幅的提高。

这个问题在增强学习中也被称为是“探索与利用”的对立问题。所谓的探索是指不拘泥于当前的表现,选择一些其他的策略完成行动;利用就是持续使用当前的最优策略,尽可能地获得更多的回报。我们假设总的资源是有限的,比方说时间有限,可以进行模拟游戏的轮数有限,我们不能无止尽地探索,也不能短视地一直利用,那么就需要尝试在两者之间寻找一个平衡。

前面我们提到,蒙特卡罗方法需要模型有明确的终止状态,那么总有一些问题是没有终止状态的,或者说有些任务需要在线学习,也就是说边尝试边学习,这些场景并不是很适合蒙特卡罗方法。而且蒙特卡罗方法也有自己的小问题,那么下一节我们就来看看另一种解决无模型问题的方法。

作者介绍

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

2017-10-12 17:364020

评论

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

Javaweb之会话技术

楠羽

技术 笔记 9月月更

HowTo:Pipy 如何统计关键指标

Flomesh

Service Mesh 服务网格

被裁后半月面试8家公司无果,凭借这份Java面试指南成功入职阿里

Geek_0c76c3

Java spring 程序员 架构 面经

通过Thread Pool Executor类解析线程池执行任务的核心流程

华为云开发者联盟

后端 开发 企业号九月金秋榜

Seal 软件供应链防火墙 v0.2 发布,提供依赖项全局洞察

SEAL安全

DevSecOps 开源安全 软件供应链 软件供应链安全 软件供应链防火墙

什么是架构,什么是架构师?

源字节1号

软件开发 软件架构

YYEVA动效播放器--动态元素完美呈现新方案

百度Geek说

移动端 企业号九月金秋榜 动画特效 AE插件

小程序化:系统集成行业降本增效的破局思考

Speedoooo

小程序 数字化转型 小程序容器 生态平台

【数据结构与算法】8道链表面试真题超详剖析,带你领略算法思想【附思路、动图、源码】

Dream-Y.ocean

链表 数据结构与算法 9月月更

docker与gosu

程序员欣宸

Docker 9月月更 gosu

Dubbo 泛化调用在vivo统一配置系统的应用

vivo互联网技术

dubbo 中间件 配置管理

【文本检测与识别-白皮书】第二章:文本检测与识别技术发展历程

合合技术团队

人工智能 文字识别 OCR

ShareSDK HarmonyOS集成指南

MobTech袤博科技

sdk HarmonyOS

易周金融分析 | 银行融资青睐可转债;苏州市手机银行应用活跃人数规模发布

易观分析

金融 银行

如何实现数据库读一致性

京东科技开发者

数据库 读写锁 事务 MVCC 一致性

现代化车企——零束科技DevOps研发数字化体系建设实践

嘉为蓝鲸

#DevOps #研发 #汽车 #科技

阿里P8手写Spring Cloud Alibaba实战学习手册,架构师养成必备

Geek_0c76c3

Java 数据库 开源 程序员 架构

从 DFS 到回溯法,再看 N 皇后问题

掘金安东尼

前端 9月月更

保障系统安全

源字节1号

软件开发 信息安全 系统安全

极客时间—架构实战营—第九期—模块一作业

阿梁

如何解决 Angular custom library module 在 ng build 时无法被识别的错误

汪子熙

typescript 前端开发 angular web开发 9月月更

Ventana Research|是时候把指标中台纳入企业数据架构了!

Kyligence

数据架构 数据管理 指标中台

开发者有话说|用成长治愈所有迷茫

法医

程序员 个人成长

苏州市大数据集团成立!博云成为首批数商代表

BoCloud博云

云计算 数字化 云平台

新来个阿里 P7,仅花 2 小时,撸出一个多线程永动任务,看完直接跪了,真牛逼!

程序知音

从零开始 - 40行代码实现一个简单Promise函数

茶无味的一天

JavaScript Promise

视频直播+小程序,打破物理空间的电商卖货时代!

Speedoooo

小程序 小程序生态 直播带货 电商营销 小程序容器

大数据ELK(五):Elasticsearch中的核心概念

Lansonli

ELK 9月月更

关于加密数据的模糊查询

知识浅谈

9月月更 加密数据

Java实现SM3加密和验证

共饮一杯无

Java 9月月更 SM3

三三复制公排互助系统开发技术详情

开发微hkkf5566

无痛的增强学习入门:蒙特卡罗方法_语言 & 开发_冯超_InfoQ精选文章