具有有限耐心臂的多臂老虎机模型的研究

具有有限耐心臂的多臂老虎机模型的研究

       多臂老虎机 (MAB)，是一种用于描述需要学习未知信息的决策问题的抽象模型。在其典型应用中，算法尝试选择最有回报的臂，而这些臂被动地遵从并接受算法的安排。然而在很多实例中，某些利益驱动的臂可以决定其是否参与。如果参与不能带来足够的收益，它们则有动机退出。例如，考虑一个数据集标注的众包场景，参与标注任务的众包工人会因他们提供的每个标注获得报酬。众包系统通常会持续分配任务给那些已经证明自己能力的工人，而可能忽视其他人。由于只有在任务完成后才能获得报酬，某些工人可能会长时间没有收到任务，从而导致他们无法从平台获得收入。他们可能会失去耐心，转而寻找其他收入来源。

       房智轩团队提出了具有有限耐心臂的多臂老虎机模型，率先对上述现象进行了简单而有力的刻画，并对该模型进行了全面的研究。团队引入了负载因子的概念作为对臂的总体耐心程度的度量。首先，团队以信息论的方法证明了负载因子严格高于某阈值的情况下，不存在任何有效的算法 (有效是指具有次线性的累积后悔值)。其次，团队在负载因子低于该阈值的情况下，对常用的典型MAB算法进行了完备的理论分析。特别地，团队基于布朗桥的性质分析了UCB算法的行为，为SE算法构造了困难实例，从而说明了已有的算法在新的模型中没有有效的理论保证。

图6. FC-SE算法的运行示例

       为此，房智轩团队提出了FC-SE算法，在负载因子低于前述阈值的情况下保证了次线性的累积后悔值。该算法受启发于网络领域中对于信息时效性 (Age of Information) 的研究工作，构造可行循环 (Feasible Cycle) 以权衡对于各个臂的探索频率。另外，团队成员研究了一个更加复杂和通用的模型：允许新的臂随时加入。团队设计了FC-Entry算法，并证明了该算法在此模型中具有有效的理论保证。最后，仿真实验结果表明，FC-SE算法的表现显著优于经典的UCB、SE算法，而FC-Entry算法也同样具有收敛的累积后悔值曲线。

图7. 仿真实验结果—累积后悔值曲线图

       房智轩团队提出具有有限耐心臂的多臂老虎机模型，拓展了MAB模型的适用范畴，为存在利益驱动的参与者的情形提供了新的思路和多种解决方案，在需要动态调整策略的在线广告投放、推荐系统和众包平台等场景中有重要的应用前景。相关成果收录于ICML 2024中。本论文一作为上海期智研究院实习生、清华大学交叉信息研究院博士生邵昱铭。