Self-Directed Apple Tasting

Abstract

We study the classical apple-tasting setting, a partial feedback model in which the learner observes the true label only when it predicts $1$. A combinatorial characterization for the rates of this problem in the online adversarial setting has been studied by Raman et al. (2024). We study the self-directed setting, in which the learner can adaptively choose the order of the points it predicts on. In the realizable setting, we establish a tetrachotomy on the expected minimax number of mistakes made by any learner. Depending on the VC dimension, the $\varnothing$-centered star number, and the self-directed dimension, we show that the rates could possibly be $\Theta (1)$, $O(\log n)\cap \omega (1)$, $\tilde{\Theta }(\sqrt{n})$, or $\Theta (n)$. In the agnostic setting, the minimax regret is $\tilde{\Theta }(\sqrt{n})$ or $\Theta (n)$, depending on the VC dimension.