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

arXiv: https://arxiv.org/abs/2605.25678 · HTML: https://mlsanity.com/paper/2605.25678/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 25 May 2026.

## Builds on (most cited first, 18 of 18)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [List Online Classification](https://mlsanity.com/paper/2303.15383/) (2023)
- [Multiclass Boosting: Simple and Intuitive Weak Learning Criteria](https://mlsanity.com/paper/2307.00642/) (2023)
- [List Sample Compression and Uniform Convergence](https://mlsanity.com/paper/2403.10889/) (2024)
- [A Characterization of List Language Identification in the Limit](https://mlsanity.com/paper/2511.04103/) (2025)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [Fast Rates for Bandit PAC Multiclass Classification](https://mlsanity.com/paper/2406.12406/) (2024)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)

## Built on by (most cited first, 2 of 2)

- [Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon](https://mlsanity.com/paper/2609.29694/) (2026)
- [Delay Complexity Dimension: Learning with Delayed and Censored Labels](https://mlsanity.com/paper/2610.18935/) (2026)

## Abstract (arXiv)

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.