PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
2026-05-25 • Data Structures and Algorithms
Data Structures and AlgorithmsMachine Learning
AI summaryⓘ
The authors study a learning scenario where a machine tries to classify items into multiple categories but only finds out if its guess was right or wrong, not the actual label. They focus on the "realizable" case, where there is a perfect classifier in the concept class. To understand how many examples the learner needs, they introduce a new measure called the bandit DS dimension, which extends previous ideas to better capture the complexity when feedback is limited to correct/incorrect signals. They also provide an algorithm, called ListCascade, that matches their theoretical predictions. This work clarifies how the difficulty of learning changes when you have less information about labels.
PAC learningmulticlass classificationbandit feedbacksample complexityrealizable settingcombinatorial dimensionDS dimensionpseudo-cubesListCascade algorithmconcept class
Authors
Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri
Abstract
We study the problem of multiclass PAC learning with bandit feedback in the realizable setting. In this framework, there is an unknown data distribution over an instance space $\mathcal{X}$ and a label space $\mathcal{Y}$, as in classical multiclass PAC learning, but the learner does not observe the labels of the i.i.d. training examples. Instead, in each round, it receives an unlabeled instance, predicts its label, and receives bandit feedback indicating only whether the prediction is correct. Despite this restriction, the goal remains the same as in classical PAC learning. We provide a general characterization of the optimal sample complexity of this problem, sharp for every concept class up to logarithmic factors. Our characterization is based on a new combinatorial dimension, termed the bandit $\mathrm{DS}$ dimension, defined via generalized combinatorial structures we call pseudo-boxes. These extend the pseudo-cubes underlying the $\mathrm{DS}$ dimension by allowing a different number of neighbors in each coordinate. In contrast to the $\mathrm{DS}$ dimension, which governs the full-information setting by counting the number of coordinates in the pseudo-cube, the bandit $\mathrm{DS}$ dimension aggregates the number of neighbors across coordinates, leading to a characterization in which the sample complexity scales with the total number of neighbors. We also propose a general learning algorithm achieving the upper bound, based on an algorithmic principle called ListCascade, which connects bandit learning to list learning and may be of independent interest.