网上电子游戏学习导论（二）-多臂老虎机

本章主要针对“非关联性（nonassociative）”的简单场景来学习基础的强化学习方法。

什么是“非关联性”呢？其实通过最后 2.9 节可以看出，非关联性在本章就是指。

非关联性问题是一种很理想化的问题，研究这种问题对于现实中的实用性意义不大，但对于入门强化学习理论，是一个不错的背景载体。

再说到强化学习，他与其他的机器学习方法最大的区别，也就是他自身的特点，在于强化学习重点关注评价性反馈（Evaluative Feedback），而不是指导性反馈（Instructive Feedback）。

指导性反馈多用在监督学习中，需要大量正确的先验知识/信息来给予“指导”，而在一些特殊背景下，网上电子游戏学习导论（二）- 多臂老虎机无法得到监督性指导，但却有大量实时的评价性反馈，这时候就需要用到强化学习。

我们可以很自然地想到，如果玩家真的从上帝视角得知了这台老虎机的回报规律，也即是知道了每个行动 a 真正能得到理论期望回报，那只需保持选择能够收获最大期望值的 action ，就能确保最大的总收益。

所以，这个问题的目标，就是要去学习探索，取得关于的信息。

但是玩家一开始显然是不知道的情况，所以他要建立一套自己对所有 a 的评估体系，即根据他目前拥有的知识，来估计/猜测当前第 t 步 a 的回报值。

如何去估计呢？这个先不急，这正是后面长篇大论的东西，简言之，关键在于要有这么一套合适的评估体系。

先假设玩家建立好了一套他认为合适的评估体系，那接下来该如何去根据评价性反馈来采取行动呢？这时候先要提到两个概念：

Exploitation 对于每一步而言，是能尽量利用上当前已掌握知识的最佳策略，能确保回报玩家认知范围内的最佳奖励值；Exploration 则会去“试错”，去尝试一些信息量少的 action ，这些 action 之所以信息量少，是因为在玩家的评估体系中被认为是低回报 action 而很少被选中，从而收获到的信息少。

不过这个低回报，既有可能是真的低回报，也有可能是被低估了，如果这个 action 事实上是一个很有价值的 action ，网上电子游戏却因过分低估而被玩家放弃，是一件非常可惜的事情。

为了避免这一情况，从长远意义上真正地最大化收益，就需要玩家适当地去探索、去试错。

信息越多，做出的选择也越客观。

可以想象，纯贪心行动很有可能陷入局部最优解（最坏情况下，贪心行动甚至可能导致玩家从头到尾都在选择一个固定的非最优的 action），很难实现让每个 action 都能满足

这时候，就需要去“探索（Exploring）”，牺牲一点眼前的利益，换来能带来长远价值的信息。

只需对贪心策略稍作修改，我们就能做到这一点。

为了确保实验结果的准确性，总共随机生成了 2000 个 k-armed bandit 问题（k=10），然后针对每个问题，在其背景下都要进行 1000 步 action 的选择，最终针对这 2000 个独立的实验的结果来逐步取均值分析。

首先，需要理解的是，是一个来自于对应的正态分布的随机值。

举个例子，玩家在第 t 步选择 action 3 ，那么这一步老虎机返回给玩家的奖励值就是一个服从正态分布的随机值，这个值或高或低，但总体的趋势还是大概率为附近的一个值。

我们从上帝视角是知道这些值的，但是玩家并不知道这些情况，只能一步一步地收集信息，以此来猜测、学习这些奖励值的规律。

然后，这些是多少呢？这些是我们在初始生成 2000 个问题时随机定下来的，我们从标准正态分布中选出 2000 组数据，1 组数据对应生成一个老虎机问题，每组数据有 10 个（所以其实是从中选出了个随机数），分别表示这个问题下的。

贪心策略只有约 1/3 的次数选到了最优 action，而 ε-贪心策略的表现则显然比单纯的贪心策略好很多，进一步验证了我们认为贪心策略陷入局部最优解的猜想。

ε = 0.1 要比 ε = 0.01 选中最优解的概率更大，这与其重视 Exploration 离不开关系，但事实上实验结果表示，最终的总 reward 还是 ε = 0.01 要高一些，原因在于其有 99% 的时间处于 Exploitation 阶段，信息的利用率更高，ε = 0.1 时，Exploitation 的时间只有 90% ，即使探索到了足够多的信息，但是利用率不够高，导致最终效果不如前者。

所以，通过实验，我们看出，Exploration 确实很重要，但是也不能过度探索，需要掌握好平衡。

设表示第 i 次选到 a 时系统返回的奖励值，表示在前 n 次执行 action a 的经验基础上，对下一次再选到 a 的预测值，那么就有

不难看出，我们一直需要存储每一个，空间复杂度为，这显然程序跑到后面，会有着巨大的内存占用。

不过，通过一个小技巧便可解决：

前面的讨论，都是基于固定奖励值分布这一条件的，即这一事实在问题生成好之后都是一直保持不变的。

然而现实中问题肯定不会如此理想，那么如果这个奖励值分布不是固定不变的，我们该如何解决呢？

显然，这种情况下玩家需要将学习的重心放在每一步近期的奖励值分布情况上，这是因为，奖励值分布的变动，网上电子游戏如果有规律的话，无论是周期性还是连续性等，都只会更多地体现在较近时刻，而很久之前的某个 reward 对于这一步而言已经很难看出其影响意义。

