孔芳，杨悦然，陈卫，李帅

1. 上海交通大学约翰·霍普克罗夫特计算机科学中心，上海 200240；2. 微软亚洲研究院，北京 100080

1 引言

随着数据时代的来临，传统离线学习方法已难以快速处理模型训练所需的爆发式增长的数据量及特征数量，这促进了在线学习模式的发展。在线学习方法接收实时数据流，定义累积懊悔（cumulative regret）取代损失函数作为新的优化函数，利用实时反馈不断迭代调整算法，从而减少离线训练所需的数据量，并提高处理效率。在许多实际问题中，最优解往往不是简单的单个目标，而是多个目标的组合形式，这推进了对组合在线学习问题的研究。组合在线学习问题，即组合多臂老虎机（combinatorial multi-armed bandits，CMAB）问题，结合了在线学习与组合优化，研究如何在与环境交互的过程中自主学习未知参数，逐步找到最优的目标组合，其应用包括社交网络中的广告投放、搜索、推荐等问题。

2 组合在线学习问题

2.1 多臂老虎机问题

多臂老虎机（multi-armed bandits）问题是一个经典的机器学习问题，该问题最初由赌场的老虎机情景演变而来，被建模为玩家与环境之间的T轮在线游戏。老虎机共有m个臂（arm），m个臂的集合即玩家 的 动 作 集 合，记 为每个臂i∈[m]都有各自未知的奖励分布，该分布的期望记作μi。玩家在每一轮游戏t∈[T]拉动其中一个臂，环境将从该臂的奖励分布中采样一个随机变 量XAt,t，作为玩家拉动该臂的奖励值。该奖励值将帮助玩家更新对臂的奖励分布的了解，进而更新其后续选择臂的策略。玩家的目标是最大化T轮的累积期望收益，即最小化与最优臂之间的累积期望收益的距离。……