Efficient Crowdsourcing of Unknown Experts using Multi-Armed Bandits
File(s)FAIA242-0768.pdf (250.29 KB)
Published version
OA Location
Author(s)
Tran-Thanh, L
Stein, S
Rogers, A
Jennings, NR
Type
Conference Paper
Abstract
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 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.
Date Issued
2012-08-27
Date Acceptance
2012-08-27
Citation
Frontiers in Artificial Intelligence and Applications, 2012, 242, pp.768-773
ISSN
1535-6698
Publisher
IOS Press
Start Page
768
End Page
773
Journal / Book Title
Frontiers in Artificial Intelligence and Applications
Volume
242
Copyright Statement
© 2012 The Author(s).
This article is published online with Open Access by IOS Press and distributed under the terms
of the Creative Commons Attribution Non-Commercial License.
This article is published online with Open Access by IOS Press and distributed under the terms
of the Creative Commons Attribution Non-Commercial License.
Identifier
http://eprints.soton.ac.uk/339244/
Source
20th European Conference on Artificial Intelligence (ECAI 2012)
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science
Publication Status
Published
Start Date
2012-08-27
Finish Date
2012-08-31
Coverage Spatial
Montpellier, France