---
title: "Self-Directed Apple Tasting"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.06677v1"
permalink: "https://feed.astralor.com/items/itm_3822b696e4e960bb88da050b"
published: "2026-11-04T15:46:56.000Z"
score: 55
channel: "ai"
tags: ["Self-Directed Apple Tasting","Raman","Depending"]
---

# 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…

## 关键点

- 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.
- We study the self-directed setting, in which the learner can adaptively choose the order of the points it predicts on.

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_3822b696e4e960bb88da050b