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

arXiv:2605.25678 · stat.ML, cs.DS, cs.LG, math.ST, stat.TH · Submitted 2026-05-25 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "PAC Learning with Bandit Feedback".

Tom: Sharp sample complexity for multiclass PAC learning under bandit feedback in the realizable setting.

Jane: First, who's behind it and why it matters.

Title and authors: Tom: I read the title of "PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting" again, and it really tells you what we're dealing with—it’s about finding a tight bound on sample complexity when we operate under this bandit feedback constraint. Jane, how does that title translate into something practical for us listening?

Jane: It means the authors have managed to provide a much sharper estimate than previous work, specifically focusing on the sample complexity in the realizable setting where we know our concept class is consistent with some true function <ref:2605.25678#pg1>. The "sharp" part suggests they've closed that gap between upper and lower bounds that used to exist.

Lu: They achieve this sharpness by introducing a new measure, the bandit DS dimension, which acts as a combinatorial parameter characterizing the difficulty of the concept class <ref:2605.25678#pg2>.

Meng: If they’ve managed to characterize it with such precision, that suggests we can build much more robust learning algorithms for scenarios where data labeling is scarce.

Lalam: It points toward a future where AI systems could learn effectively in environments where the feedback mechanism is inherently noisy or incomplete, which is actually closer to reality than perfectly labeled datasets <ref:2605.25678#pg1>.

The paper's summary: Tom: So, what's the actual core idea behind this paper? Basically, they are taking the problem of learning a multiclass concept class under bandit feedback and connecting it directly to this new dimension they call the bandit DS dimension. Jane, can you explain that connection simply?

Jane: Think of it like this: instead of counting every single data point we see, which is what classical learning does, this paper counts how complex the *structure* of the concept class is in a way that aggregates complexity across all possible directions or coordinates <ref:2605.25678#pg2>.

Lu: They define BDS(H) as the maximum total size of a pseudo-box realizable by H, which relaxes the strict Cartesian product structure while still capturing the local combinatorial richness needed for learning <ref:2605.25678#pg2>.

Meng: So they're essentially translating a complex structural property of the function space into a single number that dictates how many samples we need to train an AI model effectively. That seems like a very useful abstraction for practical application, Meng here <ref:2605.25678#pg2>.

Lalam: That abstraction is what makes it powerful; it lets us predict sample requirements based on the complexity of the problem itself rather than just running expensive experiments <ref:2605.25678#pg1>.

The paper's improvements: Tom: The paper outlines a couple of key methodological advancements, specifically mentioning an algorithmic framework called "ListCascade." What is the significance of using this ListCascade approach for establishing the upper bound?

Jane: ListCascade uses a sequence of list learners where they progressively shrink the list of candidate labels we are considering in each round <ref:2605.25678#pg2>. It’s a clever way to use binary feedback to systematically narrow down the possibilities without needing full knowledge immediately.

Lu: The upper bound relies on this framework connecting bandit learning directly into list learning guarantees, showing how that sequence of refinement leads to the required complexity scaling with the total number of neighbors in BDS(H) <ref:2605.25678#pg2>.

Meng: It’s interesting because it suggests an iterative process for improving models under uncertainty, which is something we definitely need when dealing with dynamic systems, Meng here <ref:2605.25678#pg1>.

Lalam: This iterative refinement idea could be really valuable for developing AI that learns on the fly in environments where the underlying rules are only partially known initially <ref:2605.25678#pg1>.

Conclusion: Tom: So, to wrap up, what's the big picture here regarding the sample complexity bounds they establish with this work on "PAC Learning with Bandit Feedback"? Jane, how do we summarize the main implication for practitioners?

Jane: The main implication is that we now have a much clearer understanding of how sample requirements scale with this new bandit DS dimension, which helps set realistic expectations for training any concept class in these feedback-constrained environments <ref:2605.25678#pg2>.

Lu: They've resolved the open question from earlier work regarding the multiplicative gap between upper and lower bounds by providing matching bounds based on BDS(H) <ref:2605.25678#pg1>.

Meng: For practical AI deployment, this means we can design learning processes that are guaranteed to converge within a predictable number of samples dictated by the problem's inherent structure, which is very helpful for resource planning, Meng here <ref:2605.25678#pg1>.

