谭升
非主流人工智能科学家 我和外面那些妖艳的货不一样

【强化学习】 1.5 强化学习的一个扩展举例

今天我们来讲一个很有趣的例子,英文名字叫”Tic-Tac-Toe” 中文名字有翻译成“井字棋”或者什么的,我们这里为了方便就称之为“井字棋”,叫井字棋的原因是因为其棋盘是个“井”字形的,玩法简单,但是这个玩的过程可以使用强化学习的方法来学习,这个简单的棋可以让我们从各个细节审视强化学习的特点,有点,缺点,以及一些小技巧。

“Tic-Tac-Toe”简介

规则描述

Tic-Tac-Toe的规则描述如下:
1. 使用 $3\times 3$ 的正方形棋盘,双方各使用 ‘x’和’o’ 作为棋子,轮流下棋,
2. 谁的棋子最先连成一行或者一列,或者对角线,那么获胜,棋局结束
3. 对方完成这个过程,则失败
4. 如果在最终双方都没能连成一行或者一列,或者对角线的情况下,棋局结束,则为平局。

下图来自Wikipedia:“井字棋”

Advertisements

上面的棋局,使用 ‘x’ 的一方率先完成连成一行的准则,故执’x’一方获胜。

简单规则下的问题

下面这个视频是我在Google上找到的一个小程序录的一段视频。

可见,在高级的情况下,双方(我和AI)基本都没法获胜,也就是平局会大量出现,原因是,我们对这种棋的技巧掌握的都很熟练,无法在现行环境(规则)下战胜对方,通过这个观察我们也能发现,在规则相对简单的游戏(“博弈”)中,平局会大量出现。
那么问题就要来了,我们 – 也就是人,在这种简单的规则下,多以平局收场,那么这怎么训练agent呢?如果每局训练总是平局,agent就不知道往什么方向走了。这里我们就要做出一些修改,我们让与我们agent下棋的人或者另一个agent不那么高级,换句话说,我们在简单规则下,降低规则执行者的能力,进而模拟出更高级的博弈(所谓更高级的博弈,无非是我们能力不足才会觉得当前环境,或者规则很困难)。
在后面的训练里,agent会将平局和失败都当做失败来处理,agent的目标明确,就是胜利。

非强化学习型的解决方法

这个棋局太简单,但是在如此简单的规则下,传统方法(非学习方法)都有诸多问题:
1. 使用传统的“极大极小化”(minimax)方法,这个方法会假定对方按照某个既定方案下棋,而事实是对方可能无既定方案,或者既定方案我们永远无法得知。所以这个传统的博弈思想在此不适用。而且“极大极小化”(minimax)方法有个非常大的缺点:如果其认定当前状态必然失败的情况下,即使后面对手出现重大失误(可以逆转取胜的机会),其也不会采取任何致胜招数,而是按照既定失败的套路继续下去。
2. 对于这种连续决策型问题的传统的优化方法,例如动态规划(dynamic programming),可以计算出在对阵任何对手时候的最优解,但是前提是:对手的全部信息要作为输入提前提交给算法,其中包括在某特定情况(棋局)下,对手下一步棋下在哪的概率。如果我们提前不知道这些信息(大部分情况下,这个信息无法获得)
3. 对于2中的动态规划方法,有另一种改进版就是在训练时和对手多次交手,从而记录学习出对手的信息,或者叫做给对手建模(model)然后再使用动态规划来寻找答案。

上面3中方法中,1和2对解决问题基本没有帮助,3有帮助。3和我们后面会介绍的很多强化学习方法有着非常相似的思路。

进化方法(Evolutionary Method)学习 “Tic-Tac-Toe”

进化方法 中讲解了进化方法的缺点,就是没有使用agent和环境之间的交互信息来改变agent。而这里如果把进化方法直接使用到“井字棋”中,其表策略(policy)的特点是:直接search全部可能的位置,找到获胜概率最大的位置,然后下棋。也就是,策略要考虑到当前盘面( $3\times 3$ 的棋盘上 x和o的分布)并给出获胜概率最大的下棋位置。而这个概率的获得就需要和对手多次下棋,记录,学习出来的。有了这些信息,agent就知道接下来一步或者接下来很多步应该怎么走。
一个典型的进化方法就是在“策略空间”的 hill-climb ,这种方法的策略是逐渐找出能提高表现的策略(并不是一下找到最优的方法,而是像爬山一样,每一步都找到一个能提高agent表现的方案,一步一步的向上爬)。
遗传方法就更加直接暴力了,直接直接评估大量的策略(policies),去除不合格的,留下好的,然后产生新一代的,以此迭代,直到问题解决。
解决“井字棋”问题,理论上存在很多种不同的优化方法。

