Efficient Crowdsourcing of Unknown Experts using Multi-Armed Bandits

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 ϵB 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 O(B2/3) upper bound on our algorithm's performance regret (i.e. the expected difference in utility between the moptimal 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.