pith. sign in

arxiv: 2605.25678 · v2 · pith:OXZ6YMRRnew · submitted 2026-05-25 · 📊 stat.ML · cs.DS· cs.LG· math.ST· stat.TH

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

Steve Hanneke , Qinglin Meng , Shay Moran , Amirreza Shaeiri This is my paper

Pith reviewed 2026-06-29 20:24 UTC · model grok-4.3

classification 📊 stat.ML cs.DScs.LGmath.STstat.TH
keywords PAC learningbandit feedbacksample complexityDS dimensionrealizable settingmulticlass classificationpseudo-boxesListCascade
0
0 comments X

The pith

The optimal sample complexity for realizable multiclass PAC learning with bandit feedback is characterized by the bandit DS dimension, sharp up to logarithmic factors for every concept class.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes a sharp characterization of how many samples are needed to learn a multiclass classifier when the learner only gets feedback on whether its prediction was correct, not the true label. The characterization holds in the realizable setting where a perfect classifier exists in the class. A sympathetic reader would care because it gives the precise information-theoretic limit on learning under this restricted feedback, extending classical PAC learning results. The work introduces a new dimension that aggregates neighbor counts in generalized structures called pseudo-boxes, leading to sample complexity that depends on the total number of such neighbors rather than the number of coordinates. It also supplies a general algorithm achieving the upper bound via an algorithmic principle called ListCascade.

Core claim

We provide a general characterization of the optimal sample complexity of multiclass PAC learning with bandit feedback in the realizable setting, which is sharp for every 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

What carries the argument

the bandit DS dimension, which aggregates the total number of neighbors across coordinates in pseudo-box structures that generalize pseudo-cubes by permitting varying neighbor counts per coordinate

If this is right

  • Sample complexity scales with the total number of neighbors in the pseudo-boxes rather than the number of coordinates.
  • The ListCascade principle connects bandit learning to list learning and yields an algorithm matching the upper bound.
  • The result applies to any concept class and reduces to the classical DS dimension in the full-information case.
  • The characterization is information-theoretic and holds up to logarithmic factors.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Bandit feedback increases sample requirements in proportion to the branching factor per coordinate rather than the number of features.
  • The pseudo-box construction may be adapted to other partial-observation models by redefining allowable neighbor sets.
  • Algorithms that explicitly minimize total neighbor count could be designed by choosing hypotheses with restricted pseudo-box expansions.

Load-bearing premise

The realizable setting holds and the pseudo-box construction accurately captures the number of distinguishable behaviors under bandit feedback.

What would settle it

An explicit concept class where the minimal number of samples needed for learning deviates from the scaling predicted by its bandit DS dimension by more than logarithmic factors.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper studies multiclass PAC learning with bandit feedback in the realizable setting, where only correctness feedback is received on predictions. It claims a general characterization of the optimal sample complexity that is sharp for every concept class up to logarithmic factors, based on a new bandit DS dimension defined via generalized pseudo-boxes (extending pseudo-cubes by allowing varying neighbor counts per coordinate). The characterization states that sample complexity scales with the total number of neighbors across coordinates. It also proposes the ListCascade algorithm, which connects bandit learning to list learning and achieves the claimed upper bound.

Significance. If the result holds, this would be a significant contribution by providing the first sharp (up to logs) combinatorial characterization of sample complexity under bandit feedback, extending the DS dimension to partial information. The ListCascade principle may be of independent interest. The paper claims a purely combinatorial, parameter-free dimension defined from the concept class.

major comments (2)
  1. [Abstract and definition of bandit DS dimension] Abstract and definition of bandit DS dimension: the claim that the total neighbor count across pseudo-box coordinates exactly characterizes the minimax sample complexity (up to logs) is load-bearing, yet the text provides neither the explicit construction of generalized pseudo-boxes nor a verification that this quantity tightly bounds the number of distinguishable behaviors under single-bit correctness feedback. Without this, it is impossible to confirm that the lower-bound construction matches the ListCascade upper bound.
  2. [ListCascade algorithm section] ListCascade algorithm section: the paper asserts that ListCascade achieves the upper bound matching the bandit DS dimension, but without the explicit reduction from bandit feedback to list learning or the analysis showing it meets the neighbor-count bound, the matching of upper and lower bounds cannot be assessed.
