从新手到专家：面向众感知中工人性能演变的成本感知型Bandits

# 从新手到专家：面向演化工人表现的代价感知老虎机  
来源：https://arxiv.org/html/2607.13546  
Yin Huang Qingsong Liu Jie Xu  

Y\. Huang 和 J\. Xu 任职于佛罗里达大学电气与计算机工程系。电子邮件：\{yin\.huang, jie\.xu\}@ufl\.edu。Q\. Liu 任职于马萨诸塞大学阿默斯特分校信息与计算机科学曼宁学院。电子邮件：qingsongliu@umass\.edu。

###### 摘要  

移动群智感知（MC）通过招募移动用户使用其智能手机执行感知任务，实现了交通监控和环境感知等大规模应用。一个基本挑战是不确定性下的在线工人招募：平台必须在有限预算下学习工人的感知表现。现有的基于学习的 MC 招募方法通常假设每个工人的感知质量是平稳的，即随时间均值固定。然而在实践中，工人的表现常随经验提升并最终稳定，而由于设备和情境状态的时变性，感知成本可能事先未知。本文研究一个预算约束下的在线招募问题：平台每轮选择一名工人，观察其感知质量和产生的成本，其中每位工人的期望感知质量随参与次数增加并最终收敛至一个平台，重复该过程直至预算耗尽。我们将此问题建模为一个结构化老虎机模型，其中每位工人的期望奖励根据其参与次数遵循一条未知的递增-收敛函数，且每位工人有一个未知的期望成本。我们提出了一个代价感知的在线学习框架，该框架联合学习演化的奖励轨迹和异构成本，检测表现饱和点，并分配有限预算以最大化长期感知效用。我们提供了理论性能保证，并通过大量实验验证了所提方法，展示了相对于忽略经验驱动动态或假设成本已知的基线方法的持续改进。

###### 索引词：众包、多臂老虎机、工人选择、预算约束。

## 1 引言  

