写点什么

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

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

评论

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

BSN-DDC基础网络详解(二):快速接入指南

BSN研习社

BSN-DDC

图片竟能直接生成逼真音效?这AI模型也太神奇了吧!

人称T客

云安全之浅谈密钥泄露

HummerCloud

云安全 密钥

神锁离线版和Bitwarden的自动填充:超级英雄 vs 被斗转星移的瞎鸟

神锁离线版

密码管理 密码管理器 密码安全 Bitwarden 神锁离线版

架构实战营第 10 期 - 模块六:拆分电商为微服务

kaizen

「架构实战营」

java核心技术-多线程基础

蓦然

Spring Java

前端如何实现将多页数据合并导出到Excel单Sheet页解决方案|内附代码

葡萄城技术团队

数据库 前端 架构分布式

我的2022,从紫竹院到通惠河畔

虎妞先生

学习 前端 成长 年终总结

从零开始学习BOM&DOM

虎妞先生

前端 DOM

谈谈干前端三年的几点感受

虎妞先生

前端 成长 代码人生

C++到Python全搞定,教你如何为FastDeploy贡献代码

飞桨PaddlePaddle

c++ paddle 飞桨

微信小程序底层框架实现原理|万字长文

虎妞先生

微信小程序 前端 原理 架构、

大型集团企业数据治理实践,推进全域数据资产体系建设 | 数字化标杆

袋鼠云数栈

云原生场景下,如何缓减容器隔离漏洞,监控内核关键路径?

OpenCloudOS

Linux 云原生 服务器

# 文盘Rust -- rust 连接云上数仓 starwift

TiDB 社区干货传送门

开发语言

【SOP】新扩容节点与集群版本不一致处理

TiDB 社区干货传送门

实践案例 版本升级 管理与运维 故障排查/诊断 扩/缩容

畅销10年的数据库技术图书,当之无愧的霸主!还有谁?

博文视点Broadview

辞旧岁立新年 | 展望前端工程师的2023

字节跳动终端技术

云原生 前端 前端工程师

软件测试/测试开发 | App自动化之dom结构和元素定位方式(包含滑动列表定位)

测试人

软件测试 自动化测试 测试开发

TiKV RocksDB读写原理整理

TiDB 社区干货传送门

TiDB 底层架构 TiKV 底层架构

云数据库 TiDB 试用实践——部署&运维

TiDB 社区干货传送门

版本测评

Vue3项目框架搭建封装,一次学习,终身受益【万字长文,满满干货】

虎妞先生

前端 前端架构 Vue 3 vue cli

前端包管理工具 npm yarn cnpm npx

虎妞先生

前端 包管理工具 #面试

不常用但却常问的迭代器

虎妞先生

前端 ES6

海外多语言数字货币交易app系统开发搭建

开发微hkkf5566

七年的开源商业化探索,PingCAP 为什么选了这样一条路?

TiDB 社区干货传送门

数据库前沿趋势

给webpack提了一个pr之后......

虎妞先生

前端 webpack #开源

云数据库 TiDB试用

TiDB 社区干货传送门

迈铸半导体完成1500万Pre A+轮融资,用于实现规模化量产

硬科技星球

众生皆苦,我选pnpm

虎妞先生

npm 原理 前端工程化 pnpm

十分钟用vitepress搭建项目文档

虎妞先生

前端 vite Vue 3

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