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

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 monitoring problem with side information, and focus on the case where item features are linked to true classes via a logistic regression model. Our principal contribution is a study of the performance of Thompson Sampling (TS) for this problem. Using recently developed information-theoretic tools, we show that TS achieves a Bayesian regret bound of an improved order to previous approaches. Further, we experimentally verify that efficient approximations to TS and Information Directed Sampling via Pólya-Gamma augmentation have superior empirical performance to existing methods.

Update to Theorem 1 and experimental work

References in corpus (17)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Further Optimal Regret Bounds for Thompson Sampling
• An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
• An Information-Theoretic Analysis for Thompson Sampling with Many Actions
• Information Directed Sampling for Stochastic Bandits with Graph Feedback
• Improved Optimistic Algorithms for Logistic Bandits
• Sampling Polya-Gamma random variates: alternate and approximate techniques
• Sequential Markov Chain Monte Carlo
• Variational inference for the multi-armed contextual bandit
• Asymptotically Optimal Information-Directed Sampling
• Adaptive Sensor Placement for Continuous Spaces
• On Thompson Sampling with Langevin Algorithms
• On the Performance of Thompson Sampling on Logistic Bandits
• Randomized Value Functions via Posterior State-Abstraction Sampling
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
• Be Greedy in Multi-Armed Bandits