移动群智感知（MC）已成为通过日常移动设备从广泛地点收集数据的强大范式[25 (https://arxiv.org/html/2607.13546#bib.bib63)]。通过利用无处不在的智能手机的传感器和连接性，MC 实现了任何单一用户都无法实现的大规模感知应用。例如，MC 平台已被用于监测城市交通、测量城市噪声和污染水平，以及绘制无线网络覆盖图。在典型的 MC 系统中，中央平台招募一群智能手机用户（工人）来执行感知任务，聚合他们的贡献以构建丰富的时空数据集。这类应用的成功取决于有效的工人招募，即选择合适的参与者，在有限预算和异构设备能力等实际约束下最大化数据质量。

尽管对 MC 招募和任务分配算法已有广泛研究，但大多数先前的模型假设每位工人的感知表现随时间固定或平稳。然而在现实中，参与者的表现会随着经验积累而演化。正如在线平台上的众包工人在完成每项任务后会学习和提高一样，MC 参与者可能通过重复参与变得更加熟练于感知任务。来自众包的经验证据支持这种学习效应：例如，观察到 Topcoder 开发者的准确性[39 (https://arxiv.org/html/2607.13546#bib.bib58)]随完成的任务数量显著提高，最终稳定在高水平。我们将此行为建模为每位工人的期望奖励遵循一条*递增-收敛*轨迹，这种结构同时捕捉了早期学习和最终表现饱和。这表明当前群智感知框架中存在一个关键空白：工人的提升动态基本被忽略。不考虑学习意味着现有方法可能低估那些经过更多经验可能成为顶尖表现者的新手工人，或者过度投入那些已达到其表现平台期的个人。

虽然先前的工作利用多臂老虎机（MAB）框架为 MC 系统中的工人选择建模[9 (https://arxiv.org/html/2607.13546#bib.bib86),34 (https://arxiv.org/html/2607.13546#bib.bib71),42 (https://arxiv.org/html/2607.13546#bib.bib72)]，但这些公式通常假设每位工人的质量是平稳的，并由一个固定的未知奖励参数表示。在本工作中，我们考虑一个移动群智感知系统，其中有一个小的固定参与者池，每项任务分配给一名工人。这一设置受到短期活动的启发，这些活动由特定地点的微任务构成，例如街道问题验证（如坑洼或路灯故障）、店内零售审计（如价格检查或货架可用性检查）以及局部环境测量（如噪声或空气质量读数）。在这些场景中，平台自然地在当前可用参与者范围内运作，每次分配对应一个报告、访问或测量[22 (https://arxiv.org/html/2607.13546#bib.bib81),8 (https://arxiv.org/html/2607.13546#bib.bib74),26 (https://arxiv.org/html/2607.13546#bib.bib75),37 (https://arxiv.org/html/2607.13546#bib.bib84),9 (https://arxiv.org/html/2607.13546#bib.bib86)]。每轮中，平台将感知任务分配给一名工人，观察获得的感知质量和产生的成本，然后更新其招募策略用于后续轮次；当累积成本耗尽总预算时过程终止。在这个序贯决策过程中，平台必须平衡探索与利用，因为工人的感知质量和招募成本初始都是未知的。预算约束进一步放大了探索的成本，因为每次试验都消耗有限资源。此外，工人的感知质量是非平稳且个性化的：一名工人可能在早期参与中随经验提升，然后逐渐稳定，而不同的工人可能表现出不同的学习速度和平台水平。最后，我们还以现实的方式考虑了未知成本。在实践中，工人的有效感知成本取决于其即时设备和情境状态，如电池电量、网络状况和周围环境；因此，即使平台采用预先指定的成本函数，工人特定的成本参数也并非先验已知，而是由工人每轮基于这些因素进行估计，使得平台需在线学习期望成本。

在本文中，我们将在线工人选择问题形式化为一个结构化老虎机设置：每位工人的期望感知质量遵循一条未知的递增-收敛函数，而期望成本产生一个固定但未知的成本。目标是在工人之间分配有限的任务预算，以最大化累积获得的感知质量。该设置不仅需要解决不确定性并学习异构成本，还需要对每位工人的完整学习轨迹进行建模，包括其初始技能水平、提升速度和收敛点。为了解决这一问题，我们开发了 *Time-Increasing Upper Confidence Bound* (TI-UCB) 算法的代价敏感扩展，称为 CATI-UCB，该算法设计用于结构化奖励动态和预算约束下运行。CATI-UCB 结合了三个核心组件：它使用奖励-成本比来指导探索与利用；它拟合在线线性模型以估计每位工人的早期学习行为；它采用变点检测来识别学习何时饱和。这些组件协同工作，根据工人的长期效率而非短期奖励自适应地优先排序工人。我们证明了 CATI-UCB 相对于最优策略实现了次线性遗憾，并通过实验表明其显著优于那些忽略时间奖励结构或假设平稳性的现有基线方法。

总结来说，我们的主要贡献如下：
- • 我们在众包中提出了一个新的在线工人选择问题，其中每位工人的期望奖励遵循一条未知的递增-收敛函数，且期望成本产生一个固定但未知的成本。该设置捕捉了真实的工人学习动态，并引入了超出标准平稳老虎机模型的新算法挑战。
- • 我们提出了 CATI-UCB，一种结构化老虎机算法，联合处理不确定性、代价感知和非平稳奖励动态。该算法通过在线线性回归估计每位工人的学习曲线，通过变点检测检测表现饱和，并基于奖励-成本比的上置信界选择工人。
- • 我们证明了 CATI-UCB 在非平稳奖励下相对于最优策略实现了对数遗憾。
- • 我们通过大量模拟真实工人学习模式的合成实验评估了 CATI-UCB。结果表明 CATI-UCB 始终优于基线方法。

## 2 相关工作  

**移动群智感知与工人招募：** 移动群智感知（MC）研究如何招募移动用户在不确定性下执行感知任务，大量工作利用多臂老虎机或相关框架将工人招募形式化为在线学习问题，以处理未知的工人质量、有限预算和激励约束[13 (https://arxiv.org/html/2607.13546#bib.bib68),12 (https://arxiv.org/html/2607.13546#bib.bib70),41 (https://arxiv.org/html/2607.13546#bib.bib69),34 (https://arxiv.org/html/2607.13546#bib.bib71),42 (https://arxiv.org/html/2607.13546#bib.bib72),35 (https://arxiv.org/html/2607.13546#bib.bib87),28 (https://arxiv.org/html/2607.13546#bib.bib92),33 (https://arxiv.org/html/2607.13546#bib.bib91)]。近年来的研究进一步拓宽了 MC 招募的范围，例如通过社交网络辅助招募解决参与不足问题[38 (https://arxiv.org/html/2607.13546#bib.bib85)]，或研究在时间变化资源-质量权衡下的动态在线调度[9 (https://arxiv.org/html/2607.13546#bib.bib86)]。这一系列工作通常研究在新观察反馈下的序贯服务器分配招募，这也是本文考虑的设置。然而，大多数现有的基于学习的 MC 公式要么假设工人质量平稳，要么关注其他不确定性，如真值发现、信任/声誉、请求方不确定性或激励设计[13 (https://arxiv.org/html/2607.13546#bib.bib68),12 (https://arxiv.org/html/2607.13546#bib.bib70),35 (https://arxiv.org/html/2607.13546#bib.bib87),28 (https://arxiv.org/html/2607.13546#bib.bib92),33 (https://arxiv.org/html/2607.13546#bib.bib91)]。相比之下，我们的工作聚焦于非平稳性的一个不同来源：工人的期望感知奖励随重复参与提升并最终饱和。受技能提升经验证据[39 (https://arxiv.org/html/2607.13546#bib.bib58)]的启发，我们将每位工人的期望奖励建模为参与次数的*递增-收敛*函数，同时在有限预算下在线学习工人成本。

**非平稳老虎机：** 我们研究的递增-收敛奖励趋势与非平稳老虎机文献紧密相关，后者处理随时间变化的奖励分布[18 (https://arxiv.org/html/2607.13546#bib.bib93),19 (https://arxiv.org/html/2607.13546#bib.bib95)]。现有方法通常假设分段平稳[14 (https://arxiv.org/html/2607.13546#bib.bib48),7 (https://arxiv.org/html/2607.13546#bib.bib50),6 (https://arxiv.org/html/2607.13546#bib.bib52)]或平滑变化[6 (https://arxiv.org/html/2607.13546#bib.bib52),30 (https://arxiv.org/html/2607.13546#bib.bib53)]的奖励，并通过滑动窗口、变点检测或折扣技术进行适应。最近，**休息老虎机** (rested bandits)[36 (https://arxiv.org/html/2607.13546#bib.bib12),31 (https://arxiv.org/html/2607.13546#bib.bib8),21 (https://arxiv.org/html/2607.13546#bib.bib7)]被提出，其中奖励取决于臂被拉动的次数，捕捉了技能获取等趋势。一些工作对单调或递增奖励模式进行建模[15 (https://arxiv.org/html/2607.13546#bib.bib11),27 (https://arxiv.org/html/2607.13546#bib.bib15)]，但大多数这些方法假设简化或确定性的趋势，并未明确对技能型任务中观察到的递增-收敛模式进行建模。最近的工作[40 (https://arxiv.org/html/2607.13546#bib.bib4)]考虑了与我们类似的递增-收敛结构，但聚焦于模型选择，未涉及预算约束。相比之下，我们的工作将递增-收敛结构与有限预算下的代价敏感在线学习相结合，实现了更高效的资源分配。

**带背包的老虎机：** “带背包的老虎机”（BwK）将多臂老虎机问题扩展到资源有限的环境，旨在预算约束下最大化总奖励[4 (https://arxiv.org/html/2607.13546#bib.bib39),5 (https://arxiv.org/html/2607.13546#bib.bib40),17 (https://arxiv.org/html/2607.13546#bib.bib94)]。应用包括动态定价[3 (https://arxiv.org/html/2607.13546#bib.bib41)]、采购[32 (https://arxiv.org/html/2607.13546#bib.bib42)]和按点击付费广告分配[10 (https://arxiv.org/html/2607.13546#bib.bib43)]。BwK 研究可大致分为随机和对抗两种设置。在随机情况下，每个臂遵循固定但未知的分布[4 (https://arxiv.org/html/2607.13546#bib.bib39),2 (https://arxiv.org/html/2607.13546#bib.bib44),1 (https://arxiv.org/html/2607.13546#bib.bib45),23 (https://arxiv.org/html/2607.13546#bib.bib13)]，已通过逐次消除[4 (https://arxiv.org/html/2607.13546#bib.bib39)]、UcbBwK[2 (https://arxiv.org/html/2607.13546#bib.bib44)]和原始-对偶算法[23 (https://arxiv.org/html/2607.13546#bib.bib13)]实现了最优遗憾界。在对抗情况下，奖励可被对手操纵[20 (https://arxiv.org/html/2607.13546#bib.bib46),29 (https://arxiv.org/html/2607.13546#bib.bib47)]。最近的工作还探索了非平稳 BwK[24 (https://arxiv.org/html/2607.13546#bib.bib21)]。然而，这些方法通常不考虑技能型任务中观察到的递增-收敛模式，导致次优性能。相比之下，我们的 CATI-UCB 明确建模了这一趋势，并在预算约束下自适应检测收敛点，在在线工人招募中无论在理论上还是实验上都优于先前方法。

## 3 系统模型  

我们考虑一个移动群智感知（MC）设置，其中请求方发起一个短期感知活动，具有固定预算，平台负责在一个固定池中由 \(K\) 名已承诺且当前可用的移动工人间协调任务分配，如图 1 (https://arxiv.org/html/2607.13546#S3.F1) 所示。活动以轮次进行。在每一轮中，平台选择一名工人执行一个感知任务（例如，在一个交叉口拍摄交通照片）。