Combinatorial Multi-Armed Bandit Based Unknown Worker Recruitment in Heterogeneous Crowdsensing
Mobile crowdsensing, through which a requester can coordinate a crowd of workers to complete some sensing tasks, has attracted significant attention recently. In this paper, we focus on the unknown worker recruitment problem in mobile crowdsensing, where workers' sensing qualities are unknown a priori. We consider the scenario of recruiting workers to complete some continuous sensing tasks. The whole process is divided into multiple rounds. In each round, every task may be covered by more than one recruited workers, but its completion quality only depends on these workers' maximum sensing quality. Each recruited worker will incur a cost, and each task is attached a weight to indicate its importance. Our objective is to determine a recruiting strategy to maximize the total weighted completion quality under a limited budget. We model such an unknown worker recruitment process as a novel combinatorial multi-armed bandit problem, and propose an extended UCB based worker recruitment algorithm. Moreover, we extend the problem to the case where the workers' costs are also unknown and design the corresponding algorithm. We analyze the regrets of the two proposed algorithms and demonstrate their performance through extensive simulations on real-world traces.
Code (1)
Similar Papers 제목 키워드 기반
A Semi-supervised Sensing Rate Learning based CMAB Scheme to Combat COVID-19 by Trustful Data Collection in the Crowd
The recruitment of trustworthy and high-quality workers is an important research issue for MCS. Previous studies either assume that the qualities of workers are known in advance, or assume that the platform knows the qua…
Diversity-Based Recruitment in Crowdsensing By Combinatorial Multi-Armed Bandits
This paper explores mobile crowdsensing, which leverages mobile devices and their users for collective sensing tasks under the coordination of a central requester. The primary challenge here is the variability in the sen…
DiversityMulti-Armed BanditsCost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits
We consider the distributed SGD problem, where a main node distributes gradient calculations among $n$ workers. By assigning tasks to all the workers and waiting only for the $k$ fastest ones, the main node can trade-off…
Multi-Armed BanditsOn Statistical Discrimination as a Failure of Social Learning: A Multi-Armed Bandit Approach
We analyze statistical discrimination in hiring markets using a multi-armed bandit model. Myopic firms face workers arriving with heterogeneous observable characteristics. The association between the worker's skill and c…
Adversarial Attacks on Combinatorial Multi-Armed Bandits
We study reward poisoning attacks on Combinatorial Multi-armed Bandits (CMAB). We first provide a sufficient and necessary condition for the attackability of CMAB, a notion to capture the vulnerability and robustness of …
Multi-Armed Bandits