首先，据说这个问题名字的来源是这样的，赌场里的老虎机[slot machine]有一个绰号叫单臂强盗[single-armed bandit]，因为它即使只有一只胳膊，也会把你的钱拿走。所以，当你进入一个赌场，面对一排老虎机，就像面对了一个多臂强盗，而Multi-Armed Bandit就是这样引申而来[当然还有一个说法是，可以把一排老虎机想象成一个老虎机有很多个臂，其实本质是一样的]。那么问题来了，由于不同老虎机的期望收益和期望损失不同，你采取什么老虎机选择策略来保证你的总收益最高呢？这就是经典的Multi-Armed Bandit问题。

这个经典问题集中体现了在线学习[online learning]及更宽泛的强化学习[reinforcement learning]中一个核心的权衡问题：我们是应该探索[exploration]去尝试新的可能性，还是应该守成[exploitation]，坚持目前已知的最好选择？

在Multi-Armed Bandit问题中，探索[exploration]意味着去玩还没玩过的老虎机，但是因为探索意味着不确定，这有可能使你花太多时间和金钱在收益不好的机器上；而守成[exploitation]意味着只玩目前为止给你收益最好的机器，但这又可能使你失去探索并且找到更好机器的机会。而类似抉择在日常生活中随处可见：去一个餐厅，你是不是也纠结于是点熟悉的菜品，还是点个新菜？去一个地方，是走熟知的老路还是选一条新路？而探索和守成的权衡就是在线学习的核心。

Multi-Armed Bandit的提出和研究最早可以追述到上世纪三十年代，其研究模型和方法已有很多。其解决方案涉及一个重要的统计学/哲学问题并且因此分为两派，你选择贝叶斯派[Bayesian]还是频率学派[Frequentist]?

如果你选择贝叶斯派，那么你的典型方法就是根据环境给予的反馈遵从某种随机但未知的分布，在线学习的过程就是要学出这个未知分布中的某些参数，而且要保证整个学习过程的整体收益尽量高。就是根据环境反馈猜一下概率分布的参数，然后用参数计算最大的收益，以及如何获得最大的收益。那么你在一进入赌场的时候，就会对每台老虎机扔钱的概率$p_i$就有一个先验分布[prior distribution]的假设了，比如一个很常见的我们可以用Beta分布。如果我们认为大概率$p_i$都应该是0.5，即对半开，而不太可能出现一些很极端的情况，我们就可以选择Beta(1,1)分布作为我们的先验分布。然后在我们真正摇了老虎机之后，根据相应的反馈，我们就可以调整$p_i$相应的后验分布[posterior distribution]。比如如果某台机器摇了四五次一直吐不出钱，我们就应该将这台机器的吐钱概率的分布往左推，因为它的$p_i$大概率应该是小于0.5的。那么，你的任务便是要在有限的时间内找出$p_i$后验分布比较靠右的那些机器[因为他们更容易吐钱]，这项任务就是探索[exploration]，找到之后尽可能多的去摇这些比较赚钱的机器，这就是守成[exploitation]。UCB[Upper Confidence Bound]方法是一个经典方法，能够通过严格的理论论证说明UCB可达到接近理论最优的整体收益。

如果你选择频率学派，那就没什么先验或者后验分布了，你假设你一开始对这些机器的吐钱概率一无所知。你认为每个机器的吐钱的概率$p_i$是个确定的值。那么，你的任务就是要在有限的时间内找到那些高$p_i$的机器，并尽可能多的去摇它们，以获得更多的回报。那么这里我们注意到这类问题的一大特点，即我们的资源是有限的，我们只有$N$次摇机器的机会，如何去平衡这$N$次中探索[exploration]和守成[exploitation]的次数。探索意味着广度，比如如果你是频率学家，你一开始什么都不知道，你至少每个机器都需要稍微摇几次才能对每个机器吐钱概率有个大概感觉。然后，你可能会挑几个回报大的机器来缩小你的搜索范围，然后再次探索这几个选中的机器，最后可能就专门摇一台你觉得最容易吐钱的机器了[这就又来到了exploitation阶段]。当然，这种办法也未必是最好的，只是用来说明频率学派如何理解Multi-Armed Bandit问题。

Reference

  1. Multi-armed bandit, https://en.wikipedia.org/wiki/Multi-armed_bandit

  2. 微软亚洲研究院，求通俗解释下bandit老虎机到底是个什么东西？ https://www.zhihu.com/question/53381093/answer/245802834

  3. 覃含章, 求通俗解释下bandit老虎机到底是个什么东西？ https://www.zhihu.com/question/53381093/answer/562235053

  4. Frequentist inference, https://en.wikipedia.org/wiki/Frequentist_inference

  5. Bayesian inference, https://en.wikipedia.org/wiki/Bayesian_inference