（再强调一遍，这几节的很多式子都是为了简化而针对某一个 action 而言的，可以看作是所有 action 的通式，不要理解错了）

可以看出，当 i 很大时，在式子中的影响占比才更大，这也符合了我们要将学习重心放在近期 reward 的要求。

下面再讲将设为常量的另一个重要原因。

我们先回到一般情况，对于，其中的是任意的，也即 step-size 是变长的，对于这样一组序列，如果满足随机逼近理论中的一个条件

易见，满足条件能够让其收敛，而(为常量) 则由于不满足条件中的第二项，使不能收敛。

看似这是一个坏结果，其实这一结果反而能被利用在非稳定（nonstationary）问题中，这是因为，一个不收敛的波动的其实更适合用来描述非稳定问题下的奖励值，而前面收敛的反而可能失去了非稳定环境下的一些关键波动信息。

不难看出，前面讨论的所有方法，对每个 action 而言，评估体系显然都会一定程度上受到初始值的影响。

在统计学中，这叫做被初值偏置了。

初始预估值可以用来根据先验信息提供奖励的期望标准。

此外，如果将初始值调高，还有着鼓励模型在早期更多地进行探索的作用。

以贪心策略为例，一个很高的初始预期值（称为乐观初值），会诱使模型去选择这个 action ，然而事实上 reward 要比估计值差很多，误差值会是一个较大的负数，导致模型对这个 action “失望”，评价降低，下一次，模型就会去主动尝试其他 action 。

通过这一方法，达到了鼓励模型在早期多做探索的作用。

下面是一个具体的实验，“高初始值的 greedy 策略” vs “正常初始值的 ε-greedy 策略”。

从图片可以看出，即使是纯贪心行动，由于一开始给定较高初始值，模型便如我们分析的一样，在早期进行了大量探索，收获了大量有用的信息，从而也能摆脱局部最优，达到全局最优解，而且其后期几乎 100% 利用率的优势，使其比该实验中 ε-greedy 方法的效果还要优秀。

但是乐观初值法的适用面很窄，它仅适用于固定分布的问题。

我们知道模型只会在早期多做探索，后期基本上仍是以 Exploiting 为主，对于非稳定的情况，必然需要时刻探索收集信息，此时乐观初值法就不再适用。

这一节讲到一个考虑得更全面的评估算法：Upper-Confidence-Bound(UCB)算法。

简单讲，就是我们之前的 ε-greedy 方法虽然能保证最终能探索到足够的信息，但是效率不高，因为他只是简单的随机探索，探索时每个 action 都是等概率被选择的。

我们可以想一想人是怎样探索学习的。

人在探索过程中，通过探索学到的知识，肯定会建立一套标准来判定好坏，如果重复执行某个 action ，一直返回一个低回报，那么必须要动态调整探索策略，适当调低再探索这个 action 的概率，而要尽可能多去探索“潜力”更高的 action 。

UCB 算法做的就是这么一件事。

：第 t 步之前 action a 被选中的次数。

如果增加，会给公式中的此项带来降低的影响效果。

：时间必然会增加，故此项也是一直在保持增加的。

但他的影响效果与 action a 的选择状态密切相关。

如果 a 不被选择，增加但不变，网上电子游戏故此项变大，不确定性增加；反之，，虽然增加但其增速不如，所以此项整体变小，不确定性降低。

所以，通过取便能动态调整探索策略，适当地提高更加不确定、有潜力的 action 被探索的概率。网上电子游戏

通过对比实验发现，UCB 算法确实表现要优于普通的 ε-greedy 算法。

但是作者也提到，对于更一般的强化学习问题，UCB 算法会遇到一些难点，不再那么适用，比如非稳定问题、大状态空间问题等。

前面几种算法，都是在围绕着进行取然后直接执行 action 的策略，显得有点偏激，一个看上去更合理的做法是，每个 action 对其评分后，确定一个概率分布，然后以这种分布下的趋势去做选择，而非凭借数值的绝对大小去做选择。网上电子游戏同时根据这些趋势，也能达到动态探索的效果。

这便是 Gradient Bandit Algorithms 。网上电子游戏

其中，是 action a 的偏好值，也就是前面提到的对每个 action 的评分，然后根据soft-max函数来给出选择每个 action 的概率分布。

在给定的条件下，，又与其他项不相关，故对于上式，期望意义下可以把替换为，此时再将任设的定为的均值，则有

关于的更新式中这一项，他起到一个对比基准线的作用，事实上这个基准线不一定设为均值，他的取值并不影响更新式的方差。

作者表明，其实设为均值并不一定能达到最佳效果，但总体而言是一个简单方便且效果较好的一个选择。

上图中的实验简单对比了 baseline 为均值和 baseline 为 0 时的不同效果。

本文的一开头，我们提到本章主要针对“非关联性（nonassociative）”的简单场景来学习基础的强化学习方法。

而非关联性在本章就是指无需考虑每一步行动之间的影响，以及环境对行动的影响。

非关联性问题是一种很理想化的问题，现实中很多东西都是有所联系的，包括 action 与 action 之间的关联， action 与环境之间的关联等等。

这一小节，就是关于关联性问题做了一个最基本的简单介绍。

简单而言，网上电子游戏之前一直讨论的 nonassociative 问题可以看作现在这个问题下 m=1 的特例。

在这个新任务中，我们不但要像之前一样通过探索和利用来学习每个问题的情况，还要把问题之间的关联性也学出来，也就是把环境因素也考虑进来。