SOURCE-LINKED INTELLIGENCE

Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon

arXiv · AI, language, vision and robotics · article · Aug 31, 2026 · UTC

We study realizable multiclass PAC learning with bandit feedback: the learner observes an i.i.d. instance, predicts one of $K$ labels, and learns only whether the prediction was correct. Hanneke, Meng, Moran, and Shaeiri (arXiv:2605.25678) characterized the optimal sample complexity via the bandit DS dimension $\mathrm{BDS}$ up to logarithmic factors, and asked whether every class admits sample complexity $O((\mathrm{BDS}+\log(1/δ))/ε)$. First, we show that the published lower bound $Ω((\mathrm{BDS}+\log(1/δ))/ε)$ is incorrect as stated: we exhibit explicit classes with $\mathrm{BDS}=K-1$ whos

Read original source ↗ Open in workspace

recordType

paper

region

Global