← 研踪 PaperTrailarXiv:2611.06677 · v1
Self-Directed Apple Tasting
首次提交 2026-11-04 23:46
版本更新 2026-11-04 23:46
雷达观测 2026-11-05 12:13
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-04 23:46 · 最新观测版本
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 $Θ(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.
查看此版本解读 →查看此版本原文 ↗