minor comments (1)
  1. [Abstract] The abstract uses mathrm{DS} consistently but should include a brief remark on whether the bandit DS dimension reduces to the standard DS dimension under full-information feedback.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed review and valuable feedback. We address each major comment below and plan to revise the manuscript to enhance clarity on the constructions and analyses.

read point-by-point responses

  1. Referee: [Abstract and definition of bandit DS dimension] Abstract and definition of bandit DS dimension: the claim that the total neighbor count across pseudo-box coordinates exactly characterizes the minimax sample complexity (up to logs) is load-bearing, yet the text provides neither the explicit construction of generalized pseudo-boxes nor a verification that this quantity tightly bounds the number of distinguishable behaviors under single-bit correctness feedback. Without this, it is impossible to confirm that the lower-bound construction matches the ListCascade upper bound.

    Authors: We agree that the explicit details are crucial for verifying the characterization. The definition of generalized pseudo-boxes is given in Definition 3.1 of the full manuscript, extending pseudo-cubes by allowing varying numbers of neighbors per coordinate. The verification that the total neighbor count tightly bounds the distinguishable behaviors is provided in the lower bound construction in Theorem 4.1, which uses a distribution over instances corresponding to the coordinates and neighbors in the pseudo-box. However, to address the concern, we will add a dedicated subsection in Section 3 that explicitly constructs the pseudo-boxes for a general concept class and verifies the bound on distinguishable behaviors under bandit feedback. This will make the matching with the upper bound clearer. revision: yes

  2. Referee: [ListCascade algorithm section] ListCascade algorithm section: the paper asserts that ListCascade achieves the upper bound matching the bandit DS dimension, but without the explicit reduction from bandit feedback to list learning or the analysis showing it meets the neighbor-count bound, the matching of upper and lower bounds cannot be assessed.

    Authors: The ListCascade algorithm is introduced in Section 5, with the reduction from bandit feedback to list learning described in Algorithm 1 and the surrounding text, where the learner maintains a list of candidate hypotheses and cascades through them based on bandit feedback. The analysis that it achieves the upper bound matching the bandit DS dimension (i.e., the total neighbor count) is in the proof of Theorem 5.3. We acknowledge that the reduction could be presented more explicitly. In the revision, we will expand Section 5 with a step-by-step explanation of how bandit feedback is converted to list learning queries and how the neighbor count bound is achieved, including a worked example for a simple concept class. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new dimension defined combinatorially with independent upper/lower bounds.

full rationale

The paper defines the bandit DS dimension directly from the concept class via pseudo-boxes (generalizing pseudo-cubes by variable neighbor counts per coordinate) and states that sample complexity scales with the total neighbor count. This is a standard combinatorial characterization in learning theory; the abstract and description give no equations or self-citations showing that the claimed sharpness or ListCascade algorithm reduces by construction to a fitted parameter, a self-referential definition, or a load-bearing self-citation chain. The result is presented as a new combinatorial fact with matching upper and lower bounds, which is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on the realizable assumption and on the correctness of the new combinatorial dimension; no free parameters are visible in the abstract.

axioms (1)
  • domain assumption There exists a perfect concept in the class (realizable setting).
    Stated in the abstract as the setting under which the characterization holds.
invented entities (2)
  • bandit DS dimension no independent evidence
    purpose: To characterize optimal sample complexity under bandit feedback
    New combinatorial dimension defined via pseudo-boxes; no independent evidence supplied in abstract.
  • pseudo-boxes no independent evidence
    purpose: Generalized combinatorial structures extending pseudo-cubes
    Invented to define the bandit DS dimension; no external validation given.

