# Apple Tasting: Combinatorial Dimensions and Minimax Rates

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 29 Oct 2023.

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

- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [The price of bandit information in multiclass online classification](https://mlsanity.com/paper/1302.1043/) (2013)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)

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

- [Deterministic Apple Tasting](https://mlsanity.com/paper/2410.10404/) (2024)
- [Ambiguous Online Learning](https://mlsanity.com/paper/2506.19810/) (2025)
- [Robust Online Learning](https://mlsanity.com/paper/2602.06775/) (2026)
- [Two-Action Apple Tasting with Switching Costs](https://mlsanity.com/paper/2606.03851/) (2026)

## Abstract (arXiv)

In online binary classification under apple tasting feedback, the learner only observes the true label if it predicts ``1". First studied by citehelmbold2000apple, we revisit this classical partial-feedback setting and study online learnability from a combinatorial perspective. We show that the Littlestone dimension continues to provide a tight quantitative characterization of apple tasting in the agnostic setting, closing an open question posed by citehelmbold2000apple. In addition, we give a new combinatorial parameter, called the Effective width, that tightly quantifies the minimax expected mistakes in the realizable setting. As a corollary, we use the Effective width to establish a trichotomy of the minimax expected number of mistakes in the realizable setting. In particular, we show that in the realizable setting, the expected number of mistakes of any learner, under apple tasting feedback, can be Theta(1), Theta(√T), or Theta(T). This is in contrast to the full-information realizable setting where only Theta(1) and Theta(T) are possible.