多臂老虎机/赌博机/抽奖/问题（Multi-armed Bandit/ Exploration-Exploitation Trade-off）

简介

多臂老虎机（Mulit-armed Bandit，MAB，也有叫K/N-armed bandit problem）是属于率理论中的一个随机调度问题。这里的臂（arm）是老虎机那个拉杆，如下图所示。

在某些领域中（如推荐系统），它也被称为是Exploration-Exploitation Trade-off（探索-利用均衡）问题问题，这是一个基本的困境问题。它需要你考虑是选择你不知道的信息，来探索学习更多的知识（探索，exploration）还是利用你已经知道的信息去获取你期望的回报（利用，exploitation）。例如，在推荐系统中，当一个新用户到达的时候，我们如何快速知道这个用户对不同内容的感兴趣程度，并如何选择推荐列表就是一个典型的EE问题，你需要给一些新的推荐内容来了解用户对这些新内容的兴趣，也要基于已知道的用户兴趣来获得目前最好的推荐结果。

这个问题也是强化学习（Reinforcement Learning）的一个基础。因为这类问题包含着对选择结果的奖励，因此也是强化学习中对动作的评估的重要基础。

回到概率理论中，多臂老虎机问题是一种对有限固定资源进行分配以获得收益最大化的问题，在分配的时候，每一个选择只有部分属性已知，通过分配资源以及时间的增长我们可能对选择有更好的了解。

这个问题来源是假设有一个人站在一排老虎机前，他想决定去哪些老虎机玩才能获得最好的收益，每一台及其应该玩几次，应该按照什么顺序玩，应该继续在当前机器中玩还是换一台机器。这些问题在他知道一部分老虎机的收益概率的时候就可以进行，但是说不定他不了解的老虎机中有收益更高的，所以他也需要花费一定的金钱去试试新的。

在这个问题中，每一台机器都以一个和机器相关的概率分布来随机提供奖励。赌博者的目标是通过一系列操作来最大化收益总和。这个问题的关键是探索（exploration）和利用（exploitation）之间的均衡。它需要考虑利用已有知识获取收益最高机器和探索获取更多机器信息之间的均衡。

多臂老虎机的实际运用有很多：

• 在医学领域研究不同实验治疗的效果，同时尽量减少患者的损失
• 在线广告的分配，对每个用户分配什么广告可以获取最好的收益
• 在推荐系统中，对每个用户已知的兴趣推荐，并探索新兴趣之间如何权衡问题

这个问题最初由盟军科学家在第二次世界大战中考虑过，事实证明它是难以处理的，根据彼得惠特尔的说法，这个问题被提议放在德国以外，这样德国科学家们也会浪费时间在它上面。现在通常分析的问题的版本是Herbert Robbins于1952年提出的。这个问题也简称为Bandit问题。

数学化描述

假设有K个不同的分布\bold{B}=\{R_1,\cdots,R_K\}，每个分布都有一个与之相关的收益，假设用\mu_1,\cdots,\mu_K表示与这些收入相关的概率的均值。赌博者每次都给一个分布一些钱，然后观测与之相关的收益结果。目标是最大化所有的收益总和。假设用H表示剩下还可以玩的局数。那么，Bandit问题通常也等价于一阶马尔科夫决策过程（one-state Markov decision process），在T轮游戏之后有个后悔值\rho，它的定义是最优的收益总和和目前收益之间的差值：

\rho = T\mu^* - \sum_{t=1}^T \hat{r}_t

其中\mu^*=\max_k\{\mu_k\}是最优的收益，而\hat{r}_t是第t轮游戏的收益。

零后悔策略（zero-regret strategy）是指当游戏进行了足够多的局数之后，平均每一轮的后悔值趋向于0。