pith-pipeline@v0.9.1-grok · 5812 in / 1274 out tokens · 23616 ms · 2026-06-29T20:24:42.638764+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 4 canonical work pages · 2 internal anchors

  1. [1]

    ISBN 9781605580470

    Association for Computing Machinery. ISBN 9781605580470. doi: 10.1145/1374376.1374474. Maria Florina Balcan, Heiko Röglin, and Shang-Hua Teng. Agnostic clustering. InProceedings of the 20th International Conference on Algorithmic Learning Theory, ALT’09, page 384–398, Berlin, Heidelberg,

    work page doi:10.1145/1374376.1374474

  2. [2]

    Sample complexity of agnostic multiclass classification: Natarajan dimension strikes back

    Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang. Sample complexity of agnostic multiclass classification: Natarajan dimension strikes back. InProceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026),

    2026

  3. [3]

    Efficient Optimal Learning for Contextual Bandits

    Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits.arXiv preprint arXiv:1106.2369,

    work page internal anchor Pith review Pith/arXiv arXiv

  4. [4]

    An Optimal Sauer Lemma Over $k$-ary Alphabets

    URLhttps://arxiv.org/abs/2604.12952. David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting {0, 1}-functions on randomly drawn points.Information and Computation, 115(2):248–292,

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    List online classification

    Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili. List online classification. InThe Thirty Sixth Annual Conference on Learning Theory, pages 1885–1913. PMLR,

    1913

  6. [6]

    doi: 10.1561/2200000068

    ISSN 1935-8237. doi: 10.1561/2200000068. William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.Biometrika, 25(3-4):285–294,

    work page doi:10.1561/2200000068 1935

  7. [7]

    We start from the notations

    13 A Definitions In this section, we provide the auxilary formal definitions that will be used in our paper. We start from the notations. A.1 Notations In this subsection, we present the basic notation used in the paper; all of it is standard in the literature and is included for completeness. Let N and R stand for the set of natural numbers and real numb...

    2023

  8. [8]

    Definition A.7(L-Exponential dimension Charikar and Pabbaraju [2023]).Let H ⊆ Y X be a concept class, and L∈N

    d. Definition A.7(L-Exponential dimension Charikar and Pabbaraju [2023]).Let H ⊆ Y X be a concept class, and L∈N . The L-Exponential dimensionof H, denoted by EL(H)∈ ¯N∪ {0} , is defined as thesup d∈N∪{0} such that there exists a set of instancesS⊆ Xof sizedthat isE L-shattered byH. A.3 Multiclass Learning with Bandit Feedback Algorithms To improve readab...

    2023

  9. [9]

    On the other hand, by Theorem 1 of Hanneke et al

    dL E . On the other hand, by Theorem 1 of Hanneke et al. [2026], we know that |H|S| ≤ L 2 dL E −d⌈L/2⌉ DS eKd L E d⌈L/2⌉ DS !d⌈L/2⌉ DS . Combining the above two inequalities, we have (L+

    2026

  10. [10]

    By rearranging the term, we have 2L+ 2 L+ 1 dL E ≤ 2eKd L E (L+ 1)d ⌈L/2⌉ DS !d⌈L/2⌉ DS

    dL E ≤ L+ 1 2 dL E −d⌈L/2⌉ DS eKd L E d⌈L/2⌉ DS !d⌈L/2⌉ DS . By rearranging the term, we have 2L+ 2 L+ 1 dL E ≤ 2eKd L E (L+ 1)d ⌈L/2⌉ DS !d⌈L/2⌉ DS . Taking the logarithm of both sides and rearranging the terms, we get dL E d⌈L/2⌉ DS ≤ log 2eKd L E (L+1)d⌈L/2⌉ DS log (2) . Thus, we have dL E d⌈L/2⌉ DS ≤ 1 log(2) log 2eK L+ 1 + 1 log(2) log dL E d⌈L/2⌉ DS...

    2014