Lalam: This research shows that even when information is scarce, the combinatorial geometry of what you are trying to learn still imposes a hard limit on how much data you need to get a good result <ref:2605.25678#pg1>.

Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri

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

stat.ML, cs.DS, cs.LG, math.ST, stat.TH

Submitted: 2026-05-25

Updated: 2026-10-04

Comments: Accepted at NeurIPS 2026. Minor issues have been fixed based on the NeurIPS rebuttal

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: Sharp sample complexity for multiclass PAC learning under bandit feedback in the realizable setting.

Key concepts

Bandit DS Dimension (BDS(H)): A new combinatorial measure defined as the maximum total size of a pseudo-box realizable by the concept class H. Unlike standard dimensions, it aggregates the number of neighbors across all coordinates, providing a direct link to sample complexity scaling.
ListCascade Algorithm: An algorithmic framework used to establish an upper bound on sample complexity. It works by using a sequence of list learners where the candidate label set is progressively reduced in each step through majority voting over retained positive feedback examples.
List Learning: An intermediate learning paradigm where the learner outputs a short list of candidate labels instead of just one prediction. This allows for progressive refinement under bandit feedback, enabling the algorithm to systematically narrow down the search space.

Terminology

Sample Complexity — 40× in this paper · explained in 15 episodes
List Learning — 21× in this paper · explained in 2 episodes
Hypergraph — 13× in this paper · explained in 2 episodes
Contextual Bandits — 5× in this paper · explained in 3 episodes
Clustering — 3× in this paper · explained in 2 episodes
Generalization — 3× in this paper · explained in 13 episodes
Abstraction — 2× in this paper · explained in 1 episode
Core — 2× in this paper · explained in 2 episodes
Differentially Private — 1× in this paper · explained in 3 episodes
Iterative Refinement — 1× in this paper · explained in 3 episodes
Regret — 1× in this paper · explained in 3 episodes
Reward Function — 1× in this paper · explained in 2 episodes
Sample Complexity Scaling — 1× in this paper · explained in 2 episodes
Sparsity — 1× in this paper · explained in 4 episodes
Trace — 1× in this paper · explained in 2 episodes
VC Dimension — 1× in this paper · explained in 2 episodes

Summary

Sharp sample complexity for multiclass PAC learning under bandit feedback in the realizable setting.

Our main contribution is a new combinatorial complexity parameter that sharply characterizes the sample complexity of PAC learning with bandit feedback. This characterization is based on a new combinatorial dimension termed the bandit DS dimension, which aggregates the number of neighbors across coordinates, leading to a sample complexity scaling with the total number of neighbors.

The Problem and Motivation

The paper studies multiclass PAC learning where the learner receives only binary feedback indicating whether its prediction is correct, rather than observing true labels in every round. This setting is motivated by scenarios where obtaining full information is costly or impossible, such as clinical trials where only binary outcomes are known. The fundamental question addressed is: Given a concept class H ⊆ YX, how many training samples are necessary and sufficient for PAC learning H when the learner receives only bandit feedback? Existing results showed a multiplicative gap of K up to logarithmic factors between upper and lower bounds.

The Bandit DS Dimension

The core of the contribution is the definition of a new combinatorial complexity parameter: the bandit DS dimension (BDS(H)). This dimension is defined as the maximum total size Pm i=1 Ni of a pseudo-box realizable by H, where a pseudo-box relaxes the rigid cartesian product structure while preserving local combinatorial richness. Unlike dimensions governing full information, which count coordinates, the bandit DS dimension aggregates the number of neighbors across coordinates. This dimension is used to establish matching upper and lower bounds on optimal sample complexity:

The upper bound is based on an algorithmic framework called ListCascade, which connects bandit learning to list learning.
The lower bound is obtained by turning the pseudo-box witnessing BDS(H) into a hard bandit instance, showing that any learner requires omega(BDS(H)/ϵ) samples.

The ListCascade Algorithm

The upper bound is achieved via the ListCascade algorithm, which uses a sequence of list learners with progressively shrinking list sizes. The process involves:

