多任务学习时转角遇到Bandit老虎机

注：本文的正文干货转载并少量修改自大佬覃含章（知乎id同名，知乎必关的数值优化大佬啊啊）的一篇知乎回答，链接

https://www.zhihu.com/question/53381093/answer/562235053

一个转角

事情是这样的，最近小夕在做NLP多任务学习相关的一些工作嘛，然后有一天，老大甩给小夕一篇paper

NAACL2019 | AutoSeM: Automatic Task Selection and Mixing in Multi-Task Learning

诶？看起来很有意思的样子，辅助任务不用自己选啦？mix ratio不用手调了？上图上图！！

不过小夕最近大半年的时间里炼丹炼多了（都怪BERT，又让我的数学退化了(｡ ́︿ ̀｡)），论文里各种熟悉的名词如Beta分布，Gamma函数等竟然都一时没想起来是什么，LDA白学了啊喂。

虽然可以通过上面这张图感性的理解Multi-arm Bandit（MAB，多臂老虎机）的原理，但是理性的数学公式这个小夕曾经觉得最直观的表达方式如今却变得如此陌生！！！天，我也太堕落了叭！于是最近借着这篇paper把相关的数学概念和MAB相关的一些理论啃一啃，真的不能变成一个无脑炼丹的攻城师啊喂(╯°□°）╯︵ ┻━┻

RL核心问题

要了解MAB (multi-arm bandit)，首先我们要知道它是强化学习 (reinforcement learning) 框架下的一个特例。

先来重新回顾一下什么是强化学习，以及RL的核心问题是什么。

我们知道，现在市面上各种“学习”到处都是。比如现在大家都特别熟悉机器学习（machine learning）,或者许多年以前其实统计学习（statistical learning）可能是更容易听到的一个词。那么强化学习的“学习”跟其它这些“学习”有什么区别呢？

这里自然没有什么标准答案，有这样一个解释（也可见Sutton & Barto第二章引言）：在传统的机器学习中，主流的学习方法都是所谓的“有监督学习”（supervised learning），不管是模式识别，神经网络训练等等，你的分类器并不会去主动评价（evaluate）你通过每个样本所得到的训练结果（反馈），也不存在主动选择动作（action）的选项（比如，可以选择在采集了一些样本之后去采集哪些特定的样本）。

意思就是，在这些传统的机器学习方法中（实际上也包括其它无监督学习或者半监督学习的很多方法），你并不会动态的去根据收集到的已有的样本去调整你的训练模型，你的训练模型只是单纯被动地获得样本并被教育(instruct，作为对比，active learning主要就是来解决这一问题的）。

而强化学习主要针对的是在一个可能不断演化的环境中，训练一个能主动选择自己的动作，并根据动作所返回的不同类型的反馈（feedback），动态调整自己接下来的动作，以达到在一个比较长期的时间段内平均获得的反馈质量。因此，在这个问题中，如何evaluate每次获得的反馈，并进行调整，就是RL的核心问题。

这么讲可能还比较抽象，但如果大家熟悉下围棋的AlphaGo，它的训练过程便是如此。我们认为每一局棋是一个episode。整个的训练周期就是很多很多个epsiode。那么每个episode又由很多步（step）构成。

动作——指的就是阿法狗每步下棋的位置（根据对手的落子而定）

反馈——每一次epsiode结束，胜负子的数目。

显然，我们希望能找到一个RL算法，使得我们的阿法狗能够在比较短的epsisode数目中通过调整落子的策略，就达到一个平均比较好的反馈。当然，对这个问题来说，我们的动作空间（action space，即可以选择的动作）和状态空间（state space，即棋盘的落子状态）的可能性都是极其大的。因此，AlphaGo的RL算法也是非常复杂的（相比于MAB的算法来说）。

Bandit老虎机

多臂老虎机简称MAB，我们先考虑最基本的MAB问题。

如上图所示，你进了一家赌场，假设面前有 K 台老虎机（arms）。我们知道，老虎机本质上就是个运气游戏，我们假设每台老虎机 i 都有一定概率 p_i 吐出一块钱，或者不吐钱（ 概率 1-p_i ）。假设你手上只有 T 枚代币（tokens），而每摇一次老虎机都需要花费一枚代币，也就是说你一共只能摇 T 次，那么如何做才能使得期望回报（expected reward）最大呢？

这就是最经典的MAB场景。

那么问题的核心是什么呢？自然，我们应该要假设 p_i 们是不太一样的（不然怎么摇都一样了），即有一些老虎机比较“好”（更容易吐钱），有一些则比较“差”（不太容易吐钱）。回到RL的框架，我们的动作是什么？即每次摇哪台老虎机。我们的反馈呢？即我们摇了某台特定的老虎机当回合可以观察它吐了钱没有。

这里当然还有个重要的统计学/哲学问题：即我们是贝叶斯人（Bayesian）还是频率学家（frequentist）。

对贝叶斯人来说，我们在一进入赌场就对每台老虎机扔钱的概率 p_i 就有一个先验分布（prior distribution）的假设了，比如一个很常见的我们可以用Beta分布。如果我们认为大概率 p_i 都应该是0.5，即对半开，而不太可能出现一些很极端的情况，我们就可以选择Beta(1,1)分布作为我们的先验分布。然后在我们真正摇了老虎机之后，根据相应的反馈，我们就可以调整 p_i 们相应的后验分布（posterior distribution）。

比如如果某台机器摇了四五次一直吐不出钱，我们就应该将这台机器的吐钱概率的分布往左推，因为它的 p_i 大概率应该是小于0.5的。那么，你的任务便是要在有限的时间内找出 p_i 后验分布比较靠右的那些机器（因为他们更容易吐钱），并且尽可能多的去摇这些比较赚钱的机器。

而如果你是频率学家，就没什么先验或者后验分布了，你假设你一开始对这些机器的吐钱概率一无所知。你认为每个机器的p_i 是个确定的值。那么，你的任务就是要在有限的时间内找到那些高 p_i 的机器，并尽可能多的去摇它们，以获得更多的回报。

那么这里我们注意到这类问题的一大特点，即我们只有 T 次摇机器的机会，如何去平衡这 T 次中exploration（探索）和exploitation（挖掘）的次数。探索意味着广度，比如如果你是频率学家，你一开始什么都不知道，你至少每个机器都需要稍微摇几次（假设 T>K ) ，不然问题就无法搞定了）才能对每个机器吐钱概率有个大概感觉。然后，你可能会缩小你的搜索范围，再几台机器里重点实验，最后可能就专门摇一台你觉得最容易吐钱的机器了。当然，我们之后会看到这种办法也未必是最好的。

一些MAB变种

最后说下MAB问题可能的一些（更复杂的）变种。首当其冲的在于，我们前面的讨论默认了环境是不会变化的。而一些MAB问题，这个假设可能不成立，这就好比如果一位玩家发现某个机器的 p_i 很高，一直摇之后赌场可能人为降低这台机器吐钱的概率。在这种情况下，MAB问题的环境就是随着时间/玩家的行为会发生变化。

这类问题，在合理的假设下，也是有不少研究和相应的算法的。目前做的最多的假设，也就是所谓的adversarial bandit（就不是stochastic bandit了），就是说这些 p_i 会被一个“对手”（也可以看成上帝）设定好。如果这是事先设定好，并且在玩家开始有动作之后也无法更改，我们叫做oblivious adversary setting; 如果这个对手在玩家有动作之后还能随时更改自己的设定，那就叫做adaptive adversary setting, 一般要做成zero-sum game了。此外，最近也有一些随机但nonstationary的假设下的工作。  

另外MAB有一类很重要的变种，叫做contextual MAB(cMAB)。几乎所有在线广告推送（dynamic ad display）都可以看成是cMAB问题。在这类问题中，每个arm的回报会和当前时段出现的顾客的特征（也就是这里说的context）有关。

另外，如果每台老虎机每天摇的次数有上限，那我们就得到了一个Bandit with Knapsack问题，这类问题以传统组合优化里的背包问题命名，它的研究也和最近不少研究在线背包问题的文章有关，之后我们也会专门讨论。还有很多变种，如Lipshitz bandit, 我们不再有有限台机器，而有无限台（它们的reward function满足利普西茨连续性）等。

最后，虽然转角遇到的不是爱，而是老虎机，但是看起来也蛮好玩的嘛！