Self-Directed Apple Tasting

원문 초록

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 $\emptyset$-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.