写点什么

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

  • 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:364292

评论

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

利用GCC插件实现代码分析和安全审计

科技怪咖

从零教你使用MindStudio进行Pytorch离线推理全流程

华为云开发者联盟

Python 人工智能 企业号九月金秋榜

解锁云原生新场景 | 云原生加速云边端一体化发展

York

容器 云原生 边缘计算 边云协同 边缘云原生

软件测试 | 测试开发 | 测试开发基础 mvn test | 利用 Maven Surefire Plugin 做测试用例基础执行管理

测吧(北京)科技有限公司

maven

在线数据迁移,数字化时代的必修课 —— 京东云数据迁移实践

京东科技开发者

数据 数据迁移 上云 redis'

DevOps 团队如何防御 API 攻击

SEAL安全

DevOps DevSecOps 软件供应链安全

Substrate技术及生态8月大事记 | 波卡发布新版本,XCM协议更新

One Block Community

区块链 技术 开发者 Substrate 更新

游戏技术加速数实融合,网易伏羲挖掘机器人首次曝光

网易伏羲

人工智能 机器学习 工程实践

从云计算到函数计算

Serverless Devs

云计算 阿里云 AWS

学员参加前端培训哪里比较靠谱?

小谷哥

千锋锋友学盟分享会:程序员百万年薪进阶指

千锋IT教育

计算机网络体概念

StackOverflow

编程 计算机网络 9月月更

软件测试 | 测试开发 | 持续交付-Blue Ocean 应用

测吧(北京)科技有限公司

阿里灵杰融合智能算力,全栈AI服务为探索者铺路

阿里云大数据AI技术

人工智能 大数据 企业号九月金秋榜

51单片机定时器原理及相关器件

孤衫

C语言 单片机 9月月更

《TiDB跨版本升级》 --流程概述

TiDB 社区干货传送门

迁移 实践案例 版本升级 管理与运维 安装 & 部署

Apache DolphinScheduler PMC:开源不一定也要九死一生

白鲸开源

海豚调度 开源社区 Apache DolphinScheduler 开源文化 #开源

LeetCode-58. 最后一个单词的长度(java)

bug菌

Leet Code 每日一题 9月月更

首次公开到知乎爆火!基于SpringCloud+SpringBoot+Vue电子版项目实战教程,附完整源码

退休的汤姆

Java spring 程序员 面试题 阿里

零基础学习java培训是否适合参加

小谷哥

大数据培训前景怎么样

小谷哥

基于阿里云Serverless函数计算开发的疫情数据统计推送机器人

Serverless Devs

技术分享| 基于RTM 实现的呼叫邀请如何添加推送功能?

anyRTC开发者

音视频 IM 实时消息 呼叫邀请 推送

分布式团队的高效站立会说明书 | Liga译文

LigaAI

高效工作 敏捷开发 开发团队 每日站会 企业号九月金秋榜

软件测试 | 测试开发 | 构建测试平台与对应的组织架构需要哪些能力?

测吧(北京)科技有限公司

测试

设计模式的艺术 第十七章命令设计模式练习(开发一个基于Windows平台的公告板系统。该系统提供了一个主菜单(Menu),主菜单包含一些菜单项,Menu类可以增加菜单项。菜单项主要方法是click(),每个菜单项包含一个抽象命令类)

代廉洁

设计模式的艺术

LeetCode-66. 加一(java)

bug菌

Leet Code 每日一题 9月月更

Dubbo 3 StateRouter:下一代微服务高效流量路由

阿里巴巴中间件

阿里云 开源 微服务 dubbo 中间件

零基础如何参加大数据培训

小谷哥

音视频开发进阶|第六讲:色彩和色彩空间·上篇

ZEGO即构

音视频开发 色彩 色彩空间

在java培训中心怎样才能快速学习?

小谷哥

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