HarmonyOS开发者限时福利来啦!最高10w+现金激励等你拿~ 了解详情
写点什么

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

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

评论

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

医院HIS故障,险引发人命关天大危机,竟被程序员轻松解决!

Marilyn

用友政务表格技术应用开发实践:预算一体化产品核心功能搭建

葡萄城技术团队

SpreadJS 用友

GitHub 上开源了一个很邪恶的项目!女生勿近,18香警告...

程序员生活志

有一说一,大型信息化企业的软件系统,还是用自研的好

Marilyn

敏捷开发 快速开发 开发工具 软件设计

TensorFlow 篇 | TensorFlow 2.x 基于 Keras 的模型保存及重建

Alex

tensorflow keras model save model restore tensorflow hub

阿里内部《Java架构进阶宝典》,总结了基础、进阶、架构三个阶段的知识点

Java架构之路

Java 程序员 面试 算法 编程语言

深入分析软件快速开发平台与传统软件开发方案的优缺点

Marilyn

敏捷开发

JAVA代码生成器,快速开发平台之魂

Marilyn

Java 敏捷开发 快速开发 开发工具

快速开发平台,程序员“老师傅”必备

Marilyn

敏捷开发 快速开发 开发工具

Redis Sharding集群跟一致性哈希有什么瓜葛?

Man

一致性哈希 Jedis redis cluster

架构师训练营 1 期第 4 周:系统架构 - 作业

piercebn

极客大学架构师训练营

架构师训练营第 1 期 第 4 周作业

李循律

极客大学架构师训练营

JAVA & VUE ,分离式开发平台建造思路

Marilyn

Java Vue 敏捷开发

spring-boot-route(十三)整合RabbitMQ

Java旅途

Java Spring Boot RabbitMQ

标本兼治,程序员用它整体提升公司效率

Marilyn

敏捷开发 快速开发

大企内部软件系统反复故障难以解决,业内人士:唯有彻底更换

Marilyn

敏捷开发 快速开发 开发工具

为什么巨头都在布局SaaS生态?

ToB行业头条

SASS

MySQL-技术专题-性能优化—索引篇

洛神灬殇

阿里面试官纯手打:金九银十跳槽必会Java核心知识点笔记整理

Java架构追梦

Java 数据库 架构 面试 微服务

JVM-技术专题-深入理解内存结构

洛神灬殇

Java JVM

Go语言内存管理三部曲(一)内存分配原理

网管

内存管理 内存布局 Go 语言

低代码开发平台,来自“未来”的软件开发方案

Marilyn

敏捷开发

摆脱复杂烧脑的程序代码,利用快速开发平台轻轻松松做软件

Marilyn

敏捷开发 快速开发

企业开发遇到瓶颈,何不换个新思路?快速开发了解一下

Marilyn

敏捷开发 快速开发

智能时代,快速开发平台将成为主流软件开发工具

Marilyn

敏捷开发

Go发起HTTP2.0请求流程分析(前篇)

Gopher指北

HTTP HTTP2.0 Go 语言

商业智能(Business Intelligence)系统的使用及设计原则

Marilyn

敏捷开发 快速开发 商业智能

Vidyo的解决方案到底是什么?有哪些特点?

dwqcmo

音视频 集成架构 解决方案 智能硬件

五年Java开发经验,4面阿里成功拿下offer,分享一下个人面经!

Java架构之路

Java 程序员 面试 算法 编程语言

XJR企业级软件快速开发平台规范

Marilyn

程序员 敏捷开发 软件设计

快速开发平台,高集成易扩展,进入软件疾速开发新世代

Marilyn

敏捷开发 快速开发 开发工具

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