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 $\emptyset$-centered star number, and the self-directed dimension, we show that the rates could possibly be $Θ(1)$, $O(\log n) \cap ω(1)$, $\tilde Θ(\sqrt{n})$, or $Θ(n)$. In the agnostic setting, the minimax regret is $\tilde Θ(\sqrt{n})$ or $Θ(n)$, depending on the VC dimension.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning

• arXiv preprint · 4 November 2026

  Optimizing Recourse Under Predictive Multiplicity

  Shahin Jabbari
• arXiv preprint · 5 November 2026

  Using Transformers for Teaching and Learning via Symbolic Distillation of Neural A-life Agents

  Shuwei Wang, Vadim Bulitko, Matthew R. G. Brown and 5 others
• arXiv preprint · 4 November 2026

  Timing is Everything: Inferring Temporal Membership in Continually Updated Models

  Jie Fu, Xiangpeng Deng, Yuan Hong and 1 other
• arXiv preprint · 5 November 2026

  TriAttention: Unified Sparse Mixed-Precision Attention for Long-Context LLM Inference

  Hanzhi Zhang, Qiao Zhang, Qinglei Cao and 4 others
• arXiv preprint · 4 November 2026

  Unsupervised Neural Operators for Rotating Relativistic Stars: High-Fidelity Equation of State Inference and Pulsar Spin Evolution at Scale

  Anarya Ray

All new papers in Machine Learning