Abstract
In online binary classification under \emph{apple tasting} feedback, thelearner only observes the true label if it predicts ``1". First studied by\cite{helmbold2000apple}, we revisit this classical partial-feedback settingand study online learnability from a combinatorial perspective. We show thatthe Littlestone dimension continues to provide a tight quantitativecharacterization of apple tasting in the agnostic setting, closing an openquestion posed by \cite{helmbold2000apple}. In addition, we give a newcombinatorial parameter, called the Effective width, that tightly quantifiesthe minimax expected mistakes in the realizable setting. As a corollary, we usethe Effective width to establish a \emph{trichotomy} of the minimax expectednumber of mistakes in the realizable setting. In particular, we show that inthe realizable setting, the expected number of mistakes of any learner, underapple tasting feedback, can be $\Theta(1), \Theta(\sqrt{T})$, or $\Theta(T)$.This is in contrast to the full-information realizable setting where only$\Theta(1)$ and $\Theta(T)$ are possible.