Bandit User Selection Algorithm for Budgeted and Time-Limited Mobile Crowdsensing
Shuo Yang, Xiaotian Qi, Fan Wu, Xiaofeng Gao, Guihai Chen · 2017
Due to the rapid proliferation of mobile devices, mobile crowdsensing (MCS) has become a novel and effective approach to collect large amounts of data. A critical problem in crowdsensing is to decide which mobile device users to select to perform sensing tasks, in order to maximize the platform's total obtained utility, within a fixed budget and limited time. Since the users' utilities are unknown a priori, the platform is facing a challenge of how to effectively learn the users' utilities and make optimal user selection decisions. Previous works usually considered a budgeted multi-armed bandit (MAB) approaches, but they cannot effectively address the joint constraints of fixed budget and limited time. In this paper, we build a Budgeted and Time-Limited Combinatorial Multi-Armed Bandit (BT-CMAB) model to tackle this problem, and propose an effective UCB-based user selection algorithm, namely BT- CUCB. We prove that the BT-CUCB algorithm can achieve a zero beta-regret. The evaluation results show that our proposed algorithm effectively utilize budget and time to achieve a low regret.