多臂老虎机/赌博机/抽奖/问题（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）的一个基础。因为这类问题包含着对选择结果的奖励，因此也是强化学习中对动作的评估的重要基础。

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

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