红帽白皮书新鲜出炉!点击获取,让你的云战略更胜一筹! 了解详情
写点什么

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

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

公众号推荐:

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

AI 前线公众号
2017-10-12 17:363896

评论

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

2021年Android开发者跳槽指南,附超全教程文档

android 面试 移动开发

2021年Java开发突破20k有哪些有效的路径,JVM发生内存溢出的8种原因

Java 面试 后端

2021年Java者未来的出路在哪里,Java开发校招面试题

Java 面试 后端

2021年Java高级面试题总结,2021最新大厂高频微服务面试总结

Java 面试 后端

2021年Java技术下半场在哪,35岁技术人如何转型做管理

Java 面试 后端

2021年Android笔试题总,详解Android架构进阶面试题

android 面试 移动开发

2021年Java面经分享,程序员必备技能:时间复杂度与空间复杂度的计算

Java 面试 后端

2021年Java开发者常见面试题,初级Java面试题及答案

Java 面试 后端

2021年Java网络编程总结篇,红黑树详细分析(图文详解)

Java 面试 后端

2021年Java者未来的出路在哪里,让人抓狂的Nginx性能调优

Java 面试 后端

2021年Java面经分享,别再说你不会JVM性能监控和调优了

Java 面试 后端

2021年Java工作或更难找,华为Java面试社招

Java 面试 后端

2021年Android开发陷入饱和,又是一年金九银十

android 面试 移动开发

2021年Android社招面试题精选,附答案解析

android 面试 移动开发

对比会声会影与剪映哪个制作转场效果更专业

懒得勤快

2021年Android开发者常见面试题,涨薪7K

android 面试 移动开发

2021年Java开发突破20k有哪些有效的路径,2021Java面试笔试总结

Java 面试 后端

2021年Android社招面试题,阿里蚂蚁金服五面

android 面试 移动开发

2021年Java程序员职业规划,华为Java面试题目

Java 面试 后端

2021年Android网络编程总结篇,retrofit面试

android 面试 移动开发

代码检查规则背景及总体介绍

百度开发者中心

最佳实践 代码规则

IT运维和自动化运维以及运维开发有啥不同?能解释下吗?

行云管家

互联网 运维 IT运维 自动化运维 云运维

2021年Java常见面试题,面试官让我回家等通知

Java 面试 后端

2021年Java开发前景如何,大厂Java面试真题精选

Java 面试 后端

2021年Android程序员职业规划,小白勿进

android 面试 移动开发

2021年Android程序员职业规划,阿里P7大牛亲自讲解

android 面试 移动开发

2021年Java笔试题总,教你抓住面试的重点

Java 面试 后端

【等保知识】十个等保常见问题解答汇总

行云管家

网络安全 信息安全 等级保护 过等保 数据审计

2021年Java面试心得,整理出这份8万字Java性能优化实战解析

Java 面试 后端

Github上线仅六天,收获Star超55K+,这套笔记足够你拿下90%以上的Java面试!

Java 架构 面试 后端 计算机

谁是中国最受赞赏的创投机构?

创业邦

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