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

未分类

编者按：《无痛的增强学习入门》系列文章旨在为大家介绍增强学习相关的入门知识，为大家后续的深入学习打下基础。其中包括增强学习的基本思想，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总和最大。如果用$R_t$表示t时刻的奖励，游戏将在第T轮结束，那么游戏的目标就是最大化下面的公式：

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

作者介绍：冯超，毕业于中国科学院大学，猿辅导研究团队视觉研究负责人，小猿搜题拍照搜题负责人之一。自2016年起在知乎开设了自己的专栏——《无痛的机器学习》，发表机器学习与深度学习相关文章，文章以轻松幽默的语言、细致深入的分析为特点，收到了不错的反响，并被多家媒体转载。曾多次参与社区技术分享活动。