论文记录-Combinatorial Multi-Armed Bandit Based Unknown Worker Recruitment in Heterogeneous Crowdsensing

Introduction

1. 本文研究问题：异构群智感知系统（也就是众包）中对未知worker的招募
2. 本文场景：requester招募workers收集某城市交通路口一段时间内的交通数据，整个收集过程分为多轮，每轮包含一些和地点有关的任务，对应一个交通路口。每个任务有权重，表示重要性。每个worker能做一个或多个任务，且不同worker能做的任务可能不一样。worker会告诉平台自己能做的任务和期望收到的费用。worker完成任务的质量服从未知分布。
3. 本文目的：设计worker招聘方案，在给定预算的情况下，最大限度提高总任务完成质量。
4. 本文面临的挑战：平台不知道worker的质量分布
5. 本文解决挑战的方法：让worker先完成一些任务，然后从任务结果里学习worker的质量，最后从中找最好的worker，简单来说分为exploration和exploitation。本文需要平衡这两个过程，从而实现目标（这么看一开始被完成的那些任务就被牺牲了）。
6. 本文将上述问题概括为组合多臂老虎机模型（ Combinatorial Multi Armed Bandit），并且说和现存的CMAB模型都不一样；然后本文用扩展的上置信界算法（Upper Confidence Bound）。多臂老虎机模型我之前听说过，但是完全不了解，所以要先查一下。
7. 本文贡献：
   1. 介绍了这个场景并把它概括为多臂老虎机
   2. 用UCB来解决这个问题
   3. 研究了扩展问题：worker质量和期望收费都不知道的场景
   4. 做了仿真实验，分析了性能

Combinatorial Multi Armed Bandit

1. 实质是未知概率情况下的选择问题，比如赌博
2. 具体来说，重复一个选择过程，每次有k个选项或动作可供选择，每次选择一个动作后会获得相应的奖励。目标是为了最大化k次后的奖励。选项对应的收益服从某种未知概率分布，对于实验者本人而言是黑箱，因此需要采取各种可能的方式来最大化收益。
3. 基础思路：每一轮根据之前的结果更新对收益的期望，期望计算方法为[之前采取该选项所得到的所有收益]/[之前采取过该选项的次数]，也就是平均每次得到的收益；只要时间够长，这个算出来的期望就会接近真实收益。

System model and problem

1. 字母符号表示：

需要注意：虽然worker可以提交L个任务候选，但是每一轮只能最终完成一个选项，这里假设$c_i^1$到$c_i^L$是从小到大排的，也就是说最后一个的收费最高，且实际中，c的取值一般和M的长度（就是任务数量）正相关。

• 这里有个奇怪的问题，我以为每个选项就是单独一个任务，然后c是对应的收费，但是看起来每个选项是任务集合，然后c是收费，也就是说比如有5个任务用abcde表示，某个worker的选项就会是{a,b,收费3}{b,c,d,收费5}{a,c,d,e,收费10}，这样看起来好奇怪。希望后面有解释。

• 虽然这样的设定有点别扭，不过解释是说：每一轮每个worker完成$|M_i^l|$个任务，也就会学习到到$|M_i^l|$个任务质量，就是说任务质量会被学习$|M_i^l|$次，这和传统CMAB不一样。

• 每轮每个worker最多定一个选项（也可以不选）

1. 要研究的问题：给定预算，每轮招募K个workers，使得所有轮中完成的所有任务的权重加起来最大。

2. 数学模型：

   目标函数最大化：$E[\sum_{t\geq1}u(P^t) ]$ 所有轮下来总期望收益最大

   约束：$\sum_{t\geq1}\sum_{p_i^l\in P^t}c_i^l\leq B$ 花费不超过预算

   ​ $|P^t|=K \ for\ \forall t>1$ 每一轮都招K个workers，不多不少

   ​ $\sum_{l=1}^LI\{p_i^l\in P^t\}\leq 1$ 每个worker的选项最多一个

Algorithm Design

1. 本文模型：K臂的组合多臂赌博机

