We address the expert crowdsourcing problem, in which an employer wishes to assign tasks to a set of available workers with heterogeneous working costs. Critically, as workers produce results of varying quality, the utility of each assigned task is unknown and can vary both between workers and individual tasks. Furthermore, in realistic settings, workers are likely to have limits on the number of tasks they can perform and the employer will have a fixed budget to spend on hiring workers. Given these constraints, the objective of the employer is to assign tasks to workers in order to maximise the overall utility achieved. To achieve this, we introduce a novel multi-armed bandit (MAB) model, the bounded MAB, that naturally captures the problem of expert crowdsourcing. We also propose an algorithm to solve it efficiently, called bounded ε-first, which uses the first sB of its total budget B to derive estimates of the workers' quality characteristics (exploration), while the remaining (1 - ε) B is used to maximise the total utility based on those estimates (exploitation). We show that using this technique allows us to derive an OB2/3) upper bound on our algorithm's performance regret (i.e. the expected difference in utility between the optimal and our algorithm). In addition, we demonstrate that our algorithm outperforms existing crowdsourcing methods by up to 155% in experiments based on real-world data from a prominent crowdsourcing site, while achieving up to 75% of a hypothetical optimal with full information. © 2012 The Author(s).
