Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts

We investigate online classification in the framework of prediction with expert advice where, in each round, the learning agent predicts an unknown binary label by aggregating the stochastic predictions of a number of experts. At the end of each round, the learner observes the true label and updates the function used to aggregate experts. In the variant considered in this work, we assume that at the beginning of a round the learner allocates a payment to each expert which affects the expert's performance in that round. This payment model of expert advice is realistic in many scenarios since human annotators will often only give useful advice if they are adequately compensated, and machine annotators may require more computation to return accurate predictions. Moreover, monetary incentives have been studied in crowdsourcing (Ho et al., 2015, 2016). Although this is a different setting to that considered here, it is natural to study the effect of these payments in online binary classification with stochastic expert advice. Motivated by results in crowdsourcing--e.g., Ho et al. (2016)--we assume that each expert has a productivity function which determines the probability that they predict the label correctly given the payment they received. The productivity function can be different for each expert and is initially unknown to the learner. In each round, the learner pays each expert j = 1,..., K some amount c