春争日,夏争时,扫码抽取夏日礼包!!! 了解详情
写点什么

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

  • 2017 年 7 月 16 日
  • 本文字数:3319 字

    阅读完需:约 11 分钟

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

1 基础知识

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

作为一个 85 后(暴露年龄),在年幼的时候我曾经接触一种游戏,这种游戏是一种棋类游戏,有一个棋盘,棋盘上有许多小格子,还有几个棋子和一个骰子。棋盘的样子大概是这样的:

图 1 蛇棋的棋盘

这种棋被称为蛇棋,他的玩法大概是这样的:

  1. 几个小伙伴一起玩,每个人有一个棋子,大家一开始把棋子放在图中标为“1”的格子中;
  2. 每个人依次掷骰子,根据骰子的点数将自己的棋子向前行进相应的步数。如果现在我的棋子在“1”处,并且投掷出了“4”,那么我的棋子就可以到达“5”的位置;
  3. 棋盘上有一些梯子,这些梯子十分重要,它的两边将棋盘上的两个格子相连,这样如果棋子落在其中的一个各自上时,就会自动走到梯子对应的另一个格子中。对于上面的例子,如果我的棋子在“1”处,并且投掷出 2,那么我的棋子将到达“3”,由于“3”的位置有梯子,我将直接前进到梯子的另一段——“20”;
  4. 最终的目标是到达“100”这个格子,如果在到达时投掷的数字超过了 100,那么棋子将首先到达 100,剩余的步数将反向前进。比方说我的棋子在“99”这个位置,如果我投掷出了“3”,那么我将先前进 1 步到达 100,然后再后退 2 步,这样就到达了“98”。悲剧的是“98”处还有一个梯子,于是我的棋子将顺着梯子到达“81”。

从现在的角度来看,这个游戏的可玩性其实比较有限,游戏中也没有那么多跌宕起伏的情节,但是它确实是那一代人的一大娱乐。由此引出的一系列游戏棋——尤其是大富翁系列的游戏棋,真的影响了很多人。

说了那么多游戏规则和情怀的事情,下面就将来到正题:这东西和增强学习有什么关系?

蛇棋的游戏定义

实际上这个游戏就是增强学习的一个小案例。我们先不介绍增强学习的一些抽象概念,但从这个游戏入手。蛇棋中的棋盘和游戏规则是既定的,胜利规则也是既定的,这些内容帮助玩家建立对这个游戏的世界观,以及游戏的目标。

那么游戏的参与形式呢?就是掷骰子。实际上掷骰子这个问题是一个值得大书特书的问题,君不见,有些人掷骰子的时候要气沉丹田,有的要大喝一声,有的小心翼翼……尤其一个赌局上,每个人掷骰子的模样都不相同。对于这些不同的掷骰子方式,我们显然可以认为不同方式下骰子各个面出现的概率是不同的。为什么?这个就不用细谈了吧……

所以游戏中唯一决定玩家命运的操作出现了——掷骰子的手法。这里我们运用一点抽象,让玩家的手法暂时变成 2 种手法:一种可以均匀投掷出 1~6 这 6 个数字,另一种可以均匀投掷出 1~3 这 3 个数字。这样玩家相当于有了两个选择。

接下来看看游戏的最终获胜条件。一般来说游戏是多人一起玩的(一个人玩是什么鬼……),那么谁先到达“100”,谁就获得了胜利。换句话说,用最少的投掷次数到达“100”是每一个玩家的目标。为了达到这个目标,玩家最好能尽可能地“乘坐”更多的梯子上升,这样可以快速到达终点。一般来说游戏喜欢用一些数字或得分的形式记录玩家的表现,我们这里做一个约定,玩家每走一步,将获得 -1 分,也就是扣一分,到达重点后,将得到 100 分。这样先到达重点的玩家一定会有最高分,也就相当于 TA 获得胜利。

听完了上面的描述,“精通”开发的你一定忍不住想把上面的描述变成代码,于是我们就有了下面的这段代码:

复制代码
import numpy as np
class Snake:
def __init__(self, ladder_num, dice_ranges):
self.ladder_num = ladder_num
self.dice_ranges = dice_ranges
self.ladders = dict(np.random.randint(1, 100, size=(ladder_num, 2)))
reverse_ladders = [(v, k)for k,v in self.ladders.items()]
for item in reverse_ladders:
self.ladders[item[0]] = item[1]
print 'ladders info:'
print self.ladders
print 'dice ranges:'
print dice_ranges
def start(self):
self.pos = 1
def action(self, act):
step = np.random.randint(1, self.dice_ranges[act] + 1)
self.pos += step
if self.pos == 100:
return 100, -1
elif self.pos > 100:
self.pos = 200 - self.pos
if self.pos in self.ladders:
self.pos = self.ladders[self.pos]
return -1, self.pos
if __name__ == "__main__":
env = Snake(10, [3,6])
env.start()
while Ture:
reward, state = env.action(1)
print reward, state
if state == -1:
break

这个代码主要定义了一个蛇棋类,其中包含 3 个函数:

  • 构造函数:需要传人两个参数——梯子数量和骰子数量。我们用一个 dict 存储梯子相连的两个格子的关系,用一个 list 保存可能的骰子的可投掷最大值。
  • start():将 pos 设置为“1”,也就是开始游戏
  • action():完成一次投掷,参数 act 表示玩家将采用何种手法。完成位置的更新后,函数将返回这一轮玩家的得分(-1 或 100)和玩家的最新位置

代码中的 main 函数用于展示一个蛇棋的游戏过程,运行如下所示:

