Decentralized Online Learning in Task Assignment Games for Mobile
  Crowdsensing
Bernd Simon Andrea Ortiz Walid Saad Anja Klein
The problem of coordinated data collection is studied for a mobile
crowdsensing (MCS) system. A mobile crowdsensing platform (MCSP) sequentially
publishes sensing tasks to the available mobile units (MUs) that signal their
willingness to participate in a task by sending sensing offers back to the
MCSP. From the received offers, the MCSP decides the task assignment. A stable
task assignment must address two challenges: the MCSP's and MUs' conflicting
goals, and the uncertainty about the MUs' required efforts and preferences. To
overcome these challenges a novel decentralized approach combining matching
theory and online learning, called collision-avoidance multi-armed bandit with
strategic free sensing (CA-MAB-SFS), is proposed. The task assignment problem
is modeled as a matching game considering the MCSP's and MUs' individual goals
while the MUs learn their efforts online. Our innovative "free-sensing"
mechanism significantly improves the MU's learning process while reducing
collisions during task allocation. The stable regret of CA-MAB-SFS, i.e., the
loss of learning, is analytically shown to be bounded by a sublinear function,
ensuring the convergence to a stable optimal solution. Simulation results show
that CA-MAB-SFS increases the MUs' and the MCSP's satisfaction compared to
state-of-the-art methods while reducing the average task completion time by at
least 16%.