PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

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 X and a label space 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 non-trivial concept class, up to logarithmic factors. Our characterization is based on a new combinatorial dimension, termed the bandit DS dimension, defined via generalized combinatorial structures we call pseudo-boxes. These extend the pseudo-cubes underlying the DS dimension by allowing a different number of neighbors in each coordinate. In contrast to the DS dimension, which governs the full-information setting by counting the number of coordinates in the pseudo-cube, the bandit 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.