Multi-Armed Bandit Algorithms for Crowdsourcing Systems with Online Estimation of Workers' Ability

Crowdsourcing systems have become a valuable solution for various organizations to outsource work on a temporary basis. Quality assurance in these systems remains a key issue due to the distributed setup of the crowdsourcing platforms and the absence of a priori information about the workers. Our work develops a notion of Limited-information Crowdsourcing Systems (LCS), where the task master can assign the work based on some knowledge of the workers' ability acquired over time. The key challenges in this new setup are determining an efficient workers' selection policy and estimating the abilities of the workers. To address the first challenge, we reduce the problem to an arm-limited, budget limited, multi-armed bandit (MAB) setup , and use the simplified bounded KUBE (B-KUBE) algorithm as a solution. This algorithm has previously only been experimentally evaluated, and we provide provable performance guarantees, showing that it is order optimal, namely the expected regret of B-KUBE is O(log(B)) where B is the total budget of the task master. The second challenge is solved by formalizing the notion of workers' ability mathematically, and proposing a strategy for its estimation. We experimentally evaluate B-KUBE in conjunction with this strategy, showing that it outperforms other state-of-the-art MAB algorithms when applied in the same setting.