In crowd labeling, a large amount of unlabeled data instances are outsourced
to a crowd of workers. Workers will be paid for each label they provide, but
the labeling requester usually has only a limited amount of the budget. Since
data instances have different levels of labeling difficulty and workers have
different reliability, it is desirable to have an optimal policy to allocate
the budget among all instance-worker pairs such that the overall labeling
accuracy is maximized. We consider categorical labeling tasks and formulate the
budget allocation problem as a Bayesian Markov decision process (MDP), which
simultaneously conducts learning and decision making. Using the dynamic
programming (DP) recurrence, one can obtain the optimal allocation policy.
However, 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. Our
MDP is a quite general framework, which applies to both pull crowdsourcing
marketplaces with homogeneous workers and push marketplaces with heterogeneous
workers. It can also incorporate the contextual information of instances when
they are available. The experiments on both simulated and real data show that
the proposed policy achieves a higher labeling accuracy than other existing
policies at the same budget level.

本篇论文研究了众包标注中的预算分配问题，提出了一种基于贝叶斯马尔科夫决策过程的新算法，即乐观的知识梯度策略，该算法被证明在相同的预算水平下能够实现更高的标签准确性，实验结果表明了该算法在众包标注中的效果。