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

arXiv: https://arxiv.org/abs/2109.14412 · HTML: https://mlsanity.com/paper/2109.14412/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 78 references that are in the map.
- First posted on arXiv 29 Sep 2021.

## Builds on (most cited first, 26 of 26)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)
- [Equal Opportunity in Online Classification with Partial Feedback](https://mlsanity.com/paper/1902.02242/) (2019)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [On the Performance of Thompson Sampling on Logistic Bandits](https://mlsanity.com/paper/1905.04654/) (2019)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [Information Directed Sampling for Stochastic Bandits with Graph Feedback](https://mlsanity.com/paper/1711.03198/) (2017)
- [Greedy Algorithm almost Dominates in Smoothed Contextual Bandits](https://mlsanity.com/paper/2005.10624/) (2020)
- [PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits](https://mlsanity.com/paper/1805.07458/) (2018)
- [Variational inference for the multi-armed contextual bandit](https://mlsanity.com/paper/1709.03163/) (2017)
- [Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring](https://mlsanity.com/paper/2006.09668/) (2020)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [On Thompson Sampling with Langevin Algorithms](https://mlsanity.com/paper/2002.10002/) (2020)
- [Learning the Truth From Only One Side of the Story](https://mlsanity.com/paper/2006.04858/) (2020)
- [Randomized Value Functions via Posterior State-Abstraction Sampling](https://mlsanity.com/paper/2010.02383/) (2020)
- [Adaptive Sensor Placement for Continuous Spaces](https://mlsanity.com/paper/1905.06821/) (2019)
- [On Thompson Sampling for Smoother-than-Lipschitz Bandits](https://mlsanity.com/paper/2001.02323/) (2020)

## Built on by (most cited first, 3 of 3)

- [Online Decision Mediation](https://mlsanity.com/paper/2310.18601/) (2023)
- [Randomized Confidence Bounds for Stochastic Partial Monitoring](https://mlsanity.com/paper/2402.05002/) (2024)
- [Efficient contextual partial monitoring with general function approximation](https://mlsanity.com/paper/2610.19804/) (2026)

## Abstract (arXiv)

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'olya-Gamma augmentation have superior empirical performance to existing methods.