复制代码
ladders info:
{2: 99, 67: 73, 54: 82, 73: 67, 10: 58, 43: 86, 45: 95, 93: 23, 50: 59, 17: 92, 82: 54, 99: 2, 86: 43, 23: 93, 26: 73, 59: 50, 92: 17, 58: 10, 95: 45}
dice ranges:
[3, 6]
-1 7
-1 9
-1 15
-1 19
…………(以下省略若干中间结果)
-1 73
-1 77
-1 83
-1 88
-1 90
-1 96
-1 97
100 -1

最终玩家完成了一次游戏,在这次游戏中,玩家共进行了 294 次投掷才到达重点,最终得分 -193 分。从上面的梯子情况可以看出,有些梯子真的容易让人绝望:

复制代码
99: 2
95: 45
92: 17

玩家多次掉入这种陷阱,才导致游戏进行了这么长时间。

作为好胜心很强的我们,肯定在想,刚才的游戏中,玩家只使用了一种手法啊,要是两种手法并用,甚至更多的手法并用,一定能提前完成游戏的。这就要涉及要一些策略了。

增强学习的概念

在经典的增强学习中,玩家作为 Agent,要和环境 Environment 做一系列的交互。在每一个时刻,环境将给出一个当前的状态,玩家将根据状态做出决策,这个决策会影响环境,使得环境发生一定的改变,改变后的环境会反馈给玩家一个“奖励”Reward,这个奖励可以是正向的,也可以是负向的,它用于反馈用户当前的表现。环境同时还会反馈下一时刻的状态给玩家,这样玩家就可以做新一轮的决策了。这个过程由图 2 所示。

图 2 增强学习的过程表示

看过了蛇棋,相信大家很容易就把蛇棋的游戏过程套用到上面流程中,这里就不重复一遍了,只是将图 2 中的关键实体做一个对应:

  • Agent:玩家
  • policy:策略,简单来说就选择哪种投掷手法
  • action:策略最终决定的行动,具体的投掷手法
  • Environment:棋盘,游戏规则,获胜策略等一篮子内容
  • state transition:玩家投掷完骰子后,棋子的位置将发生变化,也就是状态的变化
  • state,reward:棋盘变化后,新的棋子位置将发送给玩家,同时包含一个奖励:-1 或者 100

看到这里,我们可以把最终目标进行重新定义:如何确保在游戏结束前获得的 reward 总和最大。如果用表示 t 时刻的奖励,游戏将在第 T 轮结束,那么游戏的目标就是最大化下面的公式:

那么该如何最大化呢?我们能否求出最优的“策略”来?下次我们将继续介绍。

作者介绍

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

2017 年 7 月 16 日 17:239488

评论 1 条评论

发布
用户头像
主函数的的while语句中逻辑真不是Ture,应该是True
2020 年 01 月 09 日 09:19
回复
没有更多了
发现更多内容

QA应该更新的测试工具-2013

刘冉

软件测试

测试策略实践之分类漫谈

刘冉

2021年最新获取url参数的方法,用正则就落后啦

CRMEB

shell原样输出字符串

WindFlying

数据流水线架构

俞凡

架构 数据

数据仓库之数据质量建设(深度好文)

五分钟学大数据

11月日更

🔄 这些JS数组遍历是否都用过 🔄

空城机

JavaScript 大前端 11月日更

Redis计算UV的4种方法

大数据技术指南

11月日更

重点人员管控系统开发方案,重点人员动态管理系统

电微13828808271

测试策略实践之测试自动化与自动化测试

刘冉

测试管理 测试策略

2022 年 9 个最佳 JavaScript IDE 和代码编辑器

devpoint

JavaScript vscode IntelliJ IDEA 11月日更

🏆【Alibaba中间件技术系列】「RocketMQ技术专题」帮你梳理RocketMQ相关的消费问题以及原理分析总结

浩宇天尚

RocketMQ 消息队列 11月日更 重复消费

听说你还在写双层for循环解两数之和?

老表

Python LeetCode 11月日更 两数之和 算法与数据结构

意外发现,原来你不知道自己每天都在用门面模式

Tom弹架构

Java 架构 设计模式

质量基础设施一站式服务平台方案,NQI一站式公共平台开发

电微13828808271

TDD之让我们再聊聊TDD(续)

刘冉

TDD

博文|Apache Pulsar 在自研数据管道中的技术实践

Apache Pulsar

大数据 分布式 云原生 中间件 Apache Pulsar 消息系统

学习分布式存储应该从哪几方面着手?

守护石

Influxdb Cassandra HBase 分布式存储

前端开发:HTML5 音频的使用方法

三掌柜

11月日更

安全测试之XCodeGhost随想-2015

刘冉

软件测试 安全测试

模块三 架构文档

Asha

TDD之让我们再聊聊TDD(终)--正其思,规其行

刘冉

TDD

13 K8S之Pod资源操作

穿过生命散发芬芳

k8s 11月日更

TDD之让我们再聊聊TDD

刘冉

TDD

测试策略实践之序篇-软件缺陷,测试计划和测试架构

刘冉

测试计划 测试策略 测试架构

告别晦涩难懂的物理,《张朝阳的物理课》了解一下

脑极体

一个基于web服务器的PoW案例(一)

Regan Yue

区块链 共识算法 11月日更

应届生学的java,转自动化测试拿到15k薪资,送给大家的经验积分

六十七点五

Java 程序员 软件测试 自动化测试 测试工程师

模块四作业-考试试卷-Redis存储方案设计

沐风

无痛的增强学习入门:基本概念篇_语言 & 开发_冯超_InfoQ精选文章