Efficient crowdsourcing of unknown experts using bounded multi-armed bandits
OA Location
Author(s)
Long, Tran-Thanh
Stein, Sebastian
Rogers, Alex
Jennings, Nicholas R
Type
Journal Article
Abstract
Increasingly, organisations flexibly outsource work on a temporary basis to a global audience of workers. This so-called crowdsourcing has been applied successfully to a range of tasks, from translating text and annotating images, to collecting information during crisis situations and hiring skilled workers to build complex software. While traditionally these tasks have been small and could be completed by non-professionals, organisations are now starting to crowdsource larger, more complex tasks to experts in their respective fields. These tasks include, for example, software development and testing, web design and product marketing. While this emerging expert crowdsourcing offers flexibility and potentially lower costs, it also raises new challenges, as workers can be highly heterogeneous, both in their costs and in the quality of the work they produce. Specifically, the utility of each outsourced task is uncertain and can vary significantly between distinct workers and even between subsequent tasks assigned to the same worker. Furthermore, in realistic settings, workers have limits on the amount of work they can perform and the employer will have a fixed budget for paying workers. Given this uncertainty and the relevant constraints, the objective of the employer is to assign tasks to workers in order to maximise the overall utility achieved. To formalise this expert crowdsourcing problem, we introduce a novel multi-armed bandit (MAB) model, the bounded MAB. Furthermore, we develop an algorithm to solve it efficiently, called bounded ε-first, which proceeds in two stages: exploration and exploitation. During exploration, it first uses εB of its total budget B to learn estimates of the workers' quality characteristics. Then, during exploitation, it uses the remaining to maximise the total utility based on those estimates. Using this technique allows us to derive an upper bound on its performance regret (i.e., the expected difference in utility between our algorithm and the optimum), which means that as the budget B increases, the regret tends to 0. In addition to this theoretical advance, we apply our algorithm to real-world data from oDesk, a prominent expert crowdsourcing site. Using data from real projects, including historic project budgets, expert costs and quality ratings, we show that our algorithm outperforms existing crowdsourcing methods by up to 300%, while achieving up to of a hypothetical optimum with full information.
Date Issued
2014-09-01
Date Acceptance
2014-04-29
Citation
Artificial Intelligence, 2014, 214, pp.89-111
ISSN
0004-3702
Publisher
Elsevier
Start Page
89
End Page
111
Journal / Book Title
Artificial Intelligence
Volume
214
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000339130100005&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science
Crowdsourcing
Machine learning
Multi-armed bandits
Budget limitation
Publication Status
Published
Date Publish Online
2014-05-20