评价函数(Value Function)学习 “Tic-Tac-Toe”

上面我们说了进化方法在井字棋中使用,下面我们就要看看另一个方向的方法 —— 评价函数(value Function)的方法了。

设计评价函数

我们列一个表,这个表中的每个格子对应一种状态(state),整张表就对应井字棋的全部情况,这个表的每一项都对应一个概率值,这个概率值表示当前状态下最后获胜的期望,注意两点,一个是当前的状态,第二是最终获胜的期望。这个期望,我们就把其当做评价函数的结果,value —— value值。这个表就是我们的评价函数(Value Function)了.
在井字棋中,这个表就包含下一步棋应该怎么走的评估。通过当前状态,我们可以缩小下一步可能出现的状态范围,然后比较所有可能的状态,如果A状态比B状态有更高的获胜期望,那么我们认为A状态比B状态好,所以我们倾向于把棋子走到A状态显示的位置。
对于这个状态表,假设我们执x,那么如果某状态中包含x在一行或者一列或者对角线,那么这个状态的获胜期望是1,相反,如果o在一行或者一列或者对角线,那么这个状态的获胜期望是0;同样,如果对应状态是棋盘下满,而没有获胜方,这时候期望同样是0 。除了上述这些情况,其他状态的初始化值都是0.5,即有一半的可能性会获胜。

执行(exploitation)和探索(exploration)

当我们有了这张表(上面的评价函数)我们就有了制胜法宝,但是具体执行也是有不同方案的,我们可以查找最大value的状态,然后执行贪心(greedily)选择,这是使得获胜期望最大的策略,也就是完全执行表(value function)中的指示,这个被称为exploitation。
但是我们有时候(偶尔,occasionally)在某些步骤中不选择最大value的状态,而是选择随机状态,因为这种方式可能带我们到一个前所未见的state下。

上面两段描述的评价函数,以及状态表在井字棋中可以表现为下图:

table

学习评价函数(value function)

在下棋的过程中,我们不断修改已有value function对于井字棋,也就是上面我们提到的那张表,我们的目标是试图使其更加准确,为了达到这个目的,我们增加了一步“返回”(back up) 过程(上图中的红色箭头),这个过程在每一步贪心选择后执行,这一步执行的实质是通过当前状态值(value)来适当修改上一步状态的value,使它更接近现在状态的值(评价函数的结果,value),比如图中的红箭头就是让e的值(评价函数的结果,value)更接近g的值(评价函数的结果,value)。
上面的数学表达为,让 $s$ 为贪心选择之前的状态的值(评价函数的结果,value), $s’$ 为贪心选择后的值(评价函数的结果,value),然后我们的back up更新 $s$ 值,方式是:
$$
V(s)\leftarrow V(s)+\alpha[V(s’)-V(s)]
$$

其中 $\alpha$ 是一个小的正小数,叫做“步长”(step-size)参数,这个参数影响学习速率(the rate of learning)注意这里rate是速率的意思,而不是比率的意思,所以学习率这种翻译,我觉得欠妥。
这种基于 $[V(s’)-V(s)]$ 的变化方式(update rule)被称为“时序差分学习”(temporal-difference learning),字面解释:基于两个不同时间点的值(评价函数的结果,value)的差值的方法,这个解释基本能反应这类方法的特点。
这类方法是我们后面要重点学习。

上述方法对于这个任务可以非常出色的得出不错的结果,例如,在步长参数(step-size)被精确递减后,这个算法对于固定的对手是收敛的,每一步都能给出胜算最高的走法。也就是说,这个方法对于一个固定的对手给出了最优策略。这里的一个关键就是 步长参数(step-size) 的调整,如果这个参数不调整,那么最后的结果也会收敛,但是速度会慢很多。

“进化方法”与“评价函数”的区别

