多臂老虎机问题，有时也称为K臂或N臂老虎机问题，是概率论和机器学习中的一个基础概念。它得名于一个面对一排老虎机（常被称为“独臂强盗”）的赌徒，他必须决定玩哪些机器、每台玩多少次、按什么顺序玩，同时还要决定是坚持当前机器还是尝试不同的机器。更一般地，它描述了一个决策者，在每次分配时每个选择的属性仅部分已知，并可能随时间变得更好理解的情况下，迭代地从几个固定选择（称为臂或动作）中选择一个。一个关键方面是，选择一个臂不会影响该臂或任何其他臂的属性，这使其区别于更广泛的强化学习问题，在后者中动作可以改变未来状态和奖励分布。
该问题体现了探索-利用权衡，这是机器学习中的一个核心困境。赌徒必须在利用已知期望收益最高的机器与探索以收集其他机器更多信息之间取得平衡。目标是通过一系列拉杆操作最大化获得的总奖励。这种权衡出现在许多实际应用中，包括临床试验、自适应网络路由、金融投资组合设计以及研究组织中的资源分配。
多臂老虎机问题最初由盟军科学家在第二次世界大战期间考虑，但据彼得·惠特尔称，它被证明如此棘手，以至于有人提议将其投放到德国上空，以便德国科学家也能浪费时间研究它。现在通常分析的版本是由赫伯特·罗宾斯在1952年提出的，他在其论文《序贯实验设计的某些方面》中构建了收敛的种群选择策略。一个值得注意的理论结果是Gittins指数，由约翰·C·吉廷斯首次发表，它为最大化期望折扣奖励提供了最优策略。
正式模型
多臂老虎机可以建模为一组实数分布 \(B = \{R_1, \dots, R_K\}\)，其中每个分布与 \(K\) 个杠杆之一提供的奖励相关联，且 \(K \in \mathbb{N}^+\)。设 \(\mu_1, \dots, \mu_K\) 为这些奖励分布的均值。赌徒每轮迭代地玩一个杠杆并观察相关奖励，目标是在视界 \(H\)（即剩余轮数）内最大化收集的奖励总和。老虎机问题在形式上等价于一个单状态马尔可夫决策过程。
遗憾，记为 \(\rho\)，衡量最优策略的奖励总和与 \(T\) 轮后收集的奖励之间的期望差异。它定义为 \(\rho = T\mu^ - \sum_{t=1}^T \hat{r}_t\)，其中 \(\mu^\) 是最大奖励均值，\(\hat{r}_t\) 是第 \(t\) 轮获得的奖励。最小化遗憾是老虎机算法的主要目标。
探索与利用
探索-利用权衡是多臂老虎机问题的核心挑战。利用涉及基于当前知识选择估计奖励最高的臂，而探索涉及尝试其他臂以减少对其潜在奖励的不确定性。有效的策略必须平衡这些竞争目标，以最大化长期累积奖励。这种权衡并非老虎机问题独有；它贯穿于机器学习，包括强化学习和人工智能系统，这些系统必须在使用已知策略和发现新策略之间做出决定。
在实践中，多臂老虎机已被用于建模诸如大型组织（如科学基金会或制药公司）中管理研究项目的问题。例如，研究经理必须决定资助哪些项目，平衡利用已知潜力的项目与探索新的、不确定的想法。该模型也已应用于自适应路由以最小化网络延迟，以及金融投资组合设计，其中资产选择涉及类似的权衡。
算法与策略
已开发出几种算法来解决多臂老虎机问题。最早的一种是epsilon-greedy策略，其中代理以概率 \(\epsilon\) 选择随机臂（探索），否则选择估计奖励最高的臂（利用）。另一种流行方法是上置信界（UCB）算法，它基于臂的平均奖励和该估计的不确定性来选择臂，从而以原则性的方式有效平衡探索和利用。汤普森采样是一种贝叶斯方法，为每个臂的奖励维护后验分布，并从这些分布中采样以决定玩哪个臂。
Gittins指数由约翰·C·吉廷斯引入，为某些老虎机设置中最大化期望折扣奖励提供了最优策略。它根据臂的状态为每个臂分配一个指数，最优策略是玩指数最高的臂。这一结果在运筹学和经济学中具有影响力。
应用与实证证据
多臂老虎机框架具有众多实际应用。在临床试验中，它可用于将患者分配到不同治疗组，在收集治疗有效性信息的同时最小化患者损失。在自适应路由中，它通过动态选择网络路径帮助最小化延迟。在金融投资组合设计中，它指导在竞争性投资选项之间分配资源。
一项2024年的研究使用赌场赌博记录，将玩家在未知赔率的老虎机之间的重复选择视为大规模多臂老虎机问题。研究发现，更有经验的玩家倾向于选择赔率更好的机器，并且随着时间的推移，他们在机器选择上表现出更大的一致性，这些模式与学习和更好地利用已知选项一致。这一实证证据支持了老虎机模型与现实世界决策的相关性。
该模型也已被用于控制不同项目之间资源的动态分配，回答在难度和回报不确定的情况下应从事哪个项目的问题。这一应用在研发领域尤其相关，组织必须决定如何在竞争性举措之间分配有限资源。
与强化学习的关系
多臂老虎机问题是一个经典的强化学习问题，体现了探索-利用权衡。然而，它比一般强化学习更简单，因为所选动作不会影响臂的奖励分布。相比之下，在一般强化学习中，动作可以改变环境状态，从而影响未来奖励。这一区别使老虎机成为研究探索-利用困境的易处理起点，许多为老虎机开发的算法已扩展到更复杂的强化学习设置中。
该问题也属于随机调度的广泛范畴，其中必须在不同动作结果不确定的情况下做出决策。这一联系凸显了老虎机模型在从运筹学到人工智能等各个领域的广泛适用性。
总之，多臂老虎机问题是不确定性下决策的基本模型，具有深厚的理论根源和广泛的实践相关性。对其研究产生了优雅的算法和见解，继续为机器学习及其他领域的研究提供信息。