PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
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 𝒳 and a label space 𝒴, 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.
Related
- The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
- Nonparametric Kernel Clustering with Bandit Feedback
- Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback
- Variable-Length Feedback Coding With Universal Decoding and Bandit Channel Selection
- Decentralized Bandit Learning of Markov Perfect Equilibria
BibTeX
@misc{hanneke2026learning,
title = {{PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting}},
author = {Steve Hanneke and Qinglin Meng and Shay Moran and Amirreza Shaeiri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.25678},
eprint = {2605.25678},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.25678},
}
RIS
TY - UNPB
TI - PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
AU - Steve Hanneke
AU - Qinglin Meng
AU - Shay Moran
AU - Amirreza Shaeiri
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2605.25678
UR - https://arxiv.org/abs/2605.25678
AB - 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 𝒳 and a label space 𝒴, 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.
ER -