Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification

arXiv:2109.14412v2 Announce Type: replace
Abstract: We consider a variant of online binary classification where a learner sequentially assigns labels ($0$ or $1$) to items with unknown true class. If, but only if, the learner chooses label $1$ they immediately observe the true label of the item. The learner faces a trade-off between short-term classification accuracy and long-term information gain. This problem has previously been studied under the name of the `apple tasting' problem. We revisit this problem as a partial …

abstract apple arxiv bayesian binary class classification cs.lg labels observe tasting true type