2. 本文方法：

   1. 扩展的上置信界算法（UCB）学习任务质量
   2. 增加了对最大化权重的考虑
   3. 每轮用贪心算法招K个workers：最大化任务质量和招募费用的比（单位费用的任务质量最大化）

   原本的UCB算法

   1. 总的来说就是估计置信区间
   2. 我们认为真实的那个未知概率或者说收益是p，而根据尝试和计算推断出的概率是$\widetilde{p}$，这两个概率之间存在差值，即：$\widetilde{p}-\Delta \leq p \leq \widetilde{p}+\Delta$，这个范围就是置信区间，算法的目的就是通过一次次尝试缩小置信区间
   3. 该算法的流程是在所有臂里找$\widetilde{p}+\Delta$最大的那个，根据一系列完全没看的数学定理，$\Delta=\sqrt{2\ln T /n}$，T是目前进行过的轮数，n是这个臂已经被选过的次数，每一轮执行完会更新数据。具体来说，$\widetilde{p}$最大，选这个选项的收益就越大，而$\Delta$越大，这个选项之前被选中的次数就越小。
   4. 总结一下就是会考虑每个臂已经估计过的历史记录，尽可能去探索次数较少和收益较高的臂，兼顾收益和探索。

   本文的算法

   1. 在第t轮中，若第i个worker的第l个选项被选中，则$n_i^l(t)=n_i^l(t-1)+1$（就是比上一轮的多1），反之则保持上一轮的值不变
   2. $n_i(t)$的值是第t轮时的第i个worker每个选项的$n_i^l(t)$和该选项任务数（也就是$|M_i^l|$）相乘，然后所有的加起来，表示第i个worker的质量被学习过的次数
   3. 用普通的总值/总次数更新worker的质量（$\overline {q}_i(t)$），用不太一样的UCB平衡探索和收益（$\widehat{q}_i (t)$）
   4. 每一轮都是最大化权重*$\widehat{q}_i (t)$，也就是根据之前结果的信息推断出的最大收益

   本文的流程

   1. 最一开始，对于每个worker平台都让他去完成候选列表中的第一个任务（就是最便宜的那个）,由此初始化$n_i^l(t)$、$n_i(t)$、$\overline{q}_i(t)$。
   2. 接下来的每一轮中，都以最大化单位费用的收益增长为目的来选择K个worker和它们的任务，也就是说([选择这个任务选项的收益]-[选之前的收益])/[选这个任务的开销]，要找使得这个式子最大的那个任务选项。要注意这一步中，当某个worker已经被选了任务，那他的其他选项都不会再被考虑
   3. 第t轮的K个worker选好以后，开始各自完成任务，做完以后平台计算任务质量，由此更新$n_i^l(t)$、$n_i(t)$、$\overline{q}_i(t)$、$\widehat{q}_i (t)$。同时，目前为止的所有轮获得的收益也更新了，平台根据预算还剩多少决定是否进行下一轮。

   算法性能分析

   1. 实质是01背包问题
   2. 经过一系列我还没看的计算，该算法复杂度是$O(NLK^3\ln \tau(B))$

扩展

1. 扩展问题场景：所有worker的质量和收费都未知，收费未知是指$c_i^l=\varepsilon_i f(|M_i^l|)$这个公式里的参数$\varepsilon_i$未知，公式里的函数$f()$是公开的。具体来说，在第t轮，worker的任务已经选定后，worker根据当前电量、环境、网络等估计一个第t轮的收费参数$\varepsilon_i^t$，该值在0和1之间，且有下限$\varepsilon_{min}$，所有轮的$\varepsilon_i^t$独立同分布，分布未知，期望是$\varepsilon_i$。

2. 每一轮开始时，首先是平台选worker和任务，然后是worker报价，接着平台算一下预算够不够，不够的话就结束，反之就进入做任务的环节，之后的流程和上一部分一样。

3. 问题在于：$\varepsilon_i$也需要学习，而且每一轮会被学习一次，这和之前的任务质量不太一样。

   本文方法

   1. 新增一个符号表示：$m_i(t)=\sum_{l=1}^Ln_i^l(t)$，表示$\varepsilon_i$目前被学习过的次数（第i个worker的所有选项目前被选过的次数）
   2. 新增另一个符号表示：$\overline \varepsilon_i (t) $，计算方法和前面p那个类似，也是[在此之前的值*在此之前的次数+这次的值]/[在此之前的次数+1]
   3. 同样也新增了$\widehat \varepsilon_i (t)$，和前面的一样
   4. 把之前那个目标函数里的费用部分用这里新的符号改写然后化简，但是这里化简以后的没看懂（问了一下作者，是从regret部分分析出来的，然后又看了看之前没看的证明，发现是证明部分分析的）
   5. 于是整个流程就和之前的一模一样，只是目标函数换了
   6. 算法性能分析和前面一样，还没看，感觉不重要

Performance Evaluation

1. 实验部分对平台的介绍格外简单，用的公开数据集，这部分没什么能说的
2. 实验主要关注：期望质量和期望费用（就是前面计算的俩参数）
3. 实验内容是和另一种常用的CMAB的算法做对比
4. 针对第一个算法：分析了预算的影响（500-1000），招募工人数K的变化（得出K小一些更好，但是意味着要来更多轮），用均匀分布作为例子对比了准确率
5. 针对第二个算法：估计了质量和预算的关系，改变工人数之后的性能（和上一个不太一样了）

Conclusion

1. 没啥总结的，这个论文就这样了
2. 之后有时间就看看性能证明那里，不过个人觉得十有八九是已有证明改编的
3. 看了一点证明，还没完全看懂，大致了解思路了，不过不打算继续看了…..