Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum

Guangjian Zhang; Zhengyi Yang; Xiaoyang Wang

cs.LGAug 31, 2026

Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum

Authors: Guangjian Zhang, Zhengyi Yang, Xiaoyang Wang

Abstract

How much does high confidence cost when a multiclass learner sees only whether its prediction is correct? We separate two behaviors in realizable bandit PAC learning. An anchored dimension gives a general lower bound that is attained, up to universal constants, by a family of product-block classes. In contrast, for $n\ge16$ divisible by four, an affine multiplexer with bandit DS dimension $2n-1$ has sample complexity $Θ((n\min\{n,\ln(1/δ)\}+\ln(1/δ))/\varepsilon)$ in the standard accuracy and confidence regime. Its lower bound applies to adaptive randomized learners with improper outputs. The obstruction is that evidence collected against one candidate group cannot be reused against the others. The better of two algorithms matches this cost. One finds the correct group through a positive response. The other exhausts the rank of successive groups. The resulting confidence profile rules out a universal additive-confidence bound linear in the bandit DS dimension. Moreover, classes with identical anchored dimension, bandit DS dimension, and pointwise label width can have polynomially different sample complexities. We also sharpen the confidence accounting in ListCascade and show how one positive response replaces the bandit DS dimension by the anchored dimension in a general upper bound.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Main-text result	Property certified	Proof
Theorem 2	Structural baseline for all learners	C.4
Theorem 3	Exact randomized elimination rate	C.2
Theorem 4	PAB dimensions and algorithm	D.1
Theorem 5	Separate confidence cost across groups	E.3
Proposition 6	Two multiplexer learning procedures	E.4
Theorem 7	Matching confidence profile	E.5

Appendix

Table 1: Main-text guarantees and their proof locations. A proof location can include the supporting lemmas needed immediately before the named result.

Figure 1: Principal structural and algorithmic dependencies. The equality-query argument supports the baseline. The conservative conversion supports the PAB learner. List collection and allocation support the general cascade, which combines with positive-response restriction to give the anchored upper bound.

Figure 2: Principal dependencies for the confidence separation. The lower chain counts targets on a canonical record and controls adaptive low-rank queries. The algorithmic chain uses conservative conversion. Their meeting point is the confidence profile; the PAB rare-label benchmark then supplies the identical-parameter comparison.

PAC Learning

Probably approximately correct (PAC) learning studies when finite samples can yield predictors that generalize with bounded error and confidence.

See all 40 papers

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
May 25, 2026Steve Hanneke, Qinglin Meng, Shay Moran +1Multiclass Classification Classification
Department of Computer Science Purdue University West Lafayette, IN, USA · Faculties of Mathematics, Computer Science, and Data and Decision Sciences Technion – Israel Institute of Technology and Google Research Haifa, Israel
PAC Learning with Query Feedback
Oct 16, 2026Chase Hutton, Adam Melrod, Han ShaoPAC Learning Multiclass Classification
University of Maryland · Harvard University
Optimistic Rates for Multiclass PAC Learning
Aug 11, 2026Xiaoyu Li, Andi Han, Jiaojiao Jiang +1Sample Compression Multiclass Classification
University of New South Wales · University of Sydney

May 25, 2026J/K move · Enter open · S save

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

Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri

Department of Computer Science Purdue University West Lafayette, IN, USA · Faculties of Mathematics, Computer Science, and Data and Decision Sciences Technion – Israel Institute of Technology and Google Research Haifa, Israel

Multiclass Classification Classification PAC Learning Statistical Learning Theory

Open paper AskPDF 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

\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.

Abstract

PAC Learning

Explore similar work

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

PAC Learning with Query Feedback

Optimistic Rates for Multiclass PAC Learning