Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling

There is an increasing popularity in crowdsourcing data labeling tasks to non-expert workers or annotators recruited through commercial internet services such as Amazon Mechanical Turk. Those crowdsourcing workers need to be paid for each label they provide, while a task requester usually only has a limited amount of budget for data labeling. So it is desirable to have an optimal policy to wisely allocate the budget among workers and data instances which need to label by considering worker reliability and task difficulty such that the quality of the finally aggregated labels can be maximized. We formulate such a budget allocation problem as a Bayesian Markov decision process (MDP) which simultaneously conducts learning and decision making. Under our framework, the optimal allocation policy can be obtained by applying dynamic programming (DP), but DP quickly becomes computationally intractable when the size of the problem increases. To solve this challenge, we propose a computationally efficient approximate policy called optimistic knowledge gradient policy. Experiments on both synthetic and real data show that at the same budget level our policy results in higher quality labels than existing policies.