Initially setting the list size to K (the size of the label space Y).
In each epoch, predicting uniformly from the current list and retaining only examples where feedback is positive.
Defining the next list predictor based on a majority vote over retained samples, which reduces the candidate label set by a constant factor in each epoch (e.g., from K to K/2).

The complexity of each epoch scales with the current list size, and summing over logarithmically many epochs yields the near-optimal upper bound.

Key Results on Sample Complexity

The paper establishes sharp bounds based on BDS(H) and other related dimensions:

Theorem 4.1 provides the upper bound: mB H(ϵ, δ) = O (d B S(log K) cubed + K log K log 1/δ ϵ).
Theorem 4.2 provides the lower bound: mB H(ϵ, δ) = omega d B S + log 1/δ ϵ.

The proof relies on Lemma 4.6, which shows that with high probability, the list predictor's error rate is bounded by (tϵ)/log K for each epoch.

Supporting Technical Tools

The analysis utilizes several intermediate concepts to bridge the gap between bandit feedback and PAC guarantees:

List Learning: This serves as an intermediate object where the learner outputs a short list of candidate labels instead of a single prediction, allowing for progressive refinement under bandit feedback.
L-Exponential Dimension (EL(H)): This is used to bound the error rate of the one-inclusion list algorithm, showing that it is controlled by the BDS dimension: the L-exponential dimension is controlled, up to logarithmic factors in K, by the ⌈L/2⌉-DS dimension.
One-inclusion Hypergraph: This combinatorial object is used to define degrees (like L-degree and average L-degree), which are crucial for analyzing the performance of the list orientation chosen in Algorithm 2.

Conclusion

The work introduces BDS(H) as a new combinatorial complexity measure that sharply characterizes the sample complexity, resolving a longstanding open question up to logarithmic factors. The paper concludes by noting that it remains open whether every concept class with finite BDS(H) admits a bandit-feedback PAC learner with sample complexity O((BDS(H) + log(1/δ))/ϵ). The upper bound is achieved through ListCascade, and the lower bound confirms the necessity of samples scaling with BDS(H).

How it works

The algorithm proceeds by gradually shrinking the list of candidate labels. In epoch t, the learner explores using the previous list predictor by predicting uniformly from that list and keeps an example only when feedback is positive.

Improvements for AI systems

As a fastidious researcher, I have analyzed the provided paper, PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting. The core contribution is establishing a tight combinatorial characterization of sample complexity for multiclass PAC learning under bandit feedback using the novel bandit DS dimension (BDS).

Here are specific improvements to AI systems that can be made based on this research:

The research provides a theoretically grounded framework for designing and analyzing learning algorithms in environments where full label observation is impossible, which is a major constraint in real-world applications like clinical trials, online recommendation systems, or dynamic resource allocation.

Here are the specific improvements and capabilities derived from this work:

Acknowledge the inherent information asymmetry in high-stakes decision-making by explicitly modeling it using the bandit feedback framework instead of assuming full observability.
Design ListCascade learning algorithms to operate efficiently under severe label scarcity or cost constraints, rather than relying on brute-force exploration (like uniform random guessing).
Develop theoretically sound sample complexity guarantees for multi-class classification tasks where only binary feedback (correct/incorrect) is available after a prediction.

Specifically, the improved AI system can perform the following:

Acknowledge and optimize decision-making in environments where obtaining true labels is prohibitively expensive or impossible (e.g., medical diagnosis with limited trial enrollment, or real-time dynamic pricing models).
Execute a multi-stage learning process (ListCascade) that progressively refines a set of plausible hypotheses by intelligently exploiting scarce binary feedback, leading to a final single-label classification with guaranteed error bounds related to the inherent complexity of the problem (BDS dimension).
Provide rigorous performance guarantees for these systems: For any concept class, the system can predict an output whose expected error is bounded by a function of the problem's combinatorial structure (BDS(H)) and desired accuracy parameters, overcoming previous multiplicative gaps between lower and upper bounds.
Achieve near-optimal sample complexity in the realizable setting for this constrained learning paradigm, meaning it requires fewer training samples than previously known methods that rely on full information or less refined theoretical tools.