多臂赌博机

在概率论和机器学习中，多臂赌博机问题（英语：multi-armed bandit problem）^[1]有时称为K-或N-臂赌博机问题（英语：K-or N-armed bandit problem）^[2]，是一个必须在竞争（替代）之间分配一组固定的有限资源的问题。当每个选择的属性在分配时仅部分已知时，以最大化其预期收益的方式进行选择，并且随着时间的推移或通过向该选择分配资源可能会更好地被理解。这是一个经典的强化学习问题，体现了探索-利用权衡困境^[3][4]。这个名字来源于想象一个赌徒坐在一排赌博机（或称角子机、老虎机）前（有时被称为“单臂赌博机”），他必须决定玩哪台机器，每台机器玩多少次以及玩的顺序^[5]，并且是否继续使用当前机器或尝试不同的机器。多臂赌博机问题也属于随机调度的广义范畴。

在该问题中，每台机器根据该机器特定的概率分布提供随机奖励，该奖励是先验未知的。赌徒的目标是最大化通过一系列杠杆拉动所获得的奖励总和^[4]。赌徒在每次试验中面临的关键权衡是在“利用”具有最高预期收益的机器和“探索”以获得有关其他机器的预期收益的更多信息之间^[3]。机器学习也面临着探索和利用之间的权衡。在实践中，多臂赌博机已用于对诸如管理大型组织（如科学基金会或制药公司）中的研究项目等问题进行建模^[3][4]。在问题的早期版本中，赌徒一开始对机器一无所知。

赫伯特·罗宾斯于1952年认识到该问题的重要性，在“实验序贯设计的某些方面”中构建了收敛种群选择策略^[6]。约翰·C·吉廷斯首次发表的吉廷斯指数定理给出了最大化预期折扣奖励的最优策略^[7]。