多臂赌博机问题导论

许多实际应用需要解决序列决策问题，其中智能体必须在多个备选方案中选择最佳行动。这类应用的例子包括临床试验、推荐系统和异常检测。在某些情况下，每个行动都关联有辅助信息或上下文（例如用户画像），而反馈或奖励仅限于所选选项。例如，在临床试验中，上下文是患者的医疗记录（如健康状况、家族史等），行动对应于比较的治疗方案，奖励代表所提出治疗的结果（如成功或失败）。在这种背景下，影响长期成功的一个重要方面是在探索（例如尝试新治疗）和利用（选择目前已知的最佳治疗）之间找到良好平衡。

这种探索与利用之间的内在权衡存在于许多序列决策问题中，传统上被表述为赌博机问题，其呈现如下：给定K个可能的行动或“臂”，每个臂关联一个固定但未知的奖励概率分布，在每次迭代中，智能体选择一个臂进行拉动，并接收从相应臂的概率分布中独立于先前行动采样的奖励。智能体的任务是学会选择其行动，以最大化随时间累积的奖励。

多臂赌博机问题表述

经典的多臂赌博机（MAB）问题由K个臂定义，每个臂具有未知的奖励分布。在每个时间步t，智能体选择一个臂a_t ∈ {1, 2, ..., K}，并接收从所选臂的分布中采样的奖励r_t。目标是在T轮中最大化累积奖励，或等效地最小化遗憾，即最优臂的累积奖励与所选臂的累积奖励之间的差异。

注意，智能体必须尝试不同的臂以了解其奖励（即探索收益），同时使用这些学习到的信息来获得最佳收益（利用学习到的收益）。探索与利用之间存在自然的权衡。例如，每个臂恰好尝试一次，然后选择其中最佳者进行拉动。当臂的奖励不确定时，这种方法通常可能导致非常次优的解决方案。

针对此问题已提出不同的解决方案，基于随机表述和贝叶斯表述；然而，这些方法未考虑智能体可用的上下文或辅助信息。

上下文多臂赌博机

MAB的一个特别有用的版本是上下文多臂赌博机（CMAB），或简称为上下文赌博机，其中在每轮选择臂之前，智能体观察一个可能影响臂奖励分布的上下文向量x_t。上下文可以包括用户特征、环境变量或任何相关的辅助信息。目标仍然是最大化累积奖励，但现在策略可以依赖于观察到的上下文。

上下文赌博机因其在个性化推荐系统中的适用性而受到显著关注，其中上下文通常代表用户特征，臂对应于要推荐的不同项目或内容。奖励可能是点击、购买或任何其他形式的参与。

已开发了多种用于上下文赌博机的算法，包括LinUCB（假设上下文与每个臂的期望奖励之间存在线性关系）和带有线性模型的汤普森采样。这些算法在各种应用中表现出强大的经验性能。

多臂赌博机的实际应用

临床试验

在临床试验中，多臂赌博机框架提供了一种伦理的治疗分配方法。上下文包括患者医疗记录、人口统计信息和遗传标记。臂代表不同的治疗方案，奖励指示治疗成功或失败。赌博机算法可以动态地将更多患者分配到有希望的治疗方案，同时仍探索替代方案，可能带来更好的患者结果和更高效的试验。

推荐系统

推荐系统是赌博机算法最成功的应用之一。主要平台使用上下文赌博机来个性化内容、产品和广告推荐。探索组件允许系统发现用户对新项目的偏好，而利用则利用已知偏好最大化用户参与度。这种方法解决了新项目的冷启动问题，并适应随时间变化的用户兴趣。

异常检测

在异常检测系统中，赌博机算法可以优化有限检查资源的分配。上下文可能包括系统指标、网络流量模式或用户行为特征。臂代表不同的检查策略或异常检测模型，奖励反映是否识别出真实异常。这种方法能够将资源自适应地分配到最有希望的检测方法。

其他应用

其他应用包括金融中的投资组合优化、Web开发中的A/B测试、云计算中的资源分配以及教育技术中的自适应学习。赌博机框架的灵活性使其适用于任何在有限反馈和不确定性下需要序列决策的场景。

赌博机算法与方法

随机赌博机

随机赌博机假设每个臂的奖励是从固定分布中独立抽取的。关键算法包括ε-贪婪，以概率1-ε选择最佳臂，以概率ε选择随机臂；上置信界（UCB）算法，基于对臂潜力的乐观估计选择臂；以及汤普森采样，使用贝叶斯后验分布来平衡探索与利用。

对抗性赌博机

对抗性赌博机不对奖励生成做统计假设，将其视为可能由对手选择的任意序列。Exp3算法及其变体专为此设置设计，使用指数加权方案实现对任何奖励序列的次线性遗憾。

贝叶斯赌博机

贝叶斯赌博机维护臂可能奖励分布的概率分布。汤普森采样是最突出的贝叶斯方法，从每个臂奖励参数的后验分布中采样，并选择具有最高采样值的臂。这根据当前不确定性优雅地平衡了探索与利用。

上下文赌博机算法

上下文赌博机算法扩展这些方法以整合上下文信息。LinUCB假设线性奖励函数，并在参数估计周围维护置信椭球。神经赌博机使用深度神经网络建模上下文与奖励之间的复杂关系。这些算法在具有高维上下文的大规模应用中表现出强大性能。

当前趋势与未来展望

多臂赌博机领域正在经历复兴，除了经典赌博机问题外，受多样化实际应用推动的新问题参数和算法不断被引入。当前重要趋势包括将赌博机与深度学习集成，导致能够处理复杂高维上下文的更强大的上下文赌博机算法。

另一个显著趋势是开发用于非平稳环境的赌博机算法，其中奖励分布随时间变化。这对于许多实际应用至关重要，其中用户偏好、市场条件或系统行为不断演变。滑动窗口UCB和折扣技术等算法应对这一挑战。

对协作和分布式赌博机的兴趣日益增长，其中多个智能体同时学习并可能共享信息。这与数据隐私重要的联邦学习设置相关。此外，带有约束和安全考虑的赌博机正获得关注，特别是在医疗保健和金融应用中，必须避免某些行动。

未来研究方向包括为非常大的行动空间开发更高效的算法，整合关于行动空间的结构信息，以及改进对深度赌博机算法的理论理解。赌博机与因果推断的交叉代表了另一个有希望的方向，当干预可能具有长期效应时，能够实现更好的决策。

结论

多臂赌博机提供了一个强大的框架，用于在有限反馈和不确定性下进行序列决策。基本的探索-利用权衡出现在众多实际应用中，从临床试验到推荐系统。上下文赌博机扩展对于适应个体特征的个性化系统已证明特别有价值。

本调研全面概述了多臂赌博机的主要发展，重点关注实际应用。我们考察了问题表述、关键算法和多样化应用领域。该领域继续快速发展，新算法应对非平稳性、大行动空间和安全约束等挑战。

随着赌博机算法变得更加复杂并应用于日益复杂的问题，它们将继续在各个领域优化决策中发挥关键作用。该领域的持续研究有望在未来产生更有效的算法和更广泛的应用。