上面这些细节也佐证了我们前面提到的:“进化方法”和“评价函数学习法”的区别:
1. 进化方法的为了学习一个策略,其根本原则是策略不变(不是永久不变,是在目前的短时间内),而去和对手进行多场游戏(就是和环境的交互,interaction),或者使用一个对手的模型,来模拟进行多场游戏。在进行多次游戏后,胜利的次数给出当前策略胜率的无偏估计,然后这个无偏估计被用来优化策略(根据一定的规则从多个策略中淘汰某些,或者其他办法生成新的策略)。
但是问题是每次策略进化都需要多场游戏来计算概率,而每场游戏内的信息被忽略掉了(因为计算概率只关心结果的 —— 胜利出现的次数)而且当一个player(也可以成为agent)获得了胜利,他本场比赛的所有行为都会被认为是正确的,且每一步给予相同的得分,但实际上并不是这样,首先并不是每一步的重要性都一样,其次是并不是每一步都是正确的选择。
2. 对比之下“评价函数学习法”就有不同的表现了,每一步棋和环境的交互信息都会被利用来学习。

总之,进化方法和“评价函数学习法”都是在搜索policy的空间,但是“评价函数学习法”搜索起来更高效,因为他利用了更多的有效信息。

“Tic-Tac-Toe” 中的强化学习

这个小小的游戏基本展现了强化学习的所有特性:
1. 首先强调和环境的交互,这里就是和对手下棋。
2. 目标明确,正确的行为需要 Planning 或者 Foresight 来处理延迟出现的结果
3. 另一个显著的特征是,RL形成有效的 Planing 以及 lookahead ,而且这个过程不需要使用对手模型(model of opponent),也不会对后面全部的可选操作序列进行搜索(减少policy的搜索空间)

虽然RL的这几个有点很是吸引人,但是这不能掩盖其某些缺点:
1. 训练的时的对手,不可能是人,而还是程序,所以这个对手不是Nature的
2. 学习过程也是打碎成不同的步骤(对于井字棋每一局都是一步),而不是连续的进行,只有下完了才会产生reward信号,而不是连续的。
3. 同样对于某些连续的任务,我们也要把它拆成离散形式。

井字棋的搜索范围很小,现在alpha go所面对搜索空间比井字棋大到不知道哪去了~,1992年的时候就有学者研究了比井字棋更复杂的游戏,空间大概规模是 $10^{20}$ 他们使用了神经网络作为模型,结合上面的方法得出了很好的结果,具体我们在后面16章学习。
强化学习面对如此巨大的policy空间的行为,主要取决于他对之前学习的信息的理解程度,理解的越好,其行为就更加可靠,反之则不可靠。

先验知识(Prior Knowledge)与模型(Model)

在井字棋游戏中,RL的agent只知道游戏规则毫无游戏经验或者先验知识,先验知识是锦上添花的元素,也就是,有或者没有这个要靠缘分,就算没有我们也要解决问题,而如果有,那么我们可以利用先验知识节省大量时间,或者大幅度提高结果。RL处理先验知识有多种方式,并且对学习结果。
我们目前处理的情况都是当前环境对agent有明确的反馈,且state明确,在有些问题中state可能是隐藏的或者有大量重复的state这种情况过于复杂,不在我们初级范围内。
Model同样是强化学习中的一个组成要素:当我们的RL(agent)学习应该怎么样应对不同的状况的时候,他需要思考的就是环境会怎么对他的action进行反应,有些问题确实如此,环境对action的反应就是一个模型,但是有的问题可能比这要更复杂一些,他们有的时候什么模型都没有,不知道环境会做出什么样的反应,面对这样的问题RL也有解决方案。同样的,有模型可以帮助RL更快的学习。
但是我们的井字棋就没有这个model,原因是对手怎么下棋是不可能有模型的,这就是个 Model-Free system。存在精确模型的系统由于模型被精确的使用,所以做起来相对简单,但是有的时候建立模型的过程会成为这个问题的瓶颈,本书中我们会讨论一些Model-Free的问题,同时组合这些问题成为更复杂的系统。

总结

本文通过研究Tic-Tac-Toe这个小游戏,从实际应用的角度分析了RL的各个方面,基本涵盖了大部分主要内容,后面我们进入第二章,开始分析具体算法,欢迎大家关注。

References

Sutton R S, Barto A G. Reinforcement learning: An introduction[J]. 2011.

Share

You may also like...

说点什么

avatar
  Subscribe  
提醒

试录了几节线性代数视频课程,欢迎大家支持,
点击试看
点击购买更多内容

由于博客移至wordpress,部分公式和代码显示不正常,博主正在努力修改,如发现公式显示错误,请及时在文章下留言,感谢您的帮助,尽请原谅!