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

• URL: http://arxiv.org/abs/2605.25678v2
• Date: Tue, 26 May 2026 08:08:44 GMT
• Title: PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
• Abstract summary: We study the problem of multiclass PAC learning with bandit feedback in the realizable setting.<n>In this framework, there is an unknown data distribution over an instance space $mathcalX$ and a label space $mathcalY$.<n>We provide a general characterization of the optimal sample of this problem, sharp for every concept class up to complexity.
• Score: 46.089126569274676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  We aim to identify an approximately optimal policy from a given class based on bandit feedback.<n>Motivated by bandit multiclass classification with zero-one rewards, we focus on the emph$s$-sparse setting.<n>We show that, with $s$-sparse rewards, the induced model class admits a sharp DEC bound that scales with $s$ and directly yields the optimal rate.
  arXiv  Detail & Related papers  (2026-05-28T09:12:20Z)
• Learning Conditional Averages [52.361762722359366]
  We introduce the problem of learning conditional averages in the PAC framework.<n>Instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its neighborhood.<n>More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains.
  arXiv  Detail & Related papers  (2026-02-12T13:20:29Z)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
  We study the problem of contextual semi-bandits, where input contexts are mapped into subsets of size $m$ of a collection of $K$ possible actions.<n>Motivated by prototypical applications of contextual bandits, we focus on the $s$-sparse regime.<n>Our framework generalizes the list multiclass classification problem with bandit feedback, which can be seen as a special case with binary reward vectors.
  arXiv  Detail & Related papers  (2025-02-13T12:13:25Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Statistical learning on measures: an application to persistence diagrams [0.0]
  We consider a binary supervised learning classification problem where instead of having data in a finite-dimensional Euclidean space, we observe measures on a compact space $mathcalX$. We show that our framework allows more flexibility and diversity in the input data we can deal with. While such a framework has many possible applications, this work strongly emphasizes on classifying data via topological descriptors called persistence diagrams.
  arXiv  Detail & Related papers  (2023-03-15T09:01:37Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  We study the problem of learning one-hidden-layer ReLU networks with $k$ hidden units on $mathbbRd$ under Gaussian marginals. For the case of positive coefficients, we give the first-time algorithm for this learning problem for $k$ up to $tildeOOmega(sqrtlog d)$.
  arXiv  Detail & Related papers  (2020-06-22T17:53:54Z)
• Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
  We characterize classes for which the optimal sample complexity can be achieved by a proper learning algorithm. We show that the dual Helly number is bounded if and only if there is a proper joint dependence on $epsilon$ and $delta$.
  arXiv  Detail & Related papers  (2020-